Rafail Ostrovsky

Rafail Ostrovsky, Pattern Matching

In this paper we consider the job interval selection problem (JISP), a simple scheduling model with a rich history and numerous applications. Special cases of this problem include the so-called...

General Terms (2008)

We show that {0, 1} d endowed with edit distance embeds into ℓ1 with distortion 2 O( √ log d log log d). We further show efficient implementations of the embedding that yield solutions to various...

Visconti Concurrent Non-Malleable Witness Indistinguishability and its Applications. ECCC reprot 2006/095 (2008)

Rafail Ostrovsky, 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...

Concurrent Statistical Zero-Knowledge Arguments for NP from One Way Functions (2008)

Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky, Amit Sahai

Abstract. In this paper we show a general transformation from any honest verifier statistical zero-knowledge argument to a concurrent statistical zero-knowledge argument. Our transformation relies...

Public key encryption which is simultaneously a locally-decodable errorcorrecting code (2008)

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

Abstract Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds (2008)

Allan Borodin, Rafail Ostrovsky, Yuval Rabani Z

In the context of an adversarial input model, we consider the e ect on stability results when edges in packet routing networks can have capacities and speeds/slowdowns. In traditional packet routing...

Abstract Subquadratic Approximation Algorithms For Clustering Problems in High Dimensional Spaces (2008)

Allan Borodin, Rafail Ostrovsky, Yuval Rabani Z

One of the central problems in information retrieval, data mining, computational biology, statistical analy-sis, computer vision, geographic analysis, pattern recog-nition, distributed protocols is...

New Techniques for Non-interactive Zero-Knowledge (2008)

Juan A. Garay, Rafail Ostrovsky

Non-interactive zero-knowledge (NIZK) proof systems are fundamental primitives used in many cryptographic constructions, including CCA2-secure cryptosystems, digital signatures, and various...

Abstract (2008)

Secure multi-party computation (MPC) is a central problem in cryptography. Unfortunately, it is well known that MPC is possible if and only if the underlying communication network has very large...

Public key encryption which is simultaneously a locally-decodable errorcorrecting code (2008)

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

Security of Blind Digital Signatures (Revised Extended Abstract) (2008)

Security of Blind Digital Signatures (Revised Extended Abstract) (2008)

Abstract. Blind digital signatures were introduced by Chaum. In this paper, we show how security and blindness properties for blind digital signatures, can be simultaneously defined and satisfied in...

Public Key Encryption with keyword (2008)

Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky

We study the problem of searching on data that is encrypted using a public key system. Consider user Bob who sends email to user Alice encrypted under Alice’s public key. An email gateway wants to...

Identity-Based Zero-Knowledge (2008)

Jonathan Katz, Rafail Ostrovsky, Michael O. Rabin

Abstract. We introduce and define the notion of identity-based zeroknowledge, concentrating on the non-interactive setting. In this setting, our notion allows any prover to widely disseminate a proof...

Private Locally Decodable Codes ∗ (2008)

Rafail Ostrovsky, Omkant Pandey, Amit Sahai

We consider the problem of constructing efficient locally decodable codes in the presence of a computationally bounded adversary. Assuming the existence of one-way functions, we construct efficient...

Zero-Knowledge from Secure Multiparty Computation ∗ ABSTRACT (2008)

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai

We present a general construction of a zero-knowledge proof for an NP relation R(x, w) which only makes a black-box use of a secure protocol for a related multi-party functionality f. The latter...

Error-Correcting Codes for Automatic Control ∗ (2008)

Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman

In many control-theory applications one can classify all possible states of the device by an infinite state graph with polynomially-growing expansion. In order for a controller to control or estimate...

Simple and E cient Leader Election in the Full Information Model (2008)

Rafail Ostrovsky, Sridhar Rajagopalan, Umesh Vazirani

In this paper, we study the leader election problem in the full information model. We show tworesults in this context. First, we exhibit a constructive O(log N) round protocol that is resilient...

Round Complexity of Authenticated Broadcast with a Dishonest Majority ∗ (2008)

Juan A. Garay, Jonathan Katz, Chiu-yuen Koo, Rafail Ostrovsky

Broadcast among n parties in the presence of t ≥ n/3 malicious parties is possible only with some additional setup. The most common setup considered is the existence of a PKI and secure digital...

Matching nuts and bolts (Extended Abstract) (2008)

Moni Naor, Rafail Ostrovsky

Abstract We describe a procedure which may be helpful to any disorganized carpenter who has a mixed pile of bolts and nuts and wants to find the corresponding pairs of bolts and nuts. The procedure...

Robust Non-Interactive Zero Knowledge (2008)

Alfredo De, Santis Giovanni, Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano, Amit Sahai

and Micali in 1988, is a fundamental cryptographic primitive which has attracted considerable attention in the last decade and has been used throughout modern cryptography in several essential ways....

ABSTRACT Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions ∗ (2008)

Reza Curtmola, Juan Garay, Seny Kamara, Rafail Ostrovsky

Searchable symmetric encryption (SSE) allows a party to outsource the storage of its data to another party (a server) in a private manner, while maintaining the ability to selectively search over it....

Abstract Self-Stabilizing Symmetry Breaking in Constant-Space (extended abstract) (2008)

Alain Mayer, Yoram Ofek, Rafail Ostrovsky, Moti Yung

We investigate the problem of self-stabilizing round-robin token management scheme on an anonymous bidirectional ring of identical processors, where each processor is an asynchronous probabilistic...

Abstract (2008)

Joe Kilian Y, Eyal Kushilevitz Z, Silvio Micali X, Rafail Ostrovsky

We de ne the notions of reducibility and completeness in (two party and multi-party) private computations. Let g be an n-argument function. We say that a function f is reducible to a function g if n...

E cient Password-Authenticated Key Exchange Using Human-Memorable Passwords (2008)

Optimal and Efficient Clock Synchronization Under Drifting Clocks (Extended Abstract) (2008)

