Rafail Ostrovsky Publications
(For additional information, especially regarding journal publications, see
DBLP Bibliography Server.)
Color-coding:
security and cryptography papers.
algorithms (non-crypto) papers
-
Yuval Isahi, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
-
Zero-Knowledge from Secure Multiparty Computation
[Abstract]
[ postscript file]
[ pdf file]
In Proceedings of the ACM 2007 Symposim on Theory of Computing (STOC-2007).
-
Rafail Ostrovsky,
Yuval Rabani,
Leonard Schulman, and
Chaitanya Swamy
-
The Effectiveness of Lloyd-Type Methods for the k-Means Problem
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of 47st Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2006).
-
Yuval Isahi, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
-
Cryptography from Anonymity
[Abstract]
[ postscript file]
[ pdf file]
In Proceedings of 47st Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2006).
-
Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky
-
Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of the 13th ACM Conference on Computer and Communications Security (CCS 2006).
-
Jens Groth, Rafail Ostrovsky, Amit Sahai
-
Non-interactive Zaps and New Techniques for NIZK
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of Advances in Cryptology, (CRYPTO-2006) Springer-Verlag/IACR Lecture Notes in Computer Science.
-
Steve Lu, Rafail Ostrovsky, Amit Sahai, Hovav Shacham, and Brent Waters
-
Sequential Aggregate Signatures and Multisignatures Without Random Oracles
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2006)
Springer-Verlag/IACR Lecture Notes in Computer Science.
-
Jens Groth, Rafail Ostrovsky, Amit Sahai
-
Perfect Non-Interactive Zero Knowledge for NP
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2006)
Springer-Verlag/IACR Lecture Notes in Computer Science.
-
Rafail Ostrovsky,
Yuval Rabani,
Leonard Schulman
-
Error-Correcting Codes for Automatic Control
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of 46th Annual IEEE Symposium on the
Foundations of Computer Science (FOCS-2005).
-
Rafail Ostrovsky, William Skeith.
-
Private Searching on Streaming Data
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In addition, you can get a
[powerpoint presentation].
Preliminary version in Proceedings of Advances in Cryptology, (CRYPTO-2005)
Springer-Verlag/IACR Lecture Notes in Computer Science.
-
Rafail Ostrovsky,
Yuval Rabani.
-
Low distortion embeddings for edit distance
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
Preliminary version appeared in STOC '05.
-
Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, Adam Smith.
-
Secure Authentication Using Biometric Data
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2005)
Springer-Verlag/IACR Lecture Notes in Computer Science.
-
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky
-
Sufficient Conditions for Collision-Risistant Hashing
[Abstract]
[paper (postscript file)]
[paper (pdf file)].
In Proceedings of Second
Theory of Cryptography Conference (TCC)
Springer-Verlag Lecture Notes in Computer Science, 2005
-
Jonathan Katz, Rafail Ostrovsky, Michael O. Rabin
-
Indentity-Based Zero-Knowledge
[Abstract]
[paper (postscript file)]
[paper (pdf file)].
In addition, you can get
[SCN-talk (powerpoint)].
In Proceedings of
Security in Communication Networks: 4th International Conference, SCN 2004, Amalfi, Italy, September 8-10, 2004,
Springer-Verlag Lecture Notes in Computer Science.
-
Jonathan Katz, Rafail Ostrovsky
-
Round-Optimal Secure Two-Party Computation
[Abstract]
[paper (postscript file)]
[paper (pdf file)].
In addition, can get
[crypto talk (powerpoint)] or a
[90min talk (powerpoint)].
In Proceedings of Advances in Cryptology, (CRYPTO-2004)
Springer-Verlag/IACR Lecture Notes in Computer Science.
-
Rafail Ostrovsky, Charles Rackoff, Adam Smith
-
Efficient Consistency Proofs for Generalized Queries on a Committed Database
[Abstract]
[ postscript file]
[ pdf file]
In addition, can get
[ICALP powerpoint] talk.
In Proceedings ICALP-2004.
-
Yuval Isahi, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
-
Batch Codes and Their Applications
[Abstract]
[ postscript file]
[ pdf file]
In addition, can get
[powerpoint presentation].
In Proceedings of the ACM 2004 Symposim on Theory of Computing (STOC-2004).
-
Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, Guiseppe Persiano
-
Public Key Encryption with Keyword Search
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2004)
Springer-Verlag/IACR Lecture Notes in Computer Science.
-
Jonathan Katz, Rafail Ostrovsky, Adam Smith
-
Round Efficiency of Multi-Party Computation with a Dishonest Majority
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2003)
Springer-Verlag/IACR Lecture Notes in Computer Science.
-
William Aiello, Rafail Ostrovsky, Eyal Kushilevitz, Adi Rosen
-
Dynamic Routing on Networks with Fixed-Sized Buffers
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
[ SODA talk (pdf file)]
In Proceedings of 2003 SIAM Symposium on Discrete Algorithms (SODA-2003)
-
Jonathan Katz, Rafail Ostrovsky, Moti Yung
-
Forward Security in Password-Only Key Exchange Protocols
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of Security in Communication Networks 2002
conference (CSN-2002)
Springer-Verlag Lecture Notes in Computer Science.
-
Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, Amit Sahai
-
Universally composable two-party and multi-party secure computation.
[Abstract]
[stoc version (postscript file)]
[stoc version (pdf file)]
[full paper (postscript file)]
[full paper (pdf file)]
In Proceedings of the ACM 2002 Symposim on Theory of Computing (STOC-2002), pp. 494-503.
-
Julia Chuzhoy,
Rafail Ostrovsky,
Yuval Rabani.
-
Approximation Algorithms for the Job Interval Selection Problem and
Related Scheduling Problems.
[Abstract]
[ preliminary (postscript file)]
[ full version (pdf file)]
Preliminary version in Proceedings of 42st Annual IEEE Symposium on the
Foundations of Computer Science (FOCS-2001).
Full version accepted to
Journal of Mathematics of Operations Research.
-
Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano, Amit Sahai
-
Robust Non-Interactive Zero Knowledge
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of Advances in Cryptology, (CRYPTO-2001)
Springer-Verlag/IACR Lecture Notes in Computer Science.
-
Matthias Fitzi, Juan A. Garay, Ueli Maurer, Rafail Ostrovsky
-
Minimal Complete Primitives for Secure Multi-Party Computation
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
Journal of Cryptology
Springer-Verlag
Volume 18, Number 1, January 2005
pp.37 - 61.
Preliminary version in
Proceedings of Advances in Cryptology, (CRYPTO-2001)
Springer-Verlag/IACR Lecture Notes in Computer Science.
-
Jonathan Katz, Rafail Ostrovsky, Moti Yung
-
Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of Advances in Cryptology, (EUROCRYPT-2001)
Springer-Verlag/IACR Lecture Notes in Computer Science.
For a non-technical discussion, see
[New Scientist 2001] article regarding this
work.
-
Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky, Adam Smith
-
Efficient and Non-interactive Non-malleable Commitment
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of Advances in Cryptology, (EUROCRYPT-2001)
Springer-Verlag/IACR Lecture Notes in Computer Science.
-
Jonathan Katz, Steven Myers, Rafail Ostrovsky
-
Cryptographic Counters and Applications to Electronic Voting.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of Advances in Cryptology, (EUROCRYPT-2001)
Springer-Verlag/IACR Lecture Notes in Computer Science.
-
Allan Borodin,
Rafail Ostrovsky,
Yuval Rabani.
-
Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of the
Twelfth Annual
ACM-SIAM Symposium on Discrete
Algorithms (SODA-2001).
Full versoin in
Journal of Interconnection Networks, Vol. 5, No. 1, pp. 1-12.
-
Rafail Ostrovsky,
Yuval Rabani.
-
Polynomial Time Approximation Schemes for Geometric k-Clustering.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In addition, you can get a
[powerpoint survey presentation].
In Proceedings of 41st Annual IEEE Symposium on the
Foundations of Computer Science (FOCS-2000).
Journal version in JACM 49(2): 139-156 (2002).
-
Eyal Kushilevitz, Rafail Ostrovsky
-
One-way Trapdoor Permutations Are Sufficient for
Non-Trivial Single-Server Private Information Retrieval
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings
of Advances in Cryptology (EUROCRYPT-2000)
Springer-Verlag
Lecture Notes in Computer Science Vol. 1807, pp. 104-121.
-
Giovanni Di Crescenzo, Tal Malkin, and Rafail Ostrovsky
-
Single Database Private Information Retrieval
Implies Oblivious Transfer
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings
of Advances in Cryptology (EUROCRYPT-2000)
Springer-Verlag
Lecture Notes in Computer Science Vol 1807, pp. 122-138.
-
Giovanni Di Crescenzo and Rafail Ostrovsky
-
On Concurrent Zero-Knowledge with Pre-Processing
[Abstract]
[paper (postscript filqe)]
[paper (pdf file)]
In Proceedings
of Advances in Cryptology (CRYPT0-99), pp. 485-502,
Springer-Verlag
Lecture Notes in Computer Science, Vol 1666.
-
Allan Borodin, Rafail Ostrovsky, Yuval Rabani
-
Lower Bounds for High Dimensional Nearest Neighbor Search
and Related Problems
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
Book Chapter In Discrete and Computational Geometry - The Goodman-Pollack Festschrift. Algorithms and Combinatorics Series 3143, Springer Verlag, Berlin, August 2003, pages 252-274. Preliminary version appeared in STOC '99.
-
Ran Canetti, Rafail Ostrovsky
-
Secure Computation with Honest-Looking Parties
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of
The 31'st ACM Symposium on Theory of Computing (STOC-99)
-
Allan Borodin, Rafail Ostrovsky, Yuval Rabani
-
Subquadratic Approximation Algorithms For Clustering Problems
in High Dimensional Spaces
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In
Proceedings of
The 31'st ACM Symposium on Theory of Computing (STOC-99)
Journal version in Mahine Learning Journal
Special Issue: Theoretical Advances in Data Clustering (Guest Editors: Nina Mishra and Rajeev Motwani)
56 (1-3): 153-167, 2004
-
Giovanni Di Crescenzo, Rafail Ostrovsky, S. Rajagopalan
-
Efficient Timed-release Public-key Encryption
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In
Proceedings of EUROCRYPT-99 Springer Verlag.
-
Rafail Ostrovsky, Boaz Patt-Shamir
-
Optimal and Efficient Clock Synchronization Under Drifting Clocks
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In
Proceedings of Eeighteenth Annual ACM Symposium on
Principles of Distributed Computing (PODC-99)
-
William Aiello, Sachin Lodha, Rafail Ostrovsky
-
Fast Digital Identity Revocation
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings
of advances in cryptology, (CRYPTO-98)
Springer-Verlag Lecture Notes in Computer Science.
-
Giovanni De-Crescenzo,
Yuval Ishai, Rafail Ostrovsky
-
Universal Service-Providers for
Database Private Information Retrieval
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In
Proceedings of Seventeenth Annual ACM Symposium on
Principles of Distributed Computing (PODC-98). Journal
version appears in Journal of Cryptology 14(1): 37-74 (2001).
-
Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen
-
Amortizing Randomness in Private Multiparty Computations
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In
Proceedings of Seventeenth Annual ACM Symposium on
Principles of Distributed Computing (PODC-98)
-
Giovanni Di Crescenzo,
Yuval Ishai, Rafail Ostrovsky
-
Non-Interactive and Non-Malleable Commitment
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of
The 30's ACM Symposium on Theory of Computing (STOC-98)
-
Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani
-
Efficient Search for Approximate Nearest Neighbor in High
Dimensional Spaces
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
SIAM J. Comput. 30(2): 457-474 (2000). Preliminary version in
Proceedings of
The 30's ACM Symposium on Theory of Computing (STOC-98)
-
William Aiello,
Eyal Kushilevitz, Rafail Ostrovsky,
Adi Rosen
-
Adaptive Packet Routing for Bursty Adversarial Traffic
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In
Proceedings of
The 30's ACM Symposium on Theory of Computing (STOC-98).
Journal version appeared in JCSS 60(3): 482-509 (2000).
-
Eyal Kushilevitz, Rafail Ostrovsky
-
Replication Is Not Needed: Single Database,
Computationally-Private Information Retrieval
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In
Proceedings of Thirty-eigth Annual
IEEE Symposium on
the Foundations of Computer Science (FOCS-97)
-
Richard J. Lipton, Rafail Ostrovsky
-
Micro-Payments via Efficient Coin-Flipping
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of Second
Financial Cryptography Conference,
(FINANCIAL CRYPTO-98)
February 1998. Lecture Notes in Computer Science
LNCS volume 1465
-
Ran Canetti, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen
-
Randomness vs. Fault-Tolerance
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In
Proceedings of Sixteenth Annual ACM Symposium on
Principles of Distributed Computing (PODC-97).
Journal version in Journal of Cryptology 13(1): 107-142 (2000).
-
Shlomi Dolev, Rafail Ostrovsky
-
Efficient Anonymous Multicast and Reception
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
Preliminary version in proceedings of advances in cryptology, (CRYPTO-97)
Springer-Verlag Lecture Notes in Computer Science.
Journal version in ACM Trans. Inf. Syst. Secur. 3(2): 63-84 (2000)
-
Ari Juels, Michael Luby, Rafail Ostrovsky
-
Security of Blind Digital Signatures
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of advances in cryptology, (CRYPTO-97)
Springer-Verlag Lecture Notes in Computer Science.
-
Ran Canetti, Cynthia Dwork, Moni Naor, Rafail Ostrovsky
-
Deniable Encryption.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings
of advances in cryptology, (CRYPTO-97) Springer-Verlag
Lecture Notes in
Computer Science.
-
Rafail Ostrovsky, Victor Shoup
-
Private Information Storage
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of
The Twenty-Ninth ACM Symposium on Theory of Computing (STOC-97)
-
Rafail Ostrovsky, Yuval Rabani
-
Universal $O$(congestion$+$dilation$+\log^{1+\epsilon} N$)
Local Control Packet Switching Algorithm
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of
The Twenty-Ninth ACM Symposium on Theory of Computing (STOC-97)
-
Eyal Kushilevitz, Nati Linial, Rafail Ostrovsky
-
The Linear-Array Conjecture in Communication Complexity is False.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
Preliminary version in
Proceedings of
The Twenty-Eighth ACM Symposium on Theory of Computing (STOC-96)
Journal version in Combinatorica 19(2): 241-254 (1999)
-
Eyal Kushilevitz, Rafail Ostrovsky,
Adi Rosen
-
Characterizing Linear Size Circuits in Terms of Privacy.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
Invited paper to the
Journal of Computer and System
Sciences
special issue for STOC 96. In Vol 58, JCSS 58(1): 129-136 (1999).
Preliminary version appeared in the
Proceedings of
The Twenty-Eighth ACM Symposium on Theory of Computing (STOC-96).
-
Alain Mayer, Rafail Ostrovsky, Moti Yung
-
Self-Stabilizing Algorithms for Synchronous Unidirectional Rings.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of
Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA-96)
January 28-30,
Atlanta, Georgia
-
Rafail Ostrovsky, Wilkerson
-
Faster Computation On Directed Networks of Automata
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
Preliminary verion appeared
in the
Proceedings of Fourteenth Annual ACM Symposium on
Principles of Distributed Computing (PODC-95)
Journal version accepted to Journal of Algorithms.
-
Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen
-
LOG-Space
Polynomial End-to-End Communication
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In SIAM Journal of Computing Volume 27, 1998. SIAM J. Comput. 27(6): 1531-1549 (1998).
Preliminary version appeared in the Proceedings of
Twenty-seventh ACM Symposium on Theory of Computing STOC-95
-
Joe Kilian, Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky
-
Reducibility and Completeness In Multi-Party Private Computations.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
Preliminary version appeared in
Proceedings of Thirty-fifth Annual
IEEE Symposium on
the Foundations of Computer Science (FOCS-94).
Journal version in SIAM J. Comput. 29(4): 1189-1208 (2000)
-
Baruch Awerbuch, Rafail Ostrovsky
-
Memory-Efficient and Self-Stabilizing Network RESET.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In
Proceedings of Thirteens Annual ACM Symposium on
Principles of Distributed Computing
(PODC-94)
UCLA, Los Angeles, California,
August 14-17 1994.
-
Rafail Ostrovsky, Sridhar Rajagopalan, Umesh Vazirani
-
Simple and Efficient Leader Election
In The Full Information Model.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of
Twenty-sixth ACM Symposium on Theory of Computing (STOC-94)
-
Oded Goldreich, Rafail Ostrovsky, Erez Petrank
-
Computational Complexity and Knowledge Complexity.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
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.
-
Noga Alon,
Manuel Blum,
Amos Fiat,
Sampath K. Kannan,
Moni Naor,
Rafail Ostrovsky
-
Matching Nuts and Bolts.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of the
Fifth Annual
ACM-SIAM Symposium on Discrete
Algorithms (SODA-94)
January 23-25, 1994, Arlington, Virginia.
-
Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung
-
Interactive Hashing
Simplifies Zero-Knowledge Protocol Design.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of (EUROCRYPT-93) Springer Verlag.
-
Shay Kutten, Rafail Ostrovsky, Boaz Patt-Shamir.
-
The Las-Vegas Processor Identity Problem
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of the Second
Israel Symposium on Theory of Computing and Systems (ISTCS-93)
Journal version appeared in
J. Algorithms 37(2): 468-494 (2000).
-
Rafail Ostrovsky, Avi Wigderson
-
One-Way Functions are Essential for Non-Trivial Zero-Knowledge.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings
of the second Israel Symposium on Theory of Computing and Systems}
(ISTCS-93)
-
Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung.
-
Secure Commitment Against Powerful Adversary:
A Security Primitive based on Average Intractability.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
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
February 13-15 1992, Paris, France.
-
Alain Mayer, Yoram Ofek, Rafail Ostrovsky, Moti Yung
-
Self-Stabilizing Symmetry Breaking in Constant-Space.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In
Proceedings of 24th annual ACM Symposium on
Theory of Computing (STOC-92)
-
Shafi Goldwasser, Rafail Ostrovsky
-
Invariant Signatures and Non-Interactive Zero-Knowledge
Proofs are Equivalent.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings
of Advances in Cryptology (CRYPTO-92)
Springer-Verlag
Lecture Notes in Computer Science.
-
Moni Naor,
Rafail Ostrovsky,
Ramarathnam Venkatesan,
Moti Yung.
-
Perfect Zero-Knowledge Arguments for NP Can Be
Based on General Complexity Assumptions.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
Preliminary version appeared in Proceedings
of advances in cryptology (CRYPTO-92) Springer-Verlag
Lecture Notes in
Computer Science.
Final version appeared in J. of Cryptology, 1988.
-
Rafail Ostrovsky
-
Software Protection and Simulation on Oblivious RAMs.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
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.
Fetch PostScript file of the
JACM paper
Fetch PDF file of the
JACM paper
-
Joan Feigenbaum, Rafail Ostrovsky
-
A Note On One-Prover, Instance-Hiding
Zero-Knowledge Proof Systems.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of the first international symposium in cryptology
in Asia (ASIACRYPT'91)
November 11-14, 1991, Fujsiyoshida, Yamanashi, Japan.
-
Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung
-
Fair Games Against an All-Powerful Adversary.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
Initially presened at DIMACS worksop, 1990.
Extended abstract in the proceedings of Sequences '91,
June 1991,
Positano, Italy.
Journal version in
AMS DIMACS Series in Discrete Mathematics and Theoretical
Computer Science}. Vol 13. (Jin-Yi Cai ed.)
pp. 155-169, 1993.
-
Rafail Ostrovsky
-
One-way Functions, Hard on Average Problems and
Statistical Zero-knowledge Proofs.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In
Proceedings of 6th Annual Structure in Complexity
Theory Conference (STRUCTURES-91)
June 30 -- July 3, 1991, Chicago.
pp. 51-59.
-
Rafail Ostrovsky, Moti Yung.
-
How to Withstand Mobile Virus Attacks.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In
Proceedings of 10th annual ACM Symposium on
Principles of Distributed Computing
(PODC-91)
August 1991, Montreal, Quebec, Canada, pp. 51-59.
-
Rafail Ostrovsky and Moti Yung.
-
On Necessary Conditions for Secure Distributed Computation.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In
DIMACS Series in Discrete Mathematics and Theoretical
Computer Science, Volume 2. 1990.
Proceedings of a DIMACS
workshop, October 4-6, 1989, pp. 229-234.
-
Mihir Bellare, Silvio Micali, Rafail Ostrovsky.
-
Perfect Zero-Knowledge in Constant Rounds.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In
Proceedings of 22nd annual ACM Symposium on
Theory of Computing (STOC-90)
-
Mihir Bellare, Silvio Micali, and Rafail Ostrovsky
-
The (True) Complexity of Statistical Zero Knowledge.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of 22nd annual ACM Symposium on
Theory of Computing (STOC-90)
-
Joe Kilian, Silvio Micali, Rafail Ostrovsky
-
Minimum Resource Zero-Knowledge Proofs.
[Abstract]
[paper (postscript file)]
[paper (pdf file)]
In Proceedings of 30th annual
IEEE Symposium on
the Foundations of Computer Science (FOCS-89)
-
The Lecture Notes of the 2006 graduate Cryptography Course
 
I taught at UCLA
is available in
2006 CRYPTO LECTURE NOTES -- DRAFT