Top

Journal of Cryptology

Published in:

09-12-2016

Efficient Authentication from Hard Learning Problems

Published in: Journal of Cryptology | Issue 4/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We construct efficient authentication protocols and message authentication codes (MACs) whose security can be reduced to the learning parity with noise (LPN) problem. Despite a large body of work—starting with the \({\mathsf {HB}}\) protocol of Hopper and Blum in 2001—until now it was not even known how to construct an efficient authentication protocol from LPN which is secure against man-in-the-middle attacks. A MAC implies such a (two-round) protocol.

previous article Reproducible Circularly Secure Bit Encryption: Applications and Realizations

next article Authenticated Confidential Channel Establishment and the Security of TLS-DHE

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Available only for authorised users

While we believe the above scheme would be secure in case verification queries are not allowed, this is of limited interest in practice. Furthermore, the main technical difficulty in building an efficient MAC from LPN seems to be ensuring the secret \(\mathbf {s}\) does not leak from verification queries.

An earlier version of this paper adapted a technique originally used by Waters [44] in the context of IBE schemes that has been applied to lattice-based signature [10] and encryption schemes [1].

For MAC- and PRF-based constructions, we consider the communication one incurs by constructing a MIM secure two-round protocol from the MAC (or PRF) by having the prover compute the MAC (PRF output) on a random \(\rho \)-bit challenge message. If the adversary can observe Q executions and make q attempts to convince a verifier, the probability of a successful break is at most \(Q\cdot q/2^\rho \) (plus the security of the MAC/PRF). As we define security for \(q=1\), setting \(\rho {:}{=}\lambda \) for our statistical security parameter \(\lambda =80\) is sufficient. For the PRF-based construction an output length of \(\lambda \) is sufficient.

Such a matrix is constructed by picking the entries of the first row and column uniformly at random from \(\{0,1\}\), and then copying each value all along its corresponding diagonal.

By using a hybrid argument, one can show that this implies security even if the adversary can interact in \(k\ge 1\) independent instances concurrently (and wins if the verifier accepts in at least one instance). The use of the hybrid argument loses a factor of k in the security reduction.

The acceptance threshold \(\tau '\) below can be any value in-between \(\tau \) and 1 / 2. As we set it closer to 1 / 2, the soundness error increases while the completeness error decreases. For concreteness, we set \(\tau '\) exactly in-between \(\tau \) and 1 / 2.

