[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Lizard: Cut Off the Tail! A Practical Post-quantum Public-Key Encryption from LWE and LWR

  • Conference paper
  • First Online:
Security and Cryptography for Networks (SCN 2018)

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

Included in the following conference series:

Abstract

The LWE problem has been widely used in many constructions for post-quantum cryptography due to its reduction from the worst-case of lattice hard problems and the lightweight operations for generating its instances. The PKE schemes based on the LWE problem have a simple and fast decryption, but the encryption phase requires large parameter size for the leftover hash lemma or Gaussian samplings.

In this paper, we propose a novel PKE scheme, called Lizard, without relying on either of them. The encryption procedure of Lizard first combines several LWE samples as in the previous LWE-based PKEs, but the following step to re-randomize this combination before adding a plaintext is different: it removes several least significant bits of each component of the computed vector rather than adding an auxiliary error vector. To the best of our knowledge, Lizard is the first IND-CPA secure PKE under the hardness assumptions of the LWE and LWR problems, and its variant, namely CCALizard, achieves IND-CCA security in the (quantum) random oracle model.

Our approach accelerates the encryption speed to a large extent and also reduces the size of ciphertexts. We present an optimized C implementation of our schemes, which shows outstanding performances with concrete security: On an Intel single core processor, an encryption and decryption for CCALizard with 256-bit plaintext space under 128-bit quantum security take only 32,272 and 47,125 cycles, respectively. To achieve these results, we further take some advantages of sparse small secrets. Lizard is submitted to NIST’s post-quantum cryptography standardization process.

This work was supported by Institute for Information & communications Technology Promotion (IITP) grant funded by the Korea government (MSIT) (No. 2017-0-00616, Development of lattice-based post-quantum public-key cryptographic schemes) and Samsung Research Funding Center of Samsung Electronics under Project Number SRFC-TB1403-52, and Duhyeong Kim has been supported by NRF (National Research Foundation of Korea) Grant funded by Korean Government (NRF-2016H1A2A1906584-Global Ph.D. Fellowship Program).

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)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • 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.

    A provably secure variant of NTRU [32] is secure under the hardness assumption of ring-\(\mathsf {LWE}\), but the ring-\(\mathsf {LWE}\) problem only has a reduction from a lattice problem with ring structure, not from the standard lattice problems.

  2. 2.

    Hence, the parameter choices of [25] are irrelevant of this comparison. Note that the chosen parameter sets in [25] do not achieve the claimed security anymore, due to many recent attacks in the literatures [3,4,5].

  3. 3.

    After approving it, Albrecht’s combinatorial strategy for sparse secrets in [3] can be exploited naturally: As far as we know, the adjusted dual attack in [3] is the best attack for \(\mathsf {LWR}\) using sparse signed binary secrets.

  4. 4.

    We used the lwe-estimator [2] reported on July 6th, 2017. We remark that one can find a guideline for attacking the \(\mathsf {LWE}\) problem in [5].

  5. 5.

    Since the data type of each component of public key is \(\texttt {uint16\_t}\) and the modulus q is \(2^{11}\), our public key can be compressed by a factor 16/11.

