@article {15099, title = {Bounds on the efficiency of black-box commitment schemes}, journal = {Automata, Languages and Programming}, year = {2005}, month = {2005///}, pages = {62 - 62}, abstract = {Constructions of cryptographic primitives based on general assumptions (e.g., the existence of one-way functions) tend to be less efficient than constructions based on specific (e.g., number-theoretic) assumptions. This has prompted a recent line of research aimed at investigating the best possible efficiency of (black-box) constructions based on general assumptions. Here, we present bounds on the efficiency of statistically-binding commitment schemes constructed using black-box access to one-way permutations; our bounds are tight for the case of perfectly-binding schemes. We present the bounds in an extension of the Impagliazzo-Rudich model; that is, we show that any construction beating our bounds would imply the unconditional existence of a one-way function (from which a commitment scheme could be constructed {\textquotedblleft}from scratch{\textquotedblright}). Our analysis is the first in the area to pertain directly to an information-theoretic component of the security notion.}, doi = {10.1007/11523468_11}, author = {Horvitz,O. and Katz, Jonathan} }