About

Roberto Tamassia is the James A. & Julie N. Brown Professor of Computer Science and serves as the Chair of the Department of Computer Science at Brown University. His professional profile indicates a focus on computer science, with a notable academic and leadership role within the department. The page references his involvement in the academic community, including his position as a professor and his contributions to the field, although specific details about his research focus, background, or key contributions are not provided in the text.

Research topics

• Artificial Intelligence
• Computer Security
• Computer Science
• Theoretical computer science
• Algorithm

Selected publications

• Reconstructing with Even Less: Amplifying Leakage and Drawing Graphs

  2024-12-02 · 2 citations

  articleOpen accessSenior author

  Leakage-abuse attacks using access pattern leakage from range queries have been shown to reconstruct encrypted databases. However, prior work is either restricted to one-dimensional databases or requires access to all possible responses in two-dimensions. In this paper, we explore what an adversary can achieve with minimal leakage, focusing on denser databases, and present a leakage abuse attack from access pattern of range queries in multiple dimensions. Our attack employs a novel technique to systematically amplify access pattern leakage, inferring a large number of new query responses that have not been requested by the user. Let m be the size of the database domain. Our attack works on d-dimensional databases and achieves approximate reconstruction. For dense databases and a parameter 0 < λ < 1, our attack fully reconstructs an inner portion of size λm of the database (referred to as the λ-core) after observing O(m log m) queries, uniformly at random. These are significant improvements over previous attacks that require the full set of responses, which has size O(m2). We are the first to leverage graph drawing techniques for database reconstruction attacks. We implement our attack and evaluate it with experiments on real-world databases, achieving accurate reconstructions after observing a small percentage of the responses.

  PublisherOA PDFDOI

• PathGES: An Efficient and Secure Graph Encryption Scheme for Shortest Path Queries

  2024-12-02 · 7 citations

  articleOpen accessSenior author

  The increasing importance of graph databases and cloud storage services prompts the study of private queries on graphs. We propose PathGES, a graph encryption scheme (GES) for single-pair shortest path queries. PathGES is efficient and mitigates the state-of-the-art attack by Falzon and Paterson (2022) on the GES by Ghosh, Kamara, and Tamassia (2021), while only incurring an additional logarithmic factor in storage overhead. PathGES leverages a novel data structure that minimizes leakage and server computation.

  PublisherOA PDFDOI

• Attacks on Encrypted Response-Hiding Range Search Schemes in Multiple Dimensions

  Proceedings on Privacy Enhancing Technologies · 2023-08-03 · 10 citations

  articleOpen accessSenior author

  In this work, we present the first database reconstruction attacks against response-hiding private range search schemes on encrypted databases of arbitrary dimensions. Falzon et al. (VLDB 2022) present a number of range-supporting schemes on arbitrary dimensions exhibiting different security and efficiency trade-offs. Additionally, they characterize a form of leakage, structure pattern leakage, also present in many one-dimensional schemes e.g., Demertzis et al. (SIGMOD 2016) and Faber et al. (ESORICS 2015). We present the first systematic study of this leakage and attack a broad collection of schemes, including schemes that allow the responses to contain false-positives (often considered the gold standard in security). We characterize the information theoretic limitations of a passive persistent adversary. Our work shows that for range queries, structure pattern leakage can be as vulnerable to attacks as access pattern leakage. We give a comprehensive evaluation of our attacks with a complexity analysis, a prototype implementation, and an experimental assessment on real-world datasets.

  PublisherOA PDFDOI

• Time- and Space-Efficient Aggregate Range Queries over Encrypted Databases

  Proceedings on Privacy Enhancing Technologies · 2022-08-31 · 8 citations

  articleOpen accessSenior author

  We present ARQ, a systematic framework for creating cryptographic schemes that handle range aggregate queries (sum, minimum, median, and mode) over encrypted datasets. Our framework does not rely on trusted hardware or specialized cryptographic primitives such as property-preserving or homomorphic encryption. Instead, ARQ unifies structures from the plaintext data management community with existing structured encryption primitives. We prove how such combinations yield efficient (and secure) constructions in the encrypted setting. We also propose a series of domain reduction techniques that can improve the space efficiency of our schemes against sparse datasets at the cost of small leakage. As part of this work, we designed and implemented a new, open-source, encrypted search library called Arca and implemented the ARQ framework using this library in order to evaluate ARQ’s practicality. Our experiments on real-world datasets demonstrate the efficiency of the schemes derived from ARQ in comparison to prior work.

  PublisherOA PDFDOI

