Rafail Ostrovsky Publications (In Chronological Order)

Rafail Ostrovsky Publications
(In Chronological Order)

For additional information, see DBLP or Google Scholar.
You can also search my Publications by Topic.
Color-coding:

Security and cryptography

Algorithms

2026

David Heath, Nakul Khambhati, Rafail Ostrovsky, Turan Vural: Authenticated Garbling with Tensor Gates
[Abstract] [pdf]
ACM CCS 2026 (accepted). [DOI]
Samuel Dittmer, Rafail Ostrovsky: On Randomness Complexity of 1-Private Protocols
[Abstract] [pdf]
ICALP 2026: 79:1-79:23
Samuel Dittmer, Rohit Nema, Rafail Ostrovsky: Linear Secret-Shared Shuffle with Malicious Security
[Abstract] [pdf]
CRYPTO (8) 2026: 296-328
Cruz Barnum, David Heath, Vladimir Kolesnikov, Rafail Ostrovsky: Adaptive Garbled Circuits and Garbled RAM from Non-Programmable Random Oracles
[Abstract] [pdf]
ITC 2026: 11:1-11:21

2025

Yuval Ishai, Rafail Ostrovsky, Akash Shah: Zero-Knowledge RAM: Doubly Efficient and Black-Box
[Abstract] [pdf]
EUROCRYPT (4) 2025: 363-395
Yuval Ishai, Eyal Kushilevitz, Varun Narayanan, Rafail Ostrovsky, Akash Shah: Query-Reusable Proof Systems
[Abstract] [pdf]
EUROCRYPT (4) 2025: 333-362
Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Hendrik Waldner: Round-Optimal Black-Box Multiparty Computation from Polynomial-Time Assumptions
[Abstract] [pdf]
EUROCRYPT (5) 2025: 331-359
Michele Ciampi, Ankit Kumar Misra, Rafail Ostrovsky, Akash Shah: Black-Box Constant-Round Secure 2PC with Succinct Communication
[Abstract] [pdf]
EUROCRYPT (5) 2025: 360-389
David Heath, Vladimir Kolesnikov, Varun Narayanan, Rafail Ostrovsky, Akash Shah: Multiparty Garbling from OT with Linear Scaling and RAM Support
[Abstract] [pdf]
CRYPTO (4) 2025: 556-588
Vipul Goyal, Junru Li, Rafail Ostrovsky, Yifan Song: Towards Building Scalable Constant-Round MPC from Minimal Assumptions via Round Collapsing
[Abstract] [pdf]
CRYPTO (4) 2025: 70-104
Brett Hemenway Falk, Daniel Noble, Rafail Ostrovsky: MetaDORAM: Info-Theoretic Distributed ORAM with Less Communication
[Abstract] [pdf]
ITC 2025: 6:1-6:23
Mark Blunk, Paul Bunn, Samuel Dittmer, Steve Lu, Rafail Ostrovsky: Linear-Time Secure Merge in O(loglog n) Rounds
[Abstract] [pdf]
ITC 2025: 7:1-7:23
Rafail Ostrovsky, Yuval Rabani, Yoav Siman Tov: Budget and Profit Approximations for Spanning Tree Interdiction
[Abstract] [pdf]
APPROX/RANDOM 2025: 7:1-7:23
Michele Ciampi, Yun Lu, Rafail Ostrovsky, Vassilis Zikas: Two-Tier Black-Box Blockchains and Application to Instant Layer-1 Payments
[Abstract] [pdf]
AFT 2025: 19:1-19:24

2024

Chongwon Cho, Samuel Dittmer, Yuval Ishai, Steve Lu, Rafail Ostrovsky: Rabbit-Mix: Robust Algebraic Anonymous Broadcast from Additive Bases
[Abstract] [pdf]
USENIX Security Symposium 2024: 3151-3168
Nishanth Chandran, Juan A. Garay, Ankit Kumar Misra, Rafail Ostrovsky, Vassilis Zikas: Adaptive Security, Erasures, and Network Assumptions in Communication-Local MPC
[Abstract] [pdf]
TCC (4) 2024: 293-326
Vipul Goyal, Junru Li, Ankit Kumar Misra, Rafail Ostrovsky, Yifan Song, Chenkai Weng: Dishonest Majority Constant-Round MPC with Linear Communication from DDH
[Abstract] [pdf]
ASIACRYPT (6) 2024: 167-199

2023

Brett Hemenway Falk, Rafail Ostrovsky, Matan Shtepel, Jacob Zhang: GigaDORAM: Breaking the Billion Address Barrier
[Abstract] [pdf]
USENIX Security Symposium 2023: 3871-3888
Brett Hemenway, Daniel Noble, Rafail Ostrovsky, Matan Shtepel, Jacob Zhang: DORAM Revisited: Maliciously Secure RAM-MPC with Logarithmic Overhead
[Abstract] [pdf]
TCC (1) 2023: 441-470
Paul Bunn, Eyal Kushilevitz, Rafail Ostrovsky: Anonymous Permutation Routing
[Abstract] [pdf]
TCC (3) 2023: 33-61
Yuval Ishai, Rafail Ostrovsky, Akash Shah: Succinct Arguments for RAM Programs via Projection Codes
[Abstract] [pdf]
CRYPTO (2) 2023: 159-192
David Heath, Vladimir Kolesnikov, Rafail Ostrovsky: Tri-State Circuits - A Circuit Model that Captures RAM
[Abstract] [pdf]
CRYPTO (4) 2023: 128-160
Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Hendrik Waldner: List Oblivious Transfer and Applications to Round-Optimal Black-Box Multiparty Coin Tossing
[Abstract] [pdf]
CRYPTO (1) 2023: 459-488
Vipul Goyal, Chen-Da Liu-Zhang, Rafail Ostrovsky: Asymmetric Multi-Party Computation
[Abstract] [pdf]
ITC 2023: 6:1-6:25
Samuel Dittmer, Karim Eldefrawy, Stéphane Graham-Lengrand, Steve Lu, Rafail Ostrovsky, Vitor Pereira: Boosting the Performance of High-Assurance Cryptography: Parallel Execution and Optimizing Memory Access in Formally-Verified Line-Point Zero-Knowledge
[Abstract] [pdf]
CCS 2023: 2098-2112

2022

Fabrizio Grandoni, Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Rakesh Venkat: A refined approximation for Euclidean k-means
[Abstract] [pdf]
Information Processing Letters 176: 106251 (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
Journal version: Journal of Cryptology 39(1): 12 (2026) [Journal]
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
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: 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) 2022: 65-95
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
Brett Hemenway Falk, Daniel Noble, Rafail 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

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 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

Ohad Barta, Yuval Ishai, Rafail Ostrovsky, David J. Wu: On Succinct Arguments and Witness Encryption from Groups
[Abstract] [pdf]
CRYPTO (1) 2020: 776-806
Juan A. Garay, Aggelos Kiayias, Rafail M. Ostrovsky, Giorgos Panagiotakos, Vassilis Zikas: Resource-Restricted Cryptography: Revisiting MPC Bounds in the Proof-of-Work Era
[Abstract] [pdf]
EUROCRYPT (2) 2020: 129-158
Leonard Kleinrock, Rafail Ostrovsky, Vassilis Zikas: Proof-of-Reputation Blockchain with Nakamoto Fallback
[Abstract] [pdf]
INDOCRYPT 2020: 16-38
Karim Eldefrawy, Seoyeon Hwang, Rafail Ostrovsky, Moti Yung: Communication-Efficient (Proactive) Secure Computation for Dynamic General Adversary Structures and Dynamic Groups
[Abstract] [pdf]
SCN 2020: 108-129
Paul Bunn, Jonathan Katz, Eyal Kushilevitz, Rafail Ostrovsky: Efficient 3-Party Distributed ORAM
[Abstract] [pdf]
SCN 2020: 215-232
Samuel Dittmer, 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: Round Optimal Secure Multiparty Computation from Minimal Assumptions
[Abstract] [pdf]
TCC (2) 2020: 291-319

2019

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
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

2018

Yun Lu, Konstantinos Mitropoulos, Rafail Ostrovsky, Avraham Weinstock, Vassilis Zikas: Cryptographically Secure Detection of Injection Attacks
[Abstract] [pdf]
CCS 2018: 2240-2242
George Alter, Brett Hemenway Falk, Steve Lu, Rafail Ostrovsky: Computing Statistics from Private Data
[Abstract] [pdf]
Data Science Journal 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]
Public Key Cryptography (1) 2018: 698-711

2017

Juan A. Garay, Rafail Ostrovsky: Special Issue: Algorithmic Tools in Cryptography
[Abstract] [pdf]
Algorithmica 79(4): 985-986 (2017) (Editorial)
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]
Public Key Cryptography (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 Journal on Discrete Mathematics 30(1): 266-295 (2016) [Journal]
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
Journal version: IEEE Transactions on Information Theory 63(10): 6256-6270 (2017). [Journal]
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]
Information Processing Letters 115(12): 923-926 (2015) [Journal]
Joshua Baron, Karim El Defrawy, Joshua Lampkins, Rafail Ostrovsky: Communication-Optimal Proactive Secret Sharing for Dynamic Groups
[Abstract] [pdf]
ACNS 2015: 23-41
Sanjam Garg, Steve Lu, Rafail Ostrovsky: Black-Box Garbled RAM
[Abstract] [pdf]
FOCS 2015: 210-229
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
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
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
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): i204-i211 (2014) [Journal]
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
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
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 Theoretical Computer Science 554: 50-63 (2014) [Journal]
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 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: 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 Information and Computation 243: 178-190 (2015) [Journal]
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: 315-333
Journal version: Journal of Cryptology 35(3), Article 15 (2022). [Journal]
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
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: Constructing Non-malleable Commitments: A Black-Box Approach
[Abstract] [pdf]
FOCS 2012: 51-60

2011

Brett Hemenway, Rafail Ostrovsky, Martin J. Strauss, Mary Wootters: 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 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]
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 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: 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]
Appeared in IWCC 2011: 126-141.
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

Vipul Goyal, Abhishek Jain, Rafail Ostrovsky: 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
Paul Bunn, Rafail Ostrovsky: Asynchronous Throughput-Optimal Routing in Malicious Networks
[Abstract] [pdf]
ICALP 2010: 236-248
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: 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: 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: Simulation-Based Concurrent Non-Malleable Commitments and Decommitments
[Abstract] [postscript] [pdf]
(TCC-2009) 91-108

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. Full version appeared in Journal of Combinatorial Optimization 21(1): 47-66 (2011). [Journal]
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] (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]

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
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]

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.
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]

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.
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

2004

Jonathan Katz, Rafail Ostrovsky, Michael O. Rabin: 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.

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 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: 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 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]

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: 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.

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 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

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: 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

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). [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

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) [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

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]
STOC 1995: 559-568
Journal version: SIAM Journal on Computing 27(6): 1531-1549 (1998). [Journal]

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: 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.
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. [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.

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 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

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
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]

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 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)