Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Fine-Grained Non-interactive Key-Exchange: Constructions and Lower Bounds

  • Conference paper
  • First Online:

Abstract

In this work, we initiate a study ofK-NIKE protocols in thefine-grained setting, in which there is apolynomial gap between the running time of the honest parties and that of the adversary. Our goal is to show the possibility, or impossibility, of basing such protocols on weaker assumptions than those ofK-NIKE for\(K \ge 3\). Our contribution is threefold.

  • We show that random oracles can be used to obtain fine-grainedK-NIKE protocols forevery constantK. In particular, we show how to generalize Merkle’s two-party protocol toK parties in such a way that the honest parties askn queries each, while the adversary needs\(n^{K/(K-1)}\) queries to the random oracle to find the key.

  • We then improve the security by further using algebraic structures, while avoiding pairings. In particular, we show that there is a 4-party NIKE in Shoup’s generic group model with aquadratic gap between the number of queries by the honest parties vs. that of the adversary.

  • Finally, we show a limitation of using purely algebraic methods for obtaining 3-NIKE. In particular, we show that anyn-query 3-NIKE protocol in Maurer’s generic group model can be broken by a\(O(n^2)\)-query attacker. Maurer’s GGM is more limited compared with Shoup’s both for the parties and the adversary, as there are no explicit labels for the group elements. Despite being more limited, this model still captures the Diffie Hellman protocol. Prior to our work, it was open to break 3-NIKE protocols in Maurer’s model withany polynomial number of queries.

G. Couteau—Supported by the French Agence Nationale de la Recherche (ANR), under grant ANR-20-CE39-0001 (project SCENE), and by the France 2030 ANR Project ANR22-PECY-003 SecureCompute.

M. Mahmoody—Supported by NSF under grants CCF-1910681 and CNS1936799.

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

Access this chapter

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 12583
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 15729
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

Similar content being viewed by others

Notes

  1. 1.

    Our proof is for\(K=3\) which will directly imply the negative result for any\(K\ge 3\).

  2. 2.

    The seminal paper of Pollard describes two algorithms for solving discrete logarithms. The second, lesser known algorithm, usually calledPollard’s kangaroo algorithm, solves discrete logarithms with exponents over intervals [u, v] in time\(\sqrt{v-u}\).

  3. 3.

    This writing could be due to a direct write operation or deriving the group element from other array elements (in which case the parties do not actually have direct access to the group element itself). However, note that if the group elements are eventually encoded, a la Shoup’s model, the encoding of the group element will be accessible to the parties.

  4. 4.

    One special case is that\(\textsf{Arr}_\textsf{P}[1]=1\), but this is not necessary in this Lemma17.