• Range Search over Encrypted Multi-Attribute Data

  Proceedings of the VLDB Endowment · 2022-12-01 · 8 citations

  articleSenior author

  This work addresses expressive queries over encrypted data by presenting the first systematic study of multi-attribute range search on a symmetrically encrypted database outsourced to an honest-but-curious server. Prior work includes a thorough analysis of single-attribute range search schemes (e.g. Demertzis et al. 2016) and a proposed high-level approach for multi-attribute schemes (De Capitani di Vimercati et al. 2021). We first introduce a flexible framework for building secure range search schemes over multiple attributes (dimensions) by adapting a broad class of geometric search data structures to operate on encrypted data. Our framework encompasses widely used data structures such as multi-dimensional range trees and quadtrees, and has strong security properties that we formally prove. We then develop six concrete highly parallelizable range search schemes within our framework that offer a sliding scale of efficiency and security tradeoffs to suit the needs of the application. We evaluate our schemes with a formal complexity and security analysis, a prototype implementation, and an experimental evaluation on real-world datasets.

  PublisherDOI

• The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures

  Proceedings of the 2022 International Conference on Management of Data · 2022-06-10 · 13 citations

  articleOpen accessSenior author

  The concept of learned index structures relies on the idea that the input-output functionality of a database index can be viewed as a prediction task and, thus, implemented using a machine learning model instead of traditional algorithmic techniques. This novel angle for a decades-old problem has inspired exciting results at the intersection of machine learning and data structures. However, the advantage of learned index structures, i.e., the ability to adjust to the data at hand via the underlying ML-model, can become a disadvantage from a security perspective as it could be exploited.

  PublisherOA PDFDOI

• Response-Hiding Encrypted Ranges: Revisiting Security via Parametrized Leakage-Abuse Attacks

  2022 IEEE Symposium on Security and Privacy (SP) · 2021 · 45 citations

  Senior authorCorresponding
  • Computer Science
  • Computer Science
  • Computer Security

  Despite a growing body of work on leakage-abuse attacks for encrypted databases, attacks on practical response-hiding constructions are yet to appear. Response-hiding constructions are superior in that they nullify access-pattern based attacks by revealing only the search token and the result size of each query. Response-hiding schemes are vulnerable to existing volume attacks, which are, however, based on strong assumptions such as the uniform query assumption or the dense database assumption. More crucially, these attacks only apply to schemes that cannot be deployed in practice (ones with quadratic storage and increased leakage) while practical response-hiding schemes (Demertzis et al. [SIGMOD’16] and Faber et al. [ESORICS’15]) have linear storage and less leakage. Due to these shortcomings, the value of existing volume attacks on response-hiding schemes is unclear.In this work, we close the aforementioned gap by introducing a parametrized leakage-abuse attack that applies to practical response-hiding structured encryption schemes. The use of non-parametric estimation techniques makes our attack agnostic to both the data and the query distribution. At the very core of our technique lies the newly defined concept of a counting function with respect to a range scheme. We propose a two-phase framework to approximate the counting function for any range scheme. By simply switching one counting function for another, i.e., the so-called "parameter" of our modular attack, an adversary can attack different encrypted range schemes. We propose a constrained optimization formulation for the attack algorithm that is based on the counting functions. We demonstrate the effectiveness of our leakage-abuse attack on synthetic and real-world data under various scenarios.

  PublisherDOI

