access icon free Public key cryptosystems secure against memory leakage attacks

© The Institution of Engineering and Technology
Received 18/05/2015, Accepted 17/11/2015, Revised 05/10/2015, Published 15/04/2016

The authors present a new general construction of public key encryption (PKE) based on the restricted subset membership (RSM) assumption, which can achieve the bounded-memory leakage resilient security and the auxiliary-input leakage resilient security simultaneously. The construction is BHHO-type, as Brakerski et al. work, but the message space is much larger and the proof is more concise benefiting from the RSM assumption. Instantiating the construction with the QR assumption, the authors get the first QR-based auxiliary-input secure PKE with a larger message space than {0,1}. Moreover, the authors generalise the Goldreich–Levin theorem to large rings. This theorem helps to improve the construction to achieve the same security level with fewer public parameters and shorter ciphertexts compared with Brakerski et al. work. For the bounded-memory leakage resilient security, the construction can achieve leakage rate of 1 − o(1) and avoid the dependence between the message length and the amount of leakage. Based on the general construction, the authors also can achieve both bounded-memory leakage resilient chosen ciphertext attack (CCA) security and the auxiliary-input leakage resilient CCA security via the well-known Naor–Yung paradigm.

Inspec keywords: public key cryptography; storage management

Other keywords: RSM assumption; bounded-memory leakage resilient chosen ciphertext attack security; BHHO-type; QR-based auxiliary-input secure PKE; auxiliary-input leakage resilient CCA security; Goldreich-Levin theorem; public key encryption; public key cryptosystem; restricted subset membership assumption; memory leakage attack; Naor–Yung paradigm; bounded-memory leakage resilient CCA security

Subjects: Cryptography; Data security; File organisation

