Symmetric Primitives with Structured Secrets | SpringerLink
Skip to main content
Springer Nature Link
Log in

Symmetric Primitives with Structured Secrets

  • Conference paper
  • First Online:
Advances in Cryptology – CRYPTO 2019 (CRYPTO 2019)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 11692))

Included in the following conference series:

  • 2941 Accesses

Abstract

Securely managing encrypted data on an untrusted party is a challenging problem that has motivated the study of a wide variety of cryptographic primitives. A special class of such primitives allows an untrusted party to transform a ciphertext encrypted under one key to a ciphertext under another key, using some auxiliary information that does not leak the underlying data. Prominent examples of such primitives in the symmetric setting are key-homomorphic (weak) PRFs, updatable encryption, and proxy re-encryption. Although these primitives differ significantly in terms of their constructions and security requirements, they share two important properties: (a) they have secrets with structure or extra functionality, and (b) all known constructions of these primitives satisfying reasonably strong definitions of security are based on concrete public-key assumptions, e.g., DDH and LWE.

This raises the question of whether these objects inherently belong to the world of public-key primitives, or they can potentially be built from simple symmetric-key objects such as pseudorandom functions. In this work, we show that the latter possibility is unlikely. More specifically, we show that:

  • Any (bounded) key-homomorphic weak PRF with an abelian output group implies a (bounded) input-homomorphic weak PRF, which has recently been shown to imply not only public-key encryption  but also a variety of primitives such as PIR, lossy TDFs, and even IBE.

  • Any ciphertext-independent updatable encryption scheme that is forward and post-compromise secure implies PKE. Moreover, any symmetric-key proxy re-encryption scheme with reasonably strong security guarantees implies a forward and post-compromise secure ciphertext-independent updatable encryption, and hence PKE.

In addition, we show that unbounded (or exact) key-homomorphic weak PRFs over abelian groups are impossible in the quantum world. In other words, over abelian groups, bounded key-homomorphism is the best that we can hope for in terms of post-quantum security. Our attack also works over other structured primitives with abelian groups and exact homomorphisms, including homomorphic one-way functions and input-homomorphic weak PRFs.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 14871
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 18589
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    We note that this equality can be relaxed to achieve approximate key-homomorphic PRFs, and these (approximate) key-homomorphic PRFs can be built from lattice-based assumptions, like LWE.

  2. 2.

    A weak PRF is a PRF for which the pseudorandomness guarantee holds when the inputs are sampled uniformly at random.

  3. 3.

    This was originally envisioned by the authors of [NPR99] as a PRF in the random oracle model, but we note that it is equivalent to a weak PRF in the standard model.

  4. 4.

    We use the term “subset sum” loosely to essentially indicate subset group-operation over the output space of the KHwPRF. Depending on whether the group is additive or multiplicative, we perform either subset sums or subset products.

  5. 5.

    We remark that known algorithms to solve systems of linear equations over abelian groups need an explicit representation of the group, see [GR02] for more details. For example, such an explicit representation is not known to an adversary against a DDH-hard group \(\mathbb {G}\).

  6. 6.

    Notice that for the correctness of key exchange, we require the group \(\mathcal {Y}\) to be abelian.

  7. 7.

    Notice that it is almost always the case that \(\mathcal {Y}\) is an efficiently samplable group. By Theorem 5 of [AGKP14], a set of uniform elements with size forms a generating set for \(\mathcal {Y}\) with an overwhelming probability.

  8. 8.

    Notice that each component may live in a different cyclic group.

