skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Veil: A Storage and Communication Efficient Volume-Hiding Algorithm
This paper addresses volume leakage (i.e., leakage of the number of records in the answer set) when processing keyword queries in encrypted key-value (KV) datasets. Volume leakage, coupled with prior knowledge about data distribution and/or previously executed queries, can reveal both ciphertexts and current user queries. We develop a solution to prevent volume leakage, entitled Veil, that partitions the dataset by randomly mapping keys to a set of equi-sized buckets. Veil provides a tunable mechanism for data owners to explore a trade-off between storage and communication overheads. To make buckets indistinguishable to the adversary, Veil uses a novel padding strategy that allow buckets to overlap, reducing the need to add fake records. Both theoretical and experimental results show Veil to significantly outperform existing state-of-the-art.  more » « less
Award ID(s):
2245372 2212129
PAR ID:
10523002
Author(s) / Creator(s):
; ; ; ;
Publisher / Repository:
ACM
Date Published:
Journal Name:
Proceedings of the ACM on Management of Data
Volume:
1
Issue:
4
ISSN:
2836-6573
Page Range / eLocation ID:
1 to 27
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, 2020 IEEE European Symposium on Security and Privacy (EuroS&P))
    null (Ed.)
    Recent years have seen an increased interest towards strong security primitives for encrypted databases (such as oblivious protocols) that hide the access patterns of query execution and reveal only the volume of results. However recent work has shown that even volume leakage can enable the reconstruction of entire columns in the database. Yet existing attacks rely on a set of assumptions that are unrealistic in practice for example they (i) require a large number of queries to be issued by the user or (ii) assume certain distributions on the queries or underlying data (e.g. that the queries are distributed uniformly at random or that the database does not contain missing values). In this work we present new attacks for recovering the content of individual user queries assuming no leakage from the system except the number of results and avoiding the limiting assumptions above. Unlike prior attacks our attacks require only a single query to be issued by the user for recovering the keyword. Furthermore our attacks make no assumptions about the distribution of issued queries or the underlying data. Instead our key insight is to exploit the behavior of real-world applications. We start by surveying 11 applications to identify two key characteristics that can be exploited by attackers-(l) file injection and (ii) automatic query replay. We present attacks that leverage these two properties in concert with volume leakage independent of the details of any encrypted database system. Subsequently we perform an attack on the real Gmail web client by simulating a server-side adversary. Our attack on Gmail completes within a matter of minutes demonstrating the feasibility of our techniques. We also present three ancillary attacks for situations when certain mitigation strategies are employed. 
    more » « less
  2. ; (, Journal of Biomechanical Engineering)
    Abstract Intradiscal injection is required to deliver therapeutic agents to the intervertebral disc (IVD) nucleus pulposus (NP). However, injectate leakage following needle retraction may result in decreased treatment efficacy and adverse side effects. While enzymatic digestion is a common research approach for simulating degeneration in healthy animal IVDs, contributions to the leakage phenomenon are unknown. In this study, bovine caudal discs were treated with injection into the NP of either a tris buffer control, collagenase (to primarily target collagen), or trypsin (to primarily target proteoglycans) and then injected with fluorescent saline using a through-puncture defect protocol. Pressure–volume records during injection were used to determine volume and pressure at leakage. Discs were then frozen, transected, and photographed to visualize injectate dispersion. Collagenase treatment resulted in a large increase in injectate dispersion, along with a decrease in injection pressure relative to control. Trypsin treatment resulted in a moderate increase in dispersion, with no associated effect on pressure. This study concludes that care should be taken when employing enzymatic digestion to simulate IVD degeneration, as NP tissue disruption may affect both retention and dispersion of subsequent therapeutic injections. 
    more » « less
  3. ; ; ; ; (, USENIX Security 2023)
    We present TVA, a multi-party computation (MPC) system for secure analytics on secret-shared time series data. TVA achieves strong security guarantees in the semi-honest and malicious settings, and high expressivity by enabling complex analytics on inputs with unordered and irregular timestamps. TVA is the first system to support arbitrary composition of oblivious window operators, keyed aggregations, and multiple filter predicates, while keeping all data attributes private, including record timestamps and user-defined values in query predicates. At the core of the TVA system lie novel protocols for secure window assignment: (i) a tumbling window protocol that groups records into fixed-length time buckets and (ii) two session window protocols that identify periods of activity followed by periods of inactivity. We also contribute a new protocol for secure division with a public divisor, which may be of independent interest. We evaluate TVA on real LAN and WAN environments and show that it can efficiently compute complex window-based analytics on inputs of 2^22 records with modest use of resources. When compared to the state-of-the-art, TVA achieves up to 5.8× lower latency in queries with multiple filters and two orders of magnitude better performance in window aggregation. 
    more » « less
  4. ; (, 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022))
    Boucher, Christina; Rahmann, Sven (Ed.)
    Many bioinformatics applications involve bucketing a set of sequences where each sequence is allowed to be assigned into multiple buckets. To achieve both high sensitivity and precision, bucketing methods are desired to assign similar sequences into the same bucket while assigning dissimilar sequences into distinct buckets. Existing k-mer-based bucketing methods have been efficient in processing sequencing data with low error rate, but encounter much reduced sensitivity on data with high error rate. Locality-sensitive hashing (LSH) schemes are able to mitigate this issue through tolerating the edits in similar sequences, but state-of-the-art methods still have large gaps. Here we generalize the LSH function by allowing it to hash one sequence into multiple buckets. Formally, a bucketing function, which maps a sequence (of fixed length) into a subset of buckets, is defined to be (d₁, d₂)-sensitive if any two sequences within an edit distance of d₁ are mapped into at least one shared bucket, and any two sequences with distance at least d₂ are mapped into disjoint subsets of buckets. We construct locality-sensitive bucketing (LSB) functions with a variety of values of (d₁,d₂) and analyze their efficiency with respect to the total number of buckets needed as well as the number of buckets that a specific sequence is mapped to. We also prove lower bounds of these two parameters in different settings and show that some of our constructed LSB functions are optimal. These results provide theoretical foundations for their practical use in analyzing sequences with high error rate while also providing insights for the hardness of designing ungapped LSH functions. 
    more » « less
  5. ; (, Algorithms for Molecular Biology)
    Abstract BackgroundMany bioinformatics applications involve bucketing a set of sequences where each sequence is allowed to be assigned into multiple buckets. To achieve both high sensitivity and precision, bucketing methods are desired to assign similar sequences into the same bucket while assigning dissimilar sequences into distinct buckets. Existingk-mer-based bucketing methods have been efficient in processing sequencing data with low error rates, but encounter much reduced sensitivity on data with high error rates. Locality-sensitive hashing (LSH) schemes are able to mitigate this issue through tolerating the edits in similar sequences, but state-of-the-art methods still have large gaps. ResultsIn this paper, we generalize the LSH function by allowing it to hash one sequence into multiple buckets. Formally, a bucketing function, which maps a sequence (of fixed length) into a subset of buckets, is defined to be$$(d_1, d_2)$$ ( d 1 , d 2 ) -sensitive if any two sequences within an edit distance of$$d_1$$ d 1 are mapped into at least one shared bucket, and any two sequences with distance at least$$d_2$$ d 2 are mapped into disjoint subsets of buckets. We construct locality-sensitive bucketing (LSB) functions with a variety of values of$$(d_1,d_2)$$ ( d 1 , d 2 ) and analyze their efficiency with respect to the total number of buckets needed as well as the number of buckets that a specific sequence is mapped to. We also prove lower bounds of these two parameters in different settings and show that some of our constructed LSB functions are optimal. ConclusionThese results lay the theoretical foundations for their practical use in analyzing sequences with high error rates while also providing insights for the hardness of designing ungapped LSH functions. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email