Skip to main content
Springer Nature Link
Log in

Direct CCA-Secure KEM and Deterministic PKE from Plain LWE

  • Conference paper
  • First Online:
Post-Quantum Cryptography (PQCrypto 2019)

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

Included in the following conference series:

Abstract

We present a particularly simple and efficient CCA-secure public-key encapsulation scheme without random oracles or costly sampling. The construction is direct in the sense that it eschews generic transformations via one-time signatures or MACs typically found in standard-model constructions. This gives us a compact, conceptually simpler, and computationally efficient operation, that in particular does not require any Gaussian sampling. Nevertheless, security is based on the hardness of the plain learning-with-errors (LWE) problem with polynomial modulus-to-noise ratio.

Of further interest, we also show how to obtain CCA-secure deterministic public-key encryption (for high-entropy messages), that is more compact and efficient than existing constructions.

X. Boyen—Research supported in part by ARC Discovery Project grant number DP140103885 and ARC Future Fellowship FT140101145 from the Australian Research Council.

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
$34.99 /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
USD 29.95
Price excludes VAT (USA)
eBook
USD 59.99
Price excludes VAT (USA)
Softcover Book
USD 79.99
Price excludes VAT (USA)

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 our approach here departs significantly from the recent NIST Post-Quantum KEM competition, wherein most submitters chose to embrace random oracles and stronger hardness assumptions (e.g., many variants of ring-LWE), to address its rather idiosyncratic rules and success criteria.

  2. 2.

    It was shown in [4] that such a security notion is equevalent to the PRIV-CCA security notion for multiple messages that form a block source. See [4] for details.

References

  1. Agrawal, S., Boneh, D., Boyen, X.: Efficient lattice (H)IBE in the standard model. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 553–572. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_28

    Chapter  MATH  Google Scholar 

  2. Alwen, J., Krenn, S., Pietrzak, K., Wichs, D.: Learning with rounding, revisited. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 57–74. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_4

    Chapter  Google Scholar 

  3. Alwen, J., Krenn, S., Pietrzak, K., Wichs, D.: Learning with rounding, revisited: new reduction, properties and applications. Cryptology ePrint Archive, Report 2013/098 (2013). https://eprint.iacr.org/2013/098

    Chapter  Google Scholar 

  4. Boldyreva, A., Fehr, S., O’Neill, A.: On notions of security for deterministic encryption, and efficient constructions without random oracles. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 335–359. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_19

    Chapter  Google Scholar 

  5. Boneh, D., Canetti, R., Halevi, S., Katz, J.: Chosen-ciphertext security from identity-based encryption. SIAM J. Comput. 36(5), 1301–1328 (2006)

    Article  MathSciNet  Google Scholar 

  6. Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 41–69. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_3

    Chapter  MATH  Google Scholar 

  7. Boyen, X., Mei, Q., Waters, B.: Direct chosen ciphertext security from identity-based techniques. In: Proceedings of the 12th ACM Conference on Computer and Communications Security, pp. 320–329. ACM (2005)

    Google Scholar 

  8. Cramer, R., Shoup, V.: Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM J. Comput. 33(1), 167–226 (2003)

    Article  MathSciNet  Google Scholar 

  9. Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM J. Comput. 38(1), 97–139 (2008)

    Article  MathSciNet  Google Scholar 

  10. Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. J. Cryptol. 26(1), 80–101 (2013)

    Article  MathSciNet  Google Scholar 

  11. Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC 2008, pp. 197–206. ACM, New York (2008)

    Google Scholar 

  12. Goldwasser, S., Kalai, Y., Peikert, C., Vaikuntanathan, V.: Robustness of the learning with errors assumption. In: Innovations in Computer Science, pp. 230–240 (2010)

    Google Scholar 

  13. Kiltz, E., Galindo, D.: Direct chosen-ciphertext secure identity-based key encapsulation without random oracles. Theoret. Comput. Sci. 410(47–49), 5093–5111 (2009)

    Article  MathSciNet  Google Scholar 

  14. Lai, J., Deng, R.H., Liu, S., Kou, W.: Efficient CCA-secure PKE from identity-based techniques. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 132–147. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11925-5_10

    Chapter  Google Scholar 

  15. Micciancio, D., Peikert, C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 700–718. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_41

    Chapter  Google Scholar 

  16. Mol, P., Yilek, S.: Chosen-ciphertext security from slightly lossy trapdoor functions. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 296–311. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13013-7_18

    Chapter  Google Scholar 

  17. Peikert, C., Regev, O., Stephens-Davidowitz, N.: Pseudorandomness of ring-LWE for any ring and modulus. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 461–473. ACM (2017)

    Google Scholar 

  18. Peikert, C., Vaikuntanathan, V., Waters, B.: A framework for efficient and composable oblivious transfer. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 554–571. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_31

    Chapter  Google Scholar 

  19. Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. SIAM J. Comput. 40(6), 1803–1844 (2011)

    Article  MathSciNet  Google Scholar 

  20. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2005, pp. 84–93. ACM, New York (2005)

    Google Scholar 

  21. Rosen, A., Segev, G.: Chosen-ciphertext security via correlated products. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 419–436. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00457-5_25

    Chapter  Google Scholar 

  22. Xie, X., Xue, R., Zhang, R.: Deterministic public key encryption and identity-based encryption from lattices in the auxiliary-input setting. In: Visconti, I., De Prisco, R. (eds.) SCN 2012. LNCS, vol. 7485, pp. 1–18. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32928-9_1

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. QUT, Brisbane, Australia

    Xavier Boyen

  2. Griffith University, Brisbane, Australia

    Qinyi Li

Authors
  1. Xavier Boyen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Qinyi Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Qinyi Li .

Editor information

Editors and Affiliations

  1. University of Cincinnati, Cincinnati, OH, USA

    Jintai Ding

  2. Department of Mathematical Sciences, Florida Atlantic University, Boca Raton, FL, USA

    Rainer Steinwandt

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Boyen, X., Li, Q. (2019). Direct CCA-Secure KEM and Deterministic PKE from Plain LWE. In: Ding, J., Steinwandt, R. (eds) Post-Quantum Cryptography. PQCrypto 2019. Lecture Notes in Computer Science(), vol 11505. Springer, Cham. https://doi.org/10.1007/978-3-030-25510-7_7

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-25510-7_7

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-25509-1

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

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation