SpringerLink
Log in

Composable Long-Term Security with Rewinding

  • Conference paper
  • First Online:
Theory of Cryptography (TCC 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14372))

Included in the following conference series:

  • 307 Accesses

Abstract

We circumvent these impossibility results with new techniques, enabling rewinding-based simulation in a way that universal composability is achieved. This allows us to construct a long-term-secure composable commitment scheme in the CRS-hybrid model, which is provably impossible in the notion of Müller-Quade and Unruh. We base our construction on a statistically hiding commitment scheme in the CRS-hybrid model with CCA-like properties. To provide a CCA oracle, we cannot rely on super-polynomial extraction techniques and instead extract the value committed to via rewinding. To this end, we incorporate rewinding-based commitment extraction into the UC framework via a helper in analogy to Canetti, Lin and Pass (FOCS 2010), allowing both adversary and environment to extract statistically hiding commitments.

Our new framework provides the first setting in which a commitment scheme that is both statistically hiding and universally composable can be constructed from standard polynomial-time hardness assumptions and a CRS only. We also prove that our CCA oracle is k-robust extractable. This asserts that extraction is possible without rewinding a concurrently executed k-round protocol. Consequently any k-round (standard) UC-secure protocol remains secure in the presence of our helper.

Finally, we prove that building long-term-secure oblivious transfer (and thus general two-party computations) from long-term-revealing setups remains impossible in our setting. Still, our long-term-secure commitment scheme suffices for natural applications, such as long-term secure and composable (commit-and-prove) zero-knowledge arguments of knowledge.

M. Klooß—Research was conducted at Karlsruhe Institute of Technology.

For the full version [5], see https://eprint.iacr.org/2023/363.

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
EUR 32.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 69.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 89.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** 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.

    Informally, a functionality \(\mathcal {F} \) is long-term revealing for party P if the communication between \(\mathcal {F} \) and P can be (inefficiently) computed from the communication between \(\mathcal {F} \) and all entities except P.

  2. 2.

    Here, \(\mathcal {A} \) must not modify the security parameter, i.e. \(1^\kappa \) is the same as \(\mathcal {A} \)’s input.

  3. 3.

    We note that \(\mathcal {O}_{\textsf{CCA}} \) needs to process the extracted values and present \(\mathcal {A} \) with the expected game interface. Hence, formally, an adversary \(\mathcal {A} _{\mathcal {O}_{\textsf{CCA}}}\) is defined which handles this, and \(\textsf{recurse}\) is invoked for \(\mathcal {A} _{\mathcal {O}_{\textsf{CCA}}}\) (not \(\mathcal {A} \)).

  4. 4.

    It is easy to see that a \(2\kappa \)-fold parallel composition of \(\textsf{TRAPCOM}'\) is still a trapdoor commitment (w.r.t. \(\mathcal {O}_{\textsf{CCA}} \)). And switching \(\textrm{E}_0\) to \(\textrm{E}_1\) is exactly a switch from parallel real to parallel trapdoor commitments. Moreover, while the TDC experiment \(\textrm{E}_b\) has more than k moves, it is only \(O(1)\) more. So, it is clear that it is still \(O(k)\) rounds, and hence \(O(k)\)-robust COI and \(O(k)\)-robust pseudo-PPT are applicable.

  5. 5.

    Either m is the last message of the commit phase step 1. Or one lets \((\texttt {Other} , s, m)\) finish that step and sets \(m = \bot \) here. Either way, the message is a “start marker” initiating the first challenge. The choice does not affect the rewinding schedule.

  6. 6.

    Note that \(\textsf{f}\) could be defined as a function of \(\textrm{id}\), so this is well-defined.

  7. 7.

    Expected run-time stems from extraction of the AoK via rewinding. It can be traded for only one rewind, hence strict PPT, but with a quadratic loss in advantage.

  8. 8.

    Resampling challenges uniformly with replacement, the probability of a collision is 1/n if there are n accepting challenges, and \(n/2^{\kappa }\) is the probability that the verifier accepted the AoK (and extraction was started). Thus \(\max _{n = 1}^{2^\kappa } 2^{-\kappa } n/n = 2^{-\kappa }\) is an upper bound on failure.

  9. 9.

    If \(F_1 \vee F_2\) occurs before \(F_{\ne }\), the modified experiment immediately outputs 0, so \(F_{\ne }\) will not occur and this case is irrelevant.

  10. 10.

    Even though the original work [8] has been superseded by [2], we continue to use the conventions of [8]. We discuss the reasons for this decisions as well as the issues raised (and fixed) in [2] in the full version [5].

  11. 11.

    We restate the definition of \(\mathcal {H}\)-aided environments due to [12]: a) \(\mathcal {Z} \) invokes a single instance of \(\mathcal {H}\) immediately after invoking the adversary. b) As soon as a party (i.e. an ITI) P is corrupted (i.e. P receives a corrupted message), \(\mathcal {Z} \) lets \(\mathcal {H}\) know of this fact. \(\mathcal {H}\) interacts only with the environment, the adversary, and the corrupted parties.

  12. 12.

    Informally, an environment is balanced if it admits a runtime budget to the adversary that is, at any point, at least the sum of the runtime budgets of all other machines. The notion of probabilistic polynomial-time in distributed UC-like systems is of no concern in this paper and we refer the interested reader to [7] for a formal definition.

  13. 13.

    Here, we assume that a CRS that leads to a statistically hiding commitment scheme is efficiently recognizable.

  14. 14.

    We recall the definition of a bilateral protocol [9]: “[A] protocol \(\pi \) between n parties \(P_1, \dots , P_n\) is bilateral if all except two parties stay idle and do not transmit messages.”

References

  1. Asharov, G., Lindell, Y.: A full proof of the BGW protocol for perfectly secure multiparty computation. J. Cryptol. 30(1), 58–151 (2015). https://doi.org/10.1007/s00145-015-9214-4

    Article  MathSciNet  MATH  Google Scholar 

  2. Badertscher, C., Canetti, R., Hesse, J., Tackmann, B., Zikas, V.: Universal composition with global subroutines: capturing global setup within plain UC. In: Pass, R., Pietrzak, K. (eds.) TCC 2020, Part III. LNCS, vol. 12552, pp. 1–30. Springer, Heidelberg (Nov 2020). https://doi.org/10.1007/978-3-030-64381-2_1

  3. Beaver, D.: Commodity-based cryptography (extended abstract). In: 29th ACM STOC, pp. 446–455. ACM Press (May 1997). https://doi.org/10.1145/258533.258637

  4. Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: 20th ACM STOC, pp. 1–10. ACM Press (May 1988). https://doi.org/10.1145/62212.62213

  5. Berger, R., et al.: Composable long-term security with rewinding. Cryptology ePrint Archive, Report 2023/363 (2023). https://eprint.iacr.org/2023/363

  6. Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd FOCS, pp. 136–145. IEEE Computer Society Press (Oct 2001). https://doi.org/10.1109/SFCS.2001.959888

  7. Canetti, R.: Universally composable security. J. ACM 67(5), 28:1–28:94 (2020). https://doi.org/10.1145/3402457

  8. Canetti, R., Dodis, Y., Pass, R., Walfish, S.: Universally composable security with global setup. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 61–85. Springer, Heidelberg (Feb 2007). https://doi.org/10.1007/978-3-540-70936-7_4

  9. Canetti, R., Fischlin, M.: Universally composable commitments. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 19–40. Springer, Heidelberg (Aug 2001). https://doi.org/10.1007/3-540-44647-8_2

  10. Canetti, R., Lin, H., Pass, R.: Adaptive hardness and composable security in the plain model from standard assumptions. In: 51st FOCS, pp. 541–550. IEEE Computer Society Press (Oct 2010). https://doi.org/10.1109/FOCS.2010.86

  11. Canetti, R., Lin, H., Pass, R.: From unprovability to environmentally friendly protocols. In: 54th FOCS, pp. 70–79. IEEE Computer Society Press (Oct 2013). https://doi.org/10.1109/FOCS.2013.16

  12. Canetti, R., Lin, H., Pass, R.: Adaptive hardness and composable security in the plain model from standard assumptions. SIAM J. Comput. 45(5), 1793–1834 (2016). https://doi.org/10.1137/110847196

    Article  MathSciNet  MATH  Google Scholar 

  13. Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: 34th ACM STOC, pp. 494–503. ACM Press (May 2002). https://doi.org/10.1145/509907.509980

  14. Damgård, I., Nielsen, J.B.: Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor. In: Yung, M. (ed.) CRYPTO 2002, LNCS, vol. 2442, pp. 581–596. Springer, Heidelberg (Aug 2002). https://doi.org/10.1007/3-540-45708-9_37

  15. Döttling, N., Kraschewski, D., Müller-Quade, J.: Unconditional and composable security using a single stateful tamper-proof hardware token. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 164–181. Springer, Heidelberg (Mar 2011). https://doi.org/10.1007/978-3-642-19571-6_11

  16. Goldreich, O.: Foundations of Cryptography: Basic Applications, vol. 2. Cambridge University Press, Cambridge (2004)

    Book  MATH  Google Scholar 

  17. Goldreich, O., Krawczyk, H.: On the composition of zero-knowledge proof systems. In: Paterson, M.S. (ed.) ICALP 1990. LNCS, vol. 443, pp. 268–282. Springer, Heidelberg (1990). https://doi.org/10.1007/BFb0032038

    Chapter  Google Scholar 

  18. Gorbunov, S., Vaikuntanathan, V., Wichs, D.: Leveled fully homomorphic signatures from standard lattices. In: Servedio, R.A., Rubinfeld, R. (eds.) 47th ACM STOC, pp. 469–477. ACM Press (Jun 2015). https://doi.org/10.1145/2746539.2746576

  19. Goyal, V., Lin, H., Pandey, O., Pass, R., Sahai, A.: Round-efficient concurrently composable secure computation via a robust extraction lemma. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part I. LNCS, vol. 9014, pp. 260–289. Springer, Heidelberg (Mar 2015). https://doi.org/10.1007/978-3-662-46494-6_12

  20. Hohenberger, S., Waters, B.: Short and stateless signatures from the RSA assumption. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 654–670. Springer, Heidelberg (Aug 2009). https://doi.org/10.1007/978-3-642-03356-8_38

  21. Kiyoshima, S.: Statistical concurrent non-Malleable zero-knowledge from one-way functions. J. Cryptol. 33(3), 1318–1361 (2020). https://doi.org/10.1007/s00145-020-09348-x

    Article  MathSciNet  MATH  Google Scholar 

  22. Magri, B., Malavolta, G., Schröder, D., Unruh, D.: Everlasting UC commitments from fully malicious PUFs. J. Cryptol. 35(3), 20 (2022). https://doi.org/10.1007/s00145-022-09432-4

    Article  MathSciNet  MATH  Google Scholar 

  23. Müller-Quade, J., Unruh, D.: Long-term security and universal composability. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 41–60. Springer, Heidelberg (Feb 2007). https://doi.org/10.1007/978-3-540-70936-7_3

  24. Müller-Quade, J., Unruh, D.: Long-term security and universal composability. J. Cryptol. 23(4), 594–671 (2010). https://doi.org/10.1007/s00145-010-9068-8

    Article  MathSciNet  MATH  Google Scholar 

  25. Nielsen, J.: On Protocol Security in the Cryptographic Model. Ph.D. thesis, Aarhus Universitet (2003)

    Google Scholar 

  26. Orlandi, C., Ostrovsky, R., Rao, V., Sahai, A., Visconti, I.: Statistical concurrent non-malleable zero knowledge. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 167–191. Springer, Heidelberg (Feb 2014). https://doi.org/10.1007/978-3-642-54242-8_8

  27. Pass, R., Dustin Tseng, W.-L., Venkitasubramaniam, M.: Concurrent zero knowledge, revisited. J. Cryptol. 27(1), 45–66 (2012). https://doi.org/10.1007/s00145-012-9137-2

  28. Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (Aug 1992). https://doi.org/10.1007/3-540-46766-1_9

  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 (Aug 2008). https://doi.org/10.1007/978-3-540-85174-5_31

  30. Prabhakaran, M., Rosen, A., Sahai, A.: Concurrent zero knowledge with logarithmic round-complexity. In: 43rd FOCS, pp. 366–375. IEEE Computer Society Press (Nov 2002). https://doi.org/10.1109/SFCS.2002.1181961

  31. Prabhakaran, M., Sahai, A.: New notions of security: achieving universal composability without trusted setup. In: Babai, L. (ed.) 36th ACM STOC, pp. 242–251. ACM Press (Jun 2004). https://doi.org/10.1145/1007352.1007394

Download references

Acknowledgements

This work has been supported by KASTEL Security Research Labs. Astrid Ottenhues: This work has been supported by funding from the German Federal Ministry of Education and Research (BMBF) under the projects “PQC4MED” (ID 16KIS1044) and “Sec4IoMT” (ID 16KIS1692). Michael Klooß, Jeremias Mechler, Jörn Müller-Quade, Markus Raiber: This work has been supported by funding from the topic Engineering Secure Systems of the Helmholtz Association (HGF). Michael Klooß: This work has been supported by Helsinki Institute for Information Technology HIIT. We thank the reviewers for helpful editorial feedback.

Author information

Authors and Affiliations

  1. KASTEL Security Research Labs, Karlsruhe Institute of Technology, Karlsruhe, Germany

    Robin Berger, Jeremias Mechler, Jörn Müller-Quade, Astrid Ottenhues & Markus Raiber

  2. Aalto University, Espoo, Finland

    Michael Klooß

  3. Karlsruhe, Germany

    Brandon Broadnax

Authors
  1. Robin Berger
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Brandon Broadnax
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Michael Klooß
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jeremias Mechler
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Jörn Müller-Quade
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Astrid Ottenhues
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Markus Raiber
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Michael Klooß .

Editor information

Editors and Affiliations

  1. Apple, Cupertino, CA, USA

    Guy Rothblum

  2. NTT Research, Sunnyvale, CA, USA

    Hoeteck Wee

Rights and permissions

Reprints 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

Berger, R. et al. (2023). Composable Long-Term Security with Rewinding. In: Rothblum, G., Wee, H. (eds) Theory of Cryptography. TCC 2023. Lecture Notes in Computer Science, vol 14372. Springer, Cham. https://doi.org/10.1007/978-3-031-48624-1_19

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-48624-1_19

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-48623-4

  • Online ISBN: 978-3-031-48624-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation