Rafail Ostrovsky

Steve Lu, Rafail Ostrovsky, Amit Sahai, Hovav Shacham, Brent Waters: Sequential Aggregate Signatures, Multisignatures, and Verifiably Encrypted Signatures Without Random Oracles. J. Cryptology 26(2): 340-373 (2013)

Joshua Baron, Yuval Ishai, Rafail Ostrovsky: On Linear-Size Pseudorandom Generators and Hardcore Functions. COCOON 2013: 169-181

Vladimir Braverman, Ran Gelles, Rafail Ostrovsky: How to Catch L ₂-Heavy-Hitters on Sliding Windows. COCOON 2013: 638-650

Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti, Akshay Wadia: Universally Composable Secure Computation with (Malicious) Physically Uncloneable Functions. EUROCRYPT 2013: 702-718

Steve Lu, Rafail Ostrovsky: How to Garble RAM Programs? EUROCRYPT 2013: 719-734

Abishek Kumarasubramanian, Rafail Ostrovsky, Omkant Pandey, Akshay Wadia: Cryptography Using Captcha Puzzles. Public Key Cryptography 2013: 89-106

Vipul Goyal, Abhishek Jain, Rafail Ostrovsky, Silas Richelson, Ivan Visconti: Concurrent Zero Knowledge in the Bounded Player Model. TCC 2013: 60-79

Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, Omer Paneth: Succinct Non-interactive Arguments via Linear Interactive Proofs. TCC 2013: 315-333

Steve Lu, Rafail Ostrovsky: Distributed Oblivious RAM for Secure Two-Party Computation. TCC 2013: 377-396

Rafail Ostrovsky, Vanishree Rao, Alessandra Scafuro, Ivan Visconti: Revisiting Lower and Upper Bounds for Selective Decommitments. TCC 2013: 559-578

Vladimir Braverman, Rafail Ostrovsky, Dan Vilenchik: How Hard is Counting Triangles in the Streaming Model. CoRR abs/1304.1458 (2013)

Paul Bunn, Rafail Ostrovsky: Secure End-to-End Communication with Optimal Throughput in Unreliable Networks. CoRR abs/1304.2454 (2013)

Brett Hemenway, Rafail Ostrovsky, Mary Wootters: Local Correctability of Expander Codes. CoRR abs/1304.8129 (2013)

Jens Groth, Rafail Ostrovsky, Amit Sahai: New Techniques for Noninteractive Zero-Knowledge. J. ACM 59(3): 11 (2012)

Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy: The effectiveness of lloyd-type methods for the k-means problem. J. ACM 59(6): 28 (2012)

Vladimir Braverman, Rafail Ostrovsky, Carlo Zaniolo: Optimal sampling from sliding windows. J. Comput. Syst. Sci. 78(1): 260-272 (2012)

Milan Bradonjic, Eddie Kohler, Rafail Ostrovsky: Near-optimal radio use for wireless network synchronization. Theor. Comput. Sci. 453: 14-28 (2012)

Sanjam Garg, Abishek Kumarasubramanian, Rafail Ostrovsky, Ivan Visconti: Impossibility Results for Static Input Secure Computation. CRYPTO 2012: 424-442

Eli Ben-Sasson, Serge Fehr, Rafail Ostrovsky: Near-Linear Unconditionally-Secure Multiparty Computation with a Dishonest Minority. CRYPTO 2012: 663-680

Alfonso Cevallos, Serge Fehr, Rafail Ostrovsky, Yuval Rabani: Unconditionally-Secure Robust Secret Sharing with Compact Shares. EUROCRYPT 2012: 195-208

Vipul Goyal, Chen-Kuei Lee, Rafail Ostrovsky, Ivan Visconti: Constructing Non-malleable Commitments: A Black-Box Approach. FOCS 2012: 51-60

Joshua Baron, Rafail Ostrovsky, Ivan Visconti: Nearly Simultaneously Resettable Black-Box Zero Knowledge. ICALP (1) 2012: 88-99

Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky: Edge Fault Tolerance on Sparse Networks. ICALP (2) 2012: 452-463

Ran Gelles, Rafail Ostrovsky, Kina Winoto: Multiparty Proximity Testing with Dishonest Majority from Equality Testing. ICALP (2) 2012: 537-548

Brett Hemenway, Rafail Ostrovsky: On Homomorphic Encryption and Chosen-Ciphertext Security. Public Key Cryptography 2012: 52-65

Brett Hemenway, Steve Lu, Rafail Ostrovsky: Correlated Product Security from Any One-Way Function. Public Key Cryptography 2012: 558-575

Brett Hemenway, Rafail Ostrovsky: Extended-DDH and Lossy Trapdoor Functions. Public Key Cryptography 2012: 627-643

Joshua Baron, Karim El Defrawy, Kirill Minkovich, Rafail Ostrovsky, Eric Tressler: 5PM: Secure Pattern Matching. SCN 2012: 222-240

Eyal Kushilevitz, Steve Lu, Rafail Ostrovsky: On the (in)security of hash-based oblivious RAM and a new balancing scheme. SODA 2012: 143-156

Yuval Ishai, Rafail Ostrovsky, Hakan Seyalioglu: Identifying Cheaters without an Honest Majority. TCC 2012: 21-38

