A New Ring-Based SPHF and PAKE Protocol On Ideal Lattices

Document Type: ORIGINAL RESEARCH PAPER

Authors

1 University of Guilan, Rasht, Iran

2 Department of Mathematics, University of Guilan, Rasht, Iran

3 Dep. Math. University Campus 2, University of Guilan

Abstract

\emph{ Smooth Projective Hash Functions } ( SPHFs ) as a specific pattern of zero knowledge proof system are fundamental tools to build many efficient cryptographic schemes and protocols. As an application of SPHFs, \emph { Password - Based Authenticated Key Exchange } ( PAKE ) protocol is well-studied area in the last few years. In 2009, Katz and Vaikuntanathan described the first lattice-based PAKE using the Learning With Errors ( LWE ) problem. In this work, we present a new efficient \emph { ring-based } smooth projectice hash function `` ( Ring - SPHF ) " using Lyubashevsky, Peikert, and Regev's dual-style cryptosystem based on the Learning With Errors over Rings ( Ring - LWE ) problem. Then, using our ring-SPHF, we propose the first efficient password-based authenticated key exchange ` ` ( Ring - PAKE ) " protocol over \emph{ rings } whose security relies on ideal lattice assumptions.

Keywords


[1] Gentry, C.: Fully homomorphic encryption using ideal lattices. In: 41st ACM STOC, pp. 169–178. ACM Press, Bethesda, Maryland (2009)

[2] Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. Journal of the ACM. 60(6), 43:1–43:35 (2013)

[3] Lyubashevsky, V., Peikert, C., and Regev, O.: A toolkit for ring-LWE cryptography. In T. Johansson and P. Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 35–54. Springer, May (2013). Archive: https://eprint.iacr.org/2013/293

[4] Cramer, R., Shoup., V.: Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In: EUROCRYPT, pp. 45–64. Springer Press, Amsterdam (2002)

[5] Gennaro, R., Lindell, Y.: A framework for password-based authenticated key exchange. In: EUROCRYPT, pp. 524–543. Springer press, Warsaw (2003)

[6] Abdalla, M., Chevalier, C., Pointcheval, D.: Smooth projective hashing for conditionally extractable commitments. In: CRYPTO, pp. 671– 689. Springer press, Santa Barbara, CA (2009)

[7] Reza Ebrahimi Atani, Shahabaddin Ebrahimi Atani, Amir Hassani Karbasi, NETRU: A Noncommutative and Secure Variant of CTRU Cryptosystem, The ISC International Journal of Information Security (ISeCure), Volume 10, Issue 1, Winter and Spring 2018, Page 45-53

[8] Blazy, O., Pointcheval, D., Vergnaud, D.:Round-optimal privacy-preserving protocols with smooth projective hash functions. In: TCC, pp. 94–111. Springer press, Taormina, Sicily (2012)

[9] Katz, J., Ostrovsky, R., Yung, M.: Efficient password-authenticated key exchange using human-memorable passwords. In: EUROCRYPT, pp. 475–494. Springer press, Innsbruck (2001)

[10] Bellare, M., Pointcheval, D., Rogaway, P.: Authenticated key exchange secure against dictionary attacks. In: EUROCRYPT, pp. 139–155. Springer press, Bruges (2000)

[11] Amir Hassani Karbasi, Reza Ebrahimi Atani, Shahabaddin Ebrahimi Atani, PairTRU: Pairwise Non-commutative Extension of The NTRU Public key Cryptosystem, International Journal of Information Security Science, Volume 7, Issue 1, 2018, Page 11-19.

[12] SPEKE: RFC5931, RFC6617, IEEE P1363.2, U.S. Patent 6,226,383

[13] J-PAKE: Implemented in OPENSSL, NSS, used by FIREFOX-SYNC, https://wiki.mozilla. org/Services/KeyExchange [14] Gong, L., Lomas, T.M.A., Needham, R.M., Saltzer, J.H.: Protecting poorly chosen secrets from guessing attacks. IEEE Journal of Selected Areas in Communications. 11(5), 648–656 (1993)

[15] Halevi, S., Krawczyk, H.: Public-key cryptography and password protocols. ACM Trans. Information and System Security. 2(3), 230–268 (1999)

[16] Bellovin, S.M., Merritt, M.: Encrypted key exchange: Password-based protocols secure against dictionary attacks. In: IEEE Symposium on Security and Privacy, pp. 72–84. IEEE press (1992)

[17] MacKenzie, P.D., Patel, S., Swaminathan, R.: Password-authenticated key exchange based on RSA. In: Asiacrypt, pp. 599–613. Springer press (2000)

[18] Reza Ebrahimi Atani, Shahabaddin Ebrahimi Atani, Amir Hassani Karbasi, A Provably Secure Variant of ETRU Based on Extended Ideal Lattices Over Direct Product of Dedekind domains, To appear in the Journal of Computing and Security, (2018).

[19] Goldreich, O., Lindell, Y.: Session-key generation using human passwords only. Journal of Cryptology. 19(3), 241–340 (2006)

[20] Boyko, V., MacKenzie, P.D., Patel, S.: Provably secure password-authenticated key exchange using Diffie-Hellman. In: Eurocrypt, pp. 156–171. Springer press (2000)

[21] Nguyen, M.H., Vadhan, S.: Simpler session-key generation from short random passwords. Journal of Cryptology. 21(1), 52–96 (2008)

[22] Benhamouda, F., Blazy, O., Chevalier, C., Pointcheval, D., Vergnaud, D.: New techniques for SPHFs and efficient one-round PAKE protocols. In: CRYPTO, pp. 449–475. Springer press, Santa Barbara, CA (2013)

[23] Gennaro, R.: Faster and shorter passwordauthenticated key exchange. In: TCC, pp. 589– 606. Springer press (2008) [24] Katz, J., MacKenzie, P.D., Taban, G., Gligor, V.D.: Two-server password-only authenticated key exchange. In: 3rd International Conference on Applied Cryptography and Network Security (ACNS), pp. 1–16. Springer press (2005)

[25] Amir Hassani Karbasi, Reza Ebrahimi Atani, ILTRU: An NTRU-Like Public Key Cryptosystem Over Ideal Lattices, IACR Cryptology ePrint Archive, 2015.

[26] Canetti, R., Halevi, S., Katz, J., Lindell, Y., MacKenzie, P.D.: Universally composable password-based key exchange. In: Eurocrypt, pp. 404–421. Springer press (2005)

[27] Gennaro, R., Lindell, Y.: A framework for password-based authenticated key exchange. ACM Trans. Information and System Security. 9(2), 181–234 (2006)

[28] Jiang, S., Gong, G.: Password based key exchange with mutual authentication. In: 11th Annual International Workshop on Selected Areas in Cryptography (SAC), pp. 267–279. Springer press (2004)

[29] Katz, J., Vaikuntanathan, V.: Smooth projective hashing and password-based authenticated key exchange from lattices. In: ASIACRYPT, pp. 636– 652. Springer press, Tokyo, Japan (2009)

[30] Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM. 21(2), 120–126 (1978)

[31] Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Transactions on Information Theory, IT-22(6), 644–654 (1976)

[32] Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 84–93. ACM press (2005)

[33] Peikert, C.: Lattice Cryptography for the Internet. In: Post-Quantum Cryptography - 6th International Workshop, PQCrypto, pp. 197–219. Springer press, Waterloo, ON (2014)

[34] Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC, pp. 197–206. (2008)

[35] Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: SWIFFT: A modest proposal for FFT hashing. In: FSE, pp. 54–72. (2008)

[36] Reza Ebrahimi Atani, Shahabaddin Ebrahimi Atani, Amir Hassani Karbasi, EEH: AGGH-like public key cryptosystem over the eisenstein integers using polynomial representations, The ISC International Journal of Information Security (ISeCure), Volume 7, Issue 2, Summer and Autumn 2015, Page 115-126.

[37] Groce, A., Katz, J.: A New Framework For Efficient Password-based Authenticated Key Exchange. In: 17th ACM Conf. on Computer and Communications Security, pp. 516525. ACM Press, New York, (2010)

[38] Zhang, J., Zhang, Z., Ding, J., Snook, M., Dagdelen, O.: Authenticated key exchange from ideal lattices. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 719–751. Springer, Berlin (2015). DOI: 10.1007/ 978–3– 662–46803–624.

[39] Jintai Ding, Saed Alsayigh, Jean Lancrenon, Provably Secure Password Authenticated Key Exchange Based on RLWE for the Post-Quantum World, CT-RSA (2017), pp. 183–204, 2017. DOI: 10.1007/978–3–319–52153–411.

[40] Fabrice Benhamouda, Olivier Blazy, Lo Ducas, Willy Quach, Hash Proof Systems over Lattices Revisited, Public-Key Cryptography–PKC (2018), pp. 644–674.