B-splines are commonly utilized to construct the transformation model in free-form deformation (FFD) based registration. B-splines become smoother with increasing spline order. However, a higher-order B-spline requires a larger support region involving more control points, which means higher computational cost. In general, the third-order B-spline is considered as a good compromise between spline smoothness and computational cost. A lower-order function is seldom used to construct the transformation model for registration since it is less smooth. In this research, we investigated whether lower-order B-spline functions can be utilized for more efficient registration, while preserving smoothness of the deformation by using a novel random perturbation technique. With the proposed perturbation technique, the expected value of the cost function given probability density function (PDF) of the perturbation is minimized by a stochastic gradient descent optimization. Extensive experiments on 2D synthetically deformed brain images, and real 3D lung and brain scans demonstrated that the novel randomly perturbed free-form deformation (RPFFD) approach improves the registration accuracy and transformation smoothness. Meanwhile, lower-order RPFFD methods reduce the computational cost substantially.