All reports by Author Brett Hemenway:

__
TR24-005
| 4th January 2024
__

Daniel Noble, Brett Hemenway, Rafail Ostrovsky#### MetaDORAM: Breaking the Log-Overhead Information Theoretic Barrier

Revisions: 2

__
TR17-104
| 13th June 2017
__

Brett Hemenway, Noga Ron-Zewi, Mary Wootters#### Local List Recovery of High-rate Tensor Codes & Applications

Revisions: 1

__
TR11-118
| 6th September 2011
__

Brett Hemenway, Rafail Ostrovsky, Martin Strauss, Mary Wootters#### Public Key Locally Decodable Codes with Short Keys

__
TR10-127
| 9th August 2010
__

Brett Hemenway, Rafail Ostrovsky#### Building Injective Trapdoor Functions From Oblivious Transfer

Revisions: 1

__
TR09-127
| 25th November 2009
__

Brett Hemenway, Rafail Ostrovsky#### Lossy Trapdoor Functions from Smooth Homomorphic Hash Proof Systems

Revisions: 2

__
TR07-021
| 5th March 2007
__

Brett Hemenway, Rafail Ostrovsky#### Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code

Revisions: 3

Daniel Noble, Brett Hemenway, Rafail Ostrovsky

This paper presents the first Distributed Oblivious RAM (DORAM) protocol that achieves sub-logarithmic communication overhead without computational assumptions.

That is, given $n$ $d$-bit memory locations, we present an information-theoretically secure protocol which requires $o(d \cdot \log(n))$ bits of communication per access (when $d = \Omega(\log^2(n)$).

This comes as a surprise, ... more >>>

Brett Hemenway, Noga Ron-Zewi, Mary Wootters

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

Brett Hemenway, Rafail Ostrovsky, Martin Strauss, Mary Wootters

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

Brett Hemenway, Rafail Ostrovsky

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

Brett Hemenway, Rafail Ostrovsky

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

Brett Hemenway, Rafail Ostrovsky

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:

\begin{itemize}

\item

Our Public-Key Encryption is semantically secure under a certain number-theoretic hardness assumption

...
more >>>