**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

[ Cryptology ePrint archive ]