Sanjam Garg, Rafail Ostrovsky, Ivan Visconti, Akshay Wadia: Resettable Statistical Zero Knowledge. TCC 2012: 494-511

Chongwon Cho, Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti: Simultaneously Resettable Arguments of Knowledge. TCC 2012: 530-547

Vladimir Braverman, Rafail Ostrovsky: Approximating Large Frequency Moments with Pick-and-Drop Sampling. CoRR abs/1212.0202 (2012)

Mattew Franklin, Ran Gelles, Rafail Ostrovsky, Leonard J. Schulman: Optimal Coding for Streaming Authentication and Interactive Communication. Electronic Colloquium on Computational Complexity (ECCC) 19: 104 (2012)

Rafail Ostrovsky, Ivan Visconti: Simultaneous Resettability from Collision Resistance. Electronic Colloquium on Computational Complexity (ECCC) 19: 164 (2012)

Juan A. Garay, Clint Givens, Rafail Ostrovsky: Broadcast-Efficient Secure Multiparty Computation. IACR Cryptology ePrint Archive 2012: 130 (2012)

Rafail Ostrovsky, Alessandra Scafuro, Ivan Visconti, Akshay Wadia: Universally Composable Secure Computation with (Malicious) Physically Uncloneable Functions. IACR Cryptology ePrint Archive 2012: 143 (2012)

Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky: Almost-Everywhere Secure Computation with Edge Corruptions. IACR Cryptology ePrint Archive 2012: 221 (2012)

Abhishek Jain, Rafail Ostrovsky, Silas Richelson, Ivan Visconti: Concurrent Zero Knowledge in the Bounded Player Model. IACR Cryptology ePrint Archive 2012: 279 (2012)

Ran Gelles, Rafail Ostrovsky, Kina Winoto: Multiparty Proximity Testing with Dishonest Majority from Equality Testing. IACR Cryptology ePrint Archive 2012: 378 (2012)

Sanjam Garg, Abishek Kumarasubramanian, Rafail Ostrovsky, Ivan Visconti: Impossibility Results for Static Input Secure Computation. IACR Cryptology ePrint Archive 2012: 433 (2012)

Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin: Privacy Amplification with Asymptotically Optimal Entropy Loss. IACR Cryptology ePrint Archive 2012: 501 (2012)

Steve Lu, Rafail Ostrovsky: How to Garble RAM Programs. IACR Cryptology ePrint Archive 2012: 601 (2012)

Abishek Kumarasubramanian, Rafail Ostrovsky, Omkant Pandey, Akshay Wadia: Cryptography Using CAPTCHA Puzzles. IACR Cryptology ePrint Archive 2012: 689 (2012)

Joshua Baron, Karim El Defrawy, Kirill Minkovich, Rafail Ostrovsky, Eric Tressler: 5PM: Secure Pattern Matching. IACR Cryptology ePrint Archive 2012: 698 (2012)

Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, Omer Paneth: Succinct Non-Interactive Arguments via Linear Interactive Proofs. IACR Cryptology ePrint Archive 2012: 718 (2012)

Steve Lu, Daniel Manchala, Rafail Ostrovsky: Visual cryptography on graphs. J. Comb. Optim. 21(1): 47-66 (2011)

Reza Curtmola, Juan A. Garay, Seny Kamara, Rafail Ostrovsky: Searchable symmetric encryption: Improved definitions and efficient constructions. Journal of Computer Security 19(5): 895-934 (2011)

Brett Hemenway, Rafail Ostrovsky, Martin J. Strauss, Mary Wootters: Public Key Locally Decodable Codes with Short Keys. 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. ASIACRYPT 2011: 70-88

Juan A. Garay, Clint Givens, Rafail Ostrovsky: Secure Message Transmission by Public Discussion: A Brief Survey. IWCC 2011: 126-141

Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner: Position-Based Quantum Cryptography: Impossibility and Constructions. CRYPTO 2011: 429-446

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, Jürg Wullschleger: Constant-Rate Oblivious Transfer from Noisy Channels. CRYPTO 2011: 667-684

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai: Efficient Non-interactive Secure Computation. EUROCRYPT 2011: 406-425

Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, Brian Tagiku: Streaming k-means on Well-Clusterable Data. SODA 2011: 26-40

Leonid Barenboim, Shlomi Dolev, Rafail Ostrovsky: Deterministic and Energy-Optimal Wireless Synchronization. DISC 2011: 237-251

Rafail Ostrovsky (Ed.): IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011. IEEE 2011, isbn 978-1-4577-1843-4

Brett Hemenway, Rafail Ostrovsky, Martin Strauss, Mary Wootters: Public Key Locally Decodable Codes with Short Keys. Electronic Colloquium on Computational Complexity (ECCC) 18: 118 (2011)

Eyal Kushilevitz, Steve Lu, Rafail Ostrovsky: On the (In)security of Hash-based Oblivious RAM and a New Balancing Scheme. IACR Cryptology ePrint Archive 2011: 327 (2011)

Steve Lu, Rafail Ostrovsky: Multi-Server Oblivious RAM. IACR Cryptology ePrint Archive 2011: 384 (2011)

Sanjam Garg, Rafail Ostrovsky, Ivan Visconti, Akshay Wadia: Resettable Statistical Zero Knowledge. IACR Cryptology ePrint Archive 2011: 457 (2011)

Rafail Ostrovsky, Vanishree Rao, Alessandra Scafuro, Ivan Visconti: Revisiting Lower and Upper Bounds for Selective Decommitments. IACR Cryptology ePrint Archive 2011: 536 (2011)

Eli Ben-Sasson, Serge Fehr, Rafail Ostrovsky: Near-Linear Unconditionally-Secure Multiparty Computation with a Dishonest Minority. IACR Cryptology ePrint Archive 2011: 629 (2011)

Vladimir Braverman, Rafail Ostrovsky: Effective Computations on Sliding Windows. SIAM J. Comput. 39(6): 2113-2131 (2010)

Vipul Goyal, Abhishek Jain, Rafail Ostrovsky: Password-Authenticated Session-Key Generation on the Internet in the Plain Model. CRYPTO 2010: 277-294

Chongwon Cho, Chen-Kuei Lee, Rafail Ostrovsky: Equivalence of Uniform Key Agreement and Composition Insecurity. CRYPTO 2010: 447-464

Juan A. Garay, Clint Givens, Rafail Ostrovsky: Secure Message Transmission with Small Public Discussion. EUROCRYPT 2010: 177-196

Paul Bunn, Rafail Ostrovsky: Asynchronous Throughput-Optimal Routing in Malicious Networks. ICALP (2) 2010: 236-248

Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky: Improved Fault Tolerance and Secure Computation on Sparse Networks. ICALP (2) 2010: 249-260

Nishanth Chandran, Rafail Ostrovsky, William E. Skeith III: Public-Key Encryption with Efficient Amortized Updates. SCN 2010: 17-35

Vladimir Braverman, Kai-Min Chung, Zhenming Liu, Michael Mitzenmacher, Rafail Ostrovsky: AMS Without 4-Wise Independence on Product Domains. STACS 2010: 119-130

Vladimir Braverman, Rafail Ostrovsky: Measuring independence of datasets. STOC 2010: 271-280

Vladimir Braverman, Rafail Ostrovsky: Zero-one frequency laws. STOC 2010: 281-290

Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin: Privacy amplification with asymptotically optimal entropy loss. STOC 2010: 785-794

S. Dov Gordon, Yuval Ishai, Tal Moran, Rafail Ostrovsky, Amit Sahai: On Complete Primitives for Fairness. TCC 2010: 91-108

Rafail Ostrovsky, Omkant Pandey, Ivan Visconti: Efficiency Preserving Transformations for Concurrent Non-malleable Zero Knowledge. TCC 2010: 535-552

Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner: Position-Based Quantum Cryptography: Impossibility and Constructions. CoRR abs/1009.2490 (2010)

Leonid Barenboim, Shlomi Dolev, Rafail Ostrovsky: Deterministic and Energy-Optimal Wireless Synchronization. CoRR abs/1010.1112 (2010)

Vladimir Braverman, Rafail Ostrovsky: Recursive Sketching For Frequency Moments. CoRR abs/1011.2571 (2010)

Vladimir Braverman, Rafail Ostrovsky, Yuval Rabani: Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform. CoRR abs/1011.2590 (2010)

Vladimir Braverman, Ran Gelles, Rafail Ostrovsky: How to Catch L_2-Heavy-Hitters on Sliding Windows. CoRR abs/1012.3130 (2010)

Brett Hemenway, Rafail Ostrovsky: Building Injective Trapdoor Functions From Oblivious Transfer. Electronic Colloquium on Computational Complexity (ECCC) 17: 127 (2010)

Brett Hemenway, Rafail Ostrovsky: Homomorphic Encryption Over Cyclic Groups Implies Chosen-Ciphertext Security. IACR Cryptology ePrint Archive 2010: 99 (2010)

Brett Hemenway, Steve Lu, Rafail Ostrovsky: Correlated Product Security From Any One-Way Function and the New Notion of Decisional Correlated Product Security. IACR Cryptology ePrint Archive 2010: 100 (2010)

Paul Bunn, Rafail Ostrovsky: Throughput-Optimal Routing in Unreliable Networks. IACR Cryptology ePrint Archive 2010: 231 (2010)

Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner: Position-Based Quantum Cryptography: Impossibility and Constructions. IACR Cryptology ePrint Archive 2010: 275 (2010)

Jonathan Katz, Rafail Ostrovsky, Moti Yung: Efficient and secure authenticated key exchange using weak passwords. J. ACM 57(1) (2009)

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai: Zero-Knowledge Proofs from Secure Multiparty Computation. SIAM J. Comput. 39(3): 1121-1152 (2009)

Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman: Error-correcting codes for automatic control. IEEE Transactions on Information Theory 55(7): 2931-2941 (2009)

Milan Bradonjic, Eddie Kohler, Rafail Ostrovsky: Near-Optimal Radio Use for Wireless Network Synchronization. ALGOSENSORS 2009: 15-28

Nishanth Chandran, Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky: Position Based Cryptography. CRYPTO 2009: 391-407

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai: Extracting Correlations. FOCS 2009: 261-270

