Authentication systems using gait captured from inertial sensors have been recently developed to enhance the limitation of existing mechanisms on mobile devices and achieved promising results. However, most these systems employed pattern recognition and machine learning techniques in which biometric templates are stored insecurely, which could leave critical security and user privacy issues. Specifically, a compromise of original gait templates could result in everlasting forfeiture. In this paper, two main results will be presented. Firstly, we propose a novel gait authentication system on mobile devices in which the security and privacy are preserved by employing a fuzzy commitment scheme. Instead of storing original gait templates for user verification like in conventional approaches, we verify the user via a stored key which is biometrically encrypted by gait templates collected from a mobile accelerometer. Secondly, the discriminability of sensor-based gait templates are investigated to determine appropriate parameter values to construct an effective gait-based biometric cryptosystem. The performance of our proposed system is evaluated on the dataset including gait signals of 34 volunteers. We achieved the zeroFAR and the False Rejection Rate of approximately 16.18 % corresponding to the key length, as well as the system security level of 139 bits. The results from our experiment show that accelerometer-based gait could be further investigated to construct a biometric cryptosystem, as effective as other biometric traits such as iris, fingerprint, voice, and signature.