×

A gapless code-based hash proof system based on RQC and its applications. (English) Zbl 1502.94030

Summary: R. Cramer and V. Shoup [Lect. Notes Comput. Sci. 2332, 45–64 (2002; Zbl 1055.94011)] introduced the concept of hash proof system, also designated as smooth projective hash functions. Since then, they have found several applications, from building CCA-2 encryption as they were initially created for, to being at the core of several authenticated key exchange or even allowing witness encryption. In the post-quantum setting, the very few candidates use a language based on ciphertexts to build their hash proof system. This choice seems to inherently introduce a gap, as some elements outside the language could not be distinguish from those in the language. This creates a lawless zone, where an adversary can possibly mount an undetectable attack, particularly problematic when trying to prove security in the UC framework [R. Canetti, “Universally composable security: a new paradigm for cryptographic protocols”, in: Proceedings of the 42nd IEEE symposium on foundations of computer science, FOCS 2001, Las Vegas, NV, USA, 2001. Los Alamitos, CA: IEEE Computer Society. 136–145 (2001; doi:10.1109/SFCS.2001.959888)]. We show that this gap could be completely withdrawn using code-based cryptography. Starting from RQC (Rank quasi-cyclic), a candidate selected for the second round of the National Institute of Standards and Technology (NIST) post-quantum cryptography standardization project, we show how to build such a hash proof system from code-based cryptography and present a way, based on a proof of knowledge, to fully negate the gap. We propose two applications of our construction, a witness encryption scheme and a password authenticated key exchange (PAKE).

MSC:

94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing
68P25 Data encryption (aspects in computer science)
81P94 Quantum cryptography (quantum-theoretic aspects)
94B05 Linear codes (general theory)

Citations:

Zbl 1055.94011
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdalla, M.; Benhamouda, F.; Pointcheval, D.; Oswald, E.; Fischlin, M., Disjunctions for hash proof systems: New constructions and applications, EUROCRYPT 2015 Part II, vol. 9057 of LNCS, 69-100 (2015), Heidelberg: Springer, Heidelberg · Zbl 1326.94065
[2] Abdalla, M.; Chevalier, C.; Pointcheval, D.; Halevi, S., Smooth projective hashing for conditionally extractable commitments, CRYPTO 2009, vol. 5677 of LNCS, 671-689 (2009), Heidelberg: Springer, Heidelberg · Zbl 1252.94039 · doi:10.1007/978-3-642-03356-8_39
[3] Aguilar-Melchor C., Aragon N., Bettaieb S., Bidoux L., Blazy O., Bos J., Deneuville J.-C., Gaborit P., Persichetti E., Robert J.-M., Véron P., Zémor G. Hamming quasi-cyclic (HQC).
[4] Aguilar-Melchor C., Aragon N., Bettaieb S., Bidoux L., Blazy O., Couvreur A., Deneuville J.-C., Gaborit P., Hauteville A., Zémor G.: Rank quasi-cyclic (RQC)
[5] Aguilar-Melchor, C.; Blazy, O.; Deneuville, J-C; Gaborit, P.; Zémor, G., Efficient encryption from random quasi-cyclic codes, IEEE Trans. Inf. Theory, 64, 5, 3927-3943 (2018) · Zbl 1395.94345 · doi:10.1109/TIT.2018.2804444
[6] Alamélou Q., Blazy O., Cauchie S., Gaborit P.: A practical group signature scheme based on rank metric. In International Workshop on the Arithmetic of Finite Fields, pp. 258-275. Springer (2016) · Zbl 1409.94859
[7] Alekhnovich, M.: More on average case vs approximation complexity. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. (2003), IEEE, pp. 298-307.
[8] Aragon, N., Gaborit, P., Hauteville, A., Tillich, J.-P.: A new algorithm for solving the rank syndrome decoding problem. In 2018 IEEE International Symposium on Information Theory (ISIT) (2018), IEEE, pp. 2421-2425.
[9] Bardet, M., Briaud, P., Bros, M., Gaborit, P., Neiger, V., Ruatta, O., Tillich, J.-P.: An algebraic attack on rank metric code-based cryptosystems. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (2020), Springer, pp. 64-93. · Zbl 1479.94122
[10] Bardet, M., Bros, M., Cabarcas, D., Gaborit, P., Perlner, R., Smith-Tone, D., Tillich, J.-P., Verbel, J.: Improvements of algebraic attacks for solving the rank decoding and minrank problems. In International Conference on the Theory and Application of Cryptology and Information Security (2020), Springer, pp. 507-536. · Zbl 1511.94051
[11] Bellare, M., Pointcheval, D., Rogaway, P.: Authenticated key exchange secure against dictionary attacks. In EUROCRYPT 2000 (May 2000), B. Preneel, Ed., vol. 1807 of LNCS, Springer, Heidelberg, pp. 139-155. · Zbl 1082.94533
[12] Bellovin, S. M., and Merritt, M.: Encrypted key exchange: Password-based protocols secure against dictionary attacks. In 1992 IEEE Symposium on Security and Privacy (May 1992), IEEE Computer Society Press, pp. 72-84.
[13] Benhamouda, F.: Diverse modules and zero-knowledge. PhD thesis, PSL Research University - ENS, July 2016.
[14] Benhamouda, F., Blazy, O., Chevalier, C., Pointcheval, D., Vergnaud, D.: New techniques for SPHFs and efficient one-round PAKE protocols. In CRYPTO 2013, Part I (Aug. 2013), R. Canetti and J. A. Garay, Eds., vol. 8042 of LNCS, Springer, Heidelberg, pp. 449-475. · Zbl 1310.94125
[15] Benhamouda, F., Blazy, O., Ducas, L., and Quach, W.: Hash proof systems over lattices revisited. In PKC 2018, Part II (Mar. 2018), M. Abdalla and R. Dahab, Eds., vol. 10770 of LNCS, Springer, Heidelberg, pp. 644-674. · Zbl 1400.94119
[16] Berlekamp, E., McEliece, R., Van Tilborg, H.: On the inherent intractability of certain coding problems (corresp.). IEEE Transactions on Information Theory 24, 3 (1978), 384-386. · Zbl 0377.94018
[17] Blazy, O., Chevalier, C.: Generic construction of UC-secure oblivious transfer. In ACNS 15 (June 2015), T. Malkin, V. Kolesnikov, A. B. Lewko, and M. Polychronakis, Eds., vol. 9092 of LNCS, Springer, Heidelberg, pp. 65-86. · Zbl 1459.94099
[18] Blazy, O., Chevalier, C., Germouty, P.: Adaptive oblivious transfer and generalization. In ASIACRYPT 2016, Part II (Dec. 2016), J. H. Cheon and T. Takagi, Eds., vol. 10032 of LNCS, Springer, Heidelberg, pp. 217-247. · Zbl 1407.94089
[19] Blazy, O., Chevalier, C., Vu, Q. H.: Post-quantum UC-secure oblivious transfer in the standard model with adaptive corruptions. In Proceedings of the 14th International Conference on Availability, Reliability and Security (2019), pp. 1-6.
[20] Canetti, R.: Universally Composable Security: A New Paradigm for Cryptographic Protocols. In 42nd FOCS (Oct. 2001), IEEE Computer Society Press, pp. 136-145.
[21] Chen, K.: A new identification algorithm. In Cryptography: Policy and Algorithms (Berlin, Heidelberg, 1996), E. Dawson and J. Golić, Eds., Springer Berlin Heidelberg, pp. 244-249. · Zbl 1421.94044
[22] Cramer, R., Shoup, V.: Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In EUROCRYPT 2002 (Apr. / May 2002), L. R. Knudsen, Ed., vol. 2332 of LNCS, Springer, Heidelberg, pp. 45-64. · Zbl 1055.94011
[23] Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In CRYPTO’86 (Aug. 1987), A. M. Odlyzko, Ed., vol. 263 of LNCS, Springer, Heidelberg, pp. 186-194. · Zbl 0636.94012
[24] Gabidulin, EM, Theory of codes with maximum rank distance, Problemy Peredachi Informatsii, 21, 1, 3-16 (1985) · Zbl 0585.94013
[25] Gaborit, P., Murat, G., Ruatta, O., Zémor, G.: Low rank parity check codes and their application to cryptography. In Proceedings of the Workshop on Coding and Cryptography WCC (2013), vol. 2013.
[26] Gaborit, P.; Ruatta, O.; Schrek, J., On the complexity of the rank syndrome decoding problem, IEEE Transactions on Information Theory, 62, 2, 1006-1019 (2015) · Zbl 1359.94847 · doi:10.1109/TIT.2015.2511786
[27] Gaborit, P., Schrek, J., Zémor, G.: Full cryptanalysis of the Chen identification protocol. In International Workshop on Post-Quantum Cryptography (2011), Springer, pp. 35-50. · Zbl 1290.94074
[28] Gaborit, P.; Zémor, G., On the hardness of the decoding and the minimum distance problems for rank codes, IEEE Transactions on Information Theory, 62, 12, 7245-7252 (2016) · Zbl 1359.94848 · doi:10.1109/TIT.2016.2616127
[29] Garg, S., Gentry, C., Sahai, A., Waters, B.: Witness encryption and its applications. In 45th ACM STOC (June 2013), D. Boneh, T. Roughgarden, and J. Feigenbaum, Eds., ACM Press, pp. 467-476. · Zbl 1293.94066
[30] Gennaro, R.; Lindell, Y., A framework for password-based authenticated key exchange, ACM Transactions on Information and System Security, 9, 2, 181-234 (2006) · Zbl 1038.94534 · doi:10.1145/1151414.1151418
[31] Halevi, S.; Kalai, YT, Smooth projective hashing and two-message oblivious transfer, Journal of Cryptology, 25, 1, 158-193 (2012) · Zbl 1272.94033 · doi:10.1007/s00145-010-9092-8
[32] Hofheinz, D., Hövelmanns, K., Kiltz, E.: A modular analysis of the Fujisaki-Okamoto transformation. In TCC 2017, Part I (Nov. 2017), Y. Kalai and L. Reyzin, Eds., vol. 10677 of LNCS, Springer, Heidelberg, pp. 341-371. · Zbl 1410.94082
[33] Kalai, Y. T.: Smooth projective hashing and two-message oblivious transfer. In EUROCRYPT 2005 (May 2005), R. Cramer, Ed., vol. 3494 of LNCS, Springer, Heidelberg, pp. 78-95. · Zbl 1137.94348
[34] Katz, J., Vaikuntanathan, V.: Round-optimal password-based authenticated key exchange. In TCC 2011 (Mar. 2011), Y. Ishai, Ed., vol. 6597 of LNCS, Springer, Heidelberg, pp. 293-310. · Zbl 1295.94089
[35] Katz, J., Vaikuntanathan, V.: Smooth projective hashing and password-based authenticated key exchange from lattices. In ASIACRYPT 2009 (Dec. 2009), M. Matsui, Ed., vol. 5912 of LNCS, Springer, Heidelberg, pp. 636-652. · Zbl 1267.94122
[36] Kawachi, A., Tanaka, K., Xagawa, K.: Concurrently secure identification schemes based on the worst-case hardness of lattice problems. In International Conference on the Theory and Application of Cryptology and Information Security (2008), Springer, pp. 372-389. · Zbl 1206.94076
[37] Ling, S., Nguyen, K., Stehlé, D., Wang, H.: Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications. In PKC 2013 (Feb. / Mar. 2013), K. Kurosawa and G. Hanaoka, Eds., vol. 7778 of LNCS, Springer, Heidelberg, pp. 107-124. · Zbl 1314.94087
[38] Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In 22nd ACM STOC (May 1990), ACM Press, pp. 427-437.
[39] Ore, O., On a special class of polynomials, Transactions of the American Mathematical Society, 35, 3, 559-584 (1933) · Zbl 0007.15102 · doi:10.1090/S0002-9947-1933-1501703-0
[40] Persichetti, E.: Code-based public-key encryption resistant to key leakage. In International Conference on Availability, Reliability, and Security (2013), Springer, pp. 44-54.
[41] Pointcheval, D., Stern, J.: Security proofs for signature schemes. In International Conference on the Theory and Applications of Cryptographic Techniques (1996), Springer, pp. 387-398. · Zbl 1304.94106
[42] Stern, J., A new paradigm for public key identification, IEEE Transactions on Information Theory, 42, 6, 1757-1768 (1996) · Zbl 0944.94008 · doi:10.1109/18.556672
[43] Véron, P., Improved identification schemes based on error-correcting codes, Applicable Algebra in Engineering, Communication and Computing, 8, 1, 57-69 (1997) · Zbl 0863.94013 · doi:10.1007/s002000050053
[44] Zhang, J., Yu, Y.: Two-round PAKE from approximate SPH and instantiations from lattices. In ASIACRYPT 2017, Part III (Dec. 2017), T. Takagi and T. Peyrin, Eds., vol. 10626 of LNCS, Springer, Heidelberg, pp. 37-67. · Zbl 1417.94088
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.