• Response-Hiding Encrypted Ranges: Revisiting Security via Parametrized Leakage-Abuse Attacks.

  2021-01-01

  preprintSenior author

  Despite a growing body of work on leakage-abuse attacks for encrypted databases, attacks on practical response-hiding constructions are yet to appear. Response-hiding constructions are superior in that they nullify access-pattern based attacks by revealing only the search token and the result size of each query. Response-hiding schemes are vulnerable to existing volume attacks, which are, however, based on strong assumptions such as the uniform query assumption or the dense database assumption. More crucially, these attacks only apply to schemes that cannot be deployed in practice (ones with quadratic storage and increased leakage) while practical response-hiding schemes (Demertzis et al. [SIGMOD’16] and Faber et al. [ESORICS’15]) have linear storage and less leakage. Due to these shortcomings, the value of existing volume attacks on response-hiding schemes is unclear.In this work, we close the aforementioned gap by introducing a parametrized leakage-abuse attack that applies to practical response-hiding structured encryption schemes. The use of non-parametric estimation techniques makes our attack agnostic to both the data and the query distribution. At the very core of our technique lies the newly defined concept of a counting function with respect to a range scheme. We propose a two-phase framework to approximate the counting function for any range scheme. By simply switching one counting function for another, i.e., the so-called parameter of our modular attack, an adversary can attack different encrypted range schemes. We propose a constrained optimization formulation for the attack algorithm that is based on the counting functions. We demonstrate the effectiveness of our leakage-abuse attack on synthetic and real-world data under various scenarios.

• Efficient Graph Encryption Scheme for Shortest Path Queries

  2021-05-24 · 34 citations

  articleSenior author

  Graph encryption schemes (introduced by [Chase and Kamara, 2010]) have been receiving growing interest across various disciplines due to their attractive tradeoff between functionality, efficiency and privacy. In this paper, we advance the state of the art on encrypted graph search by providing an efficient graph encryption scheme for shortest path queries. The preprocessing time and space and the query time are proportional to those for building and querying the search structure for the unencrypted graph. Hence, the overhead of providing structured encryption is asymptotically optimal. We implement our scheme and experimentally validate its performance on real world networks. Furthermore, we extend our scheme to support verifiability.

  PublisherDOI

• Reconstructing with Less: Leakage Abuse Attacks in Two Dimensions

  2021-11-12 · 22 citations

  article

  Access and search pattern leakage from range queries are detrimental to the security of encrypted databases, as evidenced by a large body of work on attacks that reconstruct one-dimensional databases. Recently, the first attack from 2D range queries showed that higher-dimensional databases are also in danger (Falzon et al. CCS 2020). Their attack requires the access and search pattern of all possible queries. We present an order reconstruction attack that only depends on access pattern leakage, and empirically show that the order allows the attacker to infer the geometry of the underlying data. Notably, this attack also achieves full database reconstruction when the 1D horizontal and vertical projections of the points are dense. We also give an approximate database reconstruction attack that is distribution-agnostic and works with any sample of queries, given the search pattern and access pattern leakage of those queries, and the order of the database records. Finally, we show how to improve the reconstruction given knowledge of auxiliary information (e.g., the centroid of a related dataset). We support our results with formal analysis and experiments on real-world databases with queries drawn from various distributions.

  PublisherDOI

Recent grants

• TC: Large: Collaborative Research: Towards Trustworthy Interactions in the Cloud

  NSF · $1.0M · 2010–2015

• Collaborative Research: An Algorithmic Approach to Cyber-Security

  NSF · $106k · 2003–2007

• III: Large: Collaborative Research: Moving Objects Databases for Exploration of Virtual and Real Environments

  NSF · $250k · 2012–2018

• IPS: Collaborative Research: Privacy Management, Measurement, and Visualization in Distributed Environments

  NSF · $237k · 2007–2010

• Collaborative Research: Algorithms for Graphs on Surfaces

  NSF · $200k · 2008–2013

Frequent coauthors

• Michael T. Goodrich

  University of California, Irvine

  121 shared

• Giuseppe Di Battista

  84 shared

• Charalampos Papamanthou

  Yale University

  64 shared

• Giuseppe Liotta

  64 shared

• Ioannis G. Tollis

  51 shared

• Ashim Garg

  University at Buffalo, State University of New York

  49 shared

• Olga Ohrimenko

  49 shared

• Robert Cohen

  48 shared

Labs

• Tamassia LabPI

Education

• Ph.D.

  University of Illinois at Urbana-Champaign

  1988