Paper 2023/363

Composable Long-Term Security with Rewinding

Robin Berger, KASTEL, Karlsruhe Institute of Technology
Brandon Broadnax
Michael Klooß, KASTEL, Karlsruhe Institute of Technology
Jeremias Mechler, KASTEL, Karlsruhe Institute of Technology
Jörn Müller-Quade, KASTEL, Karlsruhe Institute of Technology
Astrid Ottenhues, KASTEL, Karlsruhe Institute of Technology
Markus Raiber, KASTEL, Karlsruhe Institute of Technology

Long-term security, a variant of Universally Composable (UC) security introduced by Müller-Quade and Unruh (JoC ’10), allows to analyze the security of protocols in a setting where all hardness assumptions no longer hold after the protocol execution has finished. Such a strict notion is highly desirable when properties such as input privacy need to be guaranteed for a long time, e.g. zero-knowledge proofs for secure electronic voting. Strong impossibility results rule out so-called long-term-revealing setups, e.g. a common reference string (CRS), to achieve long-term security, with known constructions for long-term security requiring hardware assumptions, e.g. signature cards. We circumvent these impossibility results by making use of new techniques, allowing rewinding-based simulation in a way that universal composability is possible. The new techniques allow 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 superpolynomial extraction techniques, as statistically hiding commitments do not define a unique value. Thus, we extract the value committed to via rewinding. However, even a CCA “rewinding oracle” without additional properties may be useless, as extracting a malicious committer could require to rewind other protocols the committer participates in. If this is e.g. a reduction, this clearly is forbidden. Fortunately, we can establish the well-known and important property of k-robust extractability, which guarantees that extraction is possible without rewinding k-round protocols the malicious committer participates in. While establishing this property for statistically binding commitment schemes is already non-trivial, it is even more complicated for statistically hiding ones. We then 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. Despite the rewinding, our variant of long-term security is universally composable. Our new framework provides the first setting in which a commitment scheme that is both statistically hiding and composable can be constructed from standard polynomial-time hardness assumptions and a CRS only. Unfortunately, we can prove that our setting does not admit long-term-secure oblivious transfer (and thus general two-party computations). 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.

Available format(s)
Publication info
universal composabilitylong-term securitycommitmentsrewinding
Contact author(s)
robin berger @ kit edu
broadnax @ mail informatik kit edu
michael klooss @ kit edu
jeremias mechler @ kit edu
joern mueller-quade @ kit edu
astrid ottenhues @ kit edu
markus raiber @ kit edu
2023-03-16: approved
2023-03-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Robin Berger and Brandon Broadnax and Michael Klooß and Jeremias Mechler and Jörn Müller-Quade and Astrid Ottenhues and Markus Raiber},
      title = {Composable Long-Term Security with Rewinding},
      howpublished = {Cryptology ePrint Archive, Paper 2023/363},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.