Rafail Ostrovsky Publications
(In Chronological Order)

For additional information, especially regarding journal publications, see DBLP or Google scholar.
You can also search my Publications by Topic.    
Color-coding: Security and cryptography Algorithms

2017
   Steve Lu, Rafail Ostrovsky
Black-Box Parallel Garbled RAM
[Abstract] [pdf]
CRYPTO (2) 2017: 66-92
 
   Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti
Four-Round Concurrent Non-Malleable Commitments from One-Way Functions
[Abstract] [pdf]
CRYPTO (2) 2017: 127-157
 
   Juan A. Garay, Yuval Ishai, Rafail Ostrovsky, Vassilis Zikas
The Price of Low Communication in Secure Multi-party Computation
[Abstract] [pdf]
CRYPTO (1) 2017: 420-446
 
   Shlomi Dolev, Karim Eldefrawy, Juan A. Garay, Muni Venkateswarlu Kumaramangalam, Rafail Ostrovsky, Moti Yung
Brief Announcement: Secure Self-Stabilizing Computation
[Abstract] [pdf]
PODC 2017: 415-417
 
   Saikrishna Badrinarayanan, Dakshita Khurana, Rafail Ostrovsky, Ivan Visconti
Unconditional UC-Secure Computation with (Stronger-Malicious) PUFs
[Abstract] [pdf]
EUROCRYPT (1) 2017: 382-411
 
   Wutichai Chongchitmate, Rafail Ostrovsky
Circuit-Private Multi-key FHE
[Abstract] [pdf]
PKC (2) 2017: 241-270
 
   Rafail Ostrovsky, Yuval Rabani, Arman Yousefi
Matrix Balancing in Lp Norms: Bounding the Convergence Rate of Osborne's Iteration
[Abstract] [pdf]
SODA 2017: 154-169
 
2016
   Nirattaya Khamsemanan, Rafail Ostrovsky, William E. Skeith III
On the Black-box Use of Somewhat Homomorphic Encryption in NonInteractive Two-Party Protocols
[Abstract] [pdf]
SIAM J. Discrete Math. 30(1): 266-295 (2016)
   Brett Hemenway, Zahra Jafargholi, Rafail Ostrovsky, Alessandra Scafuro, Daniel Wichs
Adaptively Secure Garbled Circuits from One-Way Functions
[Abstract] [pdf]
CRYPTO (3) 2016: 149-178
 
   Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti
Concurrent Non-Malleable Commitments (and More) in 3 Rounds
[Abstract] [pdf]
CRYPTO (3) 2016: 270-299
 
   Yuval Ishai, Eyal Kushilevitz, Steve Lu, Rafail Ostrovsky
Private Large-Scale Databases with Distributed Searchable Symmetric Encryption
[Abstract] [pdf]
CT-RSA 2016: 90-107
 
   Ivan Damgård, Jesper Buus Nielsen, Rafail Ostrovsky, Adi Rosén
Unconditionally Secure Computation with Reduced Interaction
[Abstract] [pdf]
EUROCRYPT (2) 2016: 420-447
 
   Richard J. Lipton, Rafail Ostrovsky, Vassilis Zikas
Provably Secure Virus Detection: Using The Observer Effect Against Malware
[Abstract] [pdf]
ICALP 2016: 32:1-32:14
 
   Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky
Coding for Interactive Communication Correcting Insertions and Deletions
[Abstract] [pdf]
ICALP 2016: 61:1-61:14
 
   Mor Baruch, Rafail Ostrovsky, Will Rosenbaum
Brief Announcement: Space-Time Tradeoffs for Distributed Verification
[Abstract] [pdf]
PODC 2016: 357-359
 
   Shlomi Dolev, Karim Eldefrawy, Joshua Lampkins, Rafail Ostrovsky, Moti Yung
Brief Announcement: Proactive Secret Sharing with a Dishonest Majority
[Abstract] [pdf]
PODC 2016: 401-403
 
   David Felber, Rafail Ostrovsky
Variability in Data Streams
[Abstract] [pdf]
PODS 2016: 251-260
 
   Brett Hemenway, Steve Lu, Rafail Ostrovsky, William Welser IV
High-Precision Secure Computation of Satellite Collision Probabilities
[Abstract] [pdf]
SCN 2016: 169-187
 
   Brett Hemenway, Rafail Ostrovsky, Silas Richelson, Alon Rosen
Adaptive Security with Quasi-Optimal Rate
[Abstract] [pdf]
TCC (A1) 2016: 525-541
 
   Shlomi Dolev, Karim El Defrawy, Joshua Lampkins, Rafail Ostrovsky, Moti Yung
Proactive Secret Sharing with a Dishonest Majority
[Abstract] [pdf]
SCN 2016: 529-548
 
2015
   Vladimir Braverman, Rafail Ostrovsky, Gregory Vorsanger
Weighted sampling without replacement from data streams
[Abstract] [pdf]
Inf. Process. Lett. 115(12): 923-926 (2015)
 
   Joshua Baron, Karim El Defrawy, Joshua Lampkins, Rafail Ostrovsky
Communication-Optimal Proactive Secret Sharing for Dynamic Groups
[Abstract] [pdf]
ACNS 2015: 23-41
 
   Vladimir Braverman, Rafail Ostrovsky, Alan Roytman
Zero-One Laws for Sliding Windows and Universal Sketches
[Abstract] [pdf]
APPROX-RANDOM 2015: 573-590
 
   David Felber, Rafail Ostrovsky
A Randomized Online Quantile Summary in O(1/epsilon * log(1/epsilon)) Words
[Abstract] [pdf]
APPROX-RANDOM 2015: 775-785
 
   Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti
Impossibility of Black-Box Simulation Against Leakage Attacks
[Abstract] [pdf]
CRYPTO (2) 2015: 130-149
 
   Sanjam Garg, Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
Cryptography with One-Way Communication
[Abstract] [pdf]
CRYPTO (2) 2015: 191-208
 
   Rafail Ostrovsky, Silas Richelson, Alessandra Scafuro
Round-Optimal Black-Box Two-Party Computation
[Abstract] [pdf]
CRYPTCRYPTO (2) 2015: 339-358
 
   Alwen, Rafail Ostrovsky, Hong-Sheng Zhou, Vassilis Zikas
Incoercible Multi-party Computation and Universally Composable Receipt-Free Voting
[Abstract] [pdf]
CRYPTO (2) 2015: 763-780
 
   Rafail Ostrovsky, Will Rosenbaum
Fast Distributed Almost Stable Matchings
[Abstract] [pdf]
PODC 2015: 101-108
 
   Melissa Chase, Rafail Ostrovsky, Ivan Visconti
Executable Proofs, Input-Size Hiding Secure Computation and a New Ideal World
[Abstract] [pdf]
EUROCRYPT (2) 2015: 532-560
 
   Rafail Ostrovsky, Anat Paskin-Cherniavsky
Locally Decodable Codes for Edit Distance
[Abstract] [pdf]
ICITS 2015: 236-249
 
   Nishanth Chandran, Wutichai Chongchitmate, Juan A. Garay, Shafi Goldwasser, Rafail Ostrovsky, Vassilis Zikas
The Hidden Graph Model:Communication Locality and Optimal Resiliency with Adaptive Faults
[Abstract] [pdf]
ITCS 2015: 153-162
 
   Yannai A. Gonczarowski, Noam Nisan, Rafail Ostrovsky, Will Rosenbaum
A Stable Marriage Requires Communication
[Abstract] [pdf]
SODA 2015: 1003-1017
 
   Sanjam Garg, Steve Lu, Rafail Ostrovsky, Alessandra Scafuro
Garbled RAM From One-Way Functions
[Abstract] [pdf]
STOC 2015: 449-458
 
   Rafail Ostrovsky, Alessandra Scafuro, Muthuramakrishnan Venkitasubramaniam
Resettably Sound Zero-Knowledge Arguments from OWFs - The (Semi) Black-Box Way
[Abstract] [pdf]
TCC (1) 2015: 345-374
 
   Brett Hemenway, Rafail Ostrovsky, Alon Rosen
Non-committing Encryption from Φ-hiding
[Abstract] [pdf]
TCC (1) 2015: 591-608
 
2014
   ask others Farhad Hormozdiari, Jong Wha J. Joo, Akshay Wadia, Feng Guan, Rafail Ostrovsky, Amit Sahai, Eleazar Eskin
Privacy preserving protocol for detecting genetic relatives using rare variants
[Abstract] [pdf]
Bioinformatics 30(12): 204-211 (2014)
 
   Yuval Ishai, Rafail Ostrovsky, Vassilis Zikas
Secure Multi-Party Computation with Identifiable Abort
[Abstract] [pdf]
CRYPTO (2) 2014: 369-386
 
   Rafail Ostrovsky, Anat Paskin-Cherniavsky, Beni Paskin-Cherniavsky
Maliciously Circuit-Private FHE
[Abstract] [pdf]
CRYPTO (1) 2014: 536-553
 
   Craig Gentry, Shai Halevi, Steve Lu, Rafail Ostrovsky, Mariana Raykova, Daniel Wichs
Garbled RAM Revisited
[Abstract] [pdf]
EUROCRYPT 2014: 405-422
 
   Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti
On Input Indistinguishable Proof Systems
[Abstract] [pdf]
ICALP (1) 2014: 895-906
 
   Prabhanjan Ananth, Nishanth Chandran, Vipul Goyal, Bhavana Kanukurthi, Rafail Ostrovsky
Achieving Privacy in Verifiable Computation with Multiple Servers - Without FHE and without Pre-processing
[Abstract] [pdf]
Public Key Cryptography 2014: 149-166
 
   Chongwon Cho, Sanjam Garg, Rafail Ostrovsky
Cross-Domain Secure Computation
[Abstract] [pdf]
Public Key Cryptography 2014: 650-668
 
   Joshua Baron, Karim El Defrawy, Joshua Lampkins, Rafail Ostrovsky
How to withstand mobile virus attacks, revisited
[Abstract] [pdf]
PODC 2014: 293-302
 
   Juan A. Garay, Clinton Givens, Rafail Ostrovsky, Pavel Raykov
Fast and unconditionally secure anonymous channel
[Abstract] [pdf]
PODC 2014: 313-321
 
   Joshua Lampkins, Rafail Ostrovsky
Communication-Efficient MPC for General Adversary Structures
[Abstract] [pdf]
SCN 2014: 155-174
 
   Rafail Ostrovsky, Vanishree Rao, Ivan Visconti
On Selective-Opening Attacks against Encryption Schemes
[Abstract] [pdf]
SCN 2014: 578-597
 
   Ran Gelles, Rafail Ostrovsky, Alan Roytman
Efficient Error-Correcting Codes for Sliding Windows
[Abstract] [pdf]
SOFSEM 2014: 258-268
 
   Vipul Goyal, Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti
Black-box non-black-box zero knowledge
[Abstract] [pdf]
STOC 2014: 515-524
 
   Claudio Orlandi, Rafail Ostrovsky, Vanishree Rao, Amit Sahai, Ivan Visconti
Statistical Concurrent Non-malleable Zero Knowledge
[Abstract] [pdf]
TCC 2014: 167-191
 
   Kai-Min Chung, Rafail Ostrovsky, Rafael Pass, Muthuramakrishnan Venkitasubramaniam, Ivan Visconti
4-Round Resettably-Sound Zero Knowledge
[Abstract] [pdf]
TCC 2014: 192-216
 
   Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky
Locally Updatable and Locally Decodable Codes
[Abstract] [pdf]
TCC 2014: 489-514
 
2013
   Vladimir Braverman, Rafail Ostrovsky
Approximating Large Frequency Moments with Pick-and-Drop Sampling
[Abstract] [pdf]
APPROX-RANDOM 2013: 42-57
 
   Vladimir Braverman, Rafail Ostrovsky
Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams
[Abstract] [pdf]
APPROX-RANDOM 2013: 58-70
 
   Vipul Goyal, Abhishek Jain, Rafail Ostrovsky, Silas Richelson, Ivan Visconti
Constant-Round Concurrent Zero Knowledge in the Bounded Player Model
[Abstract] [pdf]
ASIACRYPT (1) 2013: 21-40
 
   Brett Hemenway, Rafail Ostrovsky
Building Lossy Trapdoor Functions from Lossy Encryption
[Abstract] [pdf]
ASIACRYPT (2) 2013: 241-260
 
   Joshua Baron, Yuval Ishai, Rafail Ostrovsky
On Linear-Size Pseudorandom Generators and Hardcore Functions
[Abstract] [pdf]
Preliminary version appeared in COCOON 2013 pp: 169-181. Full version appeared in Theor. Comput. Sci. 554: 50-63 (2014)
 
   Vladimir Braverman, Ran Gelles, Rafail Ostrovsky
How to Catch L 2-Heavy-Hitters on Sliding Windows
[Abstract] [pdf]
Preliminary version appeared in COCOON 2013 pp: 638-650. Full version appeared in Theor. Comput. Sci. 554: 82-94 (2014)
 
   Matthew K. Franklin, Ren Gelles,Rafail Ostrovsky,Leonard J.Schulman
Optimal Coding for Streaming Authentication and Interactive Communication
[Abstract] [pdf]
Preliminary version appeared in CRYPTO 2013 pp: 258-276. Full version appeared in IEEE Trans. Information Theory 61(1): 133-145 (2015)
 
   Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti, Akshay Wadia
Universally Composable Secure Computation with (Malicious) Physically Uncloneable Functions
[Abstract] [pdf]
EUROCRYPT 2013: 702-718
 
   Steve Lu, Rafail Ostrovsky
How to Garble RAM Programs
[Abstract] [pdf]
EUROCRYPT 2013: 719-734
 
   Kai-Min Chung, Rafail Ostrovsky, Rafael Pass, Ivan Visconti
Simultaneous Resettability from One-Way Function
[Abstract] [pdf]
FOCS 2013: 60-69
 
   Vladimir Braverman, Rafail Ostrovsky, Dan Vilenchik
How Hard Is Counting Triangles in the Streaming Model?
[Abstract] [pdf]
ICALP (1) 2013: 244-254
 
   Brett Hemenway, Rafail Ostrovsky, Mary Wootters
Local Correctability of Expander Codes
[Abstract] [pdf]
Preliminary version appeared in ICALP 2013 pp: 540-551. Full version appeared in Inf. Comput. 243: 178-190 (2015)
 
   Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman
Robust Pseudorandom Generators
[Abstract] [pdf]
ICALP (1) 2013: 576-588
 
   Juan A. Garay, Clint Givens, Rafail Ostrovsky, Pavel Raykov
Broadcast (and Round) Efficient Verifiable Secret Sharing
[Abstract] [pdf]
ICITS 2013: 200-219
 
   Abishek Kumarasubramanian, Rafail Ostrovsky, Omkant Pandey, Akshay Wadia
Cryptography Using Captcha Puzzles
[Abstract] [pdf]
Public Key Cryptography 2013: 89-106
 
   Vipul Goyal, Abhishek Jain, Rafail Ostrovsky, Silas Richelson, Ivan Visconti
Concurrent Zero Knowledge in the Bounded Player Model
[Abstract] [pdf]
TCC 2013: 60-79
 
   Steve Lu, Rafail Ostrovsky
Distributed Oblivious RAM for Secure Two-Party Computation
[Abstract] [pdf]
TCC 2013: 377-396
 
   Rafail Ostrovsky, Vanishree Rao, Alessandra Scafuro, Ivan Visconti
Revisiting Lower and Upper Bounds for Selective Decommitments
[Abstract] [pdf]
TCC 2013: 559-578
 
   Paul Bunn, Rafail Ostrovsky
Secure End-to-End Communication with Optimal Throughput and Resilience against Malicious Adversary
[Abstract] [pdf]
DISC 2013: 403-417
 
2012
   Sanjam Garg, Abishek Kumarasubramanian, Rafail Ostrovsky, Ivan Visconti
Impossibility Results for Static Input Secure Computation
[Abstract] [pdf]
CRYPTO 2012: 424-442
 
   Eli Ben-Sasson, Serge Fehr, Rafail Ostrovsky
Near-Linear Unconditionally-Secure Multiparty Computation with a Dishonest Minority
[Abstract] [pdf]
CRYPTO 2012: 663-680
 
   Alfonso Cevallos, Serge Fehr, Rafail Ostrovsky, Yuval Rabani
Unconditionally-Secure Robust Secret Sharing with Compact Shares
[Abstract] [pdf]
EUROCRYPT 2012: 195-208
 
   Joshua Baron, Rafail Ostrovsky, Ivan Visconti
Nearly Simultaneously Resettabe Black-Box Zero Knowledge
[Abstract] [pdf]
ICALP 2012: 88-99
 
   Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky
Edge Fault Tolerance on Sparse Networks
[Abstract] [pdf]
ICALP 2012: 452-463
 
   Ran Gelles, Rafail Ostrovsky, Kina Winoto
Multiparty Proximity Testing with Dishonest Majority from Equality Testing
[Abstract] [pdf]
ICALP 2012: 537-548
 
   Brett Hemenway, Rafail Ostovsky
On Homomorphic Encryption and Chosen-Ciphertext Security
[Abstract] [pdf]
Public Key Crypotgraphy 2012: 52-65
 
   Brett Hemenway, Steve Lu, Rafail Ostrovsky
Correlated Product Security from Any One-Way Function
[Abstract] [pdf]
Public Key Cryptography 2012: 558-575
 
   Brett Hemenway, Rafail Ostovsky
Extended-DDH and Lossy Trapdoor Functions
[Abstract] [pdf]
Public Key Crypotgraphy 2012: 627-643
 
   Joshua Baron, Karim El Defawy, Kirill Minkovich, Rafail Ostrovsky, Eric Tressler
5PM: Secure Pattern Matching
[Abstract] [pdf]
Preliminary version appeared in SCN 2012 PP: 222-240. Full version appeared in Journal of Computer Security 21(5): 601-625 (2013)
 
   Eyal Kushilevitz, Steve Lu, Rafail Ostrovsky
On the (In)security of Hash-Based Oblivious RAM and a New Balancing Scheme
[Abstract] [pdf]
SODA 2012: 143-156
 
   Yuval Ishai, Rafail Otrovsky, Hakan Seyalioglu
Identifying Cheaters without an Honest Majority
[Abstract] [pdf]
TCC 2012: 21-38
 
   Sanjam Garg, Rafail Ostrovsky, Ivan Visconti, Akshay Wadia
Resettable Statistical Zero Knowledge
[Abstract] [pdf]
TCC 2012: 494-511
 
   Chongwon Cho, Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti
Simultaneously Resettable Arguments of Knowledge
[Abstract] [pdf]
TCC 2012: 530-547
 
   Vipul Goyal, Chen-Kuei Lee, Rafail Ostrovsky, Ivan Visconti
Constructing Non-malleable Commitments: A Black-Box Approach
[Abstract] [pdf]
FOCS 2012: 51-60
 
2011
   Bret Hemenway, Rafail Ostrovsky, Martin J. Strauss, Mary Wooters
Public Key Locally Decodable Codes with Short Keys
[Abstract] [pdf]
APPROX-RANDOM 2011: 605-615
 
   Brett Hemenway, Benoît Libert, Rafail Ostrovsky, Damien Vergnaud
Lossy Encryption: Constructions from General Assumptions and Efficient Selective Opening Chosen Ciphertext Security
[Abstract] [pdf]
ASIACRYPT 2011: 70-88
 
   Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schafner
Position-Based Quantum Cryptography: Impossibility and Constructions
[Abstract] [pdf]
Preliminary version appeared in Crypto 2011:429-446.Full version appeared in SIAM J. Comput. 43(1): 150-178 (2014)
 
   Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, Jurg Wullschleger
Constant-Rate Oblivious Transfer from Noisy Channels
[Abstract] [pdf]
CRYPTO 2011: 667-684
 
   Leonid Barenboim, Shlomi Dolev, Rafail Ostrovsky
Deterministic and Energy-Optimal Wireless Synchronization
[Abstract] [pdf]
Preliminary version appeared in DISC 2011:237-251. Full version appeared in TOSN 11(1): 13:1-13:25 (2014)
 
   Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai
Efficient Non-interactive Secure Computation
[Abstract] [pdf]
EUROCRYPT 2011: 406-425
 
   Juan A. Garay, Clint Givens, Rafail Ostovsky
Secure Message Transmission by Public Discussion: A Brief Survey
[Abstract] [pdf]
Preliminary version appeared in IWCC 2011:126-141 IEEE Trans. Full version appeared in Information Theory 60(4): 2373-2390 (2014)
 
   Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, Brian Tagiku
Streaming k-means on Well-Clusterable Data
[Abstract] [pdf]
SODA 2011: 26-40
 
2010
   Vladimir Braverman, Rafail Ostrovsky
Effective Computations on Sliding Windows
[Abstract] [pdf]
SIAM J. Comput. 39(6): 2113-2131 (2010)
 
   Vipul Goyal, Abhishek Jan, Rafail Ostrovsky
Passward-Authenticated Session-Key Generation on the Internet in Plain Model
[Abstract] [pdf]
Preliminary version appeared in Crypto 2010: 277-294. Full version appeared in J. ACM 57(1): 3:1-3:39 (2009)
 
   Chongwon Cho, Chen-Kuei Lee, Rafail Ostrovsky
Equivalence of Uniform Key Agreement and Composition Insecurity
[Abstract] [pdf]
CRYPTO 2010: 447-464
 
   Juan A. Garay, Clint Givens, Rafail Ostrovsky
Secure Message Transmission with Small Public Discussion
[Abstract] [pdf]
Preliminary version appeared in Eurocrypt 2010:177-196. Full version appeared in IEEE Trans. Information Theory 60(4): 2373-2390 (2014)
 
   Nishanth Chandran, Rafail Ostrovsky, Willim E. Skeith III
Public Encryption with Efficient Amortized Updates
[Abstract] [pdf]
SCN 2010: 17-35
 
   Paul Bunn, Rafail Ostrovsky
Asynchronous Throughput-Optimal Routing in Malicious Networks
[Abstract] [pdf]
ICALP 2010: 236-248
 
   Nishanth Chandran, Jual A. Garay, Rafail Ostrovsky
Improved Fault Tolerance and Secure Computation on Sparse Networks
[Abstract] [pdf]
ICALP (2) 2010: 249-260
 
   Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin
Privacy Amplification with Asymptotically Optimal Entropy Loss
[Abstract] [postscript] [pdf]
Preliminary version appeared in STOC 2010. Full version appeared in IEEE Trans. Information Theory 60(4): 2373-2390 (2014)
 
   Vladimir Braverman, Rafail Ostrovsky
Measuring Independence of Datasets
[Abstract] [postscript] [pdf]
Preliminary version in STOC 2010.271-280
 
   Vladimir Braverman, Rafail Ostrovsky
Zero-One Frequency Laws
[Abstract] [postscript] [pdf]
Preliminary version in STOC 2010. 281-290
 
   Rafail Ostrovsky, Omkant Pandey, Ivan Visconti
Efficiency Preserving Transformations for Concurrent Non-Malleable Zero Knowledge
[Abstract] [postscript] [pdf]
Preliminary version in TCC 2010: 535-552
 
   S.Dov Gordon, Yuval Ishai, Tal Moran, Rafail Ostrovsky, Amit Sahai
On Complete Primitives for Fairness
[Abstract] [postscript] [pdf]
Preliminary version in TCC 2010: 91-108
 
   Vladimir Braverman, Kai-Min Chung, Zhenming Liu, Michael Mitzenmacher, Rafail Ostrovsky
AMS Without 4-Wise Independence on Product Domains
[Abstract] [postscript] [pdf]
STACS-2010
(This paper is the result of a merge. For historical reasons, and for slightly different proofs, see:
Vladimir Braverman, Rafail Ostrovsky AMS Without 4-Wise Independence on Product Domains, September 17, 2009.); and
Vladimir Braverman, Rafail Ostrovsky Meassuring k-Wise Indepedence of Streaming Data, June 29, 2008. 119-130
 
2009
   Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
Extracting Corrolations
[Abstract] [postscript] [pdf]
Preliminary version in FOCS 2009: 261-270
 
   Nishanth Chandran, Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky
Postion Based Cryptography
[Abstract] [postscript] [pdf]
CRYPTO-2009. 391-407 (In addition, you can get [ppt].)
 
   Milan Bradonjic, Eddie Kohler, and Rafail Ostrovsky
Near-Optimal Radio Use For Wireless Network Synchronization
[Abstract] [postscript] [pdf]
ALGOSENSORS-2009. 15-28 (In addition, you can get [talk slides].)
 
   Vladimir Braverman, Rafail Ostrovsky, Carlo Zaniolo
Optimal Sampling from Sliding Windows
[Abstract] [postscript] [pdf]
(PODS-2009) 147-156
 
   Yair Amir, Paul Bunn, Rafail Ostrovsky
Authenticated Adversarial Routing
[Abstract] [postscript] [pdf]
(TCC-2009) 163-182 (In addition, you can get [ppt].)
 
   Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti
Simulation-Based Concurrent Non-Malleable Commitments and Decommitments
[Abstract] [postscript] [pdf]
(TCC-2009) 91-108
 
2008
   Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Mohammad Ali Safari, Amit Sahai
Improved algorithms for optimal embeddings
[Abstract] [pdf]
ACM Trans. Algorithms 4(4): 45:1-45:14 (2008)
 
   Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam D. Smith
Circular-Secure Encryption from Decision Diffie-Hellman
[Abstract] [pdf]
SIAM J. Comput. 38(1): 97-139 (2008)
 
   Dan Boneh, Shai Halevi, Michael Hamburg, Rafail Ostrovsky
Circular-Secure Encryption from Decision Diffie-Hellman
[Abstract] [postscript] [pdf]
CRYPTO 2008: 108-125 (See an informal description of the result in CS 2008 Annual Report).
 
   Brett Hemenway, Rafail Ostrovsky
Public-Key Locally-Decodable Codes
[Abstract] [postscript] [pdf]
CRYPTO 2008: 126-143
 
   Rafail Ostrovsky, William E. Skeith III
Communication Complexity in Algebraic Two-Party Protocols
[Abstract] [postscript] [pdf]
CRYPTO 2008: 379-396
 
   Steve Lu, Daniel Manchala, Rafail Ostrovsky
Visual Cryptography on Graphs
[Abstract] [postscript] [pdf]
Preliminary version appeared in COCOON 2008: 225-234.
Given COCOON-08 Best Paper Award. and invited to the special issue of Journal of Combinatorial Optimization for COCOON'08.
 
   Juan A. Garay, Rafail Ostrovsky
Almost-Everywhere Secure Computation
[Abstract] [postscript] [pdf]
EUROCRYPT 2008: 307-323
 
   Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti
Constant-Round Concurrent Non-malleable Zero Knowledge in the Bare Public-Key Model
[Abstract] [postscript] [pdf]
ICALP 2008: 548-559
 
   Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
Cryptography with constant computational overhead
[Abstract] [postscript] [pdf]
Preliminary version in STOC 2008: 433-442
 
   Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Mohammad Ali Safari, Amit Sahai
Improved algorithms for optimal embeddings
[Abstract] [postscript] [pdf]
ACM Transactions on Algorithms 4(4): (2008)
 
   Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam Smith
Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
[Abstract] [postscript] [pdf]
SIAM J. Comput. 38(1): 97-139 (2008)
 
2007
   Dan Boneh, Eyal Kushilevitz, Rafail Ostrovsky, William E. Skeith III
Public Key Encryption That Allows PIR Queries
[Abstract] [postscript] [pdf]
Preliminary version appeared in CRYPTO 2007: 50-67
 
   Jens Groth, Rafail Ostrovsky
Cryptography in the Multi-string Model
[Abstract] [postscript] [pdf]
Preliminary version appeared in CRYPTO 2007: 323-341
 
   Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky, Amit Sahai
Covert Multi-Party Computation
[Abstract] [postscript] [pdf]
Preliminary version appeared in FOCS 2007: 238-248
 
   Vladimir Braverman, Rafail Ostrovsky
Smooth Histograms for Sliding Windows
[Abstract] [postscript] [pdf]
Preliminary version appeared in FOCS 2007: 283-293
 
   Juan A. Garay, Jonathan Katz, Chiu-Yuen Koo, Rafail Ostrovsky
Round Complexity of Authenticated Broadcast with a Dishonest Majority
[Abstract] [postscript] [pdf]
Preliminary version appeared in FOCS 2007: 658-668
 
   Rafail Ostrovsky, Omkant Pandey, Amit Sahai
Private Locally Decodable Codes
[Abstract] [postscript] [pdf]
Preliminary version appeared in ICALP 2007: 387-398
 
   Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky
Efficient Arguments without Short PCPs
[Abstract] [postscript] [pdf]
Preliminary version appeared in IEEE Conference on Computational Complexity 2007: 278-291 (ECCC-2007)
 
   Rafail Ostrovsky, William Skeith
A Survey of Single-Database Private Information Retrieval: Techniques and Applications
[Abstract] [postscript] [pdf]
Preliminary version appeared in Proceedings of the Public Key Cryptography 2007 conference, pp. 393-411. (PKC-2007). Full version appeared as a book chapter in "Homeland Security Technology Challenges From Sensing and Encrypting to Mining and Modeling", Franceschetti, Giorgio and Grossi, Marina (EDT), Artec-House publishers.
 
   Yuval Isahi, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
Zero-Knowledge from Secure Multiparty Computation
[Abstract] [postscript] [pdf]
In Proceedings of the ACM 2007 Symposim on Theory of Computing (STOC-2007)21-30. Full version invited and accepted to SIAM Journal of Computing (SICOMP) special issue devoted to STOC-2007.
 
   Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky, Amit Sahai
Concurrent Statistical Zero-Knowledge Arguments for NP from One Way Functions
[Abstract] [postscript] [pdf]
ASIACRYPT 2007: 444-459
 
   Rafail Ostrovsky, Amit Sahai, Brent Waters
Attribute-based encryption with non-monotonic access structures
[Abstract] [postscript] [pdf]
ACM Conference on Computer and Communications Security 2007: 195-203 (CCS-2007)
 
   Paul Bunn, Rafail Ostrovsky
Secure two-party k-means clustering
[Abstract] [postscript] [pdf]
ACM Conference on Computer and Communications Security 2007: 486-497 (CCS-2007)
 
2006
   Rafail Ostrovsky, Yuval Rabani, Leonard Schulman, and Chaitanya Swamy
The Effectiveness of Lloyd-Type Methods for the k-Means Problem
[Abstract] [postscript] [pdf]
In Proceedings of 47st Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2006)165-176.
 
   Yuval Isahi, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
Cryptography from Anonymity
[Abstract] [postscript] [pdf]
In Proceedings of 47st Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2006)239-248.
 
   Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky
Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions
[Abstract] [postscript] [pdf]
In Proceedings of the 13th ACM Conference on Computer and Communications Security (CCS 2006)79-88.
 
   Jens Groth, Rafail Ostrovsky, Amit Sahai
Non-interactive Zaps and New Techniques for NIZK
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Cryptology, (CRYPTO-2006)97-111 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] [postscript] [pdf]
In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2006)465-485 Springer-Verlag/IACR Lecture Notes in Computer Science.
 
   Jens Groth, Rafail Ostrovsky, Amit Sahai
Perfect Non-Interactive Zero Knowledge for NP
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2006)339-358 Springer-Verlag/IACR Lecture Notes in Computer Science.
 
2005
   Rafail Ostrovsky, Yuval Rabani, Leonard Schulman
Error-Correcting Codes for Automatic Control
[Abstract] [postscript] [pdf]
In Proceedings of 46th Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2005)309-316.
 
   Rafail Ostrovsky, William Skeith
Private Searching on Streaming Data
[Abstract] [postscript] [pdf]
Preliminary version in Proceedings of Advances in Cryptology, (CRYPTO-2005)223-240 Springer-Verlag/IACR Lecture Notes in Computer Science. Full version appeared in Journal of Cryptology Volume 20:4, pp. 397-430, October 2007.
 
   Rafail Ostrovsky, Yuval Rabani
Low distortion embeddings for edit distance
[Abstract] [postscript] [pdf]
Preliminary version appeared in STOC '05. Full version in J. ACM 54(5): 2007.
 
   Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, Adam Smith
Secure Authentication Using Biometric Data
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2005)147-163 Springer-Verlag/IACR Lecture Notes in Computer Science.
 
   Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky
Sufficient Conditions for Collision-Risistant Hashing
[Abstract] [postscript] [pdf].
In Proceedings of Second Theory of Cryptography Conference (TCC 2005) 445-456 Springer-Verlag Lecture Notes in Computer Science, 2005
 
2004
   Jonathan Katz, Rafail Ostrovsky, Michael O. Rabin
Indentity-Based Zero-Knowledge
[Abstract] [postscript] [pdf]. In addition, you can get [SCN-talk (powerpoint)].
In Proceedings of Security in Communication Networks: 4th International Conference, (SCN 2004) 180-192, Amalfi, Italy, September 8-10, 2004, Springer-Verlag Lecture Notes in Computer Science.
 
   Jonathan Katz, Rafail Ostrovsky
Round-Optimal Secure Two-Party Computation
[Abstract] [postscript] [pdf].
In addition, can get [crypto talk (powerpoint)] or a [90min talk (powerpoint)].
In Proceedings of Advances in Cryptology, (CRYPTO-2004)335-354 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] [pdf] In addition, can get [ICALP powerpoint] talk.
In Proceedings (ICALP-2004)1041-1053.
 
   Yuval Isahi, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
Batch Codes and Their Applications
[Abstract] [postscript] [pdf] In addition, can get [powerpoint presentation].
In Proceedings of the ACM 2004 Symposim on Theory of Computing (STOC-2004)262-271.
 
   Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, Guiseppe Persiano
Public Key Encryption with Keyword Search
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2004)506-522 Springer-Verlag/IACR Lecture Notes in Computer Science.
 
2003
   Jonathan Katz, Rafail Ostrovsky, Adam Smith
Round Efficiency of Multi-Party Computation with a Dishonest Majority
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Eurocrypt, (EUROCRYPT-2003)578-595 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] [postscript] [pdf] [ SODA talk (pdf file)]
In Proceedings of 2003 SIAM Symposium on Discrete Algorithms (SODA-2003)771-780
 
2002
   Jonathan Katz, Rafail Ostrovsky, Moti Yung
Forward Security in Password-Only Key Exchange Protocols
[Abstract] [postscript] [pdf]
In Proceedings of Security in Communication Networks 2002 conference (CSN-2002)29-44 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)] [stoc version (pdf file)] [full paper postscript] [full paper pdf]
In Proceedings of the ACM 2002 Symposim on Theory of Computing (STOC-2002), pp. 494-503.
 
2001
   Julia Chuzhoy, Rafail Ostrovsky, Yuval Rabani
Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
[Abstract] [ preliminary (postscript)] [ full version (pdf file)]
Preliminary version in Proceedings of 42st Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2001)348-356. 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] [postscript] [pdf]
In Proceedings of Advances in Cryptology, (CRYPTO-2001)566-598 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] [postscript] [pdf]
Journal of Cryptology Springer-Verlag Volume 18, Number 1, January 2005 pp.37 - 61. Preliminary version in Proceedings of Advances in Cryptology, (CRYPTO-2001)80-100 Springer-Verlag/IACR Lecture Notes in Computer Science.
 
   Jonathan Katz, Rafail Ostrovsky, Moti Yung
Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Cryptology, (EUROCRYPT-2001)475-494 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] [postscript] [pdf]
In Proceedings of Advances in Cryptology, (EUROCRYPT-2001)40-59 Springer-Verlag/IACR Lecture Notes in Computer Science.
 
   Jonathan Katz, Steven Myers, Rafail Ostrovsky
Cryptographic Counters and Applications to Electronic Voting
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Cryptology, (EUROCRYPT-2001) 78-92 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] [postscript] [pdf]
In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2001) 601-610. Full versoin in Journal of Interconnection Networks, Vol. 5, No. 1, pp. 1-12.
 
2000
   Rafail Ostrovsky, Yuval Rabani
Polynomial Time Approximation Schemes for Geometric k-Clustering
[Abstract] [postscript] [pdf] In addition, you can get a [powerpoint survey presentation].
In Proceedings of 41st Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2000)349-358. 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] [postscript] [pdf]
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] [postscript] [pdf]
In Proceedings of Advances in Cryptology (EUROCRYPT-2000) Springer-Verlag Lecture Notes in Computer Science Vol 1807, pp. 122-138.
 
1999
   Giovanni Di Crescenzo and Rafail Ostrovsky
On Concurrent Zero-Knowledge with Pre-Processing
[Abstract] [postscript] [pdf]
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] [postscript] [pdf]
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) 312-321.
 
   Ran Canetti, Rafail Ostrovsky
Secure Computation with Honest-Looking Parties What If Nobody Is Truly Honest
[Abstract] [postscript] [pdf]
In Proceedings of The 31'st ACM Symposium on Theory of Computing (STOC-99)255-264
 
   Allan Borodin, Rafail Ostrovsky, Yuval Rabani
Subquadratic Approximation Algorithms For Clustering Problems in High Dimensional Spaces
[Abstract] [postscript] [pdf]
In Proceedings of The 31'st ACM Symposium on Theory of Computing (STOC-99)435-444
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] [postscript] [pdf]
In Proceedings of EUROCRYPT-99 Springer Verlag.
 
   Rafail Ostrovsky, Boaz Patt-Shamir
Optimal and Efficient Clock Synchronization Under Drifting Clocks
[Abstract] [postscript] [pdf]
In Proceedings of Eeighteenth Annual ACM Symposium on Principles of Distributed Computing (PODC-99) 3-12
 
1998
   William Aiello, Sachin Lodha, Rafail Ostrovsky
Fast Digital Identity Revocation
[Abstract] [postscript] [pdf]
In Proceedings of advances in cryptology, (CRYPTO-98)137-152 Springer-Verlag Lecture Notes in Computer Science.
 
   Giovanni De-Crescenzo, Yuval Ishai, Rafail Ostrovsky
Universal Service-Providers for Database Private Information Retrieval
[Abstract] [postscript] [pdf]
In Proceedings of Seventeenth Annual ACM Symposium on Principles of Distributed Computing (PODC-98)91-100. 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] [postscript] [pdf]
In Proceedings of Seventeenth Annual ACM Symposium on Principles of Distributed Computing (PODC-98)81-90
 
   Giovanni Di Crescenzo, Yuval Ishai, Rafail Ostrovsky
Non-Interactive and Non-Malleable Commitment
[Abstract] [postscript] [pdf]
In Proceedings of The 30's ACM Symposium on Theory of Computing (STOC-98)141-150
 
   Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani
Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
[Abstract] [postscript] [pdf]
SIAM J. Comput. 30(2): 457-474 (2000). Preliminary version in Proceedings of The 30's ACM Symposium on Theory of Computing (STOC-98) 614-623
 
   William Aiello, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen
Adaptive Packet Routing for Bursty Adversarial Traffic
[Abstract] [postscript] [pdf]
In Proceedings of The 30's ACM Symposium on Theory of Computing (STOC-98) 359-368. Journal version appeared in JCSS 60(3): 482-509 (2000).
 
   Richard J. Lipton, Rafail Ostrovsky
Micro-Payments via Efficient Coin-Flipping
[Abstract] [postscript] [pdf]
In Proceedings of Second Financial Cryptography Conference, (FINANCIAL CRYPTO-98)1-15 February 1998. Lecture Notes in Computer Science LNCS volume 1465
 
1997
   Eyal Kushilevitz, Rafail Ostrovsky
Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval
[Abstract] [postscript] [pdf]
In Proceedings of Thirty-eigth Annual IEEE Symposium on the Foundations of Computer Science (FOCS-97) 364-373
 
   Ran Canetti, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen
Randomness vs. Fault-Tolerance
[Abstract] [postscript] [pdf]
In Proceedings of Sixteenth Annual ACM Symposium on Principles of Distributed Computing (PODC-97)35-44 Journal version in Journal of Cryptology 13(1): 107-142 (2000).
 
   Shlomi Dolev, Rafail Ostrovsky
Efficient Anonymous Multicast and Reception
[Abstract] [postscript] [pdf]
Preliminary version in proceedings of advances in cryptology, (CRYPTO-97)395-409 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] [postscript] [pdf]
In Proceedings of advances in cryptology, (CRYPTO-97) 156-164 Springer-Verlag Lecture Notes in Computer Science.
 
   Ran Canetti, Cynthia Dwork, Moni Naor, Rafail Ostrovsky
Deniable Encryption
[Abstract] [postscript] [pdf]
In Proceedings of advances in cryptology, (CRYPTO-97)90-104 Springer-Verlag Lecture Notes in Computer Science.
 
   Rafail Ostrovsky, Victor Shoup
Private Information Storage
[Abstract] [postscript] [pdf]
In Proceedings of The Twenty-Ninth ACM Symposium on Theory of Computing (STOC-97) 294-303
 
   Rafail Ostrovsky, Yuval Rabani
Universal O(congestion+dilation+log^{1+\epsilon} N) Local Control Packet Switching Algorithm
[Abstract] [postscript] [pdf]
In Proceedings of The Twenty-Ninth ACM Symposium on Theory of Computing (STOC-97) 644-653
 
1996
   Eyal Kushilevitz, Nati Linial, Rafail Ostrovsky
The Linear-Array Conjecture in Communication Complexity is False
[Abstract] [postscript] [pdf]
Preliminary version in Proceedings of The Twenty-Eighth ACM Symposium on Theory of Computing (STOC-96) 1-10 Journal version in Combinatorica 19(2): 241-254 (1999)
 
   Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen
Characterizing Linear Size Circuits in Terms of Privacy
[Abstract] [postscript] [pdf]
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)541-550.
 
   Alain Mayer, Rafail Ostrovsky, Moti Yung
Self-Stabilizing Algorithms for Synchronous Unidirectional Rings
[Abstract] [postscript] [pdf]
In Proceedings of Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-96)564-573 January 28-30, Atlanta, Georgia
 
1995
   Rafail Ostrovsky, Danal Wilkarson
Faster Computation On Directed Networks of Automata
[Abstract] [postscript] [pdf]
In the Proceedings of Fourteenth Annual ACM Symposium on Principles of Distributed Computing (PODC-95) 38-46
 
   Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen
Log-Space Polynomial End-to-End Communication (Abstract)
[Abstract] [postscript] [pdf]
PODC 1995: 254
 
   Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen
LOG-Space Polynomial End-to-End Communication
[Abstract] [postscript] [pdf]
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 PG 559-568
 
1994
   Joe Kilian, Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky
Reducibility and Completeness In Multi-Party Private Computations
[Abstract] [postscript] [pdf]
Preliminary version appeared in Proceedings of Thirty-fifth Annual IEEE Symposium on the Foundations of Computer Science (FOCS-94)478-489 Journal version in SIAM J. Comput. 29(4): 1189-1208 (2000)
 
   Baruch Awerbuch, Rafail Ostrovsky
Memory-Efficient and Self-Stabilizing Network RESET.
[Abstract] [postscript] [pdf]
In Proceedings of Thirteens Annual ACM Symposium on Principles of Distributed Computing (PODC-94) 254-263 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] [postscript] [pdf]
In Proceedings of Twenty-sixth ACM Symposium on Theory of Computing (STOC-94) 234-242
 
   Oded Goldreich, Rafail Ostrovsky, Erez Petrank
Computational Complexity and Knowledge Complexity
[Abstract] [postscript] [pdf]
Preliminary version appeared in the Twenty-sixth ACM Symposium on Theory of Computing (STOC-94) 534-543 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] [postscript] [pdf]
In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms SODA 1994: 690-696 January 23-25, 1994, Arlington, Virginia.
 
1993
   Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung
Interactive Hashing Simplifies Zero-Knowledge Protocol Design
[[Abstract] [postscript] [pdf]
In Proceedings of (EUROCRYPT-93)267-273 Springer Verlag.
 
   Shay Kutten, Rafail Ostrovsky, Boaz Patt-Shamir
The Las-Vegas Processor Identity Problem (How and When to Be Unique)
[Abstract] [postscript] [pdf]
In Proceedings of the Second Israel Symposium on Theory of Computing and Systems (ISTCS-93) 150-159 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] [postscript] [pdf]
In Proceedings of the second Israel Symposium on Theory of Computing and Systems} (ISTCS-93) 3-17
 
1992
   Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung
Secure Commitment Against Powerful Adversary: A Security Primitive based on Average Intractability
[Abstract] [postscript] [pdf]
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] [postscript] [pdf]
In Proceedings of 24th annual ACM Symposium on Theory of Computing (STOC-92) 667-678
 
   Shafi Goldwasser, Rafail Ostrovsky
Invariant Signatures and Non-Interactive Zero-Knowledge Proofs are Equivalent
[Abstract] [postscript] [pdf]
In Proceedings of Advances in Cryptology (CRYPTO-92)228-245 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] [postscript] [pdf]
Preliminary version appeared in Proceedings of advances in cryptology (CRYPTO-92) 196-214 Springer-Verlag Lecture Notes in Computer Science. Final version appeared in J. of Cryptology, 1988.
 
1991
   Rafail Ostrovsky
One-way Functions, Hard on Average Problems and Statistical Zero-knowledge Proofs
[[Abstract] [postscript] [pdf]
Structure in Complexity Theory Conference 1991: 133-138. In Proceedings of 6th Annual Structure in Complexity Theory Conference (STRUCTURES-91) June 30 -- July 3, 1991, Chicago. pp. 133-138
 
   Rafail Ostrovsky, Moti Yung
How to Withstand Mobile Virus Attacks
[Abstract] [postscript] [pdf]
In Proceedings of 10th annual ACM Symposium on Principles of Distributed Computing (PODC-91) August 1991, Montreal, Quebec, Canada, pp. 51-59.
 
   Joan Feigenbaum, Rafail Ostrovsky
A Note On One-Prover, Instance-Hiding Zero-Knowledge Proof Systems
[Abstract] [postscript] [pdf]
In Proceedings of the first international symposium in cryptology in Asia (ASIACRYPT'91) 352-359 November 11-14, 1991, Fujsiyoshida, Yamanashi, Japan.
 
1990
   Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung
Fair Games Against an All-Powerful Adversary
[Abstract] [postscript] [pdf]
Presented in DIMACS Complexity and Cryptography Workshop, Princeton, October 1990. Extended abstract in proceedings of Sequences II, June 1991, Positano, Italy, R.M. Capocelli, A. De-Santis and U. Vaccaro (Eds.), Springer-Verlag. Journal version in AMS DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol 13. (Jin-Yi Cai ed.) pp. 155-169, 1991.
 
   Rafail Ostrovsky and Moti Yung
On Necessary Conditions for Secure Distributed Computation
[Abstract] [postscript] [pdf]
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.
 
   Rafail Ostrovsky
Software Protection and Simulation on Oblivious RAMs
[Abstract] [postscript] [pdf]
Preliminary version appeared as a single-author paper in Proceedings of 22nd annual ACM Symposium on Theory of Computing (STOC-90) pp. 514-523. Full version became my M.I.T. Ph.D. thesis in 1992. Journal version appeared in JACM, Vol. 43, No. 3, May 1996, pp.431-473 co-authored with Oded Goldreich
 
[
   Mihir Bellare, Silvio Micali, Rafail Ostrovsky
Perfect Zero-Knowledge in Constant Rounds
[Abstract] [postscript] [pdf]
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] [postscript] [pdf]
In Proceedings of 22nd annual ACM Symposium on Theory of Computing (STOC-90)