Vladimir Braverman, Rafail Ostrovsky, Carlo Zaniolo: Optimal sampling from sliding windows. PODS 2009: 147-156

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti: Simulation-Based Concurrent Non-malleable Commitments and Decommitments. TCC 2009: 91-108

Yair Amir, Paul Bunn, Rafail Ostrovsky: Authenticated Adversarial Routing. TCC 2009: 163-182

Vladimir Braverman, Rafail Ostrovsky: Measuring Independence of Datasets. CoRR abs/0903.0034 (2009)

Paul Bunn, Rafail Ostrovsky: Throughput in Asynchronous Networks. CoRR abs/0910.4572 (2009)

Chongwon Cho, Chen-Kuei Lee, Rafail Ostrovsky: Equivalence of Uniform Key Agreement and Composition Insecurity. Electronic Colloquium on Computational Complexity (ECCC) 16: 108 (2009)

Brett Hemenway, Rafail Ostrovsky: Lossy Trapdoor Functions from Smooth Homomorphic Hash Proof Systems. Electronic Colloquium on Computational Complexity (ECCC) 16: 127 (2009)

Brett Hemenway, Benoît Libert, Rafail Ostrovsky, Damien Vergnaud: Lossy Encryption: Constructions from General Assumptions and Efficient Selective Opening Chosen Ciphertext Security. IACR Cryptology ePrint Archive 2009: 88 (2009)

Nishanth Chandran, Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky: Position Based Cryptography. IACR Cryptology ePrint Archive 2009: 364 (2009)

Juan A. Garay, Clint Givens, Rafail Ostrovsky: Secure Message Transmission with Small Public Discussion. IACR Cryptology ePrint Archive 2009: 519 (2009)

Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam Smith: Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. SIAM J. Comput. 38(1): 97-139 (2008)

Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Mohammad Ali Safari, Amit Sahai: Improved algorithms for optimal embeddings. ACM Transactions on Algorithms 4(4) (2008)

Steve Lu, Daniel Manchala, Rafail Ostrovsky: Visual Cryptography on Graphs. COCOON 2008: 225-234

Dan Boneh, Shai Halevi, Michael Hamburg, Rafail Ostrovsky: Circular-Secure Encryption from Decision Diffie-Hellman. CRYPTO 2008: 108-125

Brett Hemenway, Rafail Ostrovsky: Public-Key Locally-Decodable Codes. CRYPTO 2008: 126-143

Rafail Ostrovsky, William E. Skeith III: Communication Complexity in Algebraic Two-Party Protocols. CRYPTO 2008: 379-396

Juan A. Garay, Rafail Ostrovsky: Almost-Everywhere Secure Computation. EUROCRYPT 2008: 307-323

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti: Constant-Round Concurrent Non-malleable Zero Knowledge in the Bare Public-Key Model. ICALP (2) 2008: 548-559

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai: Cryptography with constant computational overhead. STOC 2008: 433-442

Rafail Ostrovsky, Roberto De Prisco, Ivan Visconti (Eds.): Security and Cryptography for Networks, 6th International Conference, SCN 2008, Amalfi, Italy, September 10-12, 2008. Proceedings. Lecture Notes in Computer Science 5229, Springer 2008, isbn 978-3-540-85854-6

Vladimir Braverman, Rafail Ostrovsky: Measuring $k$-Wise Independence of Streaming Data. CoRR abs/0806.4790 (2008)

Yair Amir, Paul Bunn, Rafail Ostrovsky: Optimal-Rate Coding Theorem For Adversarial Networks in the Public-Key Setting. CoRR abs/0808.0156 (2008)

Milan Bradonjic, Eddie Kohler, Rafail Ostrovsky: Near-Optimal Radio Use For Wireless Network Synchronization. CoRR abs/0810.1756 (2008)

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti: Constant-Round Concurrent Non-Malleable Commitments and Decommitments. IACR Cryptology ePrint Archive 2008: 235 (2008)

Nishanth Chandran, Rafail Ostrovsky, William E. Skeith III: Public-Key Encryption with Efficient Amortized Updates. IACR Cryptology ePrint Archive 2008: 429 (2008)

Yair Amir, Paul Bunn, Rafail Ostrovsky: Authenticated Adversarial Routing. IACR Cryptology ePrint Archive 2008: 448 (2008)

Rafail Ostrovsky, Yuval Rabani: Low distortion embeddings for edit distance. J. ACM 54(5) (2007)

Rafail Ostrovsky, William E. Skeith III: Private Searching on Streaming Data. J. Cryptology 20(4): 397-430 (2007)

Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky, Amit Sahai: Concurrent Statistical Zero-Knowledge Arguments for NP from One Way Functions. ASIACRYPT 2007: 444-459

Rafail Ostrovsky, Amit Sahai, Brent Waters: Attribute-based encryption with non-monotonic access structures. ACM Conference on Computer and Communications Security 2007: 195-203

Paul Bunn, Rafail Ostrovsky: Secure two-party k-means clustering. ACM Conference on Computer and Communications Security 2007: 486-497

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky: Efficient Arguments without Short PCPs. IEEE Conference on Computational Complexity 2007: 278-291

Dan Boneh, Eyal Kushilevitz, Rafail Ostrovsky, William E. Skeith III: Public Key Encryption That Allows PIR Queries. CRYPTO 2007: 50-67

