Two-round man-in-the-middle security from LPN. (English) Zbl 1378.94074

Kushilevitz, Eyal (ed.) et al., Theory of cryptography. 13th international conference, TCC 2016-A, Tel Aviv, Israel, January 10–13, 2016. Proceedings. Part I. Berlin: Springer (ISBN 978-3-662-49095-2/pbk; 978-3-662-49096-9/ebook). Lecture Notes in Computer Science 9562, 225-248 (2016).
Summary: Secret-key authentication protocols have recently received a considerable amount of attention, and a long line of research has been devoted to devising efficient protocols with security based on the hardness of the learning-parity with noise (LPN) problem, with the goal of achieving low communication and round complexities, as well as highest possible security guarantees.{
} In this paper, we construct 2-round authentication protocols that are secure against sequential man-in-the-middle (MIM) attacks with tight reductions to LPN, Field-LPN, or other problems. The best prior protocols had either loose reductions and required 3 rounds [V. Lyubashevsky and D. Masny, Crypto 2013, Lect. Notes Comput. Sci. 8043, 308–325 (2013; Zbl 1316.94102)] or had a much larger key [E. Kiltz et al., Eurocrypt 2011, Lect. Notes Comput. Sci. 6632, 7–26 (2011; Zbl 1281.94083)], and Y. Dodis et al. [Eurocrypt 2012, Lect. Notes Comput. Sci. 7237, 355–374 (2012; Zbl 1297.94117)]. Our constructions follow from a new generic deterministic and round-preserving transformation enhancing actively-secure protocols of a special form to be sequentially MIM-secure while only adding a limited amount of key material and computation.
For the entire collection see [Zbl 1331.94002].


94A62 Authentication, digital signatures and secret sharing


Full Text: DOI Link


[1] Akavia, A., Bogdanov, A., Guo, S., Kamath, A., Rosen, A.: Candidate weak pseudorandom functions in ac
\[ ^{0} \]
; mod
\[ _{2} \]
. In: ITCS, pp. 251–260 (2014) · Zbl 1364.94519
[2] 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) · Zbl 1252.94044
[3] 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) · Zbl 0870.94019
[4] Bellare, M., Rogaway, P.: The security of triple encryption and a framework for code-based game-playing proofs. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 409–426. Springer, Heidelberg (2006) · Zbl 1140.94321
[5] 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) · Zbl 1337.94093
[6] Blum, A., Furst, M.L., 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) · Zbl 0870.94021
[7] Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. In: 32nd ACM STOC, pp. 435–440, Portland, Oregon, USA, May 21–23, 2000. ACM Press (2000) · Zbl 1296.68122
[8] Bringer, J., Chabanne, H., Dottax, E.: HB
\[ ^{++} \]
: a lightweight authentication protocol secure against some attacks. In: SecPerU, pp. 28–33 (2006)
[9] Damgård, I., Park, S.: Towards optimally efficient secret-key authentication from PRG. Cryptology ePrint Archive, Report 2014/426 (2014). http://eprint.iacr.org/2014/426
[10] 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) · Zbl 1297.94117
[11] Duc, D.N., Kim, K.: Securing HB
\[ ^+ \]
against GRS man-in-the-middle attack. In: SCIS (2007)
[12] 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) · Zbl 0636.94012
[13] Gilbert, H., Robshaw, M., Seurin, Y.: HB
\[ ^{\sharp } \]
: increasing the security and efficiency of HB
\[ ^{+} \]
. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 361–378. Springer, Heidelberg (2008) · Zbl 1149.94334
[14] Gilbert, H., Robshaw, M., Seurin, Y.: How to encrypt with the LPN problem. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 679–690. Springer, Heidelberg (2008) · Zbl 1155.94368
[15] 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) · Zbl 1282.94078
[16] Hopper, N.J., Blum, M.: Secure human identification protocols. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 52–66. Springer, Heidelberg (2001) · Zbl 1062.94549
[17] Jain, A., Krenn, S., Pietrzak, K., Tentes, A.: Commitments and efficient zero-knowledge proofs from learning parity with noise. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 663–680. Springer, Heidelberg (2012) · Zbl 1292.94082
[18] 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) · Zbl 1145.94470
[19] Katz, J., Shin, J.S., Smith, A.: Parallel and concurrent security of the HB and HB+ protocols. J. Cryptol. 23(3), 402–421 (2010) · Zbl 1201.94090
[20] 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) · Zbl 1281.94083
[21] 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) · Zbl 1152.94434
[22] 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, Part II. LNCS, vol. 8043, pp. 308–325. Springer, Heidelberg (2013) · Zbl 1316.94102
[23] Maurer, U.M., Sjödin, J.: A fast and key-efficient reduction of chosen-ciphertext to known-plaintext security. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 498–516. Springer, Heidelberg (2007) · Zbl 1141.94364
[24] Maurer, U.M., Tessaro, S.: Basing PRFs on constant-query weak prfs: minimizing assumptions for efficient symmetric cryptography. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 161–178. Springer, Heidelberg (2008) · Zbl 1206.94081
[25] Munilla, J., Peinado, A.: HB-MP: a further step in the hb-family of lightweight authentication protocols. Computer Networks 51(9), 2262–2267 (2007) · Zbl 1118.68015
[26] Ouafi, K., Overbeck, R., Vaudenay, S.: On the security of HB# against a man-in-the-middle attack. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 108–124. Springer, Heidelberg (2008) · Zbl 1206.94084
[27] Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th ACM STOC, Baltimore, Maryland, USA, May 22–24, 2005, pp. 84–93. ACM Press · Zbl 1192.94106
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.