All reports by Author Rafail Ostrovsky:

__
TR24-005
| 4th January 2024
__

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

Revisions: 2

__
TR23-095
| 21st June 2023
__

David Heath, Vladimir Kolesnikov, Rafail Ostrovsky#### Tri-State Circuits: A Circuit Model that Captures RAM

__
TR15-056
| 3rd April 2015
__

Sanjam Garg, Steve Lu, Rafail Ostrovsky#### Black-Box Garbled RAM

__
TR13-143
| 19th October 2013
__

Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman#### Robust Pseudorandom Generators

Revisions: 1

__
TR12-164
| 17th November 2012
__

Rafail Ostrovsky, Ivan Visconti#### Simultaneous Resettability from Collision Resistance

__
TR12-104
| 8th August 2012
__

Matthew Franklin, Ran Gelles, Rafail Ostrovsky, Leonard Schulman#### Optimal Coding for Streaming Authentication and Interactive Communication

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

__
TR09-108
| 31st October 2009
__

Chongwon Cho, Chen-Kuei Lee, Rafail Ostrovsky#### Equivalence of Uniform Key Agreement and Composition Insecurity

Revisions: 2

__
TR07-022
| 20th February 2007
__

Rafail Ostrovsky, William Skeith#### Algebraic Lower Bounds for Computing on Encrypted Data

__
TR07-021
| 5th March 2007
__

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

Revisions: 3

__
TR06-110
| 15th August 2006
__

Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Amit Sahai#### Improved Algorithms for Optimal Embeddings

__
TR06-095
| 25th July 2006
__

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti#### Concurrent Non-Malleable Witness Indistinguishability and its Applications

Revisions: 1

__
TR05-097
| 31st August 2005
__

Jens Groth, Rafail Ostrovsky, Amit Sahai#### Perfect Non-Interactive Zero Knowledge for NP

__
TR94-007
| 12th December 1994
__

Oded Goldreich, Rafail Ostrovsky, Erez Petrank#### Computational Complexity and Knowledge Complexity

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

David Heath, Vladimir Kolesnikov, Rafail Ostrovsky

We introduce tri-state circuits (TSCs). TSCs form a natural model of computation that, to our knowledge, has not been considered by theorists. The model captures a surprising combination of simplicity and power. TSCs are simple in that they allow only three wire values ($0$,$1$, and undefined – $Z$) and three ... more >>>

Sanjam Garg, Steve Lu, Rafail Ostrovsky

Garbled RAM, introduced by Lu and Ostrovsky, enables the task of garbling a RAM (Random Access Machine) program directly, there by avoiding the inefficient process of first converting it into a circuit. Garbled RAM can be seen as a RAM analogue of Yao's garbled circuit construction, except that known realizations ... more >>>

Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman

Let $G:\{0,1\}^n\to\{0,1\}^m$ be a pseudorandom generator. We say that a circuit implementation of $G$ is $(k,q)$-robust if for every set $S$ of at most $k$ wires anywhere in the circuit, there is a set $T$ of at most $q|S|$ outputs, such that conditioned on the values of $S$ and $T$ ... more >>>

Rafail Ostrovsky, Ivan Visconti

In FOCS 2001, Barak, Goldreich, Goldwasser and Lindell conjectured that the existence of ZAPs, introduced by Dwork and Naor in FOCS 2000, could lead to the design of a zero-knowledge proof system that is secure against both resetting provers and resetting verifiers. Their conjecture has been proven true by Deng, ... more >>>

Matthew Franklin, Ran Gelles, Rafail Ostrovsky, Leonard Schulman

Error correction and message authentication are well studied in the literature, and various efficient solutions have been suggested and analyzed. This is however not the case for data streams in which the message is very long, possibly infinite, and not known in advance to the sender. Trivial solutions for error-correcting ... 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 >>>

Chongwon Cho, Chen-Kuei Lee, Rafail Ostrovsky

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

Rafail Ostrovsky, William Skeith

In cryptography, there has been tremendous success in building

primitives out of homomorphic semantically-secure encryption

schemes, using homomorphic properties in a black-box way. A few

notable examples of such primitives include items like private

information retrieval schemes and collision-resistant hash functions. In this paper, we illustrate a general

methodology for ...
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 >>>

Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Amit Sahai

In the last decade, the notion of metric embeddings with

small distortion received wide attention in the literature, with

applications in combinatorial optimization, discrete mathematics, functional

analysis and bio-informatics. The notion of embedding is, given two metric

spaces on the same number of points, to find a bijection that minimizes

more >>>

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti

One of the central questions in Cryptography today is proving security of the protocols ``on the Internet'', i.e., in a concurrent setting where there are multiple interactions between players, and where the adversary can play so called ``man-in-the-middle'' attacks, forwarding and modifying messages between two or more unsuspecting players. Indeed, ... more >>>

Jens Groth, Rafail Ostrovsky, Amit Sahai

Non-interactive zero-knowledge (NIZK) systems are

fundamental cryptographic primitives used in many constructions,

including CCA2-secure cryptosystems, digital signatures, and various

cryptographic protocols. What makes them especially attractive, is

that they work equally well in a concurrent setting, which is

notoriously hard for interactive zero-knowledge protocols. However,

while for interactive zero-knowledge we ...
more >>>

Oded Goldreich, Rafail Ostrovsky, Erez Petrank

We study the computational complexity of languages which have

interactive proofs of logarithmic knowledge complexity. We show that

all such languages can be recognized in ${\cal BPP}^{\cal NP}$. Prior

to this work, for languages with greater-than-zero knowledge

complexity (and specifically, even for knowledge complexity 1) only

trivial computational complexity bounds ...
more >>>