A Linear-Time 2-Party Secure Merge Protocol [Abstract] [pdf] CSCML 2022: 408-427 Journal version: Journal of Computer and System Sciences 137: 37-49 (2023); published as "Linear-time 2-party secure merge from additively homomorphic encryption" [Journal]
Michele Ciampi, Muhammad Ishaq, Malik Magdon-Ismail, Rafail Ostrovsky, Vassilis Zikas
FairMM: A Fast and Frontrunning-Resistant Crypto Market-Maker [Abstract] [pdf] CSCML 2022: 428-446
David Heath, Vladimir Kolesnikov, Rafail Ostrovsky
Oblivious Tight Compaction In O(n) Time with Smaller Constant [Abstract] [pdf] SCN 2020: 253-274
Shaan Mathur, Rafail Ostrovsky
A Combinatorial Characterization of Self-stabilizing Population Protocols [Abstract] [pdf] SSS 2020: 167-182 Journal version: Information and Computation 285: 104829 (2022) [Journal]
Sanjam Garg, Mohammad Hajiabadi, Rafail Ostrovsky
Efficient Range-Trapdoor Functions and Applications: Rate-1 OT and More [Abstract] [pdf] TCC (1) 2020: 88-116
Arka Rai Choudhuri, Michele Ciampi, Vipul Goyal, Abhishek Jain, Rafail Ostrovsky
Ariel Hamlin, Rafail Ostrovsky, Mor Weiss, Daniel Wichs
Private Anonymous Data Access [Abstract] [pdf] EUROCRYPT (2) 2019: 244-273
Eyal Kushilevitz, Rafail Ostrovsky, Emmanuel Prouff, Adi Rosén, Adrian Thillard, Damien Vergnaud
Lower and Upper Bounds on the Randomness Complexity of Private Computations of AND [Abstract] [pdf] TCC (2) 2019: 386-406 Journal version: SIAM Journal on Discrete Mathematics 35(1): 465-484 (2021) [Journal]
Brett Hemenway Falk, Daniel Noble, Rafail Ostrovsky
Private Set Intersection with Linear Communication from General Assumptions [Abstract] [pdf] WPES@CCS 2019: 14-25
Brett Hemenway Falk, Steve Lu, Rafail Ostrovsky
DURASIFT: A Robust, Decentralized, Encrypted Database Supporting Private Searches with Complex Policy Controls [Abstract] [pdf] WPES@CCS 2019: 26-36
Theoretical Foundations for Mobile Target Defense: Proactive Secret Sharing and Secure Multiparty Computation [Abstract] [pdf] From Database to Cyber Security 2018: 470-486
Quinn Grier, Brett Hemenway Falk, Steve Lu, Rafail Ostrovsky
ETERNAL: Encrypted Transmission With an Error-correcting, Real-time, Noise-resilient Apparatus on Lightweight Devices [Abstract] [pdf] MPS@CCS 2018: 61-70
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 Journal on Discrete Mathematics 30(1): 266-295 (2016) [Journal]
Brett Hemenway, Zahra Jafargholi, Rafail Ostrovsky, Alessandra Scafuro, Daniel Wichs
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 Journal version: IEEE Transactions on Information Theory 63(10): 6256-6270 (2017). [Journal]
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 Journal version: Theory of Computing 13, Article 14 (2017). [Journal]
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
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 Journal version: Games and Economic Behavior 118: 626-647 (2019). [Journal]
Sanjam Garg, Steve Lu, Rafail Ostrovsky, Alessandra Scafuro
Garbled RAM From One-Way Functions [Abstract] [pdf] STOC 2015: 449-458
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 Journal version: SIAM Journal on Discrete Mathematics 34(1): 904-937 (2020). [Journal]
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
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 Theoretical Computer Science 554: 50-63 (2014) [Journal]
Vladimir Braverman, Ran Gelles, Rafail Ostrovsky
How to Catch L2-Heavy-Hitters on Sliding Windows [Abstract] [pdf] Preliminary version appeared in COCOON 2013 pp: 638-650. Full version appeared in Theoretical Computer Science 554: 82-94 (2014) [Journal]
Matthew K. Franklin, Ran 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 Transactions on Information Theory 61(1): 133-145 (2015) [Journal]
Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti, Akshay Wadia
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 Information and Computation 243: 178-190 (2015) [Journal]
Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman
Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky
Edge Fault Tolerance on Sparse Networks [Abstract] [pdf] ICALP 2012: 452-463 Journal version: Almost-Everywhere Secure Computation with Edge Corruptions. Journal of Cryptology 28(4): 745-768 (2015). [Journal]
Ran Gelles, Rafail Ostrovsky, Kina Winoto
Multiparty Proximity Testing with Dishonest Majority from Equality Testing [Abstract] [pdf] ICALP 2012: 537-548
Brett Hemenway, Rafail Ostrovsky
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 Ostrovsky
Extended-DDH and Lossy Trapdoor Functions [Abstract] [pdf] Public Key Crypotgraphy 2012: 627-643
Joshua Baron, Karim El Defrawy, 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) [Journal]
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 Ostrovsky, 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
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 Schaffner
Position-Based Quantum Cryptography: Impossibility and Constructions [Abstract] [pdf] Preliminary version appeared in Crypto 2011:429-446.Full version appeared in SIAM Journal on Computing 43(1): 150-178 (2014) Plenary talk at QIP 2011. [Journal]
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 ACM Transactions on Sensor Networks 11(1), Article 13: 13:1-13:25 (2014) [Journal]
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai
Password-Authenticated Session-Key Generation on the Internet in the Plain Model [Abstract] [pdf] Preliminary version appeared in Crypto 2010: 277-294.
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 Transactions on Information Theory 60(4): 2373-2390 (2014) [Journal]
Nishanth Chandran, Rafail Ostrovsky, Willim E. Skeith III
Public Encryption with Efficient Amortized Updates [Abstract] [pdf] SCN 2010: 17-35
Nishanth Chandran, Juan 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 Journal of the ACM 61(5), Article 29: 29:1-29:28 (2014) [Journal]
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
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
Position-Based Cryptography [Abstract] [postscript] [pdf] CRYPTO-2009. 391-407 (In addition, you can get [ppt].) Journal version: SIAM Journal on Computing 43(4): 1291-1341 (2014). [Journal]
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].) Journal version: Theoretical Computer Science 453: 14-28 (2012). [Journal]
Vladimir Braverman, Rafail Ostrovsky, Carlo Zaniolo
Optimal Sampling from Sliding Windows [Abstract] [postscript] [pdf] (PODS-2009) 147-156 Journal version: Journal of Computer and System Sciences 78(1): 260-272 (2012). [Journal]
Yair Amir, Paul Bunn, Rafail Ostrovsky
Authenticated Adversarial Routing [Abstract] [postscript] [pdf] (TCC-2009) 163-182 (In addition, you can get [ppt].) Journal version: Journal of Cryptology 27(4): 636-771 (2014). [Journal]
Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti
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).
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. Full version appeared in Journal of Combinatorial Optimization 21(1): 47-66 (2011). [Journal]
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] (updated author version) ACM Transactions on Algorithms 4(4): 45:1-45:14 (2008) Published journal version: [pdf]
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 Journal on Computing 38(1): 97-139 (2008) [Journal]
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 Journal version: Journal of Cryptology 27(3): 506-543 (2014). [Journal]
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 Journal version: Effective Computations on Sliding Windows. SIAM Journal on Computing 39(6): 2113-2131 (2010). [Journal]
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 Ishai, 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 on Computing (SICOMP) special issue devoted to STOC-2007. Published journal version: Zero-Knowledge Proofs from Secure Multiparty Computation, SIAM Journal on Computing 39(3): 1121-1152 (2009).
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) Journal version: Oblivious Sampling with Applications to Two-Party k-Means Clustering. Journal of Cryptology 33(3): 1362-1403 (2020). [Journal]
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. Journal version: Journal of the ACM 59(6), Article 28 (2012). [Journal]
Yuval Ishai, 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. Journal version: Journal of Computer Security 19(5): 895-934 (2011). [Journal]
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. Journal version: Sequential Aggregate Signatures, Multisignatures, and Verifiably Encrypted Signatures Without Random Oracles. Journal of Cryptology 26(2): 340-373 (2013). [Journal]
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. Journal version: New Techniques for Noninteractive Zero-Knowledge. Journal of the ACM 59(3), Article 11: 11:1-11:35 (2012). This journal version also incorporates Non-interactive Zaps and New Techniques for NIZK (CRYPTO 2006: 97-111). [Journal]
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. Journal version: IEEE Transactions on Information Theory 55(7): 2931-2941 (2009). [Journal]
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. [Journal]
Rafail Ostrovsky, Yuval Rabani
Low distortion embeddings for edit distance [Abstract] [postscript] [pdf] Preliminary version appeared in STOC '05. Full version in Journal of the ACM 54(5), Article 23 (2007). [Journal]
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
Identity-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 Ishai, 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, Giuseppe 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.
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
Forward Secrecy in Password-Only Key Exchange Protocols [Abstract] [postscript] [pdf] In Proceedings of Security in Communication Networks 2002 conference (SCN-2002)29-44 Springer-Verlag Lecture Notes in Computer Science.
Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, Amit Sahai
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 Mathematics of Operations Research 31(4): 730-738 (2006).
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] Preliminary version in Proceedings of Advances in Cryptology, (CRYPTO-2001)80-100 Springer-Verlag/IACR Lecture Notes in Computer Science. Journal version: Journal of Cryptology 18(1): 37-61 (2005). [Journal]
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. Journal version: Efficient and Secure Authenticated Key Exchange Using Weak Passwords. Journal of the ACM 57(1), Article 3: 3:1-3:39 (2009). This journal version also incorporates Forward Secrecy in Password-Only Key Exchange Protocols (SCN 2002: 29-44). [Journal] 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 version in Journal of Interconnection Networks 5(1): 1-12 (2004). [Journal]
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: Polynomial-time approximation schemes for geometric min-sum median clustering. Journal of the ACM 49(2): 139-156 (2002). [Journal]
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.
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 Machine Learning Special Issue: Theoretical Advances in Data Clustering (Guest Editors: Nina Mishra and Rajeev Motwani) 56 (1-3): 153-167, 2004 [Journal]
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
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: Universal Service-Providers for Private Information Retrieval. Journal of Cryptology 14(1): 37-74 (2001). [Journal]
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 Journal version: SIAM Journal on Discrete Mathematics 16(4): 533-544 (2003). [Journal]
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] Preliminary version in Proceedings of The 30's ACM Symposium on Theory of Computing (STOC-98) 614-623 Journal version: SIAM Journal on Computing 30(2): 457-474 (2000). [Journal]
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 Journal of Computer and System Sciences 60(3): 482-509 (2000). [Journal]
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
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). [Journal]
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: Xor-trees for efficient anonymous multicast and reception. ACM Transactions on Information and System Security 3(2): 63-84 (2000). [Journal]
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
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) [Journal]
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. [Journal]
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
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
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: Reducibility and Completeness in Private Computations. SIAM Journal on Computing 29(4): 1189-1208 (2000). [Journal]
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.
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. [Journal]
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.
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 Journal of Algorithms 37(2): 468-494 (2000). [Journal]
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
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.
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 Journal version: SIAM Journal on Computing 31(5): 1571-1595 (2002). [Journal]
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 journal version: Perfect Zero-Knowledge Arguments for NP Using Any One-Way Permutation. Journal of Cryptology 11(2): 87-108 (1998). [Journal]
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.
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 Journal of the ACM, Vol. 43, No. 3, May 1996, pp.431-473 co-authored with Oded Goldreich [Journal]
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)
David Heath, Nakul Khambhati, Rafail Ostrovsky, Turan Vural
Samuel Dittmer, Rafail Ostrovsky