About

Rafail Ostrovsky holds the Norman E. Friedman Chair in Knowledge Sciences at UCLA Samueli School of Engineering. He is a distinguished professor of computer science and mathematics at UCLA. His research focuses on the theory of computation, cryptography and security, distributed algorithms, high-dimensional search, routing and flow control in communication networks, and cybersecurity and the future internet. Ostrovsky has authored over 350 refereed publications and holds 15 issued patents. He has served as chair of the IEEE Technical Committee on Mathematical Foundations of Computing and has been involved in numerous international conference programs and editorial boards. His work has earned him multiple awards, including the IEEE Computer Society Edward J. McCluskey Technical Achievement Award, the RSA Award for Excellence in Mathematics, and the W. Wallace McDowell Award, the highest award given by the IEEE Computer Society. He is a Fellow of the AAAS, ACM, IEEE, and IACR, and a foreign member of Academia Europaea.

Research topics

• Computer Science
• Artificial Intelligence
• Computer Security
• Theoretical computer science
• Programming language
• Discrete mathematics
• Mathematics
• Computer network
• Distributed computing
• Operating system
• Algorithm

Selected publications

• Universally Composable Almost-Everywhere Secure Computation

  Journal of Cryptology · 2026-01-01 · 2 citations

  preprintOpen access
  PublisherOA PDFDOI

• Black-Box Constant-Round Secure 2PC with Succinct Communication

  Lecture notes in computer science · 2025-01-01 · 3 citations

  book-chapter
  PublisherDOI

• Query-Reusable Proof Systems

  Lecture notes in computer science · 2025-01-01

  book-chapter
  PublisherDOI

• Game of Trust: How Trustworthy Does Your Blockchain Think You Are?

  ArXiv.org · 2025-05-20

  preprintOpen access

  We investigate how a blockchain can distill the collective belief of its nodes regarding the trustworthiness of a (sub)set of nodes into a {\em reputation system} that reflects the probability of correctly performing a task. To address this question, we introduce a framework that breaks it down into two sub-problems: 1. (Information Extraction): How can the system distill trust information from a function of the nodes' true beliefs? 2. (Incentive Design): How can we incentivize nodes to truthfully report such information? To tackle the first sub-problem, we adapt, in a non-trivial manner, the well-known PageRank algorithm to our problem. For the second, we define a new class of games, called Trustworthy Reputation games (TRep games), which aim to extract the collective beliefs on trust from the actions of rational participants. We then propose a concrete TRep game whose utility function leverages Personalized PageRank and can be instantiated through a straightforward blockchain rewards mechanism. Building on this, we show how the TRep game enables the design of a reputation system. Such systems can enhance the robustness, scalability, and efficiency of blockchain and DeFi solutions. For instance, we demonstrate how such a system can be used within a Proof-of-Reputation blockchain.

  PublisherOA PDFDOI

• Towards Building Scalable Constant-Round MPC from Minimal Assumptions via Round Collapsing

  Lecture notes in computer science · 2025-01-01 · 1 citations

  book-chapter
  PublisherDOI

• Budget and Profit Approximations for Spanning Tree Interdiction

  ArXiv.org · 2025-07-25

  preprintOpen access1st authorCorresponding

  We give polynomial time logarithmic approximation guarantees for the budget minimization, as well as for the profit maximization versions of minimum spanning tree interdiction. In this problem, the goal is to remove some edges of an undirected graph with edge weights and edge costs, so as to increase the weight of a minimum spanning tree. In the budget minimization version, the goal is to minimize the total cost of the removed edges, while achieving a desired increase $Δ$ in the weight of the minimum spanning tree. An alternative objective within the same framework is to maximize the profit of interdiction, namely the increase in the weight of the minimum spanning tree, subject to a budget constraint. There are known polynomial time $O(1)$ approximation guarantees for a similar objective (maximizing the total cost of the tree, rather than the increase). However, the guarantee does not seem to apply to the increase in cost. Moreover, the same techniques do not seem to apply to the budget version. Our approximation guarantees are motivated by studying the question of minimizing the cost of increasing the minimum spanning tree by any amount. We show that in contrast to the budget and profit problems, this version of interdiction is polynomial time-solvable, and we give an efficient algorithm for solving it. The solution motivates a graph-theoretic relaxation of the NP-hard interdiction problem. The gain in minimum spanning tree weight, as a function of the set of removed edges, is super-modular. Thus, the budget problem is an instance of minimizing a linear function subject to a super-modular covering constraint. We use the graph-theoretic relaxation to design and analyze a batch greedy-based algorithm.

  PublisherOA PDFDOI

• Multiparty Garbling from OT with Linear Scaling and RAM Support

  Lecture notes in computer science · 2025-01-01 · 1 citations

  book-chapter
  PublisherDOI

• Round-Optimal Black-Box Multiparty Computation from Polynomial-Time Assumptions

  Lecture notes in computer science · 2025-01-01 · 1 citations

  book-chapter
  PublisherDOI

• Zero-Knowledge RAM: Doubly Efficient and Black-Box

  Lecture notes in computer science · 2025-01-01 · 2 citations

  book-chapter
  PublisherDOI

• Fast Networks for High-Performance Distributed Trust

  ArXiv.org · 2025-11-01

  preprintOpen access

  Organizations increasingly need to collaborate by performing a computation on their combined dataset, while keeping their data hidden from each other. Certain kinds of collaboration, such as collaborative data analytics and AI, require a level of performance beyond what current cryptographic techniques for distributed trust can provide. This is because the organizations run software in different trust domains, which can require them to communicate over WANs or the public Internet. In this paper, we explore how to instead run such applications using fast datacenter-type LANs. We show that, by carefully redesigning distributed trust frameworks for LANs, we can achieve up to order-of-magnitude better performance than naïvely using a LAN. Then, we develop deployment models for Distributed But Proximate Trust (DBPT) that allow parties to use a LAN while remaining physically and logically distinct. These developments make secure collaborative data analytics and AI significantly more practical and set new research directions for developing systems and cryptographic theory for high-performance distributed trust.

  PublisherOA PDFDOI

Recent grants

• NSFSaTC-BSF: TWC: Small: Cryptography and Communication Complexity

  NSF · $508k · 2016–2020

• TC: Small: Towards Resettable & Statistical Security in Zero Knowledge

  NSF · $568k · 2011–2015

• An In-Depth Study of Homomorphic Encryption in Cryptography

  NSF · $1.1M · 2008–2012

• CIF: Small: Energy-Efficient Scheduling and Load Balancing

  NSF · $228k · 2010–2013

• Collaborative Research: A Survivable Information Infrastructure for National Civilian BioDefense

  NSF · $404k · 2004–2008

Frequent coauthors

• Brett Hemenway

  55 shared

• Ivan Visconti

  Sapienza University of Rome

  55 shared

• Eyal Kushilevitz

  Technion – Israel Institute of Technology

  52 shared

• Yuval Ishai

  48 shared

• Amit Sahai

  44 shared

• Steve Lu

  42 shared

• Nishanth Chandran

  35 shared

• Juan A. Garay

  33 shared

Education

• Ph.D., Computer Science

  University of California, Los Angeles

  1990

• M.S., Computer Science

  University of California, Los Angeles

  1986

• B.S., Computer Science

  University of California, Los Angeles

  1984

Awards & honors

• Henry Taub Prize (1993)
• IEEE Computer Society Edward J. McCluskey Technical Achievem…
• RSA Award for Excellence in Mathematics (2018)
• W. Wallace McDowell Award (2022)
• Norman E. Friedmann Chair (2022)