Welcome to the resource topic for 2004/341
Title:
Reducing Complexity Assumptions for Statistically-Hiding Commitment
Authors: Omer Horvitz, Jonathan Katz, Chiu-Yuen Koo, Ruggero Morselli
Abstract:Determining the minimal assumptions needed to construct various
cryptographic building blocks has been a focal point of research in
theoretical cryptography. For most — but not all! — cryptographic
primitives, complexity assumptions both necessary and sufficient for their existence are known. Here, we revisit the following, decade-old question: what are the minimal assumptions needed to construct a statistically-hiding bit commitment scheme? Previously, it was known how to construct such schemes based on any one-way permutation.
In this work, we show that regular one-way functions suffice.
We show two constructions of statistically-hiding commitment schemes from regular one-way functions. Our first construction is more direct, and serves as a ``stepping-stone’’ for our second construction which has improved round complexity. Of independent interest, as part of our work we show a compiler transforming any commitment scheme which is statistically-hiding against an honest-but-curious receiver to one which is statistically-hiding against a malicious receiver. This demonstrates the equivalence of these two formulations of the problem.
Our results also improve the complexity assumptions needed for statistical zero-knowledge arguments.
ePrint: https://eprint.iacr.org/2004/341
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 .