Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Statistical Zero-Knowledge:
TR05-018 | 6th February 2005
Oded Goldreich

On Promise Problems (a survey in memory of Shimon Even [1935-2004])

The notion of promise problems was introduced and initially studied
by Even, Selman and Yacobi
(Information and Control, Vol.~61, pages 159-173, 1984).
In this article we survey some of the applications that this
notion has found in the twenty years that elapsed.
These include the notion ... more >>>

TR12-052 | 27th April 2012
Mohammad Mahmoody, David Xiao

Languages with Efficient Zero-Knowledge PCPs are in SZK

A Zero-Knowledge PCP (ZK-PCP) is a randomized PCP such that the view of any (perhaps cheating) efficient verifier can be efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC '97) constructed ZK-PCPs for all languages in $NEXP$. Ishai, Mahmoody, and Sahai (TCC '12), motivated by cryptographic applications, ... more >>>

TR12-156 | 12th November 2012
Andrej Bogdanov, Chin Ho Lee

Limits of provable security for homomorphic encryption

Revisions: 1

We show that public-key bit encryption schemes which support weak homomorphic evaluation of parity or majority cannot be proved message indistinguishable beyond AM intersect coAM via general (adaptive) reductions, and beyond statistical zero-knowledge via reductions of constant query complexity.

Previous works on the limitation of reductions for proving security of ... more >>>

TR18-056 | 20th March 2018
Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, Daniel Wichs

Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing

We present a worst case decoding problem whose hardness reduces to that of solving the Learning Parity with Noise (LPN) problem, in some parameter regime. Prior to this work, no worst case hardness result was known for LPN (as opposed to syntactically similar problems such as Learning with Errors). The ... more >>>

ISSN 1433-8092 | Imprint