[Resource Topic] 2024/1786: Black-Box Timed Commitments from Time-Lock Puzzles

Resource Cryptographic protocols
1

Welcome to the resource topic for 2024/1786

Title:
Black-Box Timed Commitments from Time-Lock Puzzles

Authors: Hamza Abusalah, Gennaro Avitabile

Abstract:

A Timed Commitment (TC) with time parameter t is hiding for time at most t, that is, commitments can be force-opened by any third party within time t. In addition to various cryptographic assumptions, the security of all known TC schemes relies on the sequentiality assumption of repeated squarings in hidden-order groups. The repeated squaring assumption is therefore a security bottleneck.

In this work, we give a black-box construction of TCs from any time-lock puzzle (TLP) by additionally relying on one-way permutations and collision-resistant hashing.

Currently, TLPs are known from (a) the specific repeated squaring assumption, (b) the general (necessary) assumption on the existence of worst-case non-parallelizing languages and indistinguishability obfuscation, and (c) any iteratively sequential function and the hardness of the circular small-secret LWE problem. The latter admits a plausibly post-quantum secure instantiation.

Hence, thanks to the generality of our transform, we get i) the first TC whose timed security is based on the the existence of non-parallelizing languages and ii) the first TC that is plausibly post-quantum secure.

We first define quasi publicly-verifiable TLPs (QPV-TLPs) and construct them from any standard TLP in a black-box manner without relying on any additional assumptions. Then, we devise a black-box commit-and-prove system to transform any QPV-TLPs into a TC.

ePrint: https://eprint.iacr.org/2024/1786

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .

2

אם ירצה ה׳

TL;DR:

This paper presents a way to build Timed Commitments (TCs) using Time-Lock Puzzles (TLPs) in a generic, “black-box” manner. This is significant because it allows constructing TCs from a wider range of assumptions than previous methods, which relied on the specific assumption of repeated squaring.

ZKP/FHE/MPC SME TL;DR:

Abusalah and Avitabile construct timed commitments (TCs) generically from time-lock puzzles (TLPs) in a black-box manner, relying additionally on one-way permutations and collision-resistant hashing. They introduce quasi-publicly verifiable TLPs (QPV-TLPs) as a key tool, which they construct from any TLP. Their TC achieves computational binding, statistical well-formedness, and public verifiability against unbounded adversaries, and its commit phase is a five-round protocol. This broadens the foundations of TCs beyond repeated squaring and yields the first plausibly post-quantum secure TC using [AMZ24]'s TLP. The construction cleverly uses a commit-and-prove system based on MPC-in-the-head to ensure consistency of commitments across multiple invocations of the TLP, achieving statistical binding.

Cryptography Practitioner TL;DR:

This paper provides a new, modular way to build timed commitments (TCs) from time-lock puzzles (TLPs). This is important for applications where you need to commit to a value now and provably reveal it after a certain time, like in sealed-bid auctions or fair multi-party computation. The construction is black-box, meaning it can use any TLP as a building block, and it achieves strong security properties. Notably, using a specific post-quantum TLP, you can get a post-quantum secure TC. The commit phase is interactive (5 rounds), but the security properties are quite strong, including statistical well-formedness and public verifiability of the forced opening.

Theoretical Computer Scientist TL;DR:

The paper establishes a black-box reduction from timed commitments (TCs) to time-lock puzzles (TLPs), assuming also one-way permutations and collision-resistant hashing. This implies that TCs exist based on the minimal assumption of non-parallelizing languages, and that plausibly post-quantum secure TCs exist. The construction introduces quasi-publicly verifiable TLPs (QPV-TLPs) and uses a novel combination of techniques, including a commit-and-prove system based on MPC-in-the-head and a careful analysis of the resulting timed commitment scheme. The results significantly broaden the theoretical foundations of TCs and open new avenues for constructing them from various cryptographic assumptions.

Non-Hype / Critical TL;DR:

The paper presents a black-box construction of timed commitments from time-lock puzzles, which is theoretically interesting as it expands the set of assumptions known to imply TCs. However, the construction is quite complex, involving a five-round commit phase and the use of a commit-and-prove system based on MPC-in-the-head. While the black-box approach offers modularity, it remains to be seen whether this leads to practically efficient TCs. The reliance on a new QPV-TLP notion, while weaker than publicly-verifiable TLPs, still requires careful scrutiny. The post-quantum security claim hinges on the security of a specific TLP construction, which needs further analysis. Overall, this is a valuable theoretical contribution, but its practical impact is yet to be determined.

Application:

  • Problem: Existing timed commitment (TC) schemes rely on the repeated squaring assumption, which is a single point of failure and might not be secure against quantum computers.
  • Solution: This paper provides a generic way to build TCs from any time-lock puzzle (TLP), which can be based on a wider range of assumptions, including some that are plausibly post-quantum secure.
  • How it works: The authors introduce a new primitive called a quasi-publicly verifiable TLP (QPV-TLP) and show how to build it from any TLP. They then use this, along with a commit-and-prove system based on MPC-in-the-head, to construct a TC with strong security properties.

Unexpected Findings:

  1. Black-Box Construction from Generic TLPs: The paper’s main contribution is a black-box construction of TCs from generic TLPs. This is surprising because previous TC constructions relied heavily on the specifics of the repeated squaring assumption. This black-box approach allows for greater flexibility and potentially weaker security assumptions.

    • Rationale: This is significant because it decouples the security of TCs from the repeated squaring assumption, opening the door to constructing TCs from other, potentially more secure, time-based primitives.

  2. Quasi-Public Verifiability: The introduction of QPV-TLPs is a novel and unexpected contribution. This relaxation of publicly verifiable TLPs is sufficient for constructing TCs and can be achieved generically from any TLP.

    • Rationale: This is a clever insight that simplifies the construction and allows for a more general result. It demonstrates that full public verifiability of the underlying TLP is not necessary for building secure TCs.

  3. Post-Quantum Secure TC: By using the plausibly post-quantum secure TLP of [AMZ24], the authors achieve the first TC that is plausibly secure against quantum adversaries.

    • Rationale: This is a major advancement in the field of timed cryptography, as it addresses the growing concern about the threat of quantum computers to existing cryptographic schemes.

(cont.) https://pdfhost.io/v/8j9wfiOHU_Notes_on_IACR_TCC_20241786

1 Like