Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with quadratic residuosity:
TR05-093 | 24th August 2005
Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan

Concurrent Zero Knowledge without Complexity Assumptions

We provide <i>unconditional</i> constructions of <i>concurrent</i>
statistical zero-knowledge proofs for a variety of non-trivial
problems (not known to have probabilistic polynomial-time
algorithms). The problems include Graph Isomorphism, Graph
Nonisomorphism, Quadratic Residuosity, Quadratic Nonresiduosity, a
restricted version of Statistical Difference, and approximate
versions of the (<b>coNP</b> forms of the) Shortest Vector ... more >>>

TR09-127 | 25th November 2009
Brett Hemenway, Rafail Ostrovsky

Lossy Trapdoor Functions from Smooth Homomorphic Hash Proof Systems

Revisions: 2

In STOC '08, Peikert and Waters introduced a powerful new primitive called Lossy Trapdoor Functions (LTDFs). Since their introduction, lossy trapdoor functions have found many uses in cryptography. In the work of Peikert and Waters, lossy trapdoor functions were used to give an efficient construction of a chosen-ciphertext secure ... more >>>

ISSN 1433-8092 | Imprint