References

  1. Alamati, N., Peikert, C.: Three’s compromised too: circular insecurity for any cycle length from (Ring-)LWE. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 659–680. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_23

    Chapter  Google Scholar 

  2. Albrecht, M.R.: A Sage Module for estimating the concrete security of learning with errors instances (2017). https://bitbucket.org/malb/lwe-estimator

  3. Albrecht, M.R.: On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 103–129. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_4

    Chapter  Google Scholar 

  4. Albrecht, M.R., Göpfert, F., Virdia, F., Wunderer, T.: Revisiting the expected cost of solving uSVP and applications to LWE. Cryptology ePrint Archive, Report 2017/815 (2017, accepted). http://eprint.iacr.org/2017/815. ASIACRYPT 2017

  5. Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169–203 (2015)

    Article  MathSciNet  Google Scholar 

  6. Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange—A new hope. In: 25th USENIX Security Symposium, USENIX Security 2016, Austin, TX, pp. 327–343. USENIX Association, August 2016

    Google Scholar 

  7. 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 

  8. 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 

  9. Bogdanov, A., Guo, S., Masny, D., Richelson, S., Rosen, A.: On the hardness of learning with rounding over small modulus. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9562, pp. 209–224. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49096-9_9

    Chapter  MATH  Google Scholar 

  10. Bos, J., et al.: Frodo: take off the ring! Practical, quantum-secure key exchange from LWE. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS 2016, pp. 1006–1018. ACM, New York (2016)

    Google Scholar 

  11. Bos, J., et al.: CRYSTALS - Kyber: a CCA-secure module-lattice-based KEM. Cryptology ePrint Archive, Report 2017/634 (2017). http://eprint.iacr.org/2017/634

  12. Bos, J.W., Costello, C., Naehrig, M., Stebila, D.: Post-quantum key exchange for the TLS protocol from the ring learning with errors problem. In: 2015 IEEE Symposium on Security and Privacy, pp. 553–570. IEEE (2015)

    Google Scholar 

  13. Brakerski, Z., Gentry, C., Halevi, S.: Packed ciphertexts in LWE-based homomorphic encryption. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 1–13. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36362-7_1

    Chapter  Google Scholar 

  14. Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 575–584. ACM (2013)

    Google Scholar 

  15. Cheon, J.H., Han, K., Kim, J., Lee, C., Son, Y.: A practical post-quantum public-key cryptosystem based on LWE. In: Hong, S., Park, J.H. (eds.) ICISC 2016. LNCS, vol. 10157, pp. 51–74. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-53177-9_3. https://eprint.iacr.org

    Chapter  Google Scholar 

  16. Cheon, J.H., Kim, D., Lee, J., Song, Y.: Lizard: cut off the tail! Practical post-quantum public-key encryption from LWE and LWR. Cryptology ePrint Archive, Report 2016/1126 (2016). https://eprint.iacr.org/2016/1126

  17. Ding, J., Xie, X., Lin, X.: A simple provably secure key exchange scheme based on the learning with errors problem. IACR Cryptology ePrint Archive, 2012:688 (2012)

    Google Scholar 

  18. Etzel, M., Whyte, W., Zhang, Z.: An open source of NTRU (2016). https://github.com/NTRUOpenSourceProject/ntru-crypto

  19. Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 537–554. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_34

    Chapter  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Google Scholar 

  22. Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054868

    Chapter  Google Scholar 

  23. Hofheinz, D., Hövelmanns, K., Kiltz, E.: A modular analysis of the Fujisaki-Okamoto transformation. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10677, pp. 341–371. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_12

    Chapter  MATH  Google Scholar 

  24. Howgrave-Graham, N., Silverman, J.H., Singer, A., Whyte, W.: NAEP: provable security in the presence of decryption failures. Cryptology ePrint Archive, Report 2003/172 (2003). http://eprint.iacr.org/2003/172

  25. Lindner, R., Peikert, C.: Better key sizes (and attacks) for LWE-based encryption. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 319–339. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19074-2_21

    Chapter  Google Scholar 

  26. National Institute of Standards and Technology: Proposed submission requirements and evaluation criteria for the post-quantum cryptography standardization process (2016). http://csrc.nist.gov/groups/ST/post-quantum-crypto/documents/call-for-proposals-draft-aug-2016.pdf

  27. Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pp. 333–342. ACM (2009)

    Google Scholar 

  28. Peikert, C.: Lattice cryptography for the internet. In: Mosca, M. (ed.) PQCrypto 2014. LNCS, vol. 8772, pp. 197–219. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11659-4_12

    Chapter  MATH  Google Scholar 

  29. 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 

  30. Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 187–196. ACM (2008)

    Google Scholar 

  31. 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 

  32. Stehlé, D., Steinfeld, R.: Making NTRU as secure as worst-case problems over ideal lattices. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 27–47. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_4

    Chapter  Google Scholar 

  33. Targhi, E.E., Unruh, D.: Quantum security of the Fujisaki-Okamoto and OAEP transforms. Cryptology ePrint Archive, Report 2015/1210 (2015). http://eprint.iacr.org/2015/1210