Jens Groth, Rafail Ostrovsky: Cryptography in the Multi-string Model. CRYPTO 2007: 323-341

Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky, Amit Sahai: Covert Multi-Party Computation. FOCS 2007: 238-248

Vladimir Braverman, Rafail Ostrovsky: Smooth Histograms for Sliding Windows. FOCS 2007: 283-293

Juan A. Garay, Jonathan Katz, Chiu-Yuen Koo, Rafail Ostrovsky: Round Complexity of Authenticated Broadcast with a Dishonest Majority. FOCS 2007: 658-668

Rafail Ostrovsky, Omkant Pandey, Amit Sahai: Private Locally Decodable Codes. ICALP 2007: 387-398

Rafail Ostrovsky, William E. Skeith III: A Survey of Single-Database Private Information Retrieval: Techniques and Applications. Public Key Cryptography 2007: 393-411

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai: Zero-knowledge from secure multiparty computation. STOC 2007: 21-30

Vladimir Braverman, Rafail Ostrovsky, Carlo Zaniolo: Succinct Sampling on Streams. CoRR abs/cs/0702151 (2007)

Brett Hemenway, Rafail Ostrovsky: Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code. Electronic Colloquium on Computational Complexity (ECCC) 14(021) (2007)

Rafail Ostrovsky, William E. Skeith III: Algebraic Lower Bounds for Computing on Encrypted Data. Electronic Colloquium on Computational Complexity (ECCC) 14(022) (2007)

Rafail Ostrovsky, Omkant Pandey, Amit Sahai: Private Locally Decodable Codes. IACR Cryptology ePrint Archive 2007: 25 (2007)

Rafail Ostrovsky, William E. Skeith III: A Survey of Single Database PIR: Techniques and Applications. IACR Cryptology ePrint Archive 2007: 59 (2007)

Rafail Ostrovsky, William E. Skeith III: Algebraic Lower Bounds for Computing on Encrypted Data. IACR Cryptology ePrint Archive 2007: 64 (2007)

Dan Boneh, Eyal Kushilevitz, Rafail Ostrovsky, William E. Skeith III: Public Key Encryption that Allows PIR Queries. IACR Cryptology ePrint Archive 2007: 73 (2007)

Brett Hemenway, Rafail Ostrovsky: Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code. IACR Cryptology ePrint Archive 2007: 83 (2007)

Paul Bunn, Rafail Ostrovsky: Secure Two-Party k-Means Clustering. IACR Cryptology ePrint Archive 2007: 231 (2007)

Rafail Ostrovsky, Amit Sahai, Brent Waters: Attribute-Based Encryption with Non-Monotonic Access Structures. IACR Cryptology ePrint Archive 2007: 323 (2007)

Juan A. Garay, Rafail Ostrovsky: Almost-everywhere Secure Computation. IACR Cryptology ePrint Archive 2007: 394 (2007)

Julia Chuzhoy, Rafail Ostrovsky, Yuval Rabani: Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems. Math. Oper. Res. 31(4): 730-738 (2006)

Reza Curtmola, Juan A. Garay, Seny Kamara, Rafail Ostrovsky: Searchable symmetric encryption: improved definitions and efficient constructions. ACM Conference on Computer and Communications Security 2006: 79-88

Jens Groth, Rafail Ostrovsky, Amit Sahai: Non-interactive Zaps and New Techniques for NIZK. CRYPTO 2006: 97-111

Jens Groth, Rafail Ostrovsky, Amit Sahai: Perfect Non-interactive Zero Knowledge for NP. EUROCRYPT 2006: 339-358

Steve Lu, Rafail Ostrovsky, Amit Sahai, Hovav Shacham, Brent Waters: Sequential Aggregate Signatures and Multisignatures Without Random Oracles. EUROCRYPT 2006: 465-485

Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy: The Effectiveness of Lloyd-Type Methods for the k-Means Problem. FOCS 2006: 165-176

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai: Cryptography from Anonymity. FOCS 2006: 239-248

Shlomi Dolev, Rafail Ostrovsky, Andreas Pfitzmann (Eds.): Anonymous Communication and its Applications, 09.10. - 14.10.2005. Dagstuhl Seminar Proceedings 05411, Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany 2006

Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam Smith: Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. CoRR abs/cs/0602007 (2006)

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti: Concurrent Non-Malleable Witness Indistinguishability and its Applications. Electronic Colloquium on Computational Complexity (ECCC) 13(095) (2006)

Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Amit Sahai: Improved Algorithms for Optimal Embeddings. Electronic Colloquium on Computational Complexity (ECCC) 13(110) (2006)

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai: Cryptography from Anonymity. IACR Cryptology ePrint Archive 2006: 84 (2006)

Steve Lu, Rafail Ostrovsky, Amit Sahai, Hovav Shacham, Brent Waters: Sequential Aggregate Signatures and Multisignatures without Random Oracles. IACR Cryptology ePrint Archive 2006: 96 (2006)

Reza Curtmola, Juan A. Garay, Seny Kamara, Rafail Ostrovsky: Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions. IACR Cryptology ePrint Archive 2006: 210 (2006)

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti: Constant-Round Concurrent NMWI and its relation to NMZK. IACR Cryptology ePrint Archive 2006: 256 (2006)

Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky, Amit Sahai: Concurrent Statistical Zero-Knowledge Arguments for NP from One Way Functions. IACR Cryptology ePrint Archive 2006: 400 (2006)

Jens Groth, Rafail Ostrovsky: Cryptography in the Multi-string Model. IACR Cryptology ePrint Archive 2006: 407 (2006)

Matthias Fitzi, Juan A. Garay, Ueli M. Maurer, Rafail Ostrovsky: Minimal Complete Primitives for Secure Multi-Party Computation. J. Cryptology 18(1): 37-61 (2005)

Rafail Ostrovsky, William E. Skeith III: Private Searching on Streaming Data. CRYPTO 2005: 223-240

Shlomi Dolev, Andreas Pfitzmann, Rafail Ostrovsky: 05411 Abstracts Collection -- Anonymous Communication and its Applications. Anonymous Communication and its Applications 2005

Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, Adam Smith: Secure Remote Authentication Using Biometric Data. EUROCRYPT 2005: 147-163

Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman: Error-Correcting Codes for Automatic Control. FOCS 2005: 309-316

Rafail Ostrovsky, Yuval Rabani: Low distortion embeddings for edit distance. STOC 2005: 218-224

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky: Sufficient Conditions for Collision-Resistant Hashing. TCC 2005: 445-456

Jens Groth, Rafail Ostrovsky, Amit Sahai: Perfect Non-Interactive Zero Knowledge for NP. Electronic Colloquium on Computational Complexity (ECCC)(097) (2005)

Rafail Ostrovsky, William E. Skeith III: Private Searching On Streaming Data. IACR Cryptology ePrint Archive 2005: 242 (2005)

Jens Groth, Rafail Ostrovsky, Amit Sahai: Perfect Non-Interactive Zero Knowledge for NP. IACR Cryptology ePrint Archive 2005: 290 (2005)

Allan Borodin, Rafail Ostrovsky, Yuval Rabani: Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds. Journal of Interconnection Networks 5(1): 1-12 (2004)

Allan Borodin, Rafail Ostrovsky, Yuval Rabani: Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. Machine Learning 56(1-3): 153-167 (2004)

Jonathan Katz, Rafail Ostrovsky: Round-Optimal Secure Two-Party Computation. CRYPTO 2004: 335-354

Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano: Public Key Encryption with Keyword Search. EUROCRYPT 2004: 506-522

Rafail Ostrovsky, Charles Rackoff, Adam Smith: Efficient Consistency Proofs for Generalized Queries on a Committed Database. ICALP 2004: 1041-1053

Jonathan Katz, Rafail Ostrovsky, Michael O. Rabin: Identity-Based Zero Knowledge. SCN 2004: 180-192

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai: Batch codes and their applications. STOC 2004: 262-271

Rafail Ostrovsky, Charles Rackoff, Adam Smith: Efficient Consistency Proofs for Generalized Queries on a Committed Database. IACR Cryptology ePrint Archive 2004: 170 (2004)

Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén: Amortizing Randomness in Private Multiparty Computations. SIAM J. Discrete Math. 16(4): 533-544 (2003)

Jonathan Katz, Rafail Ostrovsky, Adam Smith: Round Efficiency of Multi-party Computation with a Dishonest Majority. EUROCRYPT 2003: 578-595

William Aiello, Rafail Ostrovsky, Eyal Kushilevitz, Adi Rosén: Dynamic routing on networks with fixed-size buffers. SODA 2003: 771-780

Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano: Public Key Encryption with keyword Search. IACR Cryptology ePrint Archive 2003: 195 (2003)

Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam Smith: Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. IACR Cryptology ePrint Archive 2003: 235 (2003)

Rafail Ostrovsky, Yuval Rabani: Polynomial-time approximation schemes for geometric min-sum median clustering. J. ACM 49(2): 139-156 (2002)

Alain J. Mayer, Rafail Ostrovsky, Yoram Ofek, Moti Yung: Self-Stabilizing Symmetry Breaking in Constant Space. SIAM J. Comput. 31(5): 1571-1595 (2002)

Jonathan Katz, Rafail Ostrovsky, Moti Yung: Forward Secrecy in Password-Only Key Exchange Protocols. SCN 2002: 29-44

Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, Amit Sahai: Universally composable two-party and multi-party secure computation. STOC 2002: 494-503

Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, Amit Sahai: Universally Composable Two-Party and Multi-Party Secure Computation. IACR Cryptology ePrint Archive 2002: 140 (2002)

Giovanni Di Crescenzo, Yuval Ishai, Rafail Ostrovsky: Universal Service-Providers for Private Information Retrieval. J. Cryptology 14(1): 37-74 (2001)

Matthias Fitzi, Juan A. Garay, Ueli M. Maurer, Rafail Ostrovsky: Minimal Complete Primitives for Secure Multi-party Computation. CRYPTO 2001: 80-100

Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano, Amit Sahai: Robust Non-interactive Zero Knowledge. CRYPTO 2001: 566-598

Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky, Adam Smith: Efficient and Non-interactive Non-malleable Commitment. EUROCRYPT 2001: 40-59

Jonathan Katz, Steven Myers, Rafail Ostrovsky: Cryptographic Counters and Applications to Electronic Voting. EUROCRYPT 2001: 78-92

Jonathan Katz, Rafail Ostrovsky, Moti Yung: Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords. EUROCRYPT 2001: 475-494

Julia Chuzhoy, Rafail Ostrovsky, Yuval Rabani: Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems. FOCS 2001: 348-356

Allan Borodin, Rafail Ostrovsky, Yuval Rabani: Stability preserving transformations: packet routing networks with edge capacities and speeds. SODA 2001: 601-610

Jonathan Katz, Rafail Ostrovsky, Moti Yung: Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords. IACR Cryptology ePrint Archive 2001: 31 (2001)

Giovanni Di Crescenzo, Jonathan Katz, Rafail Ostrovsky, Adam Smith: Efficient and Non-Interactive Non-Malleable Commitment. IACR Cryptology ePrint Archive 2001: 32 (2001)

Shay Kutten, Rafail Ostrovsky, Boaz Patt-Shamir: The Las-Vegas Processor Identity Problem (How and When to Be Unique). J. Algorithms 37(2): 468-494 (2000)

William Aiello, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén: Adaptive Packet Routing for Bursty Adversarial Traffic. J. Comput. Syst. Sci. 60(3): 482-509 (2000)

Ran Canetti, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén: Randomness versus Fault-Tolerance. J. Cryptology 13(1): 107-142 (2000)

Joe Kilian, Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky: Reducibility and Completeness in Private Computations. SIAM J. Comput. 29(4): 1189-1208 (2000)

Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani: Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces. SIAM J. Comput. 30(2): 457-474 (2000)

Shlomi Dolev, Rafail Ostrovsky: Xor-trees for efficient anonymous multicast and reception. ACM Trans. Inf. Syst. Secur. 3(2): 63-84 (2000)

Eyal Kushilevitz, Rafail Ostrovsky: One-Way Trapdoor Permutations Are Sufficient for Non-trivial Single-Server Private Information Retrieval. EUROCRYPT 2000: 104-121

Giovanni Di Crescenzo, Tal Malkin, Rafail Ostrovsky: Single Database Private Information Retrieval Implies Oblivious Transfer. EUROCRYPT 2000: 122-138

Rafail Ostrovsky, Yuval Rabani: Polynomial Time Approximation Schemes for Geometric k-Clustering. FOCS 2000: 349-358

William Aiello, Sandeep N. Bhatt, Rafail Ostrovsky, Sivaramakrishnan Rajagopalan: Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP. ICALP 2000: 463-474

Eyal Kushilevitz, Nathan Linial, Rafail Ostrovsky: The Linear-Array Conjecture in Communication Complexity Is False. Combinatorica 19(2): 241-254 (1999)

Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén: Characterizing Linear Size Circuits in Terms of Pricacy. J. Comput. Syst. Sci. 58(1): 129-136 (1999)

Giovanni Di Crescenzo, Rafail Ostrovsky: On Concurrent Zero-Knowledge with Pre-processing. CRYPTO 1999: 485-502

Giovanni Di Crescenzo, Rafail Ostrovsky, Sivaramakrishnan Rajagopalan: Conditional Oblivious Transfer and Timed-Release Encryption. EUROCRYPT 1999: 74-89

Rafail Ostrovsky, Boaz Patt-Shamir: Optimal and Efficient Clock Synchronization Under Drifting Clocks. PODC 1999: 3-12

Ran Canetti, Rafail Ostrovsky: Secure Computation with Honest-Looking Parties: What If Nobody Is Truly Honest? (Extended Abstract). STOC 1999: 255-264

Allan Borodin, Rafail Ostrovsky, Yuval Rabani: Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems. STOC 1999: 312-321

Allan Borodin, Rafail Ostrovsky, Yuval Rabani: Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. STOC 1999: 435-444

Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung: Perfect Zero-Knowledge Arguments for NP Using Any One-Way Permutation. J. Cryptology 11(2): 87-108 (1998)

Oded Goldreich, Rafail Ostrovsky, Erez Petrank: Computational Complexity and Knowledge Complexity. SIAM J. Comput. 27(4): 1116-1141 (1998)

Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén: Log-Space Polynomial End-to-End Communication. SIAM J. Comput. 27(6): 1531-1549 (1998)

William Aiello, Sachin Lodha, Rafail Ostrovsky: Fast Digital Identity Revocation (Extended Abstract). CRYPTO 1998: 137-152

Richard J. Lipton, Rafail Ostrovsky: Micropayments via Efficient Coin-Flipping. Financial Cryptography 1998: 1-15

Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén: Amortizing Randomness in Private Multiparty Computations. PODC 1998: 81-90

Giovanni Di Crescenzo, Yuval Ishai, Rafail Ostrovsky: Universal Service-Providers for Database Private Information Retrieval (Extended Abstract). PODC 1998: 91-100

Giovanni Di Crescenzo, Yuval Ishai, Rafail Ostrovsky: Non-Interactive and Non-Malleable Commitment. STOC 1998: 141-150

William Aiello, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén: Adaptive Packet Routing for Bursty Adversarial Traffic. STOC 1998: 359-368

Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani: Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces. STOC 1998: 614-623

Ran Canetti, Cynthia Dwork, Moni Naor, Rafail Ostrovsky: Deniable Encryption. CRYPTO 1997: 90-104

Ari Juels, Michael Luby, Rafail Ostrovsky: Security of Blind Digital Signatures (Extended Abstract). CRYPTO 1997: 150-164

Shlomi Dolev, Rafail Ostrovsky: Efficient Anonymous Multicast and Reception (Extended Abstract). CRYPTO 1997: 395-409

Eyal Kushilevitz, Rafail Ostrovsky: Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval. FOCS 1997: 364-373

Ran Canetti, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén: Randomness vs. Fault-Tolerance. PODC 1997: 35-44

Rafail Ostrovsky, Victor Shoup: Private Information Storage (Extended Abstract). STOC 1997: 294-303

Rafail Ostrovsky, Yuval Rabani: Universal O(Congestion + Dilation + log^1+epsilonN) Local Control Packet Switching Algorithms. STOC 1997: 644-653

Oded Goldreich, Rafail Ostrovsky: Software Protection and Simulation on Oblivious RAMs. J. ACM 43(3): 431-473 (1996)

Alain J. Mayer, Rafail Ostrovsky, Moti Yung: Self-Stabilizing Algorithms for Synchronous Unidirectional Rings. SODA 1996: 564-573

Eyal Kushilevitz, Nathan Linial, Rafail Ostrovsky: The Linear-Array Conjecture in Communication Complexity is False. STOC 1996: 1-10

Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén: Characterizing Linear Size Circuits in Terms of Privacy. STOC 1996: 541-550

Rafail Ostrovsky, Daniel Shawcross Wilkerson: Faster Computation On Directed Networks of Automata (Extended Abstract). PODC 1995: 38-46

Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén: Log-Space Polynomial End-to-End Communication (Abstract). PODC 1995: 254

Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén: Log-space polynomial end-to-end communication. STOC 1995: 559-568

Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky: Reducibility and Completeness in Multi-Party Private Computations. FOCS 1994: 478-489

Baruch Awerbuch, Rafail Ostrovsky: Memory-Efficient and Self-Stabilizing Network {RESET} (Extended Abstract). PODC 1994: 254-263

Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky: Matching Nuts and Bolts. SODA 1994: 690-696

Rafail Ostrovsky, Sridhar Rajagopalan, Umesh V. Vazirani: Simple and efficient leader election in the full information model. STOC 1994: 234-242

Oded Goldreich, Rafail Ostrovsky, Erez Petrank: Computational complexity and knowledge complexity (extended abstract). STOC 1994: 534-543

Oded Goldreich, Rafail Ostrovsky, Erez Petrank: Computational Complexity and Knowledge Complexity. Electronic Colloquium on Computational Complexity (ECCC) 1(7) (1994)

Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung: Interactive Hashing Simplifies Zero-Knowledge Protocol Design. EUROCRYPT 1993: 267-273

Rafail Ostrovsky, Avi Wigderson: One-Way Fuctions are Essential for Non-Trivial Zero-Knowledge. ISTCS 1993: 3-17

Shay Kutten, Rafail Ostrovsky, Boaz Patt-Shamir: The Las-Vegas Processor Identity Problem (How and When to Be Unique). ISTCS 1993: 150-159

Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung: Perfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions (Extended Abstract). CRYPTO 1992: 196-214

Shafi Goldwasser, Rafail Ostrovsky: Invariant Signatures and Non-Interactive Zero-Knowledge Proofs are Equivalent (Extended Abstract). CRYPTO 1992: 228-245

Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung: Secure Commitment Against A Powerful Adversary. STACS 1992: 439-448

Alain J. Mayer, Yoram Ofek, Rafail Ostrovsky, Moti Yung: Self-Stabilizing Symmetry Breaking in Constant-Space (Extended Abstract). STOC 1992: 667-678

Joan Feigenbaum, Rafail Ostrovsky: A Note On One-Prover, Instance-Hiding Zero-Knowledge Proof Systems. ASIACRYPT 1991: 352-359

Rafail Ostrovsky: One-Way Functions, Hard on Average Problems, and Statistical Zero-Knowledge Proofs. Structure in Complexity Theory Conference 1991: 133-138

Rafail Ostrovsky, Moti Yung: How to Withstand Mobile Virus Attacks (Extended Abstract). PODC 1991: 51-59

Mihir Bellare, Silvio Micali, Rafail Ostrovsky: Perfect Zero-Knowledge in Constant Rounds. STOC 1990: 482-493

Mihir Bellare, Silvio Micali, Rafail Ostrovsky: The (True) Complexity of Statistical Zero Knowledge. STOC 1990: 494-502

Rafail Ostrovsky: Efficient Computation on Oblivious RAMs. STOC 1990: 514-523

Joe Kilian, Silvio Micali, Rafail Ostrovsky: Minimum Resource Zero-Knowledge Proofs (Extended Abstract). CRYPTO 1989: 545-546

Rafail Ostrovsky: An Efficient Software Protection Scheme. CRYPTO 1989: 610-611

Joe Kilian, Silvio Micali, Rafail Ostrovsky: Minimum Resource Zero-Knowledge Proofs (Extended Abstract). FOCS 1989: 474-479

Rafail Ostrovsky: HOLMES-I, a prolog-based reason maintenance system for collecting information from multiple experts. IPMU 1986: 329-336