References

  1. Ateniese, G., Benson, K., Hohenberger, S.: Key-private proxy re-encryption. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol. 5473, pp. 279–294. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00862-7_19

    Chapter  Google Scholar 

  2. Aono, Y., Boyen, X., Phong, L.T., Wang, L.: Key-private proxy re-encryption under LWE. In: Paul, G., Vaudenay, S. (eds.) INDOCRYPT 2013. LNCS, vol. 8250, pp. 1–18. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-03515-4_1

    Chapter  Google Scholar 

  3. Ateniese, G., Fu, K., Green, M., Hohenberger, S.: Improved proxy re-encryption schemes with applications to secure distributed storage. In: NDSS 2005. The Internet Society, February 2005

    Google Scholar 

  4. Ateniese, G., Fu, K., Green, M., Hohenberger, S.: Improved proxy re-encryption schemes with applications to secure distributed storage. ACM Trans. Inf. Syst. Secur. (TISSEC) 9(1), 1–30 (2006)

    Article  Google Scholar 

  5. Armknecht, F., Gagliardoni, T., Katzenbeisser, S., Peter, A.: General impossibility of group homomorphic encryption in the quantum world. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 556–573. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54631-0_32

    Chapter  Google Scholar 

  6. Alamati, N., Montgomery, H., Patranabis, S., Roy, A.: Minicrypt primitives with algebraic structure and applications. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019, Part II. LNCS, vol. 11477, pp. 55–82. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_3

    Chapter  Google Scholar 

  7. Barak, B.: The complexity of public-key cryptography. In: Lindell, Y. (ed.) Tutorials on the Foundations of Cryptography. ISC, pp. 45–77. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-57048-8_2

    Chapter  Google Scholar 

  8. Blaze, M., Bleumer, G., Strauss, M.: Divertible protocols and atomic proxy cryptography. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 127–144. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054122

    Chapter  Google Scholar 

  9. Berman, I., Degwekar, A., Rothblum, R.D., Vasudevan, P.N.: From laconic zero-knowledge to public-key cryptography. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part III. LNCS, vol. 10993, pp. 674–697. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_23

    Chapter  Google Scholar 

  10. Banerjee, A., Fuchsbauer, G., Peikert, C., Pietrzak, K., Stevens, S.: Key-homomorphic constrained pseudorandom functions. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 31–60. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46497-7_2

    Chapter  Google Scholar 

  11. Boneh, D., Lewi, K., Montgomery, H., Raghunathan, A.: Key homomorphic PRFs and their applications. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 410–428. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_23

    Chapter  Google Scholar 

  12. Brakerski, Z., Lombardi, A., Segev, G., Vaikuntanathan, V.: Anonymous IBE, leakage resilience and circular security from new assumptions. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part I. LNCS, vol. 10820, pp. 535–564. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_20

    Chapter  Google Scholar 

  13. Banerjee, A., Peikert, C.: New and improved key-homomorphic pseudorandom functions. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 353–370. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_20

    Chapter  Google Scholar 

  14. Banerjee, A., Peikert, C., Rosen, A.: Pseudorandom functions and lattices. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 719–737. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_42

    Chapter  Google Scholar 

  15. Bogdanov, A., Rosen, A.: Pseudorandom functions: three decades later. In: Lindell, Y. (ed.) Tutorials on the Foundations of Cryptography. ISC, pp. 79–158. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-57048-8_3

    Chapter  Google Scholar 

  16. Brakerski, Z., Vaikuntanathan, V.: Constrained key-homomorphic PRFs from standard lattice assumptions. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 1–30. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46497-7_1

    Chapter  Google Scholar 

  17. Chandran, N., Chase, M., Liu, F.-H., Nishimaki, R., Xagawa, K.: Re-encryption, functional re-encryption, and multi-hop re-encryption: a framework for achieving obfuscation-based security and instantiations from lattices. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 95–112. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54631-0_6

    Chapter  Google Scholar 

  18. Canetti, R., Hohenberger, S.: Chosen-ciphertext secure proxy re-encryption. In: Ning, P., De Capitani di Vimercati, S., Syverson, P.F. (eds.) ACM CCS 2007, pp. 185–194. ACM Press, October 2007

    Google Scholar 

  19. Childs, A.M.: Lecture notes on quantum algorithms (2017). https://www.cs.umd.edu/~amchilds/qa/qa.pdf

  20. Cheung, K.K.H., Mosca, M.: Decomposing finite abelian groups. Quantum Inf. Comput. 1(3), 26–32 (2001)

    MathSciNet  MATH  Google Scholar 

  21. Döttling, N., Garg, S.: From selective IBE to Full IBE and selective HIBE. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017, Part I. LNCS, vol. 10677, pp. 372–408. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_13

    Chapter  Google Scholar 

  22. Döttling, N., Garg, S.: Identity-based encryption from the Diffie-Hellman assumption. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part I. LNCS, vol. 10401, pp. 537–569. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_18

    Chapter  Google Scholar 

  23. Derler, D., Krenn, S., Lorünser, T., Ramacher, S., Slamanig, D., Striecks, C.: Revisiting proxy re-encryption: forward secrecy, improved security, and applications. In: Abdalla, M., Dahab, R. (eds.) PKC 2018, Part I. LNCS, vol. 10769, pp. 219–250. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76578-5_8

    Chapter  Google Scholar 

  24. 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). https://doi.org/10.1007/978-3-642-29011-4_22

    Chapter  Google Scholar 

  25. de Saint Guilhem, C., Orsini, E., Petit, C., Smart, N.P.: Secure oblivious transfer from semi-commutative masking. Cryptology ePrint Archive, Report 2018/648 (2018). https://eprint.iacr.org/2018/648

  26. Everspaugh, A., Paterson, K., Ristenpart, T., Scott, S.: Key rotation for authenticated encryption. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part III. LNCS, vol. 10403, pp. 98–129. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63697-9_4

    Chapter  Google Scholar 

  27. Fischlin, M., Harasser, P.: Invisible sanitizable signatures and public-key encryption are equivalent. In: Preneel, B., Vercauteren, F. (eds.) ACNS 2018. LNCS, vol. 10892, pp. 202–220. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93387-0_11

    Chapter  MATH  Google Scholar 

  28. Fuchsbauer, G., Kamath, C., Klein, K., Pietrzak, K.: Adaptively secure proxy re-encryption. In: Lin, D., Sako, K. (eds.) PKC 2019, Part II. LNCS, vol. 11443, pp. 317–346. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17259-6_11

    Chapter  Google Scholar 

  29. Green, M., Ateniese, G.: Identity-based proxy re-encryption. In: Katz, J., Yung, M. (eds.) ACNS 2007. LNCS, vol. 4521, pp. 288–306. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-72738-5_19

    Chapter  Google Scholar 

  30. Garg, S., Hajiabadi, M., Mahmoody, M., Mohammed, A.: Limits on the power of garbling techniques for public-key encryption. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part III. LNCS, vol. 10993, pp. 335–364. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_12

    Chapter  Google Scholar 

  31. Goldmann, M., Russell, A.: The complexity of solving equations over finite groups. Inf. Comput. 178(1), 253–262 (2002)

    Article  MathSciNet  Google Scholar 

  32. Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: 21st ACM STOC, pp. 44–61. ACM Press, May 1989

    Google Scholar 

  33. Impagliazzo, R., Zuckerman, D.: How to recycle random bits. In: 30th FOCS, pp. 248–253. IEEE Computer Society Press, October/November 1989

    Google Scholar 

  34. Jao, D., De Feo, L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 19–34. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25405-5_2

    Chapter  MATH  Google Scholar 

  35. Kushilevitz, E., Ostrovsky, R.: Replication is NOT needed: SINGLE database, computationally-private information retrieval. In: 38th FOCS, pp. 364–373. IEEE Computer Society Press, October 1997

    Google Scholar 

  36. Koppula, V., Waters, B.: Realizing chosen ciphertext security generically in attribute-based encryption and predicate encryption. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 671–700 (2019)

    Google Scholar 

  37. Lewi, K., Montgomery, H., Raghunathan, A.: Improved constructions of PRFs secure against related-key attacks. In: Boureanu, I., Owesarski, P., Vaudenay, S. (eds.) ACNS 2014. LNCS, vol. 8479, pp. 44–61. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07536-5_4

    Chapter  Google Scholar 

  38. Libert, B., Stehlé, D., Titiu, R.: Adaptively secure distributed PRFs from \(\sf LWE\). In: Beimel, A., Dziembowski, S. (eds.) TCC 2018, Part II. LNCS, vol. 11240, pp. 391–421. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03810-6_15

    Chapter  Google Scholar 

  39. Lehmann, A., Tackmann, B.: Updatable encryption with post-compromise security. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part III. LNCS, vol. 10822, pp. 685–716. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_22

    Chapter  Google Scholar 

  40. Libert, B., Vergnaud, D.: Unidirectional chosen-ciphertext secure proxy re-encryption. In: Cramer, R. (ed.) PKC 2008. LNCS, vol. 4939, pp. 360–379. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78440-1_21

    Chapter  Google Scholar 

  41. Montgomery, H.: More efficient lattice PRFs from keyed pseudorandom synthesizers. In: Chakraborty, D., Iwata, T. (eds.) INDOCRYPT 2018. LNCS, vol. 11356, pp. 190–211. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-05378-9_11

    Chapter  Google Scholar 

  42. (née Berners-Lee), E.L.: Improved security notions for proxy re-encryption to enforce access control. Cryptology ePrint Archive, Report 2017/824 (2017). https://eprint.iacr.org/2017/824

  43. Naor, M., Pinkas, B., Reingold, O.: Distributed pseudo-random functions and KDCs. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 327–346. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_23

    Chapter  Google Scholar 

  44. Naor, M., Reingold, O.: Synthesizers and their application to the parallel construction of pseudo-random functions. In: 36th FOCS, pp. 170–181. IEEE Computer Society Press, October 1995

    Google Scholar 

  45. Naor, M., Reingold, M.: Number-theoretic constructions of efficient pseudo-random functions. In: 38th FOCS, pp. 458–467. IEEE Computer Society Press, October 1997

    Google Scholar 

  46. Pietrzak, K., Sjödin, J.: Weak pseudorandom functions in Minicrypt. 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. 423–436. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-70583-3_35

    Chapter  Google Scholar 

  47. Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 187–196. ACM Press, May 2008

    Google Scholar 

  48. Rothblum, R.: Homomorphic encryption: from private-key to public-key. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 219–234. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19571-6_14

    Chapter  Google Scholar 

  49. Shamir, A.: Identity-based cryptosystems and signature schemes. In: Blakley, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47–53. Springer, Heidelberg (1985). https://doi.org/10.1007/3-540-39568-7_5

    Chapter  Google Scholar 

  50. Syalim, A., Nishide, T., Sakurai, K.: Realizing proxy re-encryption in the symmetric world. In: Abd Manaf, A., Zeki, A., Zamani, M., Chuprat, S., El-Qawasmeh, E. (eds.) ICIEIS 2011. CCIS, vol. 251, pp. 259–274. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25327-0_23

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Michigan, Ann Arbor, USA

    Navid Alamati

  2. Fujitsu Laboratories of America, Sunnyvale, USA

    Hart Montgomery & Sikhar Patranabis

  3. IIT Kharagpur, Kharagpur, India

    Sikhar Patranabis

Authors
  1. Navid Alamati
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hart Montgomery
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sikhar Patranabis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Navid Alamati or Hart Montgomery .

Editor information

Editors and Affiliations

  1. Georgia Institute of Technology, Atlanta, GA, USA

    Alexandra Boldyreva

  2. University of California at San Diego, La Jolla, CA, USA

    Daniele Micciancio

Rights and permissions

Reprints and permissions

Copyright information

© 2019 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Alamati, N., Montgomery, H., Patranabis, S. (2019). Symmetric Primitives with Structured Secrets. In: Boldyreva, A., Micciancio, D. (eds) Advances in Cryptology – CRYPTO 2019. CRYPTO 2019. Lecture Notes in Computer Science(), vol 11692. Springer, Cham. https://doi.org/10.1007/978-3-030-26948-7_23

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-26948-7_23

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-26947-0

  • Online ISBN: 978-3-030-26948-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation