-
Chapter and Conference Paper
Single-Server Private Information Retrieval with Sublinear Amortized Time
We construct new private-information-retrieval protocols in the single-server setting. Our schemes allow a client to privately fetch a sequence of database records from a server, while the server answers each ...
-
Chapter and Conference Paper
Oblivious Pseudorandom Functions from Isogenies
An oblivious PRF, or OPRF, is a protocol between a client and a server, where the server has a key k for a secure pseudorandom function F, and the client has an input x for the function. At the end of the protoco...
-
Chapter and Conference Paper
Private Information Retrieval with Sublinear Online Time
We present the first protocols for private information retrieval that allow fast (sublinear-time) database lookups without increasing the server-side storage requirements. To achieve these efficiency goals, ou...
-
Chapter and Conference Paper
The Function-Inversion Problem: Barriers and Opportunities
The task of function inversion is central to cryptanalysis: breaking block ciphers, forging signatures, and cracking password hashes are all special cases of the function-inversion problem. In 1980, Hellman s...
-
Chapter and Conference Paper
The Discrete-Logarithm Problem with Preprocessing
This paper studies discrete-log algorithms that use preprocessing. In our model, an adversary may use a very large amount of precomputation to produce an “advice” string about a specific group (e.g., NIST P-256)....
-
Article
An isoperimetric inequality for conjugation-invariant sets in the symmetric group
We prove an isoperimetric inequality for conjugation-invariant sets of size k in S n , showing that these necessarily have edge-boundary consider...
-
Chapter and Conference Paper
Collecting garbage pages in a distributed shared memory with reduced memory and communication overhead
We present a novel algorithm for Garbage Collection (GC) in Distributed Shared Memory systems (DSM). Our algorithm reduces the network traffic overhead (and the memory and computation overheads), essentially e...
