Rafail Ostrovsky Publications (In Chronological Order)

Rafail Ostrovsky Publications
(In Chronological Order)

For additional information, especially regarding journal publications, see DBLP or Google sch olar.
You can also search my Publications by Topic.
Color-coding:

Security and cryptography

Algorithms

2022

Shaan Mathur, Rafail Ostrovsky:: A combinatorial characterization of self-stabilizing population protocols
[Abstract] [pdf] Inf. Comput. 285(Part): 104829 (2022)
Fabrizio Grandoni, Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Rakesh Venkat: A refined approximation for Euclidean k-means
[Abstract] [pdf]
Inf. Process. Lett. 176: 106251 (2022)
Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, Omer Paneth: Succinct Non-Interactive Arguments via Linear Interactive Proofs
[Abstract] [pdf]
J. Cryptol. 35(3): 15 (2022)
Wutichai Chongchitmate, Yuval Ishai, Steve Lu, Rafail Ostrovsky: PSI from Ring-OLE
[Abstract] [pdf]
CCS 2022: 531-545
Samuel Dittmer, Yuval Ishai, Steve Lu, Rafail Ostrovsky: Improving Line-Point Zero Knowledge: Two Multiplications for the Price of One
[Abstract] [pdf]
CCS 2022: 829-841
Nishanth Chandran, Pouyan Forghani, Juan A. Garay, Rafail Ostrovsky, Rutvik Patel, Vassilis Zikas: Universally Composable Almost-Everywhere Secure Computation
[Abstract] [pdf]
ITC 2022: 14:1-14:25
Samuel Dittmer, Yuval Ishai, Steve Lu, Rafail Ostrovsky: Authenticated Garbling from Simple Correlations
[Abstract] [pdf]
CRYPTO (4) 2022: 57-87
Brett Hemenway Falk, Rohit Nema, Rafail Ostrovsky: A Linear-Time 2-Party Secure Merge Protocol
[Abstract] [pdf]
CSCML 2022: 408-427
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: EpiGRAM: Practical Garbled RAM
[Abstract] [pdf]
EUROCRYPT (1) 2022: 3-33
Abida Haque, David Heath, Vladimir Kolesnikov, Steve Lu, Rafail Ostrovsky, Akash Shah: Garbled Circuits with Sublinear Evaluator
[Abstract] [pdf]
EUROCRYPT (1) 2022: 37-64
Michele Ciampi, Rafail Ostrovsky, Hendrik Waldner, Vassilis Zikas: Round-Optimal and Communication-Efficient Multiparty Computation
[Abstract] [pdf]
EUROCRYPT (1)
Laasya Bangalore, Rafail Ostrovsky, Oxana Poburinnaya, Muthuramakrishnan Venkitasubramaniam: Adaptively Secure Computation for RAM Programs
[Abstract] [pdf]
EUROCRYPT (2) 2022: 187-216
Paul Bunn, Eyal Kushilevitz, Rafail Ostrovsky: CNF-FSS and Its Applications
[Abstract] [pdf]
Public Key Cryptography (1) 2022: 283-314 br>
Brett Hemenway Falk, Daniel Noble, Rafail Ostrovsky Ostrovsky: 3-Party Distributed ORAM from Oblivious Set Membership
[Abstract] [pdf]
SCN 2022: 437-461
Surya Addanki, Kevin Garbe, Eli Jaffe, Rafail Ostrovsky, Antigoni Polychroniadou: Prio+: Privacy Preserving Aggregate Statistics via Boolean Shares
[Abstract] [pdf]
SCN 2022: 516-539
Samuel Dittmer, Yuval Ishai, Steve Lu, Rafail Ostrovsky, Mohamed Elsabagh, Nikolaos Kiourtis, Brian Schulte, Angelos Stavrou:: Streaming and Unbalanced PSI from Function Secret Sharing
[Abstract] [pdf]
SCN 2022: 564-587

