Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Brett Hemenway:

TR17-104 | 13th June 2017
Brett Hemenway, Noga Ron-Zewi, Mary Wootters

Local List Recovery of High-rate Tensor Codes & Applications

In this work, we give the first construction of {\em high-rate} locally list-recoverable codes. List-recovery has been an extremely useful building block in coding theory, and our motivation is to use these codes as such a building block.
In particular, our construction gives the first {\em capacity-achieving} locally list-decodable ... more >>>

TR11-118 | 6th September 2011
Brett Hemenway, Rafail Ostrovsky, Martin Strauss, Mary Wootters

Public Key Locally Decodable Codes with Short Keys

This work considers locally decodable codes in the computationally bounded channel model. The computationally bounded channel model, introduced by Lipton in 1994, views the channel as an adversary which is restricted to polynomial-time computation. Assuming the existence of IND-CPA secure public-key encryption, we present a construction of public-key locally decodable ... more >>>

TR10-127 | 9th August 2010
Brett Hemenway, Rafail Ostrovsky

Building Injective Trapdoor Functions From Oblivious Transfer

Revisions: 1

Injective one-way trapdoor functions are one of the most fundamental cryptographic primitives. In this work we give a novel construction of injective trapdoor functions based on oblivious transfer for long strings.

Our main result is to show that any 2-message statistically sender-private semi-honest oblivious transfer (OT) for ... 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 >>>

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

ISSN 1433-8092 | Imprint