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

Tighter Security Proofs for Post-quantum Key Encapsulation Mechanism in the Multi-challenge Setting

  • Conference paper
  • First Online:
Cryptology and Network Security (CANS 2019)

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

Included in the following conference series:

  • 926 Accesses

Abstract

Due to the threat posed by quantum computers, a series of works investigate the security of cryptographic schemes in the quantum-accessible random oracle model (QROM) where the adversary can query the random oracle in superposition. In this paper, we present tighter security proofs of a generic transformations for key encapsulation mechanism (KEM) in the QROM in the multi-challenge setting, where the reduction loss is independent of the number of challenge ciphertexts. In particular, we introduce the notion of multi-challenge OW-CPA (mOW-CPA) security, which captures the one-wayness of the underlying public key encryption (PKE) under chosen plaintext attack in the multi-challenge setting. We show that the multi-challenge IND-CCA (mIND-CCA) security of KEM can be reduced to the mOW-CPA security of the underlying PKE scheme (with \(\delta \)-correctness) using transformation. Then we prove that the mOW-CPA security can be tightly reduced to the underlying post-quantum assumptions by showing the tight mOW-CPA security of two concrete PKE schemes based on LWE, where one is the Regev’s PKE scheme and the other is a variant of Frodo.

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.

    m (without m) means the ephemeral key \( K=H(m) \) (\(K =H(m,c)\)), (\( \bot \)) means implicit (explicit) rejection in decryption algorithm, and Q means adding additional hash to the ciphertext in the QROM.

  2. 2.

    \(\mathbf {B}_{\lambda }\) is the Bernoulli distribution. I.e., \(\Pr [g(x) = 1]=\lambda \) and \(\Pr [g(x) = 0]=1-\lambda \).

  3. 3.

    The proof of OW2H with redundant oracle can be found in Lemma 3 of [19].

References

  1. Abe, M., David, B., Kohlweiss, M., Nishimaki, R., Ohkubo, M.: Tagged one-time signatures: tight security and optimal tag size. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 312–331. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36362-7_20

    Chapter  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. Ambainis, A., Hamburg, M., Unruh, D.: Quantum security proofs using semi-classical oracles. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 269–295. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_10. https://eprint.iacr.org/2018/904

    Chapter  Google Scholar 

  4. Ambainis, A., Rosmanis, A., Unruh, D.: Quantum attacks on classical proof systems: the hardness of quantum rewinding. In: 55th Annual Symposium on Foundations of Computer Science, pp. 474–483. IEEE (2014)

    Google Scholar 

  5. Bellare, M., Boldyreva, A., Micali, S.: Public-key encryption in a multi-user setting: security proofs and improvements. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 259–274. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45539-6_18

    Chapter  Google Scholar 

  6. Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: CCS 1993, pp. 62–73. ACM (1993)

    Google Scholar 

  7. Blazy, O., Kiltz, E., Pan, J.: (Hierarchical) identity-based encryption from affine message authentication. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 408–425. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_23

    Chapter  Google Scholar 

  8. Blazy, O., Kakvi, S.A., Kiltz, E., Pan, J.: Tightly-secure signatures from chameleon hash functions. In: Katz, J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 256–279. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46447-2_12

    Chapter  Google Scholar 

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

  10. Bos, J., et al.: Frodo: take off the ring! Practical, quantum-secure key exchange from LWE. In: CCS 2016, pp. 1006–1018. ACM (2016)

    Google Scholar 

  11. Chen, J., Wee, H.: Fully, (almost) tightly secure IBE and dual system groups. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 435–460. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_25

    Chapter  Google Scholar 

  12. Dodis, Y., Reyzin, L., Smith, A.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 523–540. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_31

    Chapter  Google Scholar 

  13. Gay, R., Hofheinz, D., Kiltz, E., Wee, H.: Tightly CCA-secure encryption without pairings. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 1–27. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_1

    Chapter  Google Scholar 

  14. Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC 2008, pp. 197–206. ACM (2008)

    Google Scholar 

  15. Goldwasser, S., Kalai, Y., Peikert, C., Vaikuntanathan, V.: Robustness of the learning with errors assumption. In: ICS 2010, pp. 230–240 (2010)

    Google Scholar 

  16. Hofheinz, D., Jager, T.: Tightly secure signatures and public-key encryption. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 590–607. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_35

    Chapter  Google Scholar 

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

  18. Hofheinz, D., Koch, J., Striecks, C.: Identity-based encryption with (almost) tight security in the multi-instance, multi-ciphertext setting. In: Katz, J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 799–822. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46447-2_36

    Chapter  Google Scholar 

  19. Jiang, H., Zhang, Z., Chen, L., Wang, H., Ma, Z.: IND-CCA-secure key encapsulation mechanism in the quantum random oracle model, revisited. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10993, pp. 96–125. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_4

    Chapter  Google Scholar 

  20. Katsumata, S., Yamada, S., Yamakawa, T.: Tighter security proofs for GPV-IBE in the quantum random oracle model. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11273, pp. 253–282. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03329-3_9

    Chapter  MATH  Google Scholar 

  21. Libert, B., Joye, M., Yung, M., Peters, T.: Concise multi-challenge CCA-secure encryption and signatures with almost tight security. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 1–21. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45608-8_1

    Chapter  Google Scholar 

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

  23. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56, 34 (2009)

    Article  MathSciNet  Google Scholar 

  24. Renner, R., Wolf, S.: Smooth Renyi entropy and applications. In: ISIT 2004, pp. 233–233. IEEE (2004)

    Google Scholar 

  25. Saito, T., Xagawa, K., Yamakawa, T.: Tightly-secure key-encapsulation mechanism in the quantum random oracle model. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10822, pp. 520–551. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_17

    Chapter  MATH  Google Scholar 

  26. Targhi, E.E., Unruh, D.: Post-quantum security of the Fujisaki-Okamoto and OAEP transforms. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9986, pp. 192–216. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53644-5_8

    Chapter  MATH  Google Scholar 

  27. Unruh, D.: Revocable quantum timed-release encryption. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 129–146. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_8

    Chapter  Google Scholar 

  28. Wei, P., Wang, W., Zhu, B., Yiu, S.M.: Tightly-secure encryption in the multi-user, multi-challenge setting with improved efficiency. In: Pieprzyk, J., Suriadi, S. (eds.) ACISP 2017. LNCS, vol. 10342, pp. 3–22. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-60055-0_1

    Chapter  Google Scholar 

  29. Zhandry, M.: Secure identity-based encryption in the quantum random oracle model. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 758–775. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_44

    Chapter  MATH  Google Scholar 

