January, 2003



Rafail Ostrovsky - Research Summary

My research interests are in the areas of Cryptography and Distributed Algorithms, with a primary focus in Cryptography. My extensive industrial experience has influenced my choice of the type of problems that I work on: my research emphasis has always been on problems that are strongly motivated by their practical significance and their practical applications. I consider both Cryptography and Distributed Algorithms fields exciting to work in, not only due to their practical importance, but also since they are concerned with fundamental issues in computation, including fault-tolerance, randomization, knowledge, and interaction. I intend to continue to work in both fields, improving the efficiency of and our understanding of various protocol problems as well as proving lower bounds for these problems. I often find underlying ties between the techniques and questions of Cryptography and Distributed Algorithms, as both fields address the issues of cooperation and communication. I consider it to be an important effort to bring closer together approaches and tools from both fields.

1  Cryptography and related areas.

With the rapid technological advances in fiber-optic media and fast affordable hardware, the Internet and other communication networks become pervasive. As networks become ever larger and more ubiquitous -- distributed protocols are beginning to play a central role in both the scientific and business environments of today. Hand in hand with these developments come the questions of security, privacy, and fault-tolerance. For example, how do we ensure that distributed computations and protocols are not compromised, that passwords are not broken, or that we can cope with a virus spread or overloaded network traffic? Luckily, cryptography and distributed algorithms provide some of the answers to these fundamental questions. The answers can be evaluated in terms of the assumptions needed, the number of bits of communication required, the number of rounds of interaction, and the running time. The goal, of course, is to minimize the necessary assumptions (or to show that they cannot be further reduced), and to obtain the most efficient solutions. Below, I highlight some topics that I worked on in these fundamental areas.


Private Information Retrieval: In the last several years, I have worked on the problem of communication-efficient retrieval of data from a remote database in such a way that even a database administrator does now know which particular data-item has been retrieved. Disproving a widely held belief in the community, I have shown with Kushilevitz that replication of databases is not necessary for this task [27] (all prior works required replication). I have worked on other extensions and generalizations of this problem [22, 33] as well as connections to other cryptographic primitives [12] and minimal assumptions needed for this problem [13].


Zero-Knowledge: Zero-knowledge interactive proofs, introduced by Goldwasser, Micali and Rackoff, involve two parties, a prover and a verifier, who talk back and forth. The prover tries to convince the probabilistic polynomial time verifier that a given theorem is true (for example, that a CNF formula is satisfiable). A zero-knowledge proof is an interactive proof with an additional privacy constraint: informally, the verifier does not learn why the theorem is true. Zero-knowledge proofs are central to the implementation of any protocol problem with maximum privacy, as was shown by Goldreich, Micali and Wigderson. I have made significant contributions to our understanding of zero-knowledge proofs, including the equivalence between zero-knowledge and one-way functions [47], improving efficiency on various counts (see [60,59,58,55,45]) and showing how to implement the important kind of zero-knowledge (which is called zero-knowledge arguments) based on any one-way permutation [51], resolving a problem which was open since 1986. The latter allows, for example, the implementation of zero-knowledge arguments based on the Data Encryption Standard (DES) [51]. Recently, I have shown that zero-knowledge (as well as other protocols) can be made fully ``composable'' [4].


Software protection: The protection of software against duplication is one of the most important issues in current computing practice. In [52], I described a substantially (i.e. exponentially) faster algorithm then previously known for protecting software (and searching through encrypted data), which I also show in the same paper to be the best possible up to polylogarithmic factors.


Non-malleability. Dolev Dwork and Naor defined in 1991 the important notion of ``non-malleable'' protocols -- essentially protocols that remain secure when multiple copies of the protocols are executed. With several co-authors, I have made a considerable effort in developing non-malleable protocols, including one of the most basic cryptographic building blocks, the so-called ``commitment'' protocols, which are an essential ingredient in zero-knowledge proofs. In particular, I have shown the first non-interactive non-malleable commitment protocol [24] (resolving a problem open since 1991), as well as information-theoretically secure non-malleable commitment [7]. My other works in this area include non-malleable human-memorable password protocols [8] and non-malleable non-interactive Zero-Knowledge proofs which remain ``non-malleable'' even when many theorems are proven [5].


Proactive security: Together with Yung, in 1991 I put forward a model of malicious faults which can spread through the network, analogous to the spread of a virus [56]. Assuming that the detection and infection rates are comparable (i.e., assuming that the virus does not take over the entire network), we show how a distributed network can maintain computation even if a constant fraction of the machines are infected, and even if faults move around. This work was the first to initiate an area of study called proactive security with over 30 papers subsequently written by various researchers on this subject.


