Despite Fuzzy Commitment (FC) is a theoretically sound biometric-key binding scheme, it relies on error correction code (ECC) completely to mitigate biometric intra-user variations. Accordingly, FC suffers from the security–performance tradeoff. That is, the larger key size/higher security always trades with poor key release success rate and vice versa. Additionally, the FC is highly susceptible to a number of security and privacy attacks. Furthermore, the best achievable accuracy performance of FC is constrained by the simple distance metrics such as Hamming distance to measure the dissimilarity of binary biometric features. This implies many efficient matching algorithms are to be abandoned. In this paper, we propose an ECC-free key binding scheme along with cancellable transforms for minutiae-based fingerprint biometrics. Apart from that, the minutiae information is favorably protected by a strong non-invertible cancellable transform, which is crucial to prevent a number of security and privacy attacks. The scheme is not limited to binary biometrics as demanded in FC but instead can be applied to various types of biometric features and hence a more effective matcher can be chosen. Experiments conducted on FVC2002 and FVC2004 show that the accuracy performance is comparable to state-of-the-arts. We further demonstrate that the proposed scheme is robust against several major security and privacy attacks.