Leakage-Abuse Attacks Against Forward and Backward Private Searchable Symmetric Encryption

• URL: http://arxiv.org/abs/2309.04697v2
• Date: Wed, 13 Sep 2023 02:03:36 GMT
• Title: Leakage-Abuse Attacks Against Forward and Backward Private Searchable Symmetric Encryption
• Authors: Lei Xu, Leqian Zheng, Chengzhi Xu, Xingliang Yuan, Cong Wang,
• Abstract summary: Dynamic searchable encryption (DSSE) enables a server to efficiently search and update over encrypted files. To minimize the leakage during updates, a security notion named forward and backward privacy is expected for newly proposed DSSE schemes. It remains underexplored whether forward and backward private DSSE is resilient against practical leakage-abuse attacks (LAAs)
• Score: 13.057964839510596
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Dynamic searchable symmetric encryption (DSSE) enables a server to efficiently search and update over encrypted files. To minimize the leakage during updates, a security notion named forward and backward privacy is expected for newly proposed DSSE schemes. Those schemes are generally constructed in a way to break the linkability across search and update queries to a given keyword. However, it remains underexplored whether forward and backward private DSSE is resilient against practical leakage-abuse attacks (LAAs), where an attacker attempts to recover query keywords from the leakage passively collected during queries. In this paper, we aim to be the first to answer this question firmly through two non-trivial efforts. First, we revisit the spectrum of forward and backward private DSSE schemes over the past few years, and unveil some inherent constructional limitations in most schemes. Those limitations allow attackers to exploit query equality and establish a guaranteed linkage among different (refreshed) query tokens surjective to a candidate keyword. Second, we refine volumetric leakage profiles of updates and queries by associating each with a specific operation. By further exploiting update volume and query response volume, we demonstrate that all forward and backward private DSSE schemes can leak the same volumetric information (e.g., insertion volume, deletion volume) as those without such security guarantees. To testify our findings, we realize two generic LAAs, i.e., frequency matching attack and volumetric inference attack, and we evaluate them over various experimental settings in the dynamic context. Finally, we call for new efficient schemes to protect query equality and volumetric information across search and update queries.

Related papers

• HOPE: Homomorphic Order-Preserving Encryption for Outsourced Databases -- A Stateless Approach [1.1701842638497677]
  Homomorphic OPE (HOPE) is a new OPE scheme that eliminates client-side storage and avoids additional client-server interaction during query execution. We provide a formal cryptographic analysis of HOPE, proving its security under the widely accepted IND-OCPA model.
  arXiv  Detail & Related papers  (2024-11-26T00:38:46Z)
• Comment on "An Efficient Privacy-Preserving Ranked Multi-Keyword Retrieval for Multiple Data Owners in Outsourced Cloud" [0.0]
  We show that the scheme fails to resist keyword guessing attack, index privacy, and trapdoor privacy. We propose a solution to address the above said issues by correcting the errors in the important equations of the scheme.
  arXiv  Detail & Related papers  (2024-07-25T05:01:07Z)
• Data Reconstruction: When You See It and When You Don't [75.03157721978279]
  We aim to "sandwich" the concept of reconstruction attacks by addressing two complementing questions. We introduce a new definitional paradigm -- Narcissus Resiliency -- to formulate a security definition for protection against reconstruction attacks.
  arXiv  Detail & Related papers  (2024-05-24T17:49:34Z)
• AdvPrompter: Fast Adaptive Adversarial Prompting for LLMs [51.217126257318924]
  We present a novel method that uses another Large Language Models, called the AdvPrompter, to generate human-readable adversarial prompts in seconds. We train the AdvPrompter using a novel algorithm that does not require access to the gradients of the TargetLLM. The trained AdvPrompter generates suffixes that veil the input instruction without changing its meaning, such that the TargetLLM is lured to give a harmful response.
  arXiv  Detail & Related papers  (2024-04-21T22:18:13Z)
• d-DSE: Distinct Dynamic Searchable Encryption Resisting Volume Leakage in Encrypted Databases [24.259108931623203]
  Dynamic Searchable Encryption (DSE) has emerged as a solution to efficiently handle and protect large-scale data storage in encrypted databases (EDBs) Volume leakage poses a significant threat, as it enables adversaries to reconstruct search queries and potentially compromise the security and privacy of data. Padding strategies are common countermeasures for the leakage, but they significantly increase storage and communication costs.
  arXiv  Detail & Related papers  (2024-03-02T11:42:17Z)
• Hiding Access-pattern is Not Enough! Veil: A Storage and Communication Efficient Volume-Hiding Algorithm [7.810877430779854]
  Volume leakage can reveal 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.
  arXiv  Detail & Related papers  (2023-10-19T05:51:11Z)
• SWAT: A System-Wide Approach to Tunable Leakage Mitigation in Encrypted Data Stores [24.510485610026077]
  SWAT is an efficient construction that progressively enables workloads, while provably mitigating system-wide leakage. SWATis about an order of magnitude slower than an encryption-only data store that reveals various leakage patterns and is two orders of magnitude faster than a trivial zero-leakage solution.
  arXiv  Detail & Related papers  (2023-06-29T10:53:36Z)
• RiDDLE: Reversible and Diversified De-identification with Latent Encryptor [57.66174700276893]
  This work presents RiDDLE, short for Reversible and Diversified De-identification with Latent Encryptor. Built upon a pre-learned StyleGAN2 generator, RiDDLE manages to encrypt and decrypt the facial identity within the latent space.
  arXiv  Detail & Related papers  (2023-03-09T11:03:52Z)
• Is Vertical Logistic Regression Privacy-Preserving? A Comprehensive Privacy Analysis and Beyond [57.10914865054868]
  We consider vertical logistic regression (VLR) trained with mini-batch descent gradient. We provide a comprehensive and rigorous privacy analysis of VLR in a class of open-source Federated Learning frameworks.
  arXiv  Detail & Related papers  (2022-07-19T05:47:30Z)
• Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
  We construct the first fully homomorphic encryption scheme with certified deletion. Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors distribution in the form of a quantum state was deleted.
  arXiv  Detail & Related papers  (2022-03-03T10:07:32Z)
• Recovering AES Keys with a Deep Cold Boot Attack [91.22679787578438]
  Cold boot attacks inspect the corrupted random access memory soon after the power has been shut down. In this work, we combine a novel cryptographic variant of a deep error correcting code technique with a modified SAT solver scheme to apply the attack on AES keys. Our results show that our methods outperform the state of the art attack methods by a very large margin.
  arXiv  Detail & Related papers  (2021-06-09T07:57:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.