2021

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]
SIAM J. Discret. Math. 35(1): 465-484 (2021)
Sandip Banerjee, Rafail Ostrovsky, Yuval Rabani: Min-Sum Clustering (With Outliers)
[Abstract] [pdf]
APPROX-RANDOM 2021: 16:1-16:16
Sanjam Garg, Mohammad Hajiabadi, Giulio Malavolta, Rafail Ostrovsky:: How to Build a Trapdoor Function from an Encryption Scheme
[Abstract] [pdf]
ASIACRYPT (3) 2021: 220-249
Nicholas Franzese, Jonathan Katz, Steve Lu, Rafail Ostrovsky, Xiao Wang, Chenkai Weng: Constant-Overhead Zero-Knowledge for RAM Programs
[Abstract] [pdf]
CCS 2021: 178-191
Xiaoqi Duan, Vipul Goyal, Hanjun Li, Rafail Ostrovsky, Antigoni Polychroniadou, Yifan Song: ACCO: Algebraic Computation with Comparison
[Abstract] [pdf]
CCSW@CCS 2021: 21-38
Samuel Dittmer, Yuval Ishai, Rafail Ostrovsky: Line-Point Zero Knowledge and Its Applications
[Abstract] [pdf]
ITC 2021: 5:1-5:24
Brett Hemenway Falk, Rafail Ostrovsky: Secure Merge with O(n log log n) Secure Operations
[Abstract] [pdf]
ITC 2021: 7:1-7:29
Vipul Goyal, Hanjun Li, Rafail Ostrovsky, Antigoni Polychroniadou, Yifan Song: ATLAS: Efficient and Scalable MPC in the Honest Majority Setting
[Abstract] [pdf]
CRYPTO (2) 2021: 244-274
Michele Ciampi, Vipul Goyal, Rafail Ostrovsky: Threshold Garbled Circuits and Ad Hoc Secure Computation
[Abstract] [pdf]
EUROCRYPT (3) 2021: 64-93
Brett Hemenway Falk, Daniel Noble, Rafail Ostrovsky: Alibi: A Flaw in Cuckoo-Hashing Based Hierarchical ORAM Schemes and a Solution
[Abstract] [pdf]
EUROCRYPT (3) 2021: 338-369
Arka Rai Choudhuri, Michele Ciampi, Vipul Goyal, Abhishek Jain, Rafail Ostrovsky: Oblivious Transfer from Trapdoor Permutations in Minimal Rounds
[Abstract] [pdf]
TCC (2) 2021: 518-549

2020

Paul Bunn, Rafail Ostrovsky: Oblivious Sampling with Applications to Two-Party k-Means Clustering
[Abstract] [pdf]
J. Cryptol. 33(3): 1362-1403 (2020)0; efficient Error-Correcting Codes for Sliding Windows
[Abstract] [pdf]
CRYPTO (1) 2020: 776-806; On Succinct Arguments and Witness Encryption from Groups
[Abstract] [pdf]
CRYPTO (1) 2020: 776-806; Resource-Restricted Cryptography: Revisiting MPC Bounds in the Proof-of-Work Era
[Abstract] [pdf]
EUROCRYPT (2) 2020: 129-158; Proof-of-Reputation Blockchain with Nakamoto Fallback
[Abstract] [pdf]
INDOCRYPT 2020: 16-38; Communication-Efficient (Proactive) Secure Computation for Dynamic General Adversary Structures and Dynamic Groups
[Abstract] [pdf]
SCN 2020:; Efficient 3-Party Distributed ORAM
[Abstract] [pdf]
SCN 2020: 215-232; Oblivious Tight Compaction In O(n) Time with Smaller Constant
[Abstract] [pdf]
SCN 2020: 253-274; A Combinatorial Characterization of Self-stabilizing Population Protocols
[Abstract] [pdf]
SSS 2020: 167-182
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: Round Optimal Secure Multiparty Computation from Minimal Assumptions
[Abstract] [pdf]
TCC (2) 2020: 291-319

2019

Yannai A. Gonczarowski, Noam Nisan, Rafail Ostrovsky, Will Rosenbaum: A stable marriage requires communication
[Abstract] [pdf]
ASIACRYPT (2) 2019: 577-605
Saikrishna Badrinarayanan, Abhishek Jain, Rafail Ostrovsky, Ivan Visconti: UC-Secure Multiparty Computation from One-Way Functions Using Stateless Tokens
[Abstract] [pdf]
ASIACRYPT (2) 2019: 577-605
Nico DÃ¶ttling, Sanjam Garg, Yuval Ishai, Giulio Malavolta, Tamer Mour, Rafail Ostrovsky: Trapdoor Hash Functions and Their Applications
[Abstract] [pdf]
CRYPTO (3) 2019: 3-32
Nishanth Chandran, Wutichai Chongchitmate, Rafail Ostrovsky, Ivan Visconti: Universally Composable Secure Computation with Corrupted Tokens
[Abstract] [pdf]
CRYPTO (3) 2019: 432-461
Melissa Chase, Yevgeniy Dodis, Yuval Ishai, Daniel Kraschewski, Tianren Liu, Rafail Ostrovsky, Vinod Vaikuntanathan: Reusable Non-Interactive Secure Computation
[Abstract] [pdf]
CRYPTO (3) 2019: 462-488
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai: Cryptographic Sensing
[Abstract] [pdf]
CRYPTO (3) 2019: 583-604
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
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

2018

Yun Lu, Konstantinos Mitropoulos, Rafail Ostrovsky, Avraham Weinstock, Vassilis Zikas: Cryptographically Secure Detection of Injection Attacks
[Abstract] [pdf]
Data Sci. J. 17: 31 (2018)CCS 2018: 2240-2242
George Alter, Brett Hemenway Falk, Steve Lu, Rafail Ostrovsky: Computing Statistics from Private Data
[Abstract] [pdf]
Data Sci. J. 17: 31 (2018)
Saikrishna Badrinarayanan, Abhishek Jain, Rafail Ostrovsky, Ivan Visconti: Non-interactive Secure Computation from One-Way Functions
[Abstract] [pdf]
ASIACRYPT (3) 2018: 118-138
Karim Eldefrawy, Rafail Ostrovsky, Moti Yung:: 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
Sanjam Garg, Rafail Ostrovsky, Akshayaram Srinivasan: Adaptive Garbled RAM from Laconic Oblivious Transfer
[Abstract] [pdf]
CRYPTO (3) 2018: 515-544
Rafail Ostrovsky, Giuseppe Persiano, Daniele Venturi, Ivan Visconti: Continuously Non-Malleable Codes in the Split-State Model from Minimal Assumptions
[Abstract] [pdf]
CRYPTO (3) 2018: 608-639
Rafail Ostrovsky, Yuval Rabani, Arman Yousefi: Strictly Balancing Matrices in Polynomial Time Using Osborne's Iteration
[Abstract] [pdf]
ICALP 2018: 93:1-93:11
Shafi Goldwasser, Rafail Ostrovsky, Alessandra Scafuro, Adam Sealfon: Population Stability: Regulating Size in the Presence of an Adversary
[Abstract] [pdf]
PODC 2018: 397-406
Karim Eldefrawy, Rafail Ostrovsky, Sunoo Park, Moti Yung: Proactive Secure Multiparty Computation with a Dishonest Majority
[Abstract] [pdf]
SCN 2018: 200-215
Dakshita Khurana, Rafail Ostrovsky, Akshayaram Srinivasan: Round Optimal Black-Box "Commit-and-Prove
[Abstract] [pdf]
TCC (1) 2018: 286-313
Wutichai Chongchitmate, Rafail Ostrovsky: Information-Theoretic Broadcast with Dishonest Majority for Long Messages
[Abstract] [pdf]
TCC (1) 2018: 370-388
Brett Hemenway, Rafail Ostrovsky: Efficient robust secret sharing from expander graphs.
[Abstract] [pdf]
Cryptography and Communications 10(1): 79-99 (2018)
Yuval Ishai, Manika Mittal, Rafail Ostrovsky: On the Message Complexity of Secure Multiparty Computation.
[Abstract] [pdf]
PKC (1) 2018: 698-711

2017

David Felber, Rafail Ostrovsky: A Randomized Online Quantile Summary in O((1/epsilon) log(1/epsilon)) Words.
[Abstract] [pdf]
Theory of Computing 13(1): 1-17 (2017)
Rafail Ostrovsky, Mor Perry, Will Rosenbaum: Space-Time Tradeoffs for Distributed Verification
[Abstract] [pdf]
SIROCCO 2017: 53-70
Wutichai Chongchitmate, Rafail Ostrovsky, Ivan Visconti: Resettably-Sound Resettable Zero Knowledge in Constant Rounds
[Abstract] [pdf]
TCC (2) 2017: 111-138
Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti: Round-Optimal Secure Two-Party Computation from Trapdoor Permutations
[Abstract] [pdf]
TCC (1) 2017: 678-710
Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti: Delayed-Input Non-Malleable Zero Knowledge and Multi-Party Coin Tossing in Four Rounds
[Abstract] [pdf]
TCC (1) 2017: 711-742
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

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 ₂-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
Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, Omer Paneth: Succinct Non-interactive Arguments via Linear Interactive Proofs
[Abstract] [pdf]
TCC 2013:
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)
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)