Abstract. There has been much interest in password-authenticated keyexchange protocols which remain secure even when users choose passwords from a very small space of possible passwords (say, a...

Rafail Ostrovsky, Boaz Patt-Shamir

We consider the classical problem of clock synchronization in distributed systems. Previously, this problem was solved optimally and efficiently only in the case when all individual clocks are...

New Techniques for Non-interactive Zero-Knowledge (2008)

of Distributed Computing (PODC-95) (2008)

Non-interactive zero-knowledge (NIZK) proof systems are fundamental primitives used in many cryptographic constructions, including CCA2-secure cryptosystems, digital signatures, and various...

Rafail Ostrovsky, Daniel Shawcross Wilkerson

We show how an arbitrary strongly-connected directed network of synchronous nite-state automata (with bounded in- and out-degree) can accomplish a number of basic distributed network tasks in O(ND)...

Identity-Based Zero-Knowledge (2008)

Jonathan Katz Rafail, Jonathan Katz, Rafail Ostrovsky, Michael O. Rabin

We introduce and define the notion of identity-based zeroknowledge, concentrating on the non-interactive setting. In this setting, our notion allows any prover to widely disseminate a proof of a...

Concurrent Statistical Zero-Knowledge Arguments (2008)

For Np From, Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky, Amit Sahai

In this paper we show a general transformation from any honest verifier statistical zeroknowledge argument to a concurrent statistical zero-knowledge argument. Our transformation uses only one-way...

The Effectiveness of Lloyd-Type Methods for the k-Means Problem (2008)

Rafail Ostrovsky, Yuval Rabani, Et Al.

We investigate variants of Lloyd's heuristic for clustering high dimensional data in an attempt to explain its popularity (a half century after its introduction) among practitioners, and in...

Circular-Secure Encryption from Decision Diffie-Hellman (2008)

Dan Boneh, Shai Halevi, Mike Hamburg, Rafail Ostrovsky

Let E be a public-key encryption system and let (pk i, ski) be public/private key pairs for E for i = 0,..., n. A natural question is whether E remains secure once an adversary obtains an encryption...

Near-Optimal Energy Consumption for Radio Synchronization (2008)

Milan Bradonjić, Eddie Kohler, Rafail Ostrovsky

In this paper we consider a new model of communication where wireless devices can either switch their radios off to save energy (and hence, can neither send nor receive messages), or switch their...

distance, or with the square of L (2007)

Rafail Ostrovsky, Yuval Rabani, Either L

We deal with the problem of clustering data points. Given n points in a larger set (for example, R d) endowed with a distance function (for example, L 2 distance), we would like to partition the data...

The Las-Vegas Processor Identity Problem (How and When to Be Unique) (2007)

Shay Kutten, Rafail Ostrovsky, Boaz Patt-Shamir

We study the classical problem of assigning unique identifiers to identical concurrent processes. In this paper, we consider the asynchronous shared memory model, and the correctness requirement is...

Micro-Payments via Efficient Coin-Flipping (Extended Abstract) (2007)

R.J. Lipton, R. Ostrovsky, Rafail Ostrovsky

We present an authenticated coin-flipping protocol and its proof of security. We demonstrate the applicability of our scheme for online randomized micro-payment protocols. We also review some...

Yuval Rabani (2007)

Rafail Ostrovsky, Yuval Rabani, Bellcore Technion, C D \delta

In 1988, Leighton, Maggs and Rao proved a much celebrated result: that for any network, given any collection of packets with a specified route for each packet, there exists an "optimal"...

Giovanni Di Crescenzo, Tal Malkin, Rafail Ostrovsky

Abstract. A Single-Database Private Information Retrieval (PIR) is a protocol that allows a user to privately retrieve from a database an entry with as small as possible communication complexity. We...

Work done while the author was at Telcordia Technologies.

3 (2007)

Abstract. A consistent query protocol (CQP) allows a database owner to publish a very short string c which commits her and everybody else to a particular database D, so that any copy of the database...

Work done while at Columbia University Abstract. Password-only authenticated key exchange (PAKE) protocols are designed to be secure even when users choose short, easilyguessed passwords. Security...

Abstract. We consider the round complexity of multi-party computation in the presence of a static adversary who controls a majority of the parties. Here, n players wish to securely compute some...

Abstract. We consider the round complexity of multi-party computation in the presence of a static adversary who controls a majority of the parties. Here, n players wish to securely compute some...

Giovanni Di-crescenzo, Yuval Ishai, Rafail Ostrovsky

Work done while at Columbia University Abstract. Password-only authenticated key exchange (PAKE) protocols are designed to be secure even when users choose short, easilyguessed passwords. Security...

x (2007)

Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, Amit Sahai

We show how to securely realize any two-party and multi-party functionality in a universally composable way, regardless of the number of corrupted participants. That is, we consider an asynchronous...

z (2007)

A private information retrieval scheme allows a user to retrieve a data item of his choice from a remote database (or several copies of a database) while hiding from the database owner which...

Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky, Adam Smith, Telcordia Technologies Inc

Work done while the author was at Telcordia Technologies.

** * Extended Abstract *** (2007)

Rafail Ostrovsky, Victor Shoup

We consider the setting of hiding information through the use of multiple databases that do not interact with one another. In this setting, there are k 2 "databases " which can be...

y (2007)

In this paper we consider the job interval selection problem (JISP), a simple scheduling model with a rich history and numerous applications. Special cases of this problem include the so-called...

The Technion (2007)

Matthias Fitzi, Juan A. Garay, Ueli Maurer, Rafail Ostrovsky

We study the classical problem of assigning unique identiers to identical concurrent processes. In this paper, we consider the asynchronous shared memory model, and the correctness requirement is...

, and (2007)

Abstract. The study of minimal cryptographic primitives needed to implement secure computation among two or more players is a fundamental question in cryptography. The issue of complete primitives...

y (2007)

We study the relationship between the number of rounds needed to repeatedly perform a private computation (i.e., where there are many sets of inputs sequentially given to the players on which the...

Abstract. We show that general one-way trapdoor permutations are sufficient to privately retrieve an entry from a database of size n with total communication complexity strictly less than n. More...

Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky, Adam Smith, Telcordia Technologies Inc

Work done while the author was at Telcordia Technologies.

Abstract. There has been much interest in password-authenticated keyexchange protocols which remain secure even when users choose passwords from a very small space of possible passwords (say, a...

Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky, Adam Smith

Work done while the author was at Telcordia Technologies.

Matthias Fitzi, Juan A. Garay, Ueli Maurer, Rafail Ostrovsky

Abstract. There has been much interest in password-authenticated keyexchange protocols which remain secure even when users choose passwords from a very small space of possible passwords (say, a...

, and (2007)

Abstract. The study of minimal cryptographic primitives needed to implement secure computation among two or more players is a fundamental question in cryptography. The issue of complete primitives...

Instance-Hiding Proof Systems (2007)

Work done while the author was at Telcordia Technologies.

Donald Beaver, Joan Feigenbaum, Rafail Ostrovsky, Victor Shoup

We define the notion of an instance-hiding proof system (ihps) for a function f; informally, an ihps is a protocol in which a polynomial-time verifier interacts with one or more all-powerful provers...

Round Eciency of Multi-Party Computation (2007)

With Dishonest Majority, Jonathan Katz, Rafail Ostrovsky, Adam Smith

We consider the round complexity of multi-party computation in the presence of a static adversary who controls a majority of the parties. Here, n players wish to securely compute some functionality...

Public Key Encryption with keyword (2007)

Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky

We study the problem of searching on data that is encrypted using a public key system. Consider user Bob who sends email to user Alice encrypted under Alice’s public key. An email gateway wants to...

y (2007)

William Aiello, Eyal Kushilevitz, Rafail Ostrovsky

In this paper we prove a perhaps unexpected relationship between the complexity class of the boolean functions that have linear size circuits, and n-party private protocols. Specifically, let f be a...

z (2007)

One of the central tasks of networking is packet-routing when edge bandwidth is limited. Tremendous progress has been achieved by separating the issue of routing into two conceptual sub-problems:...

Succinct Sampling on Streams (2007)

Braverman, Vladimir, Ostrovsky, Rafail, Zaniolo, Carlo

A streaming model is one where data items arrive over long period of time, either one item at a time or in bursts. Typical tasks include computing various statistics over a sliding window of some...

Electronic Colloquium on Computational Complexity, Report No. 21 (2007) Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code (2007)

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

Cryptography in the Multi-string Model (2007)

Jens Groth Rafail, Jens Groth, Rafail Ostrovsky

The common random string model permits the construction of cryptographic protocols that are provably impossible to realize in the standard model. In this model, a trusted party generates a random...

Cryptography in the multi-string model (2007)

Jens Groth, Rafail Ostrovsky

The common random string model introduced by Blum, Feldman and Micali permits the construction of cryptographic protocols that are provably impossible to realize in the standard model. We can think...

Secure two-party k-means clustering (2007)

Paul Bunn, Rafail Ostrovsky

Abstract The k-Means Clustering problem is one of the most-explored prob-lems in data mining to date. With the advent of protocols that have proven to be successful in performing single database...

Attribute-based encryption with non-monotonic access structures (2007)

Rafail Ostrovsky, Amit Sahai, Brent Waters

We construct an Attribute-Based Encryption (ABE) scheme that allows a user’s private key to be expressed in terms of any access formula over attributes. Previous ABE schemes were limited to...

Cryptography in the multi-string model (2007)

Jens Groth, Rafail Ostrovsky

The common random string model introduced by Blum, Feldman and Micali permits the construction of cryptographic protocols that are provably impossible to realize in the standard model. We can think...

Constant-Round Concurrent NMWI and its relation to NMZK (2007)

Rafail Ostrovsky, Ivan Visconti

One of the central questions in Cryptography is to design round-efficient protocols that are secure under man-in-the-middle attacks. In this paper we introduce and study the notion of non-malleable...

Cryptography in the multi-string model (2007)

Jens Groth, Rafail Ostrovsky

The common random string model permits the construction of cryptographic protocols that are provably impossible to realize in the standard model. In this model, a trusted party generates a random...

Secure two-party k-means clustering (2007)

Paul Bunn, Rafail Ostrovsky

The k-Means Clustering problem is one of the most-explored problems in data mining to date. With the advent of protocols that have proven to be successful in performing single database clustering,...

Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data (2006)

Dodis, Yevgeniy, Ostrovsky, Rafail, Reyzin, Leonid, Smith, Adam

We provide formal definitions and efficient secure techniques for - turning noisy information into keys usable for any cryptographic application, and, in particular, - reliably and securely...

ii (2006)

John Joseph Bueti, Rowan B. Killip, Rafail Ostrovsky, Christoph M. Thiele

by

The effectiveness of lloyd-type methods for the k-means problem (2006)

Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy

We investigate variants of Lloyd’s heuristic for clustering high dimensional data in an attempt to explain its popularity (a half century after its introduction) among practitioners, and in order...

The effectiveness of lloyd-type methods for the k-means problem (2006)

Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy

Sequential aggregate signatures and multisignatures without random oracles (2006)

Steve Lu, Rafail Ostrovsky, Amit Sahai

Abstract. We present the first aggregate signature, the first multisignature, and the first verifiably encrypted signature provably secure without random oracles. Our constructions derive from a...

The effectiveness of lloyd-type methods for the k-means problem (2006)

Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy

Abstract (2006)

Steve Lu, Hovav Shacham, Rafail Ostrovsky, Amit Sahai, Brent Waters

We present the first aggregate signature, the first multisignature, and the first verifiably encrypted signature provably secure without random oracles. Our constructions derive from a novel...

Sequential aggregate signatures and multisignatures without random oracles (2006)

Steve Lu, Rafail Ostrovsky, Hovav Shacham

Abstract We present the first aggregate signature, the first multisignature, and the first verifiablyencrypted signature provably secure without random oracles. Our constructions derive from a novel...

Perfect non-interactive zero knowledge for NP (2006)

Abstract. Non-interactive zero-knowledge (NIZK) proof systems are fundamental cryptographic primitives used in many constructions, including CCA2-secure cryptosystems, digital signatures, and various...

Sequential Aggregate Signatures and Multisignatures without Random Oracles (2006)

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai

There is a vast body of work on implementing anonymous communication. In this paper we study the possibility of using anonymous communication as a building block, and show that one can leverage on...

Steve Lu, Rafail Ostrovsky, Amit Sahai, Hovav Shacham, Brent Waters

We present the first aggregate signature, the first multisignature, and the first verifiably encrypted signature provably secure without random oracles. Our constructions derive from a novel...

Searchable Symmetric Encryption: (2006)

Improved Definitions And, Reza Curtmola, Juan Garay, Seny Kamara, Rafail Ostrovsky

Searchable symmetric encryption (SSE) allows a party to outsource the storage of his data to another party in a private manner, while maintaining the ability to selectively search over it. This...

Concurrent Non-Malleable Witness Indistinguishability (2006)

And Its Applications, Rafail Ostrovsky, 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...

Sequential Aggregate Signatures and Multisignatures without Random Oracles (2006)

Steve Lu, Hovav Shacham, Rafail Ostrovsky, Amit Sahai, Brent Waters

We present the first aggregate signature, the first multisignature, and the first verifiably encrypted signature provably secure without random oracles. Our constructions derive from a novel...

Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions (2006)

Reza Curtmola, Juan Garay, Seny Kamara, Rafail Ostrovsky

Searchable symmetric encryption (SSE) allows a party to outsource the storage of its data to another party (a server) in a private manner, while maintaining the ability to selectively search over it....

Perfect Non-Interactive Zero Knowledge for NP (2006)

Jens Groth Rafail, Jens Groth, Rafail Ostrovsky, Amit Sahai

Non-interactive zero-knowledge (NIZK) proof systems are fundamental cryptographic primitives used in many constructions, including CCA2-secure cryptosystems, digital signatures, and various...

Non-interactive Zaps and New Techniques for NIZK (2006)

Jens Groth Rafail, Jens Groth, Rafail Ostrovsky, Amit Sahai

In 2000, Dwork and Naor proved a very surprising result: that there exist "Zaps", tworound witness-indistinguishable proofs in the plain model without a common reference string, where the...

Yuval Ishai Eyal, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai

There is a vast body of work on implementing anonymous communication. In this paper, we study the possibility of using anonymous communication as a building block, and show that one can leverage on...

Public-key encryption that allows PIR queries. Unpublished Manuscript (2006)

Dan Boneh, Eyal Kushilevitz, Rafail Ostrovsky

Non-interactive zaps and new techniques for NIZK (2006)

Perfect non-interactive zero knowledge for NP (2006)

In 2000, Dwork and Naor proved a very surprising result: that there exist “Zaps”, tworound witness-indistinguishable proofs in the plain model without a common reference string, where the...

Efficient and secure authenticated key exchange using weak passwords (2006)

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai

There is a vast body of work on implementing anonymous communication. In this paper, we study the possibility of using anonymous communication as a building block, and show that one can leverage on...

The effectiveness of lloyd-type methods for the k-means problem (2006)

Mutual authentication and authenticated key exchange are fundamental techniques for enabling secure communication over public, insecure networks. It is well-known how to design secure protocols for...

Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy

We investigate variants of Lloyd’s heuristic for clustering high dimensional data in an attempt to explain its popularity (a half century after its introduction) among practitioners, and in order...

Perfect non-interactive zero knowledge for NP (2006)

Public-key encryption that allows PIR queries. Unpublished Manuscript (2006)

Abstract. Non-interactive zero-knowledge (NIZK) proof systems are fundamental cryptographic primitives used in many constructions, including CCA2-secure cryptosystems, digital signatures, and various...

Dan Boneh, Eyal Kushilevitz, Rafail Ostrovsky, Packard Foundation

Consider the following problem: Alice wishes to maintain her email using a storageprovider Bob (such as a Yahoo! or hotmail e-mail account). This storage-provider should provide for Alice the ability...

Sequential aggregate signatures and multisignatures without random oracles (2006)

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai

There is a vast body of work on implementing anonymous communication. In this paper, we study the possibility of using anonymous communication as a building block, and show that one can leverage on...

Abstract (2006)

Steve Lu, Hovav Shacham, Rafail Ostrovsky, Amit Sahai, Brent Waters

We present the first aggregate signature, the first multisignature, and the first verifiably encrypted signature provably secure without random oracles. Our constructions derive from a novel...

Steve Lu, Rafail Ostrovsky, Amit Sahai, Hovav Shacham, Brent Waters

Abstract. We present the first aggregate signature, the first multisignature, and the first verifiably encrypted signature provably secure without random oracles. Our constructions derive from a...

Searchable symmetric encryption: improved definitions and efficient constructions (2006)

Reza Curtmola, Juan Garay, Seny Kamara, Rafail Ostrovsky

Searchable symmetric encryption (SSE) allows a party to outsource the storage of his data to another party in a private manner, while maintaining the ability to selectively search over it. This...

Syndrome Encoding and Decoding of BCH Codes in Sublinear Time Excerpted from Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data (2006)

Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam Smith

We show that the standard decoding algorithm for BCH codes can be modified to run in time polynomial in the length of the syndrome. This works for BCH codes over any field GF (q), which include...

The effectiveness of lloyd-type methods for the k-means problem (2006)

05411 Abstracts Collection -- Anonymous Communication and its Applications (2006)

We investigate variants of Lloyd’s heuristic for clustering high dimensional data in an attempt to explain its popularity (a half century after its introduction) among practitioners, and in order...

Dolev, Shlomi, Pfitzmann, Andreas, Ostrovsky, Rafail

From 09.10.05 to 14.10.05, the Dagstuhl Seminar 05411 ``Anonymous Communication and its Applications'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During...

Low distortion embeddings for edit distance (2005)

Secure remote authentication using biometric data (2005)

We show that {0, 1} d endowed with edit distance embeds into ℓ1 with distortion 2 O( √ log d log log d). We further show efficient implementations of the embedding that yield solutions to various...

Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, Adam Smith

We show two efficient techniques enabling the use of biometric data to achieve mutual authentication or authenticated key exchange over a completely insecure (i.e., adversarially controlled) channel....

General Temrs (2005)

Sufficient Conditions for Collision-Resistant Hashing (2005)

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky

Abstract. We present several new constructions of collision-resistant hash-functions (CRHFs) from general assumptions. We start with a simple construction of CRHF from any homomorphic encryption....

Secure remote authentication using biometric data (2005)

Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, Adam Smith

secret information that can be used incryptographic protocols provided two issues are addressed: (1) biometric data are not uniformly distributed; and (2) they are not exactly reproducible. Recent...

Low Distortion Embeddings for Edit Distance (2005)

Rafail Ostrovsky, Yuval Rabani, Pattern Matching

We show that endowed with edit distance embeds into #1 with distortion 2 . We further show e#cient implementations of the embedding that yield solutions to various computational problems involving...

Secure Remote Authentication Using Biometric Data (2005)

Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, Adam Smith

Biometric data o#er a potential source of high-entropy, secret information that can be used in cryptographic protocols provided two issues are addressed: (1) biometric data are not uniformly...

Perfect Non-Interactive Zero Knowledge for NP (2005)

Jens Groth Rafail, 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...

Secure Remote Authentication Using Biometric (2005)

Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, Adam Smith

Biometrics offer a potential source of high-entropy, secret information. Before such data can be used in cryptographic protocols, however, two issues must be addressed: biometric data (1) are not...

Secure remote authentication using biometric data (2005)

Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, Adam Smith

Abstract. Biometric data offer a potential source of high-entropy, secret information that can be used in cryptographic protocols provided two issues are addressed: (1) biometric data are not...

F.2.2 (2005)

Secure remote authentication using biometric data (2005)

We show that {0,1} d endowed with edit distance embeds into ℓ1 with distortion 2 O( √ log dlog log d). We further show efficient implementations of the embedding that yield solutions to various...

Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, Adam Smith

Biometric data offer a potential source of high-entropy, secret information that can be used in cryptographic protocols provided two issues are addressed: (1) biometric data are not uniformly...

Secure remote authentication using biometric data (2005)

Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, Adam Smith

Biometric data offer a potential source of high-entropy, secret information that can be used in cryptographic protocols provided two issues are addressed: (1) biometric data are not uniformly...

Secure remote authentication using biometric data (2005)

Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, Adam Smith

Abstract. Biometric data offer a potential source of high-entropy, secret information that can be used in cryptographic protocols provided two issues are addressed: (1) biometric data are not...

Round-optimal secure two-party computation (2004)

Jonathan Katz, Rafail Ostrovsky

Abstract. We consider the central cryptographic task of secure twoparty computation, where two parties wish to compute some function of their private inputs (each receiving possibly different...

Efficient Consistency Proofs for Generalized Queries on Committed Database (2004)

Batch Codes and Their Applications (2004)

A consistent query protocol (CQP) allows a database owner to publish a very short string c which commits her and everybody else to a particular database D, so that any copy of the database can later...

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai

A batch code encodes a string x into an m-tuple of strings, called buckets, such that each batch of k bits from x can be decoded by reading at most one (more generally, t) bits from each bucket....

Efficient Consistency Proofs for Generalized Queries on a Committed Database (2004)

Efficient consistency proofs for generalized queries on a committed database (2004)

A consistent query protocol (CQP) allows a database owner to publish a very short string c which commits her and everybody else to a particular database D, so that any copy of the database can later...

Batch codes and their applications (2004)

Abstract. A consistent query protocol (CQP) allows a database owner to publish a very short string c which commits her and everybody else to a particular database D, so that any copy of the database...

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai, From Teradata

A batch code encodes a string x into an m-tuple of strings, called buckets, such that each batch of k bits from x can be decoded by reading at most one (more generally, t) bits from each bucket....

Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data (2004)

Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam Smith

We provide formal definitions and efficient secure techniques for • turning noisy information into keys usable for any cryptographic application, and, in particular, • reliably and securely...

Round-optimal secure two-party computation (2004)

Jonathan Katz, Rafail Ostrovsky

Abstract. We consider the central cryptographic task of secure twoparty computation: two parties wish to compute some function of their private inputs (each receiving possibly different outputs)...

Abstract (2004)

Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data (2004)

A consistent query protocol (CQP) allows a database owner to publish a very short string c which commits her and everybody else to a particular database D, so that any copy of the database can later...

Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam Smith

We provide formal definitions and efficient secure techniques for • turning noisy information into keys usable for any cryptographic application, and, in particular, • reliably and securely...

Batch Codes and Their Applications (2004)

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai

A batch code encodes a string x into an m-tuple of strings, called buckets, such that each batch of k bits from x can be decoded by reading at most one (more generally, t) bits from each bucket....

Dynamic routing on networks with fixed-size buffers (2003)

William Aiello, Rafail Ostrovsky, Eyal Kushilevitz

The combination of the buffer size of routers deployed in the Internet and the Internet traffic itself leads routinely to routers dropping packets. Motivated by this, we initiate the rigorous study...

Round Efficiency of Multi-Party Computation with a Dishonest Majority (2003)

Round Efficiency of Multi-Party Computation with a Dishonest Majority (2003)

Abstract. We consider the round complexity of multi-party computation in the presence of a static adversary who controls a majority of the parties. Here, n players wish to securely compute some...

Dynamic routing on networks with fixed-size buffers (2003)

Abstract. We consider the round complexity of multi-party computation in the presence of a static adversary who controls a majority of the parties. Here, n players wish to securely compute some...

William Aiello, Rafail Ostrovsky, Eyal Kushilevitz

The combination of the buer size of routers deployed in the Internet and the Internet trac itself leads routinely to routers dropping packets. Motivated by this, we initiate the rigorous study of...

Efficient Consistency Proofs on a Committed Database MIT LCS (2003)

Round Efficiency of Multi-Party Computation with a Dishonest Majority (2003)

A consistent query protocol allows a database owner to publish a very short string c which commits her to a particular database D with special consistency property (i.e., given c, every allowable...

Round Efficiency of Multi-Party Computation with a Dishonest Majority (2003)

We consider the round complexity of multi-party computation in the presence of a static adversary who controls a majority of the parties. Here, n players wish to securely compute some functionality...

Universally Composable Two-Party and Multi-Party Secure Computation (2003)

We consider the round complexity of multi-party computation in the presence of a static adversary who controls a majority of the parties. Here, n players wish to securely compute some functionality...

Contents (2003)

Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, Amit Sahai

We show how to securely realize any two-party and multi-party functionality in a universally composable way, regardless of the number of corrupted participants. That is, we consider an asynchronous...

Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, Amit Sahai

We show how to securely realize any two-party and multi-party functionality in a universally composable way, regardless of the number of corrupted participants. That is, we consider an asynchronous...

Dynamic routing on networks with fixed-size buffers (2003)

William Aiello, Rafail Ostrovsky, Eyal Kushilevitz, Adi Rosen

The combination of the bu er size of routers deployed in the Internet and the Internet tra c itself leads routinely to routers dropping packets. Motivated by this, we initiate the rigorous study of...

Round Efficiency of Multi-Party Computation with a Dishonest Majority (2003)

Round Efficiency of Multi-Party Computation with a Dishonest Majority (2003)

We consider the round complexity of multi-party computation in the presence of a static adversary who controls a majority of the parties. Here, n players wish to securely compute some functionality...

Universally composable two-party and multi-party secure computation (2002)

Abstract. We consider the round complexity of multi-party computation in the presence of a static adversary who controls a majority of the parties. Here, n players wish to securely compute some...

Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, Amit Sahai

We show how to securely realize any multi-party functionality in a universally composable way, regardless of the number of corrupted participants. That is, we consider a multi-party network with open...

Universally composable two-party and multi-party secure computation (2002)

Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, Amit Sahai

We show how to securely realize any two-party and multi-party functionality in a universally composable way, regardless of the number of corrupted participants. That is, we consider an asynchronous...

Universally composable two-party and multi-party secure computation (2002)

Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, Amit Sahai

We show how to securely realize any two-party and multi-party functionality in a universally composable way, regardless of the number of corrupted participants. That is, we consider an asynchronous...

One-Way Functions are Essential for Non-Trivial Zero-Knowledge (Extended Abstract) (2002)

Rafail Ostrovsky, Avi Wigderson

Rafail Ostrovsky # Avi Wigderson + April 25, 2002 Abstract It was known that if one-way functions exist, then there are zero-knowledge proofs for every language in . We prove that unless very weak...

Efficient password-authenticated key exchange using human-memorable passwords (2001)

Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems (2001)

Abstract. There has been much interest in password-authenticated keyexchange protocols which remain secure even when users choose passwords from a very small space of possible passwords (say, a...

Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems (2001)

z

Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds (2001)

In this paper we consider the job interval selection problem (JISP), a simple scheduling model with a rich history and numerous applications. Special cases of this problem include the so-called...

Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds (2001)

In the context of an adversarial input model, we consider the effect on stability results when edges in packet routing networks can have capacities and speeds/slowdowns. In traditional packet routing...

Cryptographic counters and applications to electronic voting (2001)

In the context of an adversarial input model, we consider the effect on stability results when edges in packet routing networks can have capacities and speeds/slowdowns. In traditional packet routing...

Minimal complete primitives for secure multi-party computation (2001)

Abstract. We formalize the notion of a cryptographic counter, which allows a group of participants to increment and decrement a cryptographic representation of a (hidden) numerical value privately...

Matthias Fitzi, Juan A. Garay, Ueli Maurer, Rafail Ostrovsky

Abstract. The study of minimal cryptographic primitives needed to implement secure computation among two or more players is a fundamental question in cryptography. The issue of complete primitives...

Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems (2001)

Cryptographic counters and applications to electronic voting (2001)

In this paper we consider the job interval selection problem (JISP), a simple scheduling model with a rich history and numerous applications. Special cases of this problem include the so-called...

One-way trapdoor permutations are sufficient for non-trivial single-server private information retrieval (2000)

Abstract. We formalize the notion of a cryptographic counter, which allows a group of participants to increment and decrement a cryptographic representation of a (hidden) numerical value privately...

Polynomial time approximation schemes for geometric k-clustering (2000)

Abstract. We show that general one-way trapdoor permutations are sufficient to privately retrieve an entry from a database of size n with total communication complexity strictly less than n. More...

Rafail Ostrovsky, Yuval Rabani, Either L

The Johnson-Lindenstrauss lemma states that n points in a high dimensional Hilbert space can be embedded with small distortion of the distances into an O(log n) dimensional space by applying a random...

Randomness versus Fault-Tolerance (2000)

Ran Canetti, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen

We investigate the relations between two major requirements of multiparty protocols: fault tolerance (or resilience) and randomness. Fault-tolerance is measured in terms of the maximum number of...

Rosen: Randomness versus FaultTolerance (2000)

Ran Canetti, Eyal Kushilevitz, Rafail Ostrovsky

We investigate the relations between two major properties of multiparty protocols: fault tolerance (or resilience) and randomness. Fault-tolerance is measured in terms of the maximum number of...

One-way Trapdoor Permutations Are Sufficient for Non-Trivial Single-Server Private Information Retrieval (2000)

Single Database Private Information Retrieval Implies Oblivious Transfer (2000)

We show that general one-way trapdoor permutations are sufficient to privately retrieve an entry from a database of size n with total communication complexity strictly less than n. More specifically,...

Giovanni Di Crescenzo, Tal Malkin, Rafail Ostrovsky

A Single-Database Private Information Retrieval (PIR) is a protocol that allows a user to privately retrieve from a database an entry with as small as possible communication complexity. We call a PIR...

The Las-Vegas Processor Identity Problem (How and When to Be Unique) (2000)

Shay Kutten, Rafail Ostrovsky, Boax Patt-Shamir

of this paper appeared in the Proceedings of the Second Israel Symposium on Theory of Computing Systems, June 1993. 1 Proposed running head: Las-Vegas Processor Identity Problem 2 Abstract We study...

One-way trapdoor permutations are sufficient for non-trivial single-server private information retrieval (2000)

Single database private information retrieval implies oblivious transfer (2000)

We show that general one-way trapdoor permutations are sufficient to privately retrieve an entry from a database of size n with total communication complexity strictly less than n. More specifically,...

Giovanni Di Crescenzo, Tal Malkin, Rafail Ostrovsky

Work done at the Massachusetts Institute of Technology. Abstract. A Single-Database Private Information Retrieval (PIR) is a protocol that allows a user to privately retrieve from a database an entry...

Lower bounds for high dimensional nearest neighbor search and related problems (1999)

On Concurrent Zero-Knowledge with Pre-Processing (1999)

In spite of extensive and continuing research, for various geometric search problems (such as nearest neighbor search), the best algorithms known have performance that degrades exponentially in the...

Giovanni Di Crescenzo, Rafail Ostrovsky

Abstract. Concurrent Zero-Knowledge protocols remain zero-knowledge even when many sessions of them are executed together. These protocols have applications in a distributed setting, where many...

Optimal and Efficient Clock Synchronization under Drifting Clocks (1999)

Rafail Ostrovsky, Boaz Patt-shamir

We consider the classical problem of clock synchronization in distributed systems. Previously, this problem was solved optimally and efficiently only in the case when all individual clocks are...

On Concurrent Zero-Knowledge with Pre-Processing (Extended Abstract) (1999)

Giovanni Di Crescenzo, Rafail Ostrovsky

. Concurrent Zero-Knowledge protocols remain zero-knowledge even when many sessions of them are executed together. These protocols have applications in a distributed setting, where many executions of...

Randomness versus Fault-Tolerance (1999)

Ran Canetti, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén

We investigate the relations between two major properties of multiparty protocols: fault tolerance (or resilience) and randomness. Fault-tolerance is measured in terms of the maximum number of...

Optimal and Efficient Clock Synchronization Under Drifting Clocks (Extended Abstract) (1999)

Rafail Ostrovsky, Boaz Patt-shamir

We consider the classical problem of clock synchronization in distributed systems. Previously, this problem was solved optimally and efficiently only in the case when all individual clocks are...

Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems (1999)

Secure Computation with Honest-Looking Parties: What if nobody is truly honest? (Extended Abstract) (1999)

In spite of extensive and continuing research, for various geometric search problems (such as nearest neighbor search), the best algorithms known have performance that degrades exponentially in the...

Ran Canetti, Rafail Ostrovsky

) Ran Canetti Rafail Ostrovsky y April 28, 1999 Abstract In a secure multi-party computation a set of mutually distrustful parties interact in order to evaluate a pre-defined function of their...

Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems (1999)

Secure Computation with Honest-Looking Parties: (1999)

The curse of dimensionality describes the phenomenon whereby (in spite of extensive and continuing research) for various geometric search problems we only have algorithms with performance that grows...

What If Nobody, Ran Canetti, Rafail Ostrovsky

Ran Canetti Rafail Ostrovsky February 16, 1999 Abstract In a secure multi-party computation a set of mutually distrustful parties interact in order to evaluate a pre-defined function of their inputs,...

Lower bounds for high dimensional nearest neighbor search and related problems (1999)

Allan Borodin, Rafail Ostrovsky

Yuval Rabani z In spite of extensive and continuing research, for various geometric search problems (such as nearest neighbor search), the best algorithms known have performance that degrades...

Conditional oblivious transfer and time-released encryption (1999)

Giovanni Di Crescenzo, Rafail Ostrovsky, S. Rajagopalan

Abstract. We consider the problem of sending messages \into the future." Previous constructions for this task were either based on heuristic assumptions or did not provide anonymity to the...

Secure computation with honest-looking parties: What if nobody is truly honest (1999)

Ran Canetti, Rafail Ostrovsky

In a secure multi-party computation a set of mutually distrustful parties interact in order to evaluate a pre-de ned function of their inputs, without revealing the inputs to each other. In this...

On Concurrent Zero-Knowledge with Pre-Processing (1999)

Giovanni Di Crescenzo, Rafail Ostrovsky

Abstract. Concurrent Zero-Knowledge protocols remain zero-knowledge even when many sessions of them are executed together. These protocols have applications in a distributed setting, where many...

Adaptiv packet routing for bursty adversarial traffic (1998)

William Aiello, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen

One of the central tasks of networking is packet routing when edge bandwidth is limited. Tremendous progress has been achieved by separating the issue of routing into two conceptual subproblems: path...

Amortizing Randomness in Private Multiparty Computations (1998)

Perfect zero-knowledge arguments for NP using any one-way permutation (1998)

We study the relationship between the number of rounds needed to repeatedly perform a private computation (i.e. where there are many sets of inputs sequentially given to the players on which the...

Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung

"Perfect zero-knowledge arguments " is a cryptographic primitive which allows one polynomialtime player to convince another polynomial-time player of the validity of an NP...

Fast digital identity revocation (extended abstract (1998)

William Aiello, Sachin Lodha, Rafail Ostrovsky

author visited Bellcore, also partially supported by DIMACS. 3

Non-interactive and non-malleable commitment (1998)

Giovanni Di Crescenzo, Yuval Ishai, Rafail Ostrovsky

A commitment protocol is a fundamental cryptographic primitive used as a basic building block throughout modern cryptography. In STOC 1991, Dolev Dwork and Naor showed that in many settings the...

Xor-Trees for Efficient Anonymous Multicast and Reception (1998)

Shlomi Dolev, Rafail Ostrovsky

In this work we examine the problem of efficient anonymous broadcast and reception in general communication networks. We show an algorithm which achieves anonymous communication with O(1) amortized...

Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces (1998)

Amortizing Randomness in Private Multiparty Computations (1998)

We address the problem of designing data structures that allow efficient search for approximate nearest neighbors. More specifically, given a database consisting of a set of vectors in some high...

Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén

We study the relationship between the number of rounds needed to repeatedly perform a private computation (i.e., where there are many sets of inputs sequentially given to the players on which the...

The Las-Vegas Processor Identity Problem (How and When to Be Unique) (1998)

Shay Kutten, Rafail Ostrovsky, Boaz Patt-Shamir

We study the problem of assigning unique identifiers to identical concurrent processes. The model considered in this paper is the asynchronous shared memory model, and the correctness requirement is...

Perfect Zero-Knowledge Arguments for (1998)

Can Be Based, Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung

. "Zero-knowledge arguments" is a fundamental cryptographic primitive which allows one polynomial-time player to convince another polynomial-time player of the validity of an NP statement,...

Universal Service-Providers for Database Private Information Retrieval (1998)

Giovanni Di Crescenzo, Yuval Ishai, Rafail Ostrovsky

We consider the question of private information retrieval in the so-called "commoditybased " model. This model was recently proposed by Beaver for practically-oriented service-provider...

Adaptive Packet Routing for Bursty Adversarial Traffic (1998)

William Aiello, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen

One of the central tasks of networking is packet-routing when edge bandwidth is limited. Tremendous progress has been achieved by separating the issue of routing into two conceptual sub-problems:...

Micro-Payments via Efficient Coin-Flipping (Extended Abstract) (1998)

R.J. Lipton, Rafail Ostrovsky

We present an authenticated coin-flipping protocol and its proof of security. We demonstrate the applicability of our scheme for online randomized micro-payment protocols. We also review some...

Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces (1998)

Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces (1998)

We address the problem of designing data structures that allow efficient search for approximate nearest neighbors. More specifically, given a database consisting of a set of vectors in some high...

Computational Complexity and Knowledge Complexity (1998)

We address the problem of designing data structures that allow efficient search for approximate nearest neighbors. More specifically, given a database consisting of a set of vectors in some high...

Adaptive Packet Routing for Bursty Adversarial Traffic (1998)

.<F3.9e+05> We study the computational complexity of languages which have interactive proofs of logarithmic knowledge complexity. We show that all such languages can be recognized...

William Aiello, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen

One of the central tasks of networking is packet-routing when edge bandwidth is limited. Tremendous progress has been achieved by separating the issue of routing into two conceptual sub-problems:...

Perfect zero-knowledge arguments for NP using any one-way permutation (1998)

Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung

Abstract. \Zero-knowledge arguments " is a fundamental cryptographic primitive which allows one polynomial-time player to convince another polynomial-time player of the validity of an NP...

Perfect zero-knowledge arguments for NP using any one-way permutation (1998)

Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung

“Perfect zero-knowledge arguments ” is a cryptographic primitive which allows one polynomial-time player to convince another polynomial-time player of the validity of an NP statement, without...

Efficient search for approximate nearest neighbor in high dimensional spaces (1998)

Adaptive Packet Routing for Bursty Adversarial Traffic (1998)

We address the problem of designing data structures that allow efficient search for approximate nearest neighbors. More specifically, given a database consisting of a set of vectors in some high...

William Aiello, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen

One of the central tasks of networking is packet-routing when edge bandwidth is limited. Tremendous progress has been achieved by separating the issue of routing into two conceptual sub-problems:...

Fast digital identity revocation (extended abstract (1998)

William Aiello, Sachin Lodha, Rafail Ostrovsky

Abstract. The availability of fast and reliable Digital Identities is an essential ingredient for the successful implementation of the public-key infrastructure of the Internet. All digital identity...

Adaptive Packet Routing for Bursty Adversarial Traffic (1998)

William Aiello, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén

One of the central tasks of networking is packet-routing when edge bandwidth is limited. Tremendous progress has been achieved by separating the issue of routing into two conceptual sub-problems:...

Efficient search for approximate nearest neighbor in high dimensional spaces (1998)

Deniable encryption (1997)

Abstract. We address the problem ofdesigning data structures that allow efficient search for approximate nearest neighbors. More specifically, given a database consisting ofa set ofvectors in some...

Ran Canetti, Cynthia Dwork, Moni Naor, Rafail Ostrovsky

Consider a situation in which the transmission of encrypted messages is intercepted by an adversary who can later ask the sender to reveal the random choices (and also the secret key, if one exists)...

Replication is Not Needed: Single Database, Computationally-Private Information Retrieval (1997)

Private Information Storage (Extended Abstract) (1997)

We establish the following, quite unexpected, result: replication of data for the computational Private Information Retrieval problem is not necessary. More specifically, based on the quadratic...

R. Ostrovsky, Rafail Ostrovsky, Victor Shoup, Bellcore Bellcore Ibm

) Rafail Ostrovsky Victor Shoup y Bellcore Bellcore, IBM May 1997 Abstract This paper deals with the problem of efficiently and privately storing and retrieving information that is distributively...

Security of Blind Digital Signatures (1997)

Exte Nd Ed, Ari Juels, Michael Luby, Rafail Ostrovsky

) Ari Juels 1? Michael Luby 2 Rafail Ostrovsky 3 1 RSA Laboratories. Email: ari@rsa.com. 2 Digital Equipment Corporation, 130 Lytton Avenue, Palo Alto, CA 94301-1044. Email: luby@pa.dec.com. 3 Bell...

Private Information Storage (1997)

Extend Ed, Rafail Ostrovsky, Victor Shoup

) Rafail Ostrovsky Victor Shoup y Bellcore Bellcore, IBM Abstract This paper deals with the problem of efficiently and privately storing and retrieving information that is distributively maintained...

Security of Blind Digital Signatures (Extended Abstract) (1997)

Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval (1997)

) Ari Juels 1? Michael Luby 2 Rafail Ostrovsky 3 1 RSA Laboratories. Email: ari@rsa.com. 2 Digital Equipment Corporation, 130 Lytton Avenue, Palo Alto, CA 94301-1044. Email: luby@pa.dec.com. 3 Bell...

Extended Eyal, Eyal Kushilevitz, Rafail Ostrovsky

We establish the following, quite unexpected, result: replication of data for the computational Private Information Retrieval problem is not necessary. More specifically, based on the quadratic...

Randomness versus Fault-Tolerance (1997)

Ran Canetti, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén

We investigate the relations between the fault tolerance (or resilience) and the randomness requirements of multiparty protocols. Fault-tolerance is measured in terms of the maximum number of...

Universal O(congestion + dilation + log^(1+ε) N) Local Control Packet Switching Algorithms (1997)

Rafail Ostrovsky, Yuval Rabani, Bellcore Technion, C D \delta

In 1988, Leighton, Maggs and Rao proved a much celebrated result: that for any network, given any collection of packets with a specified route for each packet, there exists an "optimal "...

Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval (1997)

Private information storage (extended abstract (1997)

We establish the following, quite unexpected, result: replication of data for the computational Private Information Retrieval problem is not necessary. More specifically, based on the quadratic...

Rafail Ostrovsky, Victor Shoup, Bellcore Bellcore Ibm

This paper deals with the problem of e ciently and privately storing and retrieving information that is distributively maintained in several databases that do not communicate with one another. The...

Security of blind digital signatures (extended abstract (1997)

Universal O(congestion + dilation + log 1+ N) Local Control Packet Switching Algorithms (1997)

Abstract. Blind digital signatures were introduced by Chaum. In this paper, we show how security and blindness properties for blind digital signatures, can be simultaneously de ned and satis ed,...

Rafail Ostrovsky, Yuval Rabani, Bellcore Technion

In 1988, Leighton, Maggs and Rao proved a much celebrated result: that for any network, given any collection of packets with a speci ed route for each packet, there exists an \optimal "...

Software Protection and Simulation on Oblivious RAMs (1996)

Oded Goldreich Rafail, Oded Goldreich, Rafail Ostrovsky

Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the...

Software Protection and Simulation on Oblivious RAMs (1996)

Oded Goldreich Rafail, Oded Goldreich, Rafail Ostrovsky

Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the...

Characterizing Linear Size Circuits in Terms of Privacy (1996)

Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén

In this paper we prove a perhaps unexpected relationship between the complexity class of the boolean functions that have linear size circuits, and n-party private protocols. Specifically, let f be a...

The Linear-Array Conjecture in Communication Complexity is False (1996)

Eyal Kushilevitz Nathan, Nathan Linial, Rafail Ostrovsky

A linear array network consists of k + 1 processors P 0 ; P 1 ; : : : ; P k with links only between P i and P i+1 (0 i ! k). It is required to compute some boolean function f(x; y) in this network,...

Deniable Encryption (1996)

Ran Canetti, Cynthia Dwork, Moni Naor, Rafail Ostrovsky

Consider a situation in which the transmission of encrypted messages is intercepted by an adversary who can later ask the sender to reveal the random choices (and also the secret key, if one exists)...

Self-Stabilizing Algorithms for Synchronous Unidirectional Rings (Extended Summary) (1996)

Alain Mayer, Rafail Ostrovsky, Moti Yung

In this work we investigate the notion of built-in faulttolerant (i.e. self-stabilizing) computations on a synchronous uniform unidirectional ring network. Our main result is a protocol-compiler that...

Software Protection and Simulation on Oblivious RAMs (1996)

Oded Goldreich, Rafail Ostrovsky

Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the...

Software Protection and Simulation on Oblivious RAMs (1996)

Oded Goldreich Rafail, Oded Goldreich, Rafail Ostrovsky

Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the...

Software Protection and Simulation on Oblivious RAMs (1996)

Oded Goldreich, Rafail Ostrovsky

Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the...

Perfect Zero-Knowledge Arguments for NP Using any One-Way Permutation (1996)

Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung

"Zero-knowledge arguments" is a cryptographic primitive which allows one polynomialtime player to convince another polynomial-time player of the validity of an NP statement, without...

Deniable Encryption (1996)

Ran Canetti, Cynthia Dwork, Moni Naor, Rafail Ostrovsky

. Consider a situation in which the transmission of encrypted messages is intercepted by an adversary who can later ask the sender to reveal the random choices (and also the secret key, if one...

Characterizing Linear Size Circuits in Terms of Privacy (1996)

Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén

In this paper we prove a perhaps unexpected relationship between the complexity class of the boolean functions that have linear size circuits, and n-party private protocols. Specifically, let f be a...

Deniable Encryption (1996)

Ran Canetti, Cynthia Dwork, Moni Naor, Rafail Ostrovsky

Consider a situation in which the transmission of an encrypted message can be intercepted by an authority, and subsequently (say, in response to court order) the sender can be coerced to reveal the...

Ostrovsky, \The linear-array conjecture in communication complexity is false (1996)

Eyal Kushilevitz, Nathan Linial, Rafail Ostrovsky

LOG-Space Polynomial End-to-End Communication (1995)

Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen

Communication between processors is the essence of distributed computing: clearly, without communication distributed computation is impossible. However, as networks become larger and larger, the...

Faster Computation On Directed Networks of Automata (1995)

Rafail Ostrovsky, Daniel Shawcross Wilkerson

We show how an arbitrary strongly-connected directed network of synchronous finite-state automata (with bounded in- and out-degree) can accomplish a number of basic distributed network tasks in O(ND)...

Log-Space Polynomial End-to-End Communication (1995)

Log-Space Polynomial End-to-End Communication (1995)

Communication between processors is the essence of distributed computing: clearly, without communication distributed computation is impossible. However, as networks become larger and larger, the...

Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen

Communication between processors is the essence of distributed computing: clearly, without communication distributed computation is impossible. However, as networks become larger and larger, the...

Computational complexity and knowledge complexity (1994)

Memory-Efficient and Self-Stabilizing Network RESET (1994)

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 BPP NP Prior to this work,...

Baruch Awerbuch, Rafail Ostrovsky

In this paper we consider the question of fault-tolerant distributed network protocols with extremely small memory requirements per processor. In particular, we show that even in the case of...

Simple and Efficient Leader Election in the Full Information Model (1994)

Rafail Ostrovsky, Sridhar Rajagopalan, Umesh Vazirani

In this paper, we study the leader election problem in the full information model. We show two results in this context. First, we exhibit a constructive O(log N) round protocol that is resilient...

Computational Complexity and Knowledge Complexity (1994)

Matching Nuts and Bolts (Extended Abstract) (1994)

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 BPP NP . Prior to this work,...

Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky

) Noga Alon y Manuel Blum z Amos Fiat x Sampath Kannan -- Moni Naor k Rafail Ostrovsky Abstract We describe a procedure which may be helpful to any disorganized carpenter who has a mixed pile of...

Computational Complexity and Knowledge Complexity (1994)

Oded Goldreich Rafail, 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 BPP NP . Prior to this work,...

Computational Complexity and Knowledge Complexity (1994)

Computational Complexity and Knowledge Complexity (1994)

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 BPP NP . Prior to this work,...

Reducibility and Completeness In Multi-Party Private Computations (1994)

. 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 BPP NP . Prior to this...

Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky

We define the notions of reducibility and completeness in multi-party private computations. Let g be an n-argument function. We say that a function f is reducible to g if n honest-butcurious players...

Matching Nuts and Bolts (1994)

Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky

) Noga Alon Manuel Blum y Amos Fiat z Sampath Kannan x Moni Naor -- Rafail Ostrovsky k Abstract We describe a procedure which may be helpful to any disorganized carpenter who has a mixed pile of...

Memory-Efficient and Self-Stabilizing Network RESET (Extended Abstract) (1994)

Baruch Awerbuch, Rafail Ostrovsky

In this paper we consider the question of fault-tolerant distributed network protocols with extremely small memory requirements per processor. In particular, we show that even in the case of...

Interactive Hashing Simplifies Zero-Knowledge Protocol Design (1993)

Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung

Often the core difficulty in designing zero-knowledge protocols arises from having to consider every possible cheating verifier trying to extract aAditional information. We here consider a compiler...

One-Way Functions are Essential for Non-Trivial Zero-Knowledge (1993)

Exte Nd Ed, Rafail Ostrovsky, Avi Wigderson

) Rafail Ostrovsky y Avi Wigderson z TR-93-073 Novemeber, 1993 Abstract It was known that if one-way functions exist, then there are zero-knowledge proofs for every language in PSPACE. We prove that...

How and When to Be Unique (Extended Abstract) (1993)

Any Non-Private Boolean Function Is Complete For Private Multi-Party Computations (1993)

Shay Kutten y Rafail Ostrovsky z Boaz Patt-Shamir x TR-93-074 November, 1993 Abstract One of the fundamental problems in distributed computing is how identical processors with identical local memory...

Eyal Kushilevitz Silvio, Silvio Micali, Rafail Ostrovsky

Let g be an n-argument boolean function. Suppose we are given a black-box for g, to which n honest-but-curious players can secretly give inputs and it broadcasts the result of operating g on these...

The Las-Vegas Processor Identity Problem (How and When to Be Unique) (Extended Abstract) (1993)

One-Way Functions are Essential for Non-Trivial Zero-Knowledge (Extended Abstract) (1993)

Shay Kutten Rafail Ostrovsky y Boaz Patt-Shamir z T.J. Watson Research Center UC Berkeley and Lab for Computer Science IBM ICSI MIT Abstract One of the fundamental problems in distributed computing...

R. Ostrovsky, Rafail Ostrovsky, Avi Wigderson

) Rafail Ostrovsky y Avi Wigderson z Abstract It was known that if one-way functions exist, then there are zero-knowledge proofs for every language in PSPACE . We prove that unless very weak one-way...

Matching Nuts and Bolts (1993)

Exte Nd Ed, Noga Alon, Manuel Blum, Sampath Kannan, Moni Naor, Rafail Ostrovsky

) Noga Alon y Manuel Blum z Amos Fiat x Sampath Kannan -- Moni Naor k Rafail Ostrovsky TR-93-075 Novemeber, 1993 Abstract We describe a procedure which may be helpful to any disorganized carpenter...

Instance-Hiding Proof Systems (1993)

Donald Beaver, Joan Feigenbaum, Rafail Ostrovsky, Victor Shoup

We define the notion of an instance-hiding proof system (ihps) for a function f ; informally, an ihps is a protocol in which a polynomial-time verifier interacts with one or more all-powerful provers...

Fair games against an all-powerful adversary (1993)

Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung

Suppose that a weak (polynomial time) device needs to interact over a clear channel with a strong (in nitely-powerful) and untrustworthy adversarial device. Assuming the existence of one-way...

The Las-Vegas Processor Identity Problem (How and When to Be Unique (1993)

One-way Functions are Essential for Non-Trivial Zero-Knowledge (1993)

We study the problem of assigning unique identi ers to identical concurrent processes. The model considered in this paper is the asynchronous shared memory model, and the correctness requirement is...

Rafail Ostrovsky, Avi Wigderson

It was known that if one-way functions exist, then there are zero-knowledge proofs for every language in PSPACE. We prove that unless very weak one-way functions exist, Zero-Knowledge proofs can be...

Interactive hashing simplifis zero-knowledge protocol design (Extended Abstract) (1993)

Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung

Often the core difficulty in designing zero-knowledge protocols arises from having to consider every possible cheating verifier trying to extract additional information. We here consider a compiler...

The Las-Vegas Processor Identity Problem (How and When to Be Unique (1993)

The Las-Vegas Processor Identity Problem (How and When to Be Unique (1993)

We study the classical problem of assigning unique identifiers to identical concurrent processes. In this paper, we consider the asynchronous shared memory model, and the correctness requirement is...

Software protection and simulation on oblivious RAMs /--by Rafail M. Ostrovsky. (1992)

One of the fundamental problems in distributed computing is how identical processes with identical local memory can choose unique IDs provided they can flip a coin. The variant considered in this...

Ostrovsky, Rafail.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1992.

Invariant Signatures and Non-Interactive Zero-Knowledge Proofs are Equivalent (1992)

Extended Shafi, Shafi Goldwasser, Rafail Ostrovsky

The standard definition of digital signatures allows a document to have many valid signatures. In this paper, we consider a subclass of digital signatures, called invariant signatures, in which all...

Secure Commitment Against A Powerful Adversary - A security primitive based on average intractability (Extended Abstract) (1992)

Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung

Secure commitment is a primitive enabling information hiding, which is one of the most basic tools in cryptography. Specifically, it is a two-party partial-information game between a...

Self-Stabilizing Symmetry Breaking in Constant-Space (1992)

Extended Alain, Alain Mayer, Yoram Ofek, Rafail Ostrovsky, Moti Yung

We investigate the problem of self-stabilizing round-robin token management scheme on an anonymous bidirectional ring of identical processors, where each processor is an asynchronous probabilistic...

Perfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions (extended abstract) (1992)

Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung

"Zero-knowledge arguments" is a fundamental cryptographic primitive which allows one polynomial-time player to convince another polynomial-time player of the validity of an NP statement,...

1.1.2 Learning by Executing the SH-package............. 5 (1992)

Rafail Ostrovsky

Software protection is one of the most important issues concerning computer practice. There exist many heuristics and ad-hoc methods for protection, but the problem as a whole has not received the...

Noninteractive zero-knowledge (1991)

Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano

Abstract. Non-Interactive Zero Knowledge (NIZK), introduced by Blum, Feldman, and Micali in 1988, is a fundamental cryptographic primitive which has attracted considerable attention in the last...

Noninteractive zero-knowledge (1991)

Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano

Abstract. Non-Interactive Zero Knowledge (NIZK), introduced by Blum, Feldman, and Micali in 1988, is a fundamental cryptographic primitive which has attracted considerable attention in the last...

How To Withstand Mobile Virus Attacks (1991)

Exte Nd Ed, Rafail Ostrovsky, Moti Yung

Rafail Ostrovsky Moti Yung y Abstract We initiate a study of distributed adversarial model of computation in which faults are non-stationary and can move through the network, analogous to a spread of...

Fair Games Against an All-Powerful Adversary (1991)

Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung

Suppose that a weak (polynomial time) device needs to interact over a clear channel with a strong (infinitely-powerful) and untrustworthy adversarial device. Assuming the existence of one-way...

Perfect Zero-Knowledge in Constant Rounds (1990)

Perfect Zero-knowledge, Constant Rounds, Mihir Bellare, Silvio Micali, Rafail Ostrovsky

Quadratic residuosity and graph isomorphism are classic problems and the canonical examples of zero-knowledge languages. However, despite much research effort, all previous zeroknowledge proofs for...

The (True) Complexity of Statistical Zero Knowledge (Extended Abstract) (1990)

Mihir Bellare, Silvio Micali, Rafail Ostrovsky

) Mihir Bellare Silvio Micali y Rafail Ostrovsky z MIT Laboratory for Computer Science 545 Technology Square Cambridge, MA 02139 Abstract Statistical zero-knowledge is a very strong privacy...

On necessary conditions for secure distributed computing (1990)

Rafail Ostrovsky, Moti Yung

What assumptions are required to achieve anunconditionally secure distributed circuit evaluation in a fully connected network? This question was addressed with respect to the allowed number of...

Minimum Resource Zero-Knowledge Proofs (1989)

Joe Kilian, Silvio Micali, Rafail Ostrovsky

) Joe Kilian Silvio Micali y Rafail Ostrovsky z Abstract We consider several resources relating to zero-knowledge protocols: The number of envelopes used in the protocol, the number of oblivious...

Minimum resource zero-knowledge proofs (1989)

Joe Kilian, Silvio Micali, Rafail Ostrovsky

We consider several resources relating to zero-knowledge protocols: The number of envelopes used in the protocol, the number of oblivious transfers protocols executed during the protocol, and the...

Conditional oblivious transfer and timed-release encryption (1592)

Giovanni Di Crescenzo, Rafail Ostrovsky, Sivaramakrishnan Rajagopalan

Abstract. We consider the problem of sending messages “into the future.” Previous constructions for this task were either based on heuristic assumptions or did not provide anonymity to the sender...

Subquadratic Approximation Algorithms For Clustering Problems in High Dimensional Spaces

Interactive Hashing Simplifies Zero-Knowledge Protocol Design

One of the central problems in information retrieval, data mining, computational biology, statistical analysis, computer vision, geographic analysis, pattern recognition, distributed protocols is the...

Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung

Often the core difficulty in designing zero-knowledge protocols arises from having to consider every possible cheating verifier trying to extract additional information. We here consider a compiler...

Invariant Signatures and Non-Interactive Zero-Knowledge Proofs are Equivalent (Extended Abstract)

Shafi Goldwasser, Rafail Ostrovsky

The standard definition of digital signatures allows a document to have many valid signatures. In this paper, we consider a subclass of digital signatures, called invariant signatures, in which all...

One-Way Functions, Hard on Average Problems, and Statistical Zero-Knowledge Proofs (Extended Abstract)

R. Ostrovsky, Rafail Ostrovsky

Rafail Ostrovsky y MIT Laboratory for Computer Science 545 Technology Square, Cambridge, MA 02139 Abstract In this paper, we study connections among one-way functions, hard on the average problems,...

Reducibility and Completeness In Private Computations

Joe Kilian, Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky

We define the notions of reducibility and completeness in (two party and multi-party) private computations. Let g be an n-argument function. We say that a function f is reducible to a function g if n...

Conditional Oblivious Transfer and Timed-Release Encryption

Giovanni Di Crescenzo, Rafail Ostrovsky, S. Rajagopalan

. We consider the problem of sending messages "into the future. " Previous constructions for this task were either based on heuristic assumptions or did not provide anonymity to the sender...

Subquadratic Approximation Algorithms For Clustering Problems in High Dimensional Spaces