Download references

Acknowledgements

We would like to thank the anonymous reviewers for their helpful comments. Zhengyu Zhang and Puwen Wei were supported by the National Natural Science Foundation of China (No. 61502276). Haiyang Xue was supported by the National Natural Science Foundation of China (No. 61602473) and the National Cryptography Development Fund (No. MMJJ20170116).

Author information

Authors and Affiliations

  1. School of Cyber Science and Technology, Shandong University, Qingdao, China

    Puwen Wei

  2. Key Laboratory of Cryptologic Technology and Information Security, Shandong University, Ministry of Education, Jinan, China

    Zhengyu Zhang & Puwen Wei

  3. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China

    Haiyang Xue

Authors
  1. Zhengyu Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Puwen Wei
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Haiyang Xue
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Puwen Wei .

Editor information

Editors and Affiliations

  1. Fujian Normal University, Fuzhou, China

    Yi Mu

  2. Singapore Management University, Singapore, Singapore

    Robert H. Deng

  3. Fujian Normal University, Fuzhou, China

    Xinyi Huang

A Proof of Lemma 9

A Proof of Lemma 9

Proof

We have

$$\begin{aligned} \begin{aligned}&|\mathbf {E}_{j\leftarrow J_1}[2^{-H_{\infty }(Y|J_1=j)}]-\mathbf {E}_{j\leftarrow J_2}[2^{-H_{\infty }(Y|J_2=j)}]|\\ =&|\sum _{j}\Pr [J_1=j]2^{-H_{\infty }(Y|j)}-\sum _{j}\Pr [J_2=j]2^{-H_{\infty }(Y|j)}|\\ \le&\sum _{j}|\Pr [J_1=j]-\Pr [J_2=j]|2^{-H_{\infty }(Y|j)} \le \varepsilon . \end{aligned} \end{aligned}$$
(9)

The last inequality follows from \(\varDelta (J_1,J_2)\le \varepsilon /2\) and the \( 2^{-H_{\infty }(Y|j)} \le 1\). Hence

$$\begin{aligned} \begin{aligned}&|\hat{H}_{\infty }(Y|J_1)-\hat{H}_{\infty }(Y|J_2)|\\ =&|-\log \mathbf {E}_{j\leftarrow J_1}[2^{-H_{\infty }(Y|J_1=j)}]+\log \mathbf {E}_{j\leftarrow J_2}[2^{-H_{\infty }(Y|J_2=j)}]|\\ =&|\log \frac{\mathbf {E}_{j\leftarrow J_2}[2^{-H_{\infty }(Y|J_2=j)}]}{\mathbf {E}_{j\leftarrow J_1}[2^{-H_{\infty }(Y|J_1=j)}]}| \le \log (1+ \frac{\varepsilon }{\mathbf {E}_{j\leftarrow J_1}[2^{-H_{\infty }(Y|J_1=j)}]})\\ \le&\frac{\varepsilon }{\mathbf {E}_{j\leftarrow J_1}[2^{-H_{\infty }(Y|J_1=j)}]} +1 = \varepsilon 2^{\hat{H}_{\infty }(Y|J_1)}+1. \end{aligned} \end{aligned}$$
(10)

For the last inequality we use the fact that \( \log (x+1)\le x+1\).

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

Zhang, Z., Wei, P., Xue, H. (2019). Tighter Security Proofs for Post-quantum Key Encapsulation Mechanism in the Multi-challenge Setting. In: Mu, Y., Deng, R., Huang, X. (eds) Cryptology and Network Security. CANS 2019. Lecture Notes in Computer Science(), vol 11829. Springer, Cham. https://doi.org/10.1007/978-3-030-31578-8_8

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-31578-8_8

  • Published:

  • Publisher Name: Springer, Cham

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

  • Online ISBN: 978-3-030-31578-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation