STATISTICALLY HIDING COMMITMENTS AND STATISTICAL ZERO-KNOWLEDGE ARGUMENTS FROM ANY ONE-WAY FUNCTION

被引：63

作者：

Haitner, Iftach ^{[1
]}

Nguyen, Minh-Huyen ^{[2
]}

Ong, Shien Jin ^{[2
]}

Reingold, Omer ^{[3
]}

Vadhan, Salil ^{[2
]}

机构：

[1] Microsoft Res, Cambridge, MA 02142 USA

[2] Harvard Univ, Sch Engn & Appl Sci, Cambridge, MA 02138 USA

[3] Weizmann Inst Sci, Fac Math & Comp Sci, IL-76100 Rehovot, Israel

来源：

SIAM JOURNAL ON COMPUTING | 2009年 / 39卷 / 03期

关键词：

cryptography; statistically hiding commitments; statistical zero-knowledge argument systems; one-way functions; interactive hashing; SECRECY; PROOFS; SECURE; NP;

D O I：

10.1137/080725404

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We give a construction of statistically hiding commitment schemes (those in which the hiding property holds against even computationally unbounded adversaries) under the minimal complexity assumption that one-way functions exist. Consequently, one-way functions suffice to give statistical zero-knowledge arguments for any NP statement ( whereby even a computationally unbounded adversarial verifier learns nothing other than the fact that the assertion being proven is true, and no polynomial-time adversarial prover can convince the verifier of a false statement). These results resolve an open question posed by Naor et al. [J. Cryptology, 11 (1998), pp. 87-108].

引用

页码：1153 / 1218

页数：66

共 40 条

[1] PRIVACY AMPLIFICATION BY PUBLIC DISCUSSION [J].