References

  1. Brzuska, C., Couteau, G.: On building fine-grained one-way functions from strong average-case hardness. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part II. LNCS, vol. 13276, pp. 584–613. Springer, Heidelberg (2022).https://doi.org/10.1007/978-3-031-07085-3_20

  2. Biham, E., Goren, Y.J., Ishai, Y.: Basing weak public-key cryptography on strong one-way functions. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 55–72. Springer, Heidelberg (2008).https://doi.org/10.1007/978-3-540-78524-8_4

    Chapter MATH  Google Scholar 

  3. Brassard, G., Høyer, P., Kalach, K., Kaplan, M., Laplante, S., Salvail, L.: Merkle puzzles in a quantum world. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 391–410. Springer, Heidelberg (2011).https://doi.org/10.1007/978-3-642-22792-9_22

    Chapter MATH  Google Scholar 

  4. Brakerski, Z., Jain, A., Komargodski, I., Passelègue, A., Wichs, D.: Non-trivial witness encryption and null-iO from standard assumptions. In: Catalano, D., De Prisco, R. (eds.) SCN 2018. LNCS, vol. 11035, pp. 425–441. Springer, Cham (2018).https://doi.org/10.1007/978-3-319-98113-0_23

    Chapter MATH  Google Scholar 

  5. Barak, B., Mahmoody-Ghidary, M.: Merkle puzzles are optimal — anO(n2)-query attack on any key exchange from a random oracle. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 374–390. Springer, Heidelberg (2009).https://doi.org/10.1007/978-3-642-03356-8_22

    Chapter  Google Scholar 

  6. Barak, B., Mahmoody-Ghidary, M.: Merkle’s key agreement protocol is optimal: an\(O(n^2)\) attack on any key agreement from random oracles. J. Cryptol.30(3), 699–734 (2017)

    Article MATH  Google Scholar 

  7. Barak, B., Mahmoody-Ghidary, M.: Lower bounds on signatures from symmetric primitives. In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), pp. 680–688. IEEE (2007)

    Google Scholar 

  8. Ball, M., Rosen, A., Sabin, M., Vasudevan, P.N.: Average-case fine-grained hardness. In: 49th ACM STOC, pp. 483–496. ACM Press, June 2017

    Google Scholar 

  9. Ball, M., Rosen, A., Sabin, M., Vasudevan, P.N.: Proofs of work from worst-case assumptions. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part I. LNCS, vol. 10991, pp. 789–819. Springer, Cham (2018).https://doi.org/10.1007/978-3-319-96884-1_26

    Chapter  Google Scholar 

  10. Boneh, D., Zhandry, M.: Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 480–499. Springer, Heidelberg (2014).https://doi.org/10.1007/978-3-662-44371-2_27

    Chapter  Google Scholar 

  11. Campanelli, M., Gennaro, R.: Fine-grained secure computation. In: Beimel, A., Dziembowski, S. (eds.) TCC 2018, Part II. LNCS, vol. 11240, pp. 66–97. Springer, Cham (2018).https://doi.org/10.1007/978-3-030-03810-6_3

    Chapter  Google Scholar 

  12. Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inf. Theory22(6), 644–654 (1976)

    Article MathSciNet MATH  Google Scholar 

  13. Dinur, I., Hasson, B.: Distributed Merkle’s puzzles. In: Nissim, K., Waters, B. (eds.) TCC 2021, Part II. LNCS, vol. 13043, pp. 310–332. Springer, Cham (2021).https://doi.org/10.1007/978-3-030-90453-1_11

    Chapter  Google Scholar 

  14. Döttling, N., Hartmann, D., Hofheinz, D., Kiltz, E., Schäge, S., Ursu, B.: On the impossibility of purely algebraic signatures. In: Nissim, K., Waters, B. (eds.) TCC 2021, Part III. LNCS, vol. 13044, pp. 317–349. Springer, Cham (2021).https://doi.org/10.1007/978-3-030-90456-2_11

    Chapter MATH  Google Scholar 

  15. Degwekar, Akshay, Vaikuntanathan, Vinod, Vasudevan, Prashant Nalini: Fine-Grained Cryptography. In: Robshaw, Matthew, Katz, Jonathan (eds.) CRYPTO 2016, Part III. LNCS, vol. 9816, pp. 533–562. Springer, Heidelberg (2016).https://doi.org/10.1007/978-3-662-53015-3_19

    Chapter  Google Scholar 

  16. Egashira, S., Wang, Y., Tanaka, K.: Fine-grained cryptography revisited. J. Cryptol.34(3), 23 (2021)

    Article MathSciNet MATH  Google Scholar 

  17. Freire, E.S.V., Hofheinz, D., Kiltz, E., Paterson, K.G.: Non-Interactive Key Exchange. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 254–271. Springer, Heidelberg (2013).https://doi.org/10.1007/978-3-642-36362-7_17

    Chapter MATH  Google Scholar 

  18. G. Fuchsbauer, E. Kiltz, and J. Loss. The algebraic group model and its applications. Cryptology ePrint Archive, Paper 2017/620, 2017.https://eprint.iacr.org/2017/620

  19. Guo, S., Kamath, P., Rosen, A., Sotiraki, K.: Limits on the efficiency of (ring) LWE-based non-interactive key exchange. J. Cryptol.35(1), 1 (2022)

    Article MathSciNet MATH  Google Scholar 

  20. Joux, Antoine: A one round protocol for tripartite Diffie–Hellman. In: Bosma, Wieb (ed.) ANTS 2000. LNCS, vol. 1838, pp. 385–393. Springer, Heidelberg (2000).https://doi.org/10.1007/10722028_23

    Chapter  Google Scholar 

  21. LaVigne, Rio, Lincoln, Andrea, Vassilevska Williams, Virginia: Public-key cryptography in the fine-grained setting. In: Boldyreva, Alexandra, Micciancio, Daniele (eds.) CRYPTO 2019, Part III. LNCS, vol. 11694, pp. 605–635. Springer, Cham (2019).https://doi.org/10.1007/978-3-030-26954-8_20

    Chapter MATH  Google Scholar 

  22. Maurer, Ueli: Abstract models of computation in cryptography. In: Smart, Nigel P.. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 1–12. Springer, Heidelberg (2005).https://doi.org/10.1007/11586821_1

    Chapter MATH  Google Scholar 

  23. Merkle, R.: C.s. 244 project proposal. Facsimile (1974).http://www.merkle.com/1974

  24. Merkle, R.C.: Secure communications over insecure channels. Commun. ACM21(4), 294–299 (1978)

    Article MATH  Google Scholar 

  25. Pollard, J.M.: A monte Carlo method for factorization. BIT15, 331–334 (1975).http://cr.yp.to/bib/entries.html#1975/pollard

  26. Shanks, D.: Class number, a theory of factorization, and genera. In: Proceedings of Symposium Mathematical Society, pp. 41–440 (1971)

    Google Scholar 

  27. Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 256–266. Springer, Heidelberg (1997).https://doi.org/10.1007/3-540-69053-0_18

    Chapter  Google Scholar 

  28. Wang, Y., Pan, J.: Non-interactive zero-knowledge proofs with fine-grained security. In: EUROCRYPT 2022, Part II. LNCS, vol. 13276, pp. 305–335. Springer, Heidelberg (2022).https://doi.org/10.1007/978-3-031-07085-3_11

  29. Zhandry, M.: To label, or not to label (in generic groups). In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13509, pp. 66–96. Springer, Cham (2022).https://doi.org/10.1007/978-3-031-15982-4_3

