Reducing Complexity Assumptions for Statistically-Hiding Commitment

Iftach Haitner; Omer Horvitz; Jonathan Katz; Chiu-Yuen Koo; Ruggero Morselli; Ronen Shaltiel

doi:10.1007/s00145-007-9012-8

Back

Reducing Complexity Assumptions for Statistically-Hiding Commitment

Journal article

Peer reviewed

Reducing Complexity Assumptions for Statistically-Hiding Commitment

Iftach Haitner, Omer Horvitz, Jonathan Katz, Chiu-Yuen Koo, Ruggero Morselli and Ronen Shaltiel

Journal of Cryptology, Vol.22(3), pp.283-310

Jul/2009

DOI: https://doi.org/10.1007/s00145-007-9012-8

Files and links (2)

url

https://doi.org/10.1007/s00145-007-9012-8View

Published (Version of record) Restricted

url

https://ezproxy.weizmann.ac.il/login?url=http://dx.doi.org/10.1007/s00145-007-9012-8View

Published (Version of record) Restricted

Abstract

We revisit the following question: what are the minimal assumptions needed to construct statistically-hiding commitment schemes? Naor et al. show how to construct such schemes based on any one-way permutation. We improve upon this by showing a construction based on any approximable preimage-size one-way function. These are one-way functions for which it is possible to efficiently approximate the number of pre-images of a given output. A special case is the class of regular one-way functions where all points in the image of the function have the same (known) number of pre-images. We also prove two additional results related to statistically-hiding commitment. First, we prove a (folklore) parallel composition theorem showing, roughly speaking, that the statistical hiding property of any such commitment scheme is amplified exponentially when multiple independent parallel executions of the scheme are carried out. Second, we show a compiler which transforms any commitment scheme which is statistically hiding against an honest-but-curious receiver into one which is statistically hiding even against a malicious receiver.

Details

Title: Reducing Complexity Assumptions for Statistically-Hiding Commitment
Creators: Iftach Haitner (null)
Omer Horvitz (null)
Jonathan Katz (null)
Chiu-Yuen Koo (null)
Ruggero Morselli (null)
Ronen Shaltiel (null)
Resource Type: Journal article
Publication Details: Journal of Cryptology, Vol.22(3), pp.283-310; Jul/2009
Number of pages: 28
Language: English
DOI: https://doi.org/10.1007/s00145-007-9012-8
Grant note: US-Israel Binational Science Foundation [2002246, 2004329]; U.S. Army Research Office award [DAAD19-01-1-0494]; NSF CAREER award [0447075]Research supported by US-Israel Binational Science Foundation grant 2002246.Research of O.H. supported by U.S. Army Research Office award DAAD19-01-1-0494. Research of J.K. supported by NSF CAREER award #0447075.Research supported by US-Israel Binational Science Foundation grant 2004329._ALMAME_DELIMITER_
Scientific Unit: The Weizmann Institute of Science
Record Identifier: 993262417703596

Metrics

1 Record Views