http://iet.metastore.ingenta.com
1887

Low Noise LPN: Key dependent message secure public key encryption an sample amplification

Low Noise LPN: Key dependent message secure public key encryption an sample amplification

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Information Security — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Cryptographic schemes based on the learning parity with noise (LPN) problem have several very desirable aspects: low computational overhead, simple implementation and conjectured post-quantum hardness. Choosing the LPN noise parameter sufficiently low allows for public key cryptography. In this study, the authors construct the first standard model public key encryption scheme with key dependent message security based solely on the low-noise LPN problem. Additionally, they establish a new connection between LPN with a bounded number of samples and LPN with an unbounded number of samples. In essence, they show that if LPN with a small error and a small number of samples is hard, then LPN with a slightly larger error and an unbounded number of samples is also hard. The key technical ingredient to establish both results is a variant of the LPN problem called the extended LPN problem.

References

    1. 1)
      • 1. Blum, A., Furst, M.L., Kearns, M.J., et al: ‘Cryptographic primitives based on hard learning problems’. Proc. 13th Annual Int. Cryptology Conf. Advances in Cryptology – CRYPTO ‘93, Santa Barbara, CA, USA, 22–26 August 1993 , pp. 278291.
    2. 2)
      • 2. Hopper, N.J., Blum, M.: ‘Secure human identification protocols’. Advances in Cryptology – ASIACRYPT 2001, Seventh Int. Conf. on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, 9–13 December 2001, pp. 5266.
    3. 3)
      • 3. Katz, J., Shin, J.S., Smith, A.: ‘Parallel and concurrent security of the HB and hb+ protocols’, J. Cryptol., 2010, 23, (3), pp. 402421.
    4. 4)
      • 4. Heyse, S., Kiltz, E., Lyubashevsky, V., et al: ‘Lapin: an efficient authentication protocol based on ring-LPN’. Fast Software Encryption – 19th Int. Workshop, FSE 2012, Washington, DC, USA, 19–21 March 2012, pp. 346365, Revised Selected Papers.
    5. 5)
      • 5. Lyubashevsky, V., Masny, D.: ‘Man-in-the-middle secure authentication schemes from LPN and weak PRFs’. Proc., Part II Advances in Cryptology – CRYPTO 2013 – 33rd Annual Cryptology Conf., Santa Barbara, CA, USA, 18–22 August 2013, pp. 308325.
    6. 6)
      • 6. Alekhnovich, M.: ‘More on average case vs. approximation complexity’. 44th Symp. on Foundations of Computer Science (FOCS 2003), Cambridge, MA, USA, 11–14 October 2003, pp. 298307.
    7. 7)
      • 7. Döttling, N., Müller-Quade, J., Nascimento, A.C.A.: ‘IND-CCA secure cryptography based on a variant of the LPN problem’. Proc. Advances in Cryptology – ASIACRYPT 2012 – 3018th Int. Conf. on the Theory and Application of Cryptology and Information Security, Beijing, China, 2–6 December 2012, pp. 485503.
    8. 8)
      • 8. Kiltz, E., Masny, D., Pietrzak, K.: ‘Simple chosen-ciphertext security from low-noise LPN’. Public Key Cryptography, 2014, pp. 118.
    9. 9)
      • 9. David, B., Dowsley, R., Nascimento, A.C.A.: ‘Universally composable oblivious transfer based on a variant of LPN’. Proc. Cryptology and Network Security – 13th Int. Conf., CANS 2014, Heraklion, Crete, Greece, 22–24 October 2014, pp. 143158.
    10. 10)
      • 10. Black, J., Rogaway, P., Shrimpton, T.: ‘Encryption-scheme security in the presence of key-dependent messages’. Selected Areas in Cryptography, Ninth Annual Int. Workshop, SAC 2002, St. John's, Newfoundland, Canada, 15–16 August 2002, pp. 6275, Revised Papers.
    11. 11)
      • 11. Adão, P., Bana, G., Herzog, J., et al: ‘Soundness of formal encryption in the presence of key-cycles’. Computer Security – ESORICS 2005, 10th European Symp. on Research in Computer Security, Milan, Italy, 12–14 September 2005, pp. 374396.
    12. 12)
      • 12. Boneh, D., Halevi, S., Hamburg, M., et al: ‘Circular-secure encryption from decision Diffie–Hellman’. Proc. Advances in Cryptology – CRYPTO 2008, 28th Annual Int. Cryptology Conf., Santa Barbara, CA, USA, 17–21 August 2008, pp. 108125.
    13. 13)
      • 13. Acar, T., Belenkiy, M., Bellare, M., et al: ‘Cryptographic agility and its relation to circular encryption’. Proc. Advances in Cryptology – EUROCRYPT 2010, 29th Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, French Riviera, 30 May–3 June 2010, pp. 403422.
    14. 14)
      • 14. Cash, D., Green, M., Hohenberger, S.: ‘New definitions and separations for circular security’. Proc. Public Key Cryptography – PKC 2012 – 15th Int. Conf. on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, 21–23 May 2012, pp. 540557.
    15. 15)
      • 15. Applebaum, B., Cash, D., Peikert, C., et al: ‘Fast cryptographic primitives and circular secure encryption based on hard learning problems’. CRYPTO, 2009, pp. 595618.
    16. 16)
      • 16. Applebaum, B.: ‘Garbling XOR gates ‘for free’ in the standard model’. TCC, 2013, pp. 162181.
    17. 17)
      • 17. Applebaum, B.: ‘Key-dependent message security: generic amplification and completeness’. Proc. Advances in Cryptology – EUROCRYPT 2011 – 30th Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, 15–19 May 2011, pp. 527546.
    18. 18)
      • 18. O'Neill, A., Peikert, C., Waters, B.: ‘Bi-deniable public-key encryption’. Proc. Advances in Cryptology – CRYPTO 2011 – 31st Annual Cryptology Conf., Santa Barbara, CA, USA, 14–18 August 2011, pp. 525542.
    19. 19)
      • 19. Alperin-Sheriff, J., Peikert, C.: ‘Circular and KDM security for identity-based encryption’. Proc. Public Key Cryptography – PKC 2012 – 15th Int. Conf. on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, 21–23 May 2012, pp. 334352.
    20. 20)
      • 20. Impagliazzo, R., Levin, L.A., Luby, M.: ‘Pseudo-random generation from one-way functions (extended abstracts)’. Proc. of the 21st Annual ACM Symp. on Theory of Computing, Seattle, Washington, DC, USA, 14–17 May 1989, pp. 1224.
    21. 21)
      • 21. Dodis, Y., Reyzin, L., Smith, A.: ‘Fuzzy extractors: how to generate strong keys from biometrics and other noisy data’. Proc. Advances in Cryptology – EUROCRYPT 2004, Int. Conf. on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, 2–6 May 2004, pp. 523540.
    22. 22)
      • 22. Gentry, C., Peikert, C., Vaikuntanathan, V.: ‘Trapdoors for hard lattices and new cryptographic constructions’. Proc. of the 40th Annual ACM Symp. on Theory of Computing, Victoria, British Columbia, Canada, 17–20 May 2008, pp. 197206.
    23. 23)
      • 23. Applebaum, B., Ishai, Y., Kushilevitz, E.: ‘Cryptography with constant input locality’. Proc. Advances in Cryptology – CRYPTO 2007, 27th Annual Int. Cryptology Conf., Santa Barbara, CA, USA, 19–23 August 2007 , pp. 92110.
    24. 24)
      • 24. Aharonov, D., Regev, O.: ‘A lattice problem in quantum NP’. Proc. 44th Symp. on Foundations of Computer Science (FOCS 2003), Cambridge, MA, USA, 11–14 October 2003, pp. 210219.
    25. 25)
      • 25. Micciancio, D., Regev, O.: ‘Worst-case to average-case reductions based on Gaussian measures’. Proc. 45th Symp. on Foundations of Computer Science (FOCS 2004), Rome, Italy, 17–19 October 2004, pp. 372381.
    26. 26)
      • 26. Regev, O.: ‘On lattices, learning with errors, random linear codes, and cryptography’. Proc. of the 37th Annual ACM Symp. on Theory of Computing, Baltimore, MD, USA, 22–24 May 2005, pp. 8493.
    27. 27)
      • 27. Peikert, C.: ‘An efficient and parallel Gaussian sampler for lattices’. Proc. Advances in Cryptology – CRYPTO 2010, 30th Annual Cryptology Conf., Santa Barbara, CA, USA, 15–19 August 2010, pp. 8097.
    28. 28)
      • 28. Lyubashevsky, V.: ‘The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem’. Proc. Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, Eighth Int. Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and Ninth Int. Workshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, 22–24 August 2005, pp. 378389.
    29. 29)
      • 29. Döttling, N.: ‘Low noise LPN: KDM secure public key encryption and sample amplification’. Proc. Public-Key Cryptography – PKC 2015 – 18th IACR Int. Conf. on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, 30 March–1 April 2015, pp. 604626.
    30. 30)
      • 30. Forney, G.D.: ‘Generalized minimum distance decoding’, IEEE Trans. Inf. Theory, 1966, 12, (2), pp. 125131.
    31. 31)
      • 31. Sipser, M., Spielman, D.A.: ‘Expander codes’. 35th Annual Symp. on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20–22 November 1994, pp. 566576.
    32. 32)
      • 32. Spielman, D.A.: ‘Linear-time encodable and decodable error-correcting codes’. Proc. of the 27th Annual ACM Symp. on Theory of Computing, Las Vegas, NV, USA, 29 May–1 June 1995, pp. 388397.
    33. 33)
      • 33. Dunbar, S.R.: ‘Topics in probability theory and stochastic processes’. Available at http://www.math.unl.edu/sdunbar1/ProbabilityTheory/Lessons/BernoulliTrials/DeMoivreLaplaceCLT/demoivrelaplaceclt.pdf, 2011, accessed 07January 2015.
    34. 34)
      • 34. Goldreich, O., Levin, L.A.: ‘A hard-core predicate for all one-way functions’. Proc. of the 21st Annual ACM Symp. on Theory of Computing, Seattle, Washington, DC, USA, 14–17 May 1989, pp. 2532.
    35. 35)
      • 35. Goldreich, O.: ‘Foundations of cryptography: basic tools’ (Cambridge University Press, New York, NY, USA, 2000).
    36. 36)
      • 36. Cash, D., Hofheinz, D., Kiltz, E., et al: ‘Bonsai trees, or how to delegate a lattice basis’. Proc. Advances in Cryptology – EUROCRYPT 2010, 29th Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, French Riviera, 30 May–3 June 2010, pp. 523552.
    37. 37)
      • 37. Agrawal, S., Boneh, D., Boyen, X.: ‘Efficient lattice (H)IBE in the standard model’. Proc. Advances in Cryptology – EUROCRYPT 2010, 29th Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, French Riviera, 30 May–3 June 2010, pp. 553572.
    38. 38)
      • 38. Agrawal, S., Boneh, D., Boyen, X.: ‘Lattice basis delegation in fixed dimension and shorter ciphertext hierarchical IBE’. Advances in Cryptology – CRYPTO 2010, 30th Annual Cryptology Conf., Santa Barbara, CA, USA, 15–19 August 2010, pp. 98115.
    39. 39)
      • 39. Böhl, F., Hofheinz, D., Jager, T., et al: ‘Practical signatures from standard assumptions’. Proc. Advances in Cryptology – EUROCRYPT 2013, 32nd Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, Athens, Greece, 26–30 May 2013, pp. 461485.
    40. 40)
      • 40. Ducas, L., Durmus, A., Lepoint, T., et al: ‘Lattice signatures and bimodal Gaussians’. Proc., Part I Advances in Cryptology – CRYPTO 2013 – 33rd Annual Cryptology Conf., Santa Barbara, CA, USA, 18–22 August 2013, pp. 4056.
    41. 41)
      • 41. Ducas, L., Micciancio, D.: ‘Improved short lattice signatures in the standard model’. Proc., Part I Advances in Cryptology – CRYPTO 2014 – 34th Annual Cryptology Conf., Santa Barbara, CA, USA, 17–21 August 2014, pp. 335352.
    42. 42)
      • 42. Döttling, N.: ‘Cryptography based on the hardness of decoding’. PhD thesis, Karlsruhe Institute of Technology, May 2014. Available at http://www.nbnresolving.org/urn:nbn:de:swb:90-411105.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2015.0495
Loading

Related content

content/journals/10.1049/iet-ifs.2015.0495
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address