Cryptology ePrint Archive: Report 2008/034

Perfectly Hiding Commitment Scheme with Two-Round from Any One-Way Permutation

Chunming Tang and Dingyi Pei and Zhuojun Liu and Zheng-an Yao and Mingsheng Wang

Abstract: Commitment schemes are arguably among the most important and useful primitives in cryptography. According to the computational power of receivers, commitments can be classified into three possible types: {\it computational hiding commitments, statistically hiding commitments} and {\it perfect computational commitments}. The fist commitment with constant rounds had been constructed from any one-way functions in last centuries, and the second with non-constant rounds were constructed from any one-way functions in FOCS2006, STOC2006 and STOC2007 respectively, furthermore, the lower bound of round complexity of statistically hiding commitments has been proven to be $\frac{n}{logn}$ rounds under the existence of one-way function.

Perfectly hiding commitments implies statistically hiding, hence, it is also infeasible to construct a practically perfectly hiding commitments with constant rounds under the existence of one-way function. In order to construct a perfectly hiding commitments with constant rounds, we have to relax the assumption that one-way functions exist. In this paper, we will construct a practically perfectly hiding commitment with two-round from any one-way permutation. To the best of our knowledge, these are the best results so far.

Category / Keywords: Cryptography, perfectly hiding commitments,one-way permutation, $\Sigma$-protocol.

Date: received 23 Jan 2008, last revised 5 Feb 2008

Contact author: tangcm622 at hotmail com

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: revise my paper according to some suggestions from others

Version: 20080205:122231 (All versions of this report)

Short URL: ia.cr/2008/034

Discussion forum: Show discussion | Start new discussion