Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Errata to (Nearly) Round-Optimal Black-Box Constructions of Commitments Secure against Selective Opening Attacks

David Xiao

Published Jan 1, 2013• 7 citations
Publisher
DOI
10.1007/978-3-642-36594-2_40

Related papers

Round-Optimal Black-Box Statistically Binding Selective-Opening Secure Commitments

David Xiao

Lecture notes in computer science•Jan 1, 2012•3 citations

Round-Optimal Black-Box Secure Computation from Two-Round Malicious OT

Yuval Ishai, Dakshita Khurana, Amit Sahai +1 more

Lecture notes in computer science•Jan 1, 2022•6 citations

A Black-Box Construction of Fully-Simulatable, Round-Optimal Oblivious Transfer from Strongly Uniform Key Agreement

Daniele Friolo, Daniel Masny, Daniele Venturi

Lecture notes in computer science•Jan 1, 2019•21 citations

The Round Complexity of Black-Box Post-quantum Secure Computation

Rohit Chatterjee, Xiao Rong Liang, Omkant Pandey +1 more

arXiv:2502.13830•Lecture notes in computer science•Jan 1, 2025•3 citations

Breaking the Three Round Barrier for Non-malleable Commitments

Vipul Goyal, Dakshita Khurana, Amit Sahai

We construct two-message non-malleable commitments with respect to opening in the standard model, assuming only one-to-one one-way functions. Our protocol consists of two unidirectional messages by the committer (with no message from the receiver), and is secure against all polynomial-time adversaries in the standard synchronous setting. Pass (TCC 2013) proved that any commitment scheme with non-malleability with respect to commitment, using only 2 rounds of communication, cannot be proved secure via a black-box reduction to any "standard" intractability assumption. We extend this by showing a similar impossibility result for commitments with non-malleability with respect to opening, another standard notion of non-malleability for commitments, for any 2-message challenge-response protocol, as well. However, somewhat surprisingly, we show that this barrier breaks down in the setting of two unidirectional messages by the committer (with no message from the receiver), for non-malleability with respect to opening.°Our protocol makes only black-box use of any non-interactive statistically binding commitment scheme. Such a scheme can be based on any one-to-one one-way function.°Our techniques depart significantly from the commit-challenge-response structure followed by nearly all prior works on non-malleable protocols in the standard model. Our methods are combinatorial in nature.°Our protocol resolves the round complexity of commitments with non-malleability with respect to opening via natural (non-embedding) black-box security reductions. We show that completely non-interactive non-malleable commitments w.r.t. opening cannot be proved secure via most natural black-box reductions. This result extends to also rule out bi-directional two-message non-malleable commitments w.r.t. opening in the synchronous or asynchronous setting.°Our protocol, together with our impossibility result, also resolves the round complexity of block-wise non-malleable codes (Chandran et al) w.r.t. natural black-box reductions.

Annual Symposium on Foundations of Computer Science•Oct 1, 2016•11 citations

Constructions and Bounds for Unconditionally Secure Non-Interactive Commitment Schemes

Carlo Blundo, Barbara Masucci, Douglas R. Stinson +1 more

Designs Codes and Cryptography•Jun 1, 2002•31 citations
We construct two-message non-malleable commitments with respect to opening in the standard model, assuming only one-to-one one-way functions. Our protocol consists of two unidirectional messages by the committer (with no message from the receiver), and is secure against all polynomial-time adversaries in the standard synchronous setting. Pass (TCC 2013) proved that any commitment scheme with non-malleability with respect to commitment, using only 2 rounds of communication, cannot be proved secure via a black-box reduction to any "standard" intractability assumption. We extend this by showing a similar impossibility result for commitments with non-malleability with respect to opening, another standard notion of non-malleability for commitments, for any 2-message challenge-response protocol, as well. However, somewhat surprisingly, we show that this barrier breaks down in the setting of two unidirectional messages by the committer (with no message from the receiver), for non-malleability with respect to opening.°Our protocol makes only black-box use of any non-interactive statistically binding commitment scheme. Such a scheme can be based on any one-to-one one-way function.°Our techniques depart significantly from the commit-challenge-response structure followed by nearly all prior works on non-malleable protocols in the standard model. Our methods are combinatorial in nature.°Our protocol resolves the round complexity of commitments with non-malleability with respect to opening via natural (non-embedding) black-box security reductions. We show that completely non-interactive non-malleable commitments w.r.t. opening cannot be proved secure via most natural black-box reductions. This result extends to also rule out bi-directional two-message non-malleable commitments w.r.t. opening in the synchronous or asynchronous setting.°Our protocol, together with our impossibility result, also resolves the round complexity of block-wise non-malleable codes (Chandran et al) w.r.t. natural black-box reductions.