The code \(\mathsf {C}\) can be constructed as follows. We first sample a random matrix \(\mathbf {C}\in \mathbb {Z}_2^{\mu \times \ell }\) and map \(\mathbf {y}\in \mathbb {Z}_2^\mu \) to \(\mathsf {C}(\mathbf {y}) = (\mathbf {c}\in \mathbb {Z}_2^\ell ,\mathbf {c}'\in \mathbb {Z}_2^\ell )\) where \(\mathbf {c}= \mathbf {C}^{\mathsf {T}}\cdot \mathbf {y}\) and \(\mathbf {c}' = \overline{\mathbf {c}}\). A random code \(\mathbf {C}\) has high distance with high probability and \(\mathsf {C}(\mathbf {y}) = (\mathbf {c},\mathbf {c}')\) has weight exactly \(\ell \).

Recall that we assume that \(\mathcal {A}\) does not repeat queries and does not ask verification queries \((m,\phi )\) if \(\phi \) was the output of a tag query \(m\).

This representation is unique once the irreducible polynomial f defining \(\mathbb {F}_{2^\ell } = \mathbb {F}_2[x]/(f)\) is fixed.

S. Agrawal, D. Boneh, X. Boyen, Efficient lattice (H)IBE in the standard model, in EUROCRYPT 2010, volume 6110 of LNCS, ed. by H. Gilbert (Springer, May 2010), pp. 553–572

Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, H. van der Vorst, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide (SIAM, Philadelphia, 2000)

E. Berlekamp, R. McEliece, H. van Tilborg, On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory, 24(3), 384–386 (1978)MathSciNetCrossRefMATH

O. Blazy, E. Kiltz, J. Pan, (Hierarchical) identity-based encryption from affine message authentication, in In CRYPTO 2014, volume 8616 of LNCS, ed. by J.A. Garay, R. Gennaro (Springer, Aug 2014), pp. 408–425

A. Blum, M.L. Furst, M.J. Kearns, R.J. Lipton, Cryptographic primitives based on hard learning problems, in CRYPTO’93, volume 773 of LNCS, ed. by D.R. Stinson (Springer, Aug 1994), pp. 278–291

A. Blum, A. Kalai, H. Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM, 50(4), 506–519 (2003)MathSciNetCrossRefMATH

S. Bogos, F. Tramèr, S. Vaudenay, On solving LPN using BKW and variants—implementation and analysis. Cryptogr. Commun. 8(3), 331–369 (2016)

S. Bogos, S. Vaudenay, Observations on the LPN solving algorithm from Eurocrypt’16. Cryptology ePrint Archive, Report 2016/437 (2016). http://eprint.iacr.org/2016/437

S. Bogos, S. Vaudenay, Optimization of LPN solving algorithms. Cryptology ePrint Archive, Report 2016/288 (2016). http://eprint.iacr.org/2016/288

10.

X. Boyen, Lattice mixing and vanishing trapdoors: a framework for fully secure short signatures and more, in PKC 2010, volume 6056 of LNCS, ed. by P.Q. Nguyen, D. Pointcheval (Springer, May 2010), pp. 499–517

11.

J. Bringer, H. Chabanne, E. Dottax, \({\sf HB}^{++}\): a lightweight authentication protocol secure against some attacks, in SecPerU 2006 (IEEE Computer Society, June 2006), pp. 28–33

12.

D. Cash, E. Kiltz, S. Tessaro, Two-round man-in-the-middle security from LPN, in TCC 2016-A, volume 9562 of LNCS, ed. by E. Kushilevitz, T. Malkin (Springer, Jan 2016), pp. 225–248

13.

J. Chen, H. Wee, Fully, (almost) tightly secure IBE and dual system groups, in CRYPTO 2013, volume 8043 of LNCS, ed. by R. Canetti, J.A. Garay (Springer, Aug 2013), pp. 435–460

14.

R. Cramer, I. Damgård, On the amortized complexity of zero-knowledge protocols, in CRYPTO 2009, volume 5677 of LNCS, ed. by S. Halevi (Springer, Aug 2009), pp. 177–191

15.

Y. Dodis, E. Kiltz, K. Pietrzak, D. Wichs, Message authentication, revisited, in EUROCRYPT 2012, volume 7237 of LNCS, ed. by D. Pointcheval, T. Johansson (Springer, April 2012), pp. 355–374

16.

D.N. Duc, K. Kim, Securing \({\sf HB}^{+}\) against GRS man-in-the-middle attack, in 2007 symposium on cryptography and information security, Jan 2007

17.

J.-B. Fischer, J. Stern, An efficient pseudo-random generator provably as secure as syndrome decoding, in EUROCRYPT’96, volume 1070 of LNCS, ed. by U.M. Maurer (Springer, May 1996), pp. 245–255

18.

M. Fürer, Faster integer multiplication. SIAM J. Comput. 39(3), 979–1005 (2009)

19.

L. Gaspar, G. Leurent, F.-X. Standaert, Hardware implementation and side-channel analysis of Lapin, in CT-RSA 2014, LNCS (Springer, 2014), pp. 206–226

20.

H. Gilbert, M. Robshaw, H. Sibert, An active attack against \({\sf HB}^{+}\)—a provably secure lightweight authentication protocol. Cryptology ePrint Archive, Report 2005/237 (2005). http://eprint.iacr.org/

21.

H. Gilbert, M.J.B. Robshaw, Y. Seurin, Good variants of HB+ are hard to find, in FC 2008, volume 5143 of LNCS, ed. by G. Tsudik (Springer, Jan 2008), pp. 156–170

22.

H. Gilbert, M.J.B. Robshaw, Y. Seurin, HB\(^\sharp \): increasing the security and efficiency of HB\(^+\), in EUROCRYPT 2008, volume 4965 of LNCS, ed. by N.P. Smart (Springer, April 2008), pp. 361–378

23.

O. Goldreich, S. Goldwasser, S. Micali, How to construct random functions. J. ACM 33(4), 792–807 (1986)MathSciNetCrossRefMATH

24.

Q. Guo, T. Johansson, C. Löndahl, Solving LPN using covering codes, in ASIACRYPT 2014, volume 8873 of LNCS, ed. by P. Sarkar, T. Iwata (Springer, Dec 2014), pp. 1–20

25.

S. Heyse, E. Kiltz, V. Lyubashevsky, C. Paar, K. Pietrzak, Lapin: an efficient authentication protocol based on Ring-LPN, in FSE 2012, volume 7549 of LNCS, ed. by A. Canteaut (Springer, March 2012), pp. 346–365

26.

W. Hoeffding, Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13–30 (1963)

27.

N.J. Hopper, M. Blum, Secure human identification protocols, in ASIACRYPT 2001, volume 2248 of LNCS, ed. by C. Boyd (Springer, Dec 2001), pp. 52–66

28.

A. Juels, S.A. Weis, Authenticating pervasive devices with human protocols, inCRYPTO 2005, volume 3621 of LNCS, ed. by V. Shoup (Springer, Aug 2005), pp. 293–308

29.

T. Kailath, A.H. Sayed, Fast Reliable Algorithms for Matrices with Structure (SIAM, Philadelphia, 1999)

30.

J. Katz, J.S. Shin, Parallel and concurrent security of the HB and HB+ protocols, in EUROCRYPT 2006, volume 4004 of LNCS, ed. by S. Vaudenay (Springer, May/June 2006), pp. 73–87

31.

J. Katz, J.S. Shin, A. Smith, Parallel and concurrent security of the HB and HB+ protocols. J. Cryptol. 23(3), 402–421 (2010)

32.

M.J. Kearns, Efficient noise-tolerant learning from statistical queries. J. ACM 45(6), 983–1006 (1998)

33.

E. Kiltz, K. Pietrzak, D. Cash, A. Jain, D. Venturi, Efficient authentication from hard learning problems, in EUROCRYPT 2011, volume 6632 of LNCS, ed. by K.G. Paterson (Springer, May 2011), pp. 7–26.

34.

É. Levieil, P.-A. Fouque, An improved LPN algorithm, in SCN 06, volume 4116 of LNCS, ed. by R. De Prisco, M. Yung (Springer, Sept 2006), pp. 348–359

35.

V. Lyubashevsky, D. Masny, Man-in-the-middle secure authentication schemes from LPN and weak PRFs, in CRYPTO 2013, volume 8043 of LNCS, ed. by R. Canetti, J.A. Garay (Springer, Aug 2013), pp. 308–325

36.

V. Lyubashevsky, C. Peikert, O. Regev, On ideal lattices and learning with errors over rings, in EUROCRYPT 2010, volume 6110 of LNCS, ed. by H. Gilbert (Springer, June 2010), pp. 1–23

37.

J. Munilla, A. Peinado, \({\sf HB\sf -\sf MP}\): a further step in the HB-family of lightweight authentication protocols. Comput. Netw. 51(9), 2262–2267 (2007)

38.

K. Ouafi, R. Overbeck, S. Vaudenay, On the security of HB# against a man-in-the-middle attack, in ASIACRYPT 2008, volume 5350 of LNCS, ed. by J. Pieprzyk (Springer, Dec 2008), pp. 108–124

39.

C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem: extended abstract, in 41st ACM STOC, ed. by M. Mitzenmacher (ACM Press, May/June 2009), pp. 333–342

40.

K. Pietrzak, Subspace LWE, in TCC 2012, volume 7194 of LNCS, ed. by R. Cramer (Springer, March 2012), pp. 548–563

41.

O. Regev, On lattices, learning with errors, random linear codes, and cryptography, in 37th ACM STOC, ed. by H.N. Gabow, R. Fagin (ACM Press, May 2005), pp. 84–93

42.

Schönhage, V. Strassen, Schnelle multiplikation grosser zahlen. Computing 7, 281–292 (1971)

43.

J. Van De Graaf, Towards a formal definition of security for quantum protocols. PhD thesis, Universite de Montreal, Monreal, P.Q., Canada, Canada, AAINQ35648, 1998

44.

B.R. Waters, Efficient identity-based encryption without random oracles, in EUROCRYPT 2005, volume 3494 of LNCS, ed. by R. Cramer (Springer, May 2005), pp. 114–127

45.

J. Watrous, Zero-knowledge against quantum attacks. SIAM J. Comput. 39(1), 25–58 (2009)

46.

B. Zhang, L. Jiao, M. Wang, Faster algorithms for solving LPN, in EUROCRYPT 2016, volume 9665 of LNCS, ed. by M. Fischlin, J.-S. Coron (Springer, May 2016), pp. 168–195

Title: Efficient Authentication from Hard Learning Problems
Publication date: 09-12-2016
Published in: Journal of Cryptology / Issue 4/2017
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-016-9247-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2017

Fairness Versus Guaranteed Output Delivery in Secure Multiparty Computation

Authenticated Confidential Channel Establishment and the Security of TLS-DHE

The Hunting of the SNARK

Reproducible Circularly Secure Bit Encryption: Applications and Realizations

From Private Simultaneous Messages to Zero-Information Arthur–Merlin Protocols and Back

Information Theoretical Cryptogenography

Premium Partner