A Review of “Post-Quantum Biometric Authentication based on Homomorphic Encryption and Classic McEliece” [Póster]

A Review of “Post-Quantum Biometric Authentication based on Homomorphic Encryption and Classic McEliece” Rosario Arjona, Paula López-González, Roberto Román and Iluminada Baturone Instituto de Microelectrónica de Sevilla (IMSE-CNM), Universidad de Sevilla-CSIC 41092, Seville, Spain {arjona, paula, roman, lumi}@imse-cnm.csic.es Abstract- This work proposes a secure biometric authentication scheme that applies homomorphic encryption based on the Classic McEliece public-key encryption algorithm, which is a finalist at the round 4 of the NIST post-quantum standardization process. Its use is proposed in a non-device-centric biometric authentication architecture composed of client devices and external servers (database, computation and authentication servers). Privacy, irreversibility, revocability and unlinkability are satisfied and the scheme is robust to stolen-device, False Acceptance Rate, and similarity-based attacks as well as to honest-but-curious servers. Experimental results with public databases (FERET and LFW) and an Android App, Python code and MySQL show that the proposed scheme improves the accuracy of the unprotected scheme, allows real-time execution in the clients and servers for Classic McEliece security parameter sets of 128 and 256 bits, and offer reduced storage requirements and communication overheads. Index Terms- Biometric template protection, homomorphic encryption, post-quantum security Tipo de contribución: Investigación ya publicada en R. Arjona, P. López-González, R. Román, I. Baturone: “Post-Quantum Biometric Authentication Based on Homomorphic Encryption and Classic McEliece”, Appl. Sci., vol. 13, 757, 2023 [1]. I. INTRODUCTION A biometric recognition scheme usually includes an enrollment phase and a verification phase. At the enrollment phase, biometric characteristics of a person are acquired, and discriminative features are extracted and stored as a reference. At the verification phase, features are extracted from biometric queries which are matched to the stored reference. If during matching, the comparison result (typically a distance measurement) satisfies a threshold, the recognition decision determines that the person is successfully authenticated. In a non-device-centric authentication architecture, acquisition and feature extraction are performed on the client device, and storage, comparison and decision are performed on external servers (database, computation and authentication servers. Since communication, storage and authentication are performed on the cloud, biometric features should be protected. Homomorphic encryption not only allows that features are protected at communication and storage, but also at comparison. Only the comparison result is obtained in the unprotected domain by the authentication server. With the availability of large-scale quantum computers in the future, many of the current proposed biometric protection schemes will be broken. In order to provide long-term security, post-quantum cryptography should be considered. Among public-key encryption and key-establishment algorithms of the NIST post-quantum standardization process, Classic McEliece, which employs Goppa code-based cryptography, was selected as a candidate for the round 4. The security achieved by the McEliece system remains stable over 40 years of attacks. Although Classic McEliece requires higher key sizes and generation times than other proposals, this may not be a drawback for biometric recognition systems because keys need only to be generated and transmitted at the enrollment phase. In the other side, Classic McEliece provides the smallest protected data size of any of the NIST post-quantum cryptography candidates, which is interesting to reduce biometric data storage and communication. II. PROTECTION OF BIOMETRIC FEATURES Classic McEliece definition is composed of the three main algorithms key generation (KeyGen), encoding (ENCODE) and decoding (DECODE). In addition, the parameter set specification is 𝑞 = 2𝑚, 𝑛 ≤ 𝑞 and 𝑘 = 𝑛 − 𝑡𝑚. KeyGen has not inputs and generates the public and private keys (𝑇 and Γ, respectively). ENCODE receives as inputs the public key 𝑇 and a plaintext vector 𝑒 ∈ 𝔽2 𝑛 of Hamming weight 𝑡. The output of ENCODE is the ciphertext vector 𝑐 ∈ 𝔽2 𝑛−𝑘. DECODE receives as inputs the private key Γ and a vector 𝑐 ∈ 𝔽2 𝑛−𝑘 and returns the plaintext vector 𝑒 if its Hamming weight is 𝑡. Our proposal for biometric protection adapts the Classic McEliece NIST proposal as follows. We apply the ENCODE algorithm to the enrollment and verification vectors 𝑒𝑏𝑅 and 𝑒𝑏𝑉, respectively, obtaining the ciphertexts 𝑐𝑏𝑅 and 𝑐𝑏𝑉, with 𝑐𝑏𝑅= 𝐻 · 𝑒𝑏𝑅 and 𝑐𝑏𝑉= 𝐻 · 𝑒𝑏𝑉, where 𝐻 is the paritycheck matrix of the Goppa code employed. Our modification is that the vectors 𝑒𝑏𝑅 and 𝑒𝑏𝑉 are constructed with a Hamming weight greater than 𝑡 so that DECODE algorithm cannot recover 𝑒𝑏𝑅 and 𝑒𝑏𝑉, from 𝑐𝑏𝑅 and 𝑐𝑏𝑉, even with the knowledge of the private key Γ. At the verification phase, an XOR operation is applied to the encoded vectors, that is, 𝑐𝑏𝑅⊕𝑐𝑏𝑉= 𝐻 · 𝑒𝑏𝑅⊕ 𝐻 · 𝑒𝑏𝑉. Then, we exploit the homomorphic property of Classic McEliece that ENCODE(𝑒𝑏𝑅⊕ 𝑒𝑏𝑉)=ENCODE(𝑒𝑏𝑅) ⊕ 𝐸𝑁𝐶𝑂𝐷𝐸(𝑒𝑏𝑉). Hence, 𝑐𝑏𝑅⊕𝑐𝑏𝑉= 𝐻 · 𝑒𝑏𝑅⊕ 𝐻 · 𝑒𝑏𝑉= 𝐻 · (𝑒𝑏𝑅⊕ 𝑒𝑏𝑉). The final step is that 𝑒𝑏𝑅⊕ 𝑒𝑏𝑉 is recovered by the DECODE algorithm because it is ensured that 𝑒𝑏𝑅⊕ 𝑒𝑏𝑉 has Hamming weight smaller than or equal to 𝑡. From the JNIC 2024 ISBN:978-84-09-62140-8 514 comparison 𝑒𝑏𝑖 𝑅⊕𝑒𝑏𝑖 𝑉, a distance measurement can be obtained, for example the Hamming distance by computing the Hamming weight. The sum of the partial distances when all the substrings e𝑏𝑖 𝑅⊕𝑒𝑏𝑖 𝑉 are decoded generates the final distance result, which is compared to a threshold value. III. AUTHENTICATION SCHEME PROPOSED We employ the protection proposal described above in a nondevice-centric authentication architecture as follows. Fig. 1 illustrates the verification phase. Previously, at the setup phase, the authentication server generates its pair of public and private keys (𝑇𝐴, Γ𝐴) by means of the Classic McEliece KeyGen algorithm and sends the public key to the client device. Also, a threshold value 𝑡ℎ that determines the recognition decision is set. At the enrollment phase, the client device acquires the user identifier 𝐼𝐷𝑈 and the biometric samples 𝑆𝑈𝑅. Binary biometric features 𝑏𝑈𝑅 ∈ 𝔽2 𝑙 that preserve the distances are extracted from 𝑆𝑈𝑅. Then, the transformation of the enrollment binary features is applied to 𝑏𝑈𝑅, thus obtaining the substrings 𝑒𝑏𝑖 𝑈𝑅 ∈ 𝔽2 𝑛 with Hamming weight greater than 𝑡. The ENCODE algorithm is employed to encode the substrings 𝑒𝑏𝑖 𝑈𝑅 by using the authentication server public key 𝑇𝐴, resulting the encoded substrings 𝑐𝑏𝑖 𝑈𝑅 ∈ 𝔽2 𝑛−𝑘. The client device also maps the 𝐼𝐷𝑈 to an index 𝑥𝑈 in a way that is only known by it and so that a PIR (Private Information Retrieval) is applied during the verification phase. The substrings 𝑐𝑏𝑖 𝑈𝑅 and the index 𝑥𝑈 are sent to the database server. IV. CONCLUSIONS In this work, we have proposed a biometric protection scheme based on homomorphic encryption and Classic McEliece as well as its use in a non-device-centric biometric authentication architecture with honest-but-curious servers. A specific transformation of features is proposed to preclude decoding protected biometric features, even knowing the private key and even the servers interchanging information. Therefore, in an honest-but-curious adversarial model, the security is maintained, and recognition performance is improved in a normal scenario and preserved in a stolen-device scenario. Parameter sets were selected to achieve security levels of 128 and 256 bits for Classic McEliece (mceliece6688128 and mceliece348864 parameter sets, respectively). Irreversibility is ensured by the impossibility of decoding ciphertexts with more errors than those permitted. Also, Classic McEliece-based protected features are random even though they are generated from the same sample, and thus, revocability, and unlinkability are satisfied. In addition, the scheme is robust to False-Acceptance-Rate (FAR) and similarity-based attacks. A practical realization is illustrated, which was performed by considering a smartphone as device client [2] and computers as database, computation and authentication servers. FaceNet embeddings were selected as biometric features. Execution times obtained allows real-time authentication. A relevant advantage of our proposal is that Classic McEliece generates protected data with sizes much lower than other approaches [3]-[4] (in more than 94.3%), which reduces storage and communication costs. ACKNOWLEDGEMENTS This research was conducted thanks to Grants CPP2022- 009796 and PDC2023-145873-I00 funded by MICIU/AEI/10.13039/501100011033 and the “European Union NextGenerationEU/PRTR”, and Grant PID2020- 119397RB-I00 funded by MICIU/AEI/ 10.13039/501100011033. The work of Roberto Román was supported by VI Plan Propio de Investigación y Transferencia through the University of Seville. REFERENCES [1] R. Arjona, P. López-González, R. Román, I. Baturone: “Post-Quantum Biometric Authentication Based on Homomorphic Encryption and Classic McEliece”, Appl. Sci., vol. 13, 757, 2023. [2] P. López-González, R. Arjona, R. Román, I. Baturone: “A facial authentication system using post-quantum-secure data generated on mobile devices”. In Proc. of the 28th Annual Int. Conf. on Mobile Computing and Networking (MobiCom), pp. 803–805, 2022. [3] J. Kolberg, P. Drozdowski, M. Gomez-Barrero, C. Rathgeb, C. Busch: “Efficiency Analysis of Post-quantum-secure Face Template Protection Schemes based on Homomorphic Encryption” in Int. Conf. of the Biometrics Special Interest Group (BIOSIG), Darmstadt, Germany, 2020. [4] R. Román, R. Arjona, I. Baturone: “A Quantum-Resistant Face Template Protection Scheme using Kyber and Saber Public Key Encryption Algorithms”, in Int. Conf. of the Biometrics Special Interest Group (BIOSIG), Darmstadt, Germany, 2022. Fig. 1. Verification phase of the authentication protocol based on the Classic McEliece protection proposed. Client Device Feature Extraction 𝑆𝑈𝑉 ENCODE 𝑏𝑈𝑉 ∈ 𝔽2 𝑙 Computation Server 𝐶 Verification Feature Transformation 𝑐𝑏𝑖 𝑈𝑉 ∈ 𝔽2 𝑛−𝑘 𝑇𝐴 𝑇𝐴 Authentication Server (𝑇𝐴, Γ𝐴) PIR 𝐼 𝑥𝑈 DECODE Γ𝐴 HD and thbased Decision XOR 𝑐𝑏𝑖 𝑈𝑅 ⊕𝑐𝑏𝑛𝑖 𝑈𝑉 𝑒𝑏𝑖 𝑈𝑉 ∈ 𝔽2 𝑛Nonce Generation 𝑚 𝑖∈ 𝔽2 𝑛−𝑘 Nonce Generation 𝑚 𝑖∈ 𝔽2 𝑛−𝑘 XOR 𝑐𝑏𝑛𝑖 𝑈𝑉 ∈ 𝔽2 𝑛−𝑘 XOR 𝐼𝐷𝑈Map 𝑥𝑈 𝑥𝑈, 𝑐𝑏𝑖 𝑈𝑅) 𝑚 𝑖∈ 𝔽2 𝑛−𝑘 𝑐𝑏𝑛𝑖 𝑈𝑉 𝑐𝑏𝑖 𝑈𝑅 ⊕ 𝑐𝑏𝑛𝑖 𝑈𝑉 ⊕𝑚 𝑖⊕ 𝑚 𝑖∈ 𝔽2 𝑛−𝑘 𝑒𝑏𝑖 𝑈𝑅 ⊕ 𝑒𝑏𝑖 𝑈𝑉 ∈ 𝔽2 𝑛 SECURE CHANNEL Database Server 𝐷 𝑐𝑏𝑖 𝑈𝑅 𝑚 𝑖∈ 𝔽2 𝑛−𝑘 𝐼 𝑥𝑈 𝑥𝑈 A Review of “Post-Quantum Biometric Authentication based on Homomorphic Encryption and Classic McEliece” 515