Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Public Key Cryptography:
TR07-021 | 5th March 2007
Brett Hemenway, Rafail Ostrovsky

Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code

Revisions: 3

In this paper, we introduce the notion of a Public-Key Encryption (PKE) Scheme that is also a Locally-Decodable Error-Correcting Code.
In particular, our construction simultaneously satisfies all of the following properties:
Our Public-Key Encryption is semantically secure under a certain number-theoretic hardness assumption
... more >>>

TR09-108 | 31st October 2009
Chongwon Cho, Chen-Kuei Lee, Rafail Ostrovsky

Equivalence of Uniform Key Agreement and Composition Insecurity

Revisions: 1

It is well known that proving the security of a key agreement protocol (even in a special case where the protocol transcript looks random to an outside observer) is at least as difficult as proving $P \not = NP$. Another (seemingly unrelated) statement in cryptography is the existence of two ... more >>>

TR17-065 | 20th April 2017
Boaz Barak

The Complexity of Public-Key Cryptograph

We survey the computational foundations for public-key cryptography. We discuss the computational assumptions that have been used as bases for public-key encryption schemes, and the types of evidence we have for the veracity of these assumptions.

This is a survey that appeared in a book of surveys in honor of ... more >>>

TR17-172 | 3rd November 2017
Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan

From Laconic Zero-Knowledge to Public-Key Cryptography

Since its inception, public-key encryption (PKE) has been one of the main cornerstones of cryptography. A central goal in cryptographic research is to understand the foundations of public-key encryption and in particular, base its existence on a natural and generic complexity-theoretic assumption. An intriguing candidate for such an assumption is ... more >>>

TR21-124 | 17th August 2021
Iftach Haitner, Noam Mazor, Jad Silbak, Eliad Tsfadia

On the Complexity of Two-Party Differential Privacy

Revisions: 1

In distributed differential privacy, the parties perform analysis over their joint data while preserving the privacy for both datasets. Interestingly, for a few fundamental two-party functions such as inner product and Hamming distance, the accuracy of the distributed solution lags way behind what is achievable in the client-server setting. McGregor, ... more >>>

ISSN 1433-8092 | Imprint