Connection between Privacy and Complexity: In [36] we show a surprising connection between the underlying computational complexity of the function and the number of random bits needed to compute it privately: a function has a linear-size circuit if and only if it can be computed privately with a constant number of random bits. (Other connections between randomness and privacy are shown in [29], and in [23]).


Other Work in Cryptography: I have made contributions to the development of other cryptographic primitives as well [19, 21, 54, 53, 50, 48, 43, 3, 40], including deniable encryption [32] and some recent works on secure multiparty computation [17 6, 1] and electronic voting protocols [9].


2  Distributed Computing and Fault-Tolerance.


Fault-tolerant protocols and computations play an important role in distributed networks: as networks (such as the Internet) become larger and larger, the need for distributed algorithms which are resilient against errors is apparent. By examining different types of faults, different questions about fault-tolerance can be studied. I am interested in finding efficient fault-tolerant algorithms resilient against errors in various settings. For brevity, I give here only three of my research directions in this area:


Routing and Distributed Protocols: In [34], with Rabani we show a nearly-optimal (in terms of packet delivery time) randomized routing strategy for arbitrary topology networks, answering the problem posed in 1988 by Leighton, Maggs and Rao. In [26] we give a routing algorithm competitive against bursty adversarial traffic where the algorithm has to choose packet-routes. In [49,41,39,37, 11,2], various questions regarding distributed fault-tolerant protocols are addressed. For example, in a recent paper, we have shown that on overloaded networks (such as the Internet) it is beneficial to study network throughput [2], deriving results that are incomparable with advesarial queuing theory.


Distributed Communication Complexity: In our Combinatorica paper [35] with Kushilevitz and Linial we show that in some distributed protocols an intermediary can help in reducing the cost of communication, disproving a 14 year old conjecture of Tiwari from 1982.


Search problems on High-dimensional data One of the central problems in computational geometry and data-mining protocols is the issue of dealing with high-dimensional data. In computational geometry, many such problems suffer from the so-called ``curse of dimensionality,'' which basically says that work needed to solve the problem grows exponentially with the problem's dimension. The key problem in that space (which many other problems are reducible to) is the problem of ``nearest-neighbor search.'' In [25], with Kushilevitz and Rabani we show a very efficient protocol for solving an approximate version of this fundamental problem, considerably strengthening the previous results of Kleinberg. At the heart of our construction is the new notion of ``distance-preserving dimension reduction'' technique for the Hamming Cube (in a certain range of distances). Our notion of dimension reduction is further sharpened in our recent breakthrough JACM paper with Rabani [14]. (Our dimension-reduction technique is an analog of the celebrated Johnson-Lindenstrauss lemma for the Hamming Cube.) The technique proved to be a powerful new tool with which many high-dimensional problems (such as finding approximate MST [18] or a PTAS for k-clustering [14]) can be solved in high-dimensional spaces. On the lower-bound front, with Borodin and Rabani we showed a lower bound for nearest-neighbor as well as partial-match problems using tools from communication complexity [16].

Publications

[1] Round Efficiency of Multi-Party Computation with a Dishonest Majority
Jonathan Katz, Rafail Ostrovsky, Adam Smith.
 To appear in EUROCRYPT-2003.
[2] Dynamic Routing on Networks with Fixed-Sized Buffers
William Aiello, Rafail Ostrovsky, Eyal Kushilevitz, Adi Rosen
 In proceedings of 2003 Symposium on Discrete Algorithms (SODA-2003)
[3] Forward Security in Password-Only Key Exchange Protocols
Jonathan Katz, Rafail Ostrovsky and Moti Yung,
 In Security in Communication Networks 2002 conference (SCN-2002).
[4] Universally composable two-party and multi-party secure computation.
Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, Amit Sahai
 In The ACM 2002 Symposium on Theory of Computing (STOC-2002) pp. 494-503.
[5] Robust Non-interactive Zero Knowledge.
Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano, Amit Sahai
 In CRYPTO 2001: 566-598.
[6] Minimal Complete Primitives for Secure Multi-party Computation.
Matthias Fitzi, Juan A. Garay, Ueli M. Maurer, Rafail Ostrovsky
 In CRYPTO 2001: 80-100
[7] Efficient and Non-interactive Non-malleable Commitment.
Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky, Adam Smith
 In EUROCRYPT 2001: 40-59.
[8] Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords.
Jonathan Katz, Rafail Ostrovsky, Moti Yung
 In EUROCRYPT 2001: 475-494.