Download references

Author information

Authors and Affiliations

  1. University of Virginia, Charlottesville, USA

    Abtin Afshar & Mohammad Mahmoody

  2. CNRS, IRIF, Université Paris Cité, Paris, France

    Geoffroy Couteau

  3. University of Texas at Austin, Austin, USA

    Elahe Sadeghi

Authors
  1. Abtin Afshar

    You can also search for this author inPubMed Google Scholar

  2. Geoffroy Couteau

    You can also search for this author inPubMed Google Scholar

  3. Mohammad Mahmoody

    You can also search for this author inPubMed Google Scholar

  4. Elahe Sadeghi

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toElahe Sadeghi.

Editor information

Editors and Affiliations

  1. Bar-Ilan University, Ramat Gan, Israel

    Carmit Hazay

  2. Simula UiB, Bergen, Norway

    Martijn Stam

Rights and permissions

Copyright information

© 2023 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Afshar, A., Couteau, G., Mahmoody, M., Sadeghi, E. (2023). Fine-Grained Non-interactive Key-Exchange: Constructions and Lower Bounds. In: Hazay, C., Stam, M. (eds) Advances in Cryptology – EUROCRYPT 2023. EUROCRYPT 2023. Lecture Notes in Computer Science, vol 14004. Springer, Cham. https://doi.org/10.1007/978-3-031-30545-0_3

Download citation

Publish with us

Societies and partnerships

Access this chapter

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 12583
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 15729
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

[8]ページ先頭
©2009-2025 Movatter.jp