Download references

Acknowledgments

We would like to thank Martin Albrecht and Fernando Virdia for valuable discussions on parameter selection. We would also like to thank Leo Ducas, Peter Schwabe, Tsuyoshi Takagi, Yuntao Wang and anonymous SCN 2018 reviewers for their useful comments.

Author information

Authors and Affiliations

  1. Seoul National University, Seoul, Republic of Korea

    Jung Hee Cheon, Duhyeong Kim & Joohee Lee

  2. University of California, San Diego, USA

    Yongsoo Song

Authors
  1. Jung Hee Cheon
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Duhyeong Kim
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Joohee Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Yongsoo Song
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Joohee Lee .

Editor information

Editors and Affiliations

  1. University of Catania, Catania, Italy

    Dario Catalano

  2. University of Salerno, Fisciano, Italy

    Roberto De Prisco

A IND-CCA Variant of Lizard

A IND-CCA Variant of Lizard

In this section, we present CCA-secure encryption scheme, say CCALizard, achieved by applying a variant of Fujisaki-Okamoto (FO) transformation [19, 20, 23, 33] to our Lizard encryption scheme. More precisely, we first convert Lizard into IND-CCA Key Encapsulation Mechanism (KEM) applying the transformation in [23], and then combine it with a (one-time) CCA-secure symmetric encryption scheme.

\(\mathsf {G}:{\mathbb {Z}}_t^{\ell }\rightarrow B_{m,h_r}\), \(\mathsf {H}:{\mathbb {Z}}_t^{\ell }\rightarrow \{0,1\}^d \), \(\mathsf {H'}:{\mathbb {Z}}_t^{\ell }\rightarrow {\mathbb {Z}}_t^{\ell }\) are the hash functions, where \(\{0,1\}^d\) is the plaintext space for CCALizard. Here, \(\mathsf {Lizard.Enc}_\mathsf {pk}(\delta ; \mathbf {v})\) denotes the encryption of \(\delta \) with the random vector \(\mathbf {v}\), i.e., the output of \(\mathsf {Lizard.Enc}_\mathsf {pk}(\delta ; \mathbf {v})\) is (\(\left\lfloor {(p/q)\cdot A^T\mathbf {v}}\right\rceil \), \(\left\lfloor {(p/t)\cdot \mathbf {\delta }+(p/q)\cdot B^T\mathbf {v}}\right\rceil \)).

CCALizard consists of three algorithms (\(\mathsf {CCALizard.KeyGen}\), \(\mathsf {CCALizard.Enc}\), \(\mathsf {CCALizard.Dec}\)). \(\mathsf {CCALizard.KeyGen}\) is the same as \(\mathsf {Lizard.KeyGen}\), and \(\mathsf {CCALizard.Enc}\) and \(\mathsf {CCALizard.Dec}\) are as follows:

  • \(\mathsf {CCALizard.Enc}_\mathsf {pk}(\mathbf {m} \in \{0,1\}^{d})\):

    • Choose \(\delta \leftarrow {\mathbb {Z}}_t^{\ell }\).

    • Compute a tuple of vectors \(\mathbf {c}_1 := \mathsf {H}(\delta )\oplus \mathbf {m}\), \(\mathbf {c}_2 :=\mathsf {Lizard.Enc}_\mathsf {pk}(\delta ; \mathsf {G}(\delta ))\), \(\mathbf {c}_3 := \mathsf {H}'(\delta )\).

    • Output the ciphertext \(\mathbf {c} = (\mathbf {c}_1,\mathbf {c}_2,\mathbf {c}_3)\in \{0,1\}^{d}\times \mathbb {Z}_p^{n+\ell }\times {\mathbb {Z}}_t^{\ell }\).

  • \(\mathsf {CCALizard.Dec}_\mathsf {sk}(\mathbf {c})\):

    • Parse \(\mathbf {c}\) into \(\mathbf {c} = (\mathbf {c}_1,\mathbf {c}_2,\mathbf {c}_3)\in \{0,1\}^{d}\times \mathbb {Z}_p^{n+\ell }\times {\mathbb {Z}}_t^{\ell }\).

    • Compute \(\delta ' \leftarrow \mathsf {Lizard.Dec}_\mathsf {sk}(\mathbf {c}_2)\) and \(\mathbf {v}'\leftarrow \mathsf {G}(\delta ')\).

    • If \((\mathbf {c}_2, \mathbf {c}_3) = (\mathsf {Lizard.Enc}_\mathsf {pk}(\delta '; \mathbf {v}'), \mathsf {H}'(\delta '))\), then compute and output \(\mathbf {m}'\leftarrow \mathsf {H}(\delta ')\oplus \mathbf {c}_1\).

    • Otherwise, output \(\perp \).

Correctness. If Lizard is correct with the probability \(1-\epsilon \), then CCALizard is correct except with the probability \(1-\epsilon \) in the (quantum) random oracle model [23].

Security. CCALizard achieves tight IND-CCA security in the random oracle model, and non-tight IND-CCA security in the quantum random oracle model. For IND-CCA security in ROM, the hash function \(H'\) and the hash value \(\mathbf {d}\) is not necessary.

Theorem 3

([23], Theorems 3.2 and 3.3). For any IND-CCA adversary \(\mathcal {B}\) on CCALizard issuing at most \(q_D\) queries to the decryption oracle, \(q_G\) queries to the random oracle \(\mathsf {G}\), and \(q_H\) queries to the random oracle \(\mathsf {H}\), there exists an IND-CPA adversary \(\mathcal {A}\) on Lizard such that

$$\begin{aligned}&{{\textsf {\textit{Adv}}}}_{\mathsf {CCALizard}}^{{{\textsf {\textit{CCA}}}}}(\mathcal {B})\le q_G\cdot \epsilon +\frac{q_H}{2^{\omega (\log \lambda )}} +\frac{2q_G + 1}{t^\ell } + 3 \cdot {{\textsf {\textit{Adv}}}}_{{{\textsf {\textit{Lizard}}}}}^{{{\textsf {\textit{CPA}}}}}(\mathcal {A}) \end{aligned}$$

where \(\lambda \) is a security parameter and \(\epsilon \) is a decryption failure probability of Lizard and CCALizard.

Theorem 4

([23], Theorems 4.4 and 4.5). For any IND-CCA quantum adversary \(\mathcal {B}\) on CCALizard issuing at most \(q_D\) (classical) queries to the decryption oracle, \(q_G\) queries to the quantum random oracle \(\mathsf {G}\), \(q_H\) queries to the quantum random oracle \(\mathsf {H}\), and \(q_{H'}\) queries to the quantum random oracle \(\mathsf {H}'\), there exists an IND-CPA quantum adversary \(\mathcal {A}\) on Lizard such that

$$\begin{aligned}&{{\textsf {\textit{Adv}}}}_{\mathsf {CCALizard}}^{{{\textsf {\textit{CCA}}}}}(\mathcal {B})\le \small {(q_H + 2q_{H'})\sqrt{8\epsilon (q_G+1)^2 + (1 + 2q_G)\sqrt{{{\textsf {\textit{Adv}}}}_{{{\textsf {\textit{Lizard}}}}}^{{{\textsf {\textit{CPA}}}}}(\mathcal {A})}}} \end{aligned}$$

where \(\epsilon \) is a decryption failure probability of Lizard and CCALizard.

Parameters for CCALizard. We use the recommended parameters in Table 2 for CCALizard and set \(t=2\), \(\ell = d = 256\).

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Cheon, J.H., Kim, D., Lee, J., Song, Y. (2018). Lizard: Cut Off the Tail! A Practical Post-quantum Public-Key Encryption from LWE and LWR. In: Catalano, D., De Prisco, R. (eds) Security and Cryptography for Networks. SCN 2018. Lecture Notes in Computer Science(), vol 11035. Springer, Cham. https://doi.org/10.1007/978-3-319-98113-0_9

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-98113-0_9

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-98112-3

  • Online ISBN: 978-3-319-98113-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation