nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Post-quantum Provably-Secure Authentication and MAC from Mersenne Primes

verfasst von : Houda Ferradi, Keita Xagawa

Erschienen in: Topics in Cryptology – CT-RSA 2020

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper presents a novel, yet efficient secret-key authentication and MAC, which provide post-quantum security promise, whose security is reduced to the quantum-safe conjectured hardness of Mersenne Low Hamming Combination ($\mathsf {MERS}$) assumption recently introduced by Aggarwal, Joux, Prakash, and Santha (CRYPTO 2018). Our protocols are very suitable to weak devices like smart card and RFID tags.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Traceable Ring Signatures with Post-quantum Security

Nächstes Kapitel Another Look at Some Isogeny Hardness Assumptions

Nur mit Berechtigung zugänglich

Later, Katz, Shin, and Smith gave simplified security proofs of them [26].

“MIM security” in [15] is defined by two-phase games. This is $(\{P,V\},\{V\})$-auth security, while the MIM security is $(\{\},\{P,V\})$-auth security using [31]’s terminology.

For example, n can be 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, and so on. Mersenne-756839 employed $n = 756839$ and Ramstake employed $n = 216091$ and 756839.

In the original definition, a is chosen from $\{0,1\}^n$. This change introduces only negligible distance.

The Mersenne Low Hamming Ratio Assumption states that, given an n-bit Mersenne prime $p=2^n-1$ and an integer h, any PPT adversary cannot distinguish between $F/G \bmod {p}$ with $F, G \leftarrow _{\$}\mathfrak {H}_{n,h}$, and $R \leftarrow \mathbb {Z}_p$ with non-negligible advantage.

Aggarwal, D., Joux, A., Prakash, A., Santha, M.: A new public-key cryptosystem via Mersenne numbers. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10993, pp. 459–482. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_16CrossRef

Aggarwal, D., Joux, A., Prakash, A., Santha, M.: Mersenne-756839. Technical report, National Institute of Standards and Technology (2017). https://csrc.nist.gov/projects/post-quantum-cryptography/round-1-submissions

Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 595–618. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_35CrossRef

Armknecht, F., Hamann, M., Mikhalev, V.: Lightweight authentication protocols on ultra-constrained RFIDs - myths and facts. In: Saxena, N., Sadeghi, A.-R. (eds.) RFIDSec 2014. LNCS, vol. 8651, pp. 1–18. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13066-8_1CrossRef

Bellare, M., Rogaway, P.: Entity authentication and key distribution. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 232–249. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48329-2_21CrossRef

Bernstein, D.J., Lange, T.: Never trust a bunny. In: Hoepman, J.-H., Verbauwhede, I. (eds.) RFIDSec 2012. LNCS, vol. 7739, pp. 137–148. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36140-1_10CrossRef

Beunardeau, M., Connolly, A., Géraud, R., Naccache, D.: On the hardness of the Mersenne low hamming ratio assumption. In: Lange, T., Dunkelman, O. (eds.) LATINCRYPT 2017. LNCS, vol. 11368, pp. 166–174. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25283-0_9CrossRef

Blum, A., Furst, M., Kearns, M., Lipton, R.J.: Cryptographic primitives based on hard learning problems. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 278–291. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48329-2_24CrossRef

Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM 50(4), 506–519 (2003). https://doi.org/10.1145/792538.792543CrossRefMathSciNetMATH

10.

de Boer, K., Ducas, L., Jeffery, S., de Wolf, R.: Attacks on the AJPS Mersenne-based cryptosystem. In: Lange, T., Steinwandt, R. (eds.) PQCrypto 2018. LNCS, vol. 10786, pp. 101–120. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-79063-3_5CrossRef

11.

Bos, J.W., Kleinjung, T., Lenstra, A.K., Montgomery, P.L.: Efficient SIMD arithmetic modulo a Mersenne number. In: Proceedings of the 2011 IEEE 20th Symposium on Computer Arithmetic, ARITH 2011, pp. 213–221. IEEE Computer Society, Washington, DC (2011). https://doi.org/10.1109/ARITH.2011.37

12.

Bringer, J., Chabanne, H., Dottax, E.: HB$^+$: a lightweight authentication protocol secure against some attacks. In: Proceedings of the Second International Workshop on Security, Privacy and Trust in Pervasive and Ubiquitous Computing, SECPERU 2006, pp. 28–33. IEEE Computer Society, Washington, DC (2006). https://doi.org/10.1109/SECPERU.2006.10

13.

Cash, D., Kiltz, E., Tessaro, S.: Two-round man-in-the-middle security from LPN. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9562, pp. 225–248. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49096-9_10CrossRef

14.

Coron, J.S., Gini, A.: Improved cryptanalysis of the AJPS Mersenne based cryptosystem. In: Number-Theoretic Methods in Cryptology 2019 - NutMiC 2019 (2019). https://eprint.iacr.org/2019/610

15.

Dodis, Y., Kiltz, E., Pietrzak, K., Wichs, D.: Message authentication, revisited. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 355–374. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_22CrossRef

16.

Duc, D.N., Kim, K.: Securing HB$^+$ against GRS man-in-the-middle attack. In: SCIS 2007, The 2007 Symposium on Cryptography and Information Security, pp. 2B3-4. IEICE, Sasebo, 23–26 January 2007

17.

Esser, A., Kübler, R., May, A.: LPN decoded. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 486–514. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_17CrossRef

18.

Ferradi, H., Naccache, D.: Integer reconstruction public-key encryption. Cryptology ePrint Archive, Report 2017/1231 (2017). https://eprint.iacr.org/2017/1231

19.

Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12CrossRef

20.

Gilbert, H., Robshaw, M.J.B., Seurin, Y.: Good variants of HB⁺ are hard to find. In: Tsudik, G. (ed.) FC 2008. LNCS, vol. 5143, pp. 156–170. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85230-8_12CrossRef

21.

Gilbert, H., Robshaw, M.J.B., Seurin, Y.: HB$^{\#}$: increasing the security and efficiency of HB$^{+}$. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 361–378. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_21CrossRef

22.

Gilbert, H., Robshaw, M.J.B., Sibert, H.: Active attack against HB+: a provably secure lightweight authentication protocol. Electron. Lett. 41(21), 1169–1170 (2005). https://doi.org/10.1049/el:20052622. https://eprint.iacr.org/2005/237CrossRef

23.

Heyse, S., Kiltz, E., Lyubashevsky, V., Paar, C., Pietrzak, K.: Lapin: an efficient authentication protocol based on ring-LPN. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 346–365. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34047-5_20CrossRef

24.

Hopper, N.J., Blum, M.: Secure human identification protocols. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 52–66. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45682-1_4CrossRef

25.

Juels, A., Weis, S.A.: Authenticating pervasive devices with human protocols. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 293–308. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_18CrossRef

26.

Katz, J., Shin, J.S., Smith, A.: Parallel and concurrent security of the HB and HB+ protocols. J. Cryptol. 23(3), 402–421 (2010). https://doi.org/10.1007/s00145-010-9061-2CrossRefMathSciNetMATH

27.

Kiltz, E., Pietrzak, K., Cash, D., Jain, A., Venturi, D.: Efficient authentication from hard learning problems. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 7–26. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_3CrossRef

28.

Kiltz, E., Pietrzak, K., Venturi, D., Cash, D., Jain, A.: Efficient authentication from hard learning problems. J. Cryptol. 30(4), 1238–1275 (2017). https://doi.org/10.1007/s00145-016-9247-3CrossRefMathSciNetMATH

29.

Levieil, É., Fouque, P.-A.: An improved LPN algorithm. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 348–359. Springer, Heidelberg (2006). https://doi.org/10.1007/11832072_24CrossRef

30.

Lyubashevsky, V., Masny, D.: Man-in-the-middle secure authentication schemes from LPN and weak PRFs. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 308–325. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_18CrossRefMATH

31.

Mol, P., Tessaro, S.: Secret-key authentication beyond the challenge-response paradigm: definitional issues and new protocols. unpublished manuscripts (2012). https://homes.cs.washington.edu/~tessaro/

32.

Munilla, J., Peinado, A.: HB-MP: a further step in the HB-family of lightweight authentication protocols. Comput. Netw. 51(9), 2262–2267 (2007). https://doi.org/10.1016/j.comnet.2007.01.011CrossRefMATH

33.

Preneel, B.: Hash functions and MAC algorithms based on block ciphers. In: Darnell, M. (ed.) Cryptography and Coding 1997. LNCS, vol. 1355, pp. 270–282. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0024473CrossRef

34.

Rubinfeld, R.: Randomness and computation. Course, MIT (2012). https://people.csail.mit.edu/ronitt/COURSE/S12/handouts/lec5.pdf

35.

Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997). https://doi.org/10.1137/S0097539795293172CrossRefMathSciNetMATH

36.

Szepieniec, A.: Ramstake. Technical report. National Institute of Standards and Technology (2017). https://csrc.nist.gov/projects/post-quantum-cryptography/round-1-submissions

37.

Tiepelt, M., Szepieniec, A.: Quantum LLL with an application to Mersenne number cryptosystems. In: Schwabe, P., Thériault, N. (eds.) LATINCRYPT 2019. LNCS, vol. 11774, pp. 3–23. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-30530-7_1CrossRef

38.

Vaudenay, S.: On privacy models for RFID. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 68–87. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-76900-2_5CrossRef

Titel: Post-quantum Provably-Secure Authentication and MAC from Mersenne Primes
verfasst von: Houda Ferradi
Keita Xagawa
Verlag: Springer International Publishing
Buch: Topics in Cryptology – CT-RSA 2020
Print ISBN: 978-3-030-40185-6

Electronic ISBN: 978-3-030-40186-3

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-40186-3_20

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"