[9] Cryptographic Counters and Applications to Electronic Voting
Jonathan Katz, Steven Myers, Rafail Ostrovsky
 In EUROCRYPT 2001: 78-92.
[10] Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems.
Julia Chuzhoy, Rafail Ostrovsky, Yuval Rabani
 In FOCS 2001: 348-356.
[11] Stability preserving transformations: packet routing networks with edge capacities and speeds.
Allan Borodin, Rafail Ostrovsky, Yuval Rabani
 In SODA 2001: 601-610.
[12] One-Way Trapdoor Permutations Are Sufficient for Non-trivial Single-Server Private Information Retrieval.
Eyal Kushilevitz, Rafail Ostrovsky
 In EUROCRYPT 2000: 104-121.
[13] Single Database Private Information Retrieval Implies Oblivious Transfer
Giovanni Di Crescenzo, Tal Malkin, Rafail Ostrovsky
 In EUROCRYPT 2000: 122-138.
[14] Polynomial Time Approximation Schemes for Geometric k-Clustering.
Rafail Ostrovsky, Yuval Rabani
 Preliminary version in FOCS-2000, Journal version appeared in JACM 49(2): 139-156 (2002).
[15] On Concurrent Zero-Knowledge with Pre-processing
Giovanni Di Crescenzo, Rafail Ostrovsky.
 In CRYPTO-1999: 485-502.
[16] Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems
Allan Borodin, Rafail Ostrovsky and Yuval Rabani
 In Proceedings of The 31'st ACM Symposium on Theory of Computing (STOC-99)
[17] Secure Computation with Honest-Looking Parties: What if Nobody is Truly Honest?
Ran Canetti and Rafail Ostrovsky
 In Proceedings of The 31'st ACM Symposium on Theory of Computing (STOC-99)
[18] Subquadratic Approximation Algorithms For Clustering Problems in High Dimensional Spaces
Allan Borodin, Rafail Ostrovsky and Yuval Rabani
 In Proceedings of The 31'st ACM Symposium on Theory of Computing (STOC-99)
[19] Efficient Timed-release Public-key Encryption
Giovanni Di Crescenzo, Rafail Ostrovsky and S Rajagopalan
 In Proceedings of (EUROCRYPT-99) Springer Verlag.
[20] Optimal and Efficient Clock Synchronization Under Drifting Clocks
Rafail Ostrovsky and Boaz Patt-Shamir
 In Proceedings of Eeighteenth Annual ACM Symposium on Principles of Distributed Computing (PODC-99)
[21] Fast Digital Identity Revocation
William Aiello, Sachin Lodha and Rafail Ostrovsky
 In Proceedings of advances in cryptology, (CRYPTO-98) Springer-Verlag Lecture Notes in Computer Science.
[22] Universal Service-Providers for Database Private Information Retrieval
Giovanni De-Crescenzo, Yuval Ishai and Rafail Ostrovsky
 In Proceedings of Seventeenth Annual ACM Symposium on Principles of Distributed Computing (PODC-98) Journal version in Journal of Cryptology 14(1): 37-74 (2001).
[23] Amortizing Randomness in Private Multiparty Computations
Eyal Kushilevitz, Rafail Ostrovsky and Adi Rosén
 In Proceedings of Seventeenth Annual ACM Symposium on Principles of Distributed Computing (PODC-98)
[24] Non-Interactive and Non-Malleable Commitment
Giovanni Di Crescenzo, Yuval Ishai, and Rafail Ostrovsky
 Appeared in Proceedings of The 30's ACM Symposium on Theory of Computing (STOC-98)
[25] Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
Eyal Kushilevitz, Rafail Ostrovsky and Yuval Rabani
 In Proceedings of The 30's ACM Symposium on Theory of Computing (STOC-98) Journal version in: SIAM J. Comput. 30(2): 457-474 (2000)
[26] Adaptive Packet Routing for Bursty Adversarial Traffic
William Aiello, Eyal Kushilevitz, Rafail Ostrovsky and Adi Rosén
 Appeared in Proceedings of The 30's ACM Symposium on Theory of Computing (STOC-98) Journal version in JCSS 60(3): 482-509 (2000).
[27] Replication Is Not Needed:
Single Database, Computationally-Private Information Retrieval
Eyal Kushilevitz and Rafail Ostrovsky
 In Proceedings of Thirty-eigth Annual IEEE Symposium on the Foundations of Computer Science (FOCS-97)
[28] Micro-Payments via Efficient Coin-Flipping
Richard J. Lipton and Rafail Ostrovsky
 In Proceedings of Second Financial Cryptography Conference, (FINANCIAL CRYPTO-98) February 1998. Lecture Notes in Computer Science LNCS volume 1465
[29] Randomness vs. Fault-Tolerance
Ran Canetti, Eyal Kushilevitz, Rafail Ostrovsky and Adi Rosén
 In Proceedings of Sixteenth Annual ACM Symposium on Principles of Distributed Computing (PODC-97)
[30] Efficient Anonymous Multicast and Reception
Shlomi Dolev and Rafail Ostrovsky
 In Proceedings of advances in cryptology, (CRYPTO-97) Springer-Verlag Lecture Notes in Computer Science. Journal Version in ACM transaction on Information and System Security vol 3., no. 2, pp. 63-84, 2000.
[31] Security of Blind Digital Signatures
Ari Juels, Michael Luby and Rafail Ostrovsky
 In Proceedings of advances in cryptology, (CRYPTO-97) Springer-Verlag Lecture Notes in Computer Science.
[32] Deniable Encryption.
Ran Canetti, Cynthia Dwork, Moni Naor and Rafail Ostrovsky
 In Proceedings of advances in cryptology, (CRYPTO-97) Springer-Verlag Lecture Notes in Computer Science.
[33] Private Information Storage
Rafail Ostrovsky and Victor Shoup
 In Proceedings of The Twenty-Ninth ACM Symposium on Theory of Computing (STOC-97)
[34] Universal O(congestion+dilation+log1+e N) Local Control
Packet Switching Algorithm
Rafail Ostrovsky and Yuval Rabani
 Preliminary version in Proceedings of The Twenty-Ninth ACM Symposium on Theory of Computing (STOC-97)
[35] The Linear-Array Conjecture in Communication Complexity is False.
Eyal Kushilevitz, Nati Linial and Rafail Ostrovsky
 Preliminary version in Proceedings of The Twenty-Eighth ACM Symposium on Theory of Computing (STOC-96) Journal version Accepted to COMBINATORICA.
[36] Characterizing Linear Size Circuits in Terms of Privacy.
Eyal Kushilevitz, Rafail Ostrovsky and Adi Rosén
 Invited paper to the Journal of Computer and System Sciences special issue for STOC 96. Appeared in Vol 58, December 1998, JCSS 58(1): 129-136 (1999). Preliminary version appeared in the Proceedings of The Twenty-Eighth ACM Symposium on Theory of Computing (STOC-96)
[37] Self-Stabilizing Algorithms for Synchronous Unidirectional Rings.
Alain Mayer, Rafail Ostrovsky and Moti Yung
 In Proceedings of Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-96)
[38] Faster Computation On Directed Networks of Automata
Rafail Ostrovsky and Daniel Wilkerson
 In the Proceedings of Fourteenth Annual ACM Symposium on Principles of Distributed Computing (PODC-95) Journal version accepted to Journal of Algorithms, to appear.
[39] LOG-Space Polynomial End-to-End Communication
Eyal Kushilevitz, Rafail Ostrovsky and Adi Rosén
 Preliminary version appeared in the Proceedings of Twenty-seventh ACM Symposium on Theory of Computing (STOC-95) Journal version in SIAM J. Comput. 27(6): 1531-1549 (1998)
[40] Reducibility and Completeness In Multi-Party Private Computations.
Eyal Kushilevitz, Silvio Micali and Rafail Ostrovsky
 In Proceedings of Thirty-fifth Annual IEEE Symposium on the Foundations of Computer Science (FOCS-94) FULL VERSION (jointly with J. Kilian) accepted to SICOMP, appeared in SIAM J. Comput. 29(4): 1189-1208 (2000).
[41] Memory-Efficient and Self-Stabilizing Network RESET.
Baruch Awerbuch and Rafail Ostrovsky
 In Proceedings of Thirteens Annual ACM Symposium on Principles of Distributed Computing (PODC-94)
[42] Simple and Efficient Leader Election In The Full Information Model.
Rafail Ostrovsky, Sridhar Rajagopalan and Umesh Vazirani
 In Proceedings of Twenty-sixth ACM Symposium on Theory of Computing (STOC-94) Montreal, Quebec, Canada, May 23-25, 1994.
[43] Computational Complexity and Knowledge Complexity.
Oded Goldreich, Rafail Ostrovsky and Erez Petrank
Preliminary version appeared in the Twenty-sixth ACM Symposium on Theory of Computing (STOC-94) Full version in SIAM Journal on Computing, 27(4):1116-1141, August 1998.
[44] Matching Nuts and Bolts.
Noga Alon, Manuel Blum, Amos Fiat, Sampath K. Kannan, Moni Naor, and Rafail Ostrovsky
 In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-94)
[45] Interactive Hashing Simplifies Zero-Knowledge Protocol Design.
Rafail Ostrovsky, Ramarathnam Venkatesan and Moti Yung
 In Proceedings of (EUROCRYPT-93) Springer Verlag.
[46] The Las-Vegas Processor Identity Problem.
Shay Kutten, Rafail Ostrovsky and Boaz Patt-Shamir.
In Proceedings of the Second Israel Symposium on Theory of Computing and Systems (ISTCS-93) Journal version submitted to SICOMP. Journal version in J. Algorithms 37(2): 468-494 (2000).
[47] One-Way Functions are Essential for Non-Trivial Zero-Knowledge.
Rafail Ostrovsky and Avi Wigderson
In Proceedings of the second Israel Symposium on Theory of Computing and Systems (ISTCS-93) Received Henry H. Taub Prize and $1,000 Award.
[48] Secure Commitment Against Powerful Adversary:
A Security Primitive based on Average Intractability.
Rafail Ostrovsky, Ramarathnam Venkatesan and Moti Yung.
In Proceedings of 9th Symposium on Theoretical Aspects of Computer Science (STACS-92) (LNCS 577 Springer Verlag Ed. A. Finkel and M. Jantzen) pp. 439-448
[49] Self-Stabilizing Symmetry Breaking in Constant-Space.
Alain Mayer, Yoram Ofek, Rafail Ostrovsky, and Moti Yung
 Proceedings of 24th annual ACM Symposium on Theory of Computing (STOC-92)
[50] Invariant Signatures and Non-Interactive Zero-Knowledge Proofs are Equivalent.
Shafi Goldwasser and Rafail Ostrovsky
 In Proceedings of Advances in Cryptology, (CRYPTO-92) Springer-Verlag Lecture Notes in Computer Science.
[51] Perfect Zero-Knowledge Arguments for NP Can Be Based
on General Complexity Assumptions.
Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan and Moti Yung.
 In Proceedings of advances in cryptology, (CRYPTO-92) Springer-Verlag Lecture Notes in Computer Science. Journal version Appeared in J. of Cryptology, 1988.
[52] Software Protection and Simulation on Oblivious RAMs.
Rafail Ostrovsky
 M.I.T. Ph.D. Thesis, 1992. Preliminary version appeared in Proceedings of 22nd annual ACM Symposium on Theory of Computing (STOC-90) pp. 514-523. Journal version appeared in the Journal of the JACM, Vol. 43, No. 3, May 1996, pp.431-473. written jointly with Oded Goldreich.
[53] A Note On One-Prover, Instance-Hiding Zero-Knowledge Proof Systems.
Joan Feigenbaum and Rafail Ostrovsky
 In Proceedings of the first international symposium in cryptology in Asia (ASIACRYPT'91) Journal version, entitled ``Instance-Hiding Proof Systems'' co-authored with Beaver, Feigenbaum and Shoup submitted to J. of Cryptology.
[54] Fair Games Against an All-Powerful Adversary.
Rafail Ostrovsky, Ramarathnam Venkatesan and Moti Yung.
 Extended abstract in the proceedings of Sequences '91, Positano, Italy. Journal version in AMS DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Vol 13. (Jin-Yi Cai ed.) 1993
[55] One-way Functions, Hard on Average Problems and
Statistical Zero-knowledge Proofs.
Rafail Ostrovsky
In Proceedings of 6 Annual Structure in Complexity Theory Conference (STRUCTURES-91) pp. 51-59.
[56] How to Withstand Mobile Virus Attacks.
Rafail Ostrovsky and Moti Yung.
In Proceedings of 10th annual ACM Symposium on Principles of Distributed Computing (PODC-91)
[57] On Necessary Conditions for Secure Distributed Computation.
Rafail Ostrovsky and Moti Yung.
 In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 2. 1990.
[58] Perfect Zero-Knowledge in Constant Rounds.
Mihir Bellare, Silvio Micali, Rafail Ostrovsky.
 In Proceedings of 22nd annual ACM Symposium on Theory of Computing (STOC-90)
[59] The (True) Complexity of Statistical Zero Knowledge.
Mihir Bellare, Silvio Micali, and Rafail Ostrovsky
 In Proceedings of 22nd annual ACM Symposium on Theory of Computing (STOC-90)
[60] Minimum Resource Zero-Knowledge Proofs.
Joe Kilian, Silvio Micali, Rafail Ostrovsky
 In Proceedings of 30th annual IEEE Symposium on the Foundations of Computer Science (FOCS-89)