References

    1. 1)
      • 15. Cramer, R., Shoup, V.: ‘Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption’. EUROCRYPT 2002, Amsterdam, The Netherlands, April 28–May 2, 2002, pp. 45–64.
    2. 2)
      • 22. Pandey, O.: ‘Achieving constant round leakage-resilient zero-knowledge’. TCC 2014, San Diego, CA, USA, February 24–26, 2014, pp. 146–166.
    3. 3)
      • 32. Hofheinz, D., Kiltz, E.: ‘The group of signed quadratic residues and applications’. CRYPTO 2009, Santa Barbara, CA, USA, August 16–20, 2009, pp. 637–653.
    4. 4)
      • 5. Dodis, Y., Kalai, Y.T., Lovett, S.: ‘On cryptography with auxiliary input’. STOC 2009, New York, NY, USA, 2009, pp. 621–630.
    5. 5)
      • 9. Brakerski, Z., Goldwasser, S.: ‘Circular and leakage resilient public-key encryption under subgroup indistinguishability – (or: Quadratic residuosity strikes back)’. CRYPTO 2010, Santa Barbara, CA, USA, August 15–19, 2010, pp. 1–20.
    6. 6)
      • 11. Liu, S., Weng, J., Zhao, Y.: ‘Efficient public key cryptosystem resilient to key leakage chosen ciphertext attacks’. CT-RSA 2013, San Francisco, CA, USA, February 25–March 1, 2013, pp. 84–100.
    7. 7)
      • 33. Zhang, Z., Cao, Z., Qian, H.: ‘Chosen-ciphertext attack secure public key encryption with auxiliary inputs’, Secur. Commun. Netw., 2012, 5, (12), pp. 1404–1411.
    8. 8)
      • 10. Qin, L., Liu, S.: ‘Leakage-resilient chosen-ciphertext secure public-key encryption from hash proof system and one-time lossy filter’. ASIACRYPT 2013, Bengaluru, India, December 1–5, 2013, pp. 381–400.
    9. 9)
      • 13. Yuen, T.H., Chow, S.S.M., Zhang, Y., et al: ‘Identity-based encryption resilient to continual auxiliary leakage’. EUROCRYPT 2012, Cambridge, UK, April 15–19, 2012, pp. 117–134.
    10. 10)
      • 20. Sun, S.F., Gu, D., Liu, S.: ‘Efficient leakage-resilient identity-based encryption with CCA security’. Pairing-Based Cryptography, Beijing, China, November 22–24, 2013, pp. 149–167.
    11. 11)
      • 27. Chor, B., Goldreich, O.: ‘Unbiased bits from sources of weak randomness and probabilistic communication complexity’, SIAM J. Comput., 1988, 17, (2), pp. 230–261.
    12. 12)
      • 19. Lewko, A.B., Rouselakis, Y., Waters, B.: ‘Achieving leakage resilience through dual system encryption’. TCC 2011, Providence, RI, USA, March 28–30, 2011, pp. 70–88.
    13. 13)
      • 2. Dziembowski, S., Pietrzak, K.: ‘Leakage-resilient cryptography’. FOCS 2008, Washington, DC, USA, October 25–28, 2008, pp. 293–302.
    14. 14)
      • 29. Carter, L., Wegman, M.N.: ‘Universal classes of hash functions (extended abstract)’. STOC ’77, Boulder, CO, USA, May 2–4, 1977, pp. 106–112.
    15. 15)
      • 21. Garg, S., Jain, A., Sahai, A.: ‘Leakage-resilient zero knowledge’. CRYPTO 2011, Santa Barbara, CA, USA, August 14–18, 2011, pp. 297–315.
    16. 16)
      • 24. Boneh, D., Halevi, S., Hamburg, M., et al: ‘Circular-secure encryption from decision diffiehellman’. CRYPTO 2008, Santa Barbara, CA, USA, August 17–21, 2008, pp. 108–125.
    17. 17)
      • 6. Katz, J., Vaikuntanathan, V.: ‘Signature schemes with bounded leakage resilience’. ASIACRYPT 2009, Tokyo, Japan, December 6–10, 2009, pp. 703–720.
    18. 18)
      • 30. Boneh, D., Goh, E.G., Nissim, K.: ‘Evaluating 2-dnf formulas on ciphertexts’. TCC 2005, Cambridge, MA, USA, February 10–12, 2005, pp. 325–341.
    19. 19)
      • 18. Chow, S.S.M., Dodis, Y., Rouselakis, Y., et al: ‘Practical leakage-resilient identity-based encryption from simple assumptions’. ACM Conf. on Computer and Communications Security, Chicago, Illinois, USA, October 4–8, 2010, pp. 152–161.
    20. 20)
      • 23. Dodis, Y., Goldwasser, S., Kalai, Y.T., et al: ‘Public-key encryption schemes with auxiliary inputs’. TCC 2010, Zurich, Switzerland, February 9–11, 2010, pp. 361–381.
    21. 21)
      • 17. Cramer, R., Shoup, V.: ‘A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack’. CRYPTO ‘98, Santa Barbara, California, USA, August 23–27, 1998, pp. 13–25.
    22. 22)
      • 26. Dodis, Y., Ostrovsky, R., Reyzin, L., et al: ‘Fuzzy extractors: How to generate strong keys from biometrics and other noisy data’, SIAM J. Comput., 2008, 38, (1), pp. 97–139.
    23. 23)
      • 14. Halderman, J.A., Schoen, S.D., Heninger, N., et al ‘Lest we remember: Cold boot attacks on encryption keys’. USENIX Security Symp., San Jose, CA, USA, July 28–August 1, 2008, pp. 45–60.
    24. 24)
      • 25. Gentry, C., Peikert, C., Vaikuntanathan, V.: ‘Trapdoors for hard lattices and new cryptographic constructions’. STOC 2008, Victoria, Canada, May 17–20, 2008, pp. 197–206.
    25. 25)
      • 16. Naor, M., Yung, M.: ‘Public-key cryptosystems provably secure against chosen ciphertext attacks’. STOC 1990, Baltimore, MD, USA, May 13–17, 1990, pp. 427–437.
    26. 26)
      • 12. Qin, L., Liu, S.: ‘Leakage-flexible cca-secure public-key encryption: Simple construction and free of pairing’. PKC 2014, Buenos Aires, Argentina, March 26–28, 2014, pp. 19–36.
    27. 27)
      • 7. Alwen, J., Dodis, Y., Naor, M., et al: ‘Public-key encryption in the bounded-retrieval model’. EUROCRYPT 2010, Riviera, French, May 30–June 3, 2010, pp. 113–134.
    28. 28)
      • 8. Dodis, Y., Haralambiev, K., López-Alt, A., et al: ‘Cryptography against continuous memory attacks’. FOCS 2010, Las Vegas, USA, 2010, pp. 511–520.
    29. 29)
      • 4. Naor, M., Segev, G.: ‘Public-key cryptosystems resilient to key leakage’, SIAM J. Comput., 2012, 41, (4), pp. 772–814.
    30. 30)
      • 28. Wegman, M.N., Carter, L.: ‘New hash functions and their use in authentication and set equality’, J. Comput. Syst. Sci., 1981, 22, (3), pp. 265–279.
    31. 31)
      • 1. Micali, S., Reyzin, L.: ‘Physically observable cryptography (extended abstract)’. TCC 2004, Cambridge, MA, USA, February 19–21, 2004, pp. 278–296.
    32. 32)
      • 3. Akavia, A., Goldwasser, S., Vaikuntanathan, V.: ‘Simultaneous hardcore bits and cryptography against memory attacks’. TCC 2009, San Francisco, CA, USA, March 15–17, 2009, pp. 474–495.
    33. 33)
      • 31. Kiltz, E., Pietrzak, K., Stam, M., et al: ‘A new randomness extraction paradigm for hybrid encryption’. EUROCRYPT 2009, Cologne, Germany, April 26–30, 2009, pp. 590–609.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2015.0195
Loading

Related content

content/journals/10.1049/iet-ifs.2015.0195
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading