Pushing the Limits of Frequency Analysis in Leakage Abuse Attacks

• URL: http://arxiv.org/abs/2508.11563v1
• Date: Fri, 15 Aug 2025 16:16:13 GMT
• Title: Pushing the Limits of Frequency Analysis in Leakage Abuse Attacks
• Authors: Nathaniel Moyer, Charalampos Papamanthou, Evgenios Kornaropoulos,
• Abstract summary: We focus on the cryptanalytic technique of frequency analysis in the context of leakage-abuse attacks on schemes that support encrypted range queries.<n>We introduce a generic attack framework called Leakage-Abuse via Matching (LAMA) that works even on high-dimensional encrypted data.
• Score: 9.3678097985623
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Searchable encryption (SE) is the most scalable cryptographic primitive for searching on encrypted data. Typical SE constructions often allow access-pattern leakage, revealing which encrypted records are retrieved in the server's responses. All the known generic cryptanalyses assume either that the queries are issued uniformly at random or that the attacker observes the search-pattern leakage. It remains unclear what can be reconstructed when using only the access-pattern leakage and knowledge of the query distribution. In this work, we focus on the cryptanalytic technique of frequency analysis in the context of leakage-abuse attacks on schemes that support encrypted range queries. Frequency analysis matches the frequency of retrieval of an encrypted record with a plaintext value based on its probability of retrieval that follows from the knowledge of the query distribution. We generalize this underexplored cryptanalytic technique and introduce a generic attack framework called Leakage-Abuse via Matching (LAMA) that works even on high-dimensional encrypted data. We identify a parameterization of LAMA that brings frequency analysis to its limit -- that is, we prove that there is no additional frequency matching that an attacker can perform to refine the result. Furthermore, we show that our results hold for any class of convex queries, and not just axis-aligned rectangles, which is the assumption in all other attacks on range schemes. Using these results, we identify query distributions that make frequency analysis challenging for the attacker and, thus, can act as a mitigation mechanism. Finally, we implement and benchmark LAMA and reconstruct, for the first time, plaintext data from encrypted range queries spanning up to four dimensions.

Related papers

• Privacy-Preserving Anonymization of System and Network Event Logs Using Salt-Based Hashing and Temporal Noise [5.85293491327449]
  Event logs contain Personally Identifiable Information (PII)<n>Overly aggressive anonymization can destroy contextual integrity, while weak techniques risk re-identification through linkage or inference attacks.<n>This paper introduces novel field-specific anonymization methods that address this trade-off.
  arXiv  Detail & Related papers  (2025-07-29T15:16:42Z)
• Anomaly Detection with LWE Encrypted Control [5.263161322684099]
  We present a novel mechanism for anomaly detection over Learning with Errors encrypted signals.<n>The detector exploits the homomorphic property of LWE encryption to perform hypothesis tests on transformations of the encrypted samples.
  arXiv  Detail & Related papers  (2025-02-14T16:38:51Z)
• Towards Copyright Protection for Knowledge Bases of Retrieval-augmented Language Models via Reasoning [58.57194301645823]
  Large language models (LLMs) are increasingly integrated into real-world personalized applications.<n>The valuable and often proprietary nature of the knowledge bases used in RAG introduces the risk of unauthorized usage by adversaries.<n>Existing methods that can be generalized as watermarking techniques to protect these knowledge bases typically involve poisoning or backdoor attacks.<n>We propose name for harmless' copyright protection of knowledge bases.
  arXiv  Detail & Related papers  (2025-02-10T09:15:56Z)
• Cryptanalysis via Machine Learning Based Information Theoretic Metrics [58.96805474751668]
  We propose two novel applications of machine learning (ML) algorithms to perform cryptanalysis on any cryptosystem.<n>These algorithms can be readily applied in an audit setting to evaluate the robustness of a cryptosystem.<n>We show that our classification model correctly identifies the encryption schemes that are not IND-CPA secure, such as DES, RSA, and AES ECB, with high accuracy.
  arXiv  Detail & Related papers  (2025-01-25T04:53:36Z)
• InputSnatch: Stealing Input in LLM Services via Timing Side-Channel Attacks [9.748438507132207]
  Large language models (LLMs) possess extensive knowledge and question-answering capabilities.<n> cache-sharing methods are commonly employed to enhance efficiency by reusing cached states or responses for the same or similar inference requests.<n>We propose a novel timing-based side-channel attack to execute input theft in LLMs inference.
  arXiv  Detail & Related papers  (2024-11-27T10:14:38Z)
• AdvQDet: Detecting Query-Based Adversarial Attacks with Adversarial Contrastive Prompt Tuning [93.77763753231338]
  Adversarial Contrastive Prompt Tuning (ACPT) is proposed to fine-tune the CLIP image encoder to extract similar embeddings for any two intermediate adversarial queries. We show that ACPT can detect 7 state-of-the-art query-based attacks with $>99%$ detection rate within 5 shots. We also show that ACPT is robust to 3 types of adaptive attacks.
  arXiv  Detail & Related papers  (2024-08-04T09:53:50Z)
• Leakage-Abuse Attacks Against Forward and Backward Private Searchable Symmetric Encryption [13.057964839510596]
  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)
  arXiv  Detail & Related papers  (2023-09-09T06:39:35Z)
• Backdoor Learning on Sequence to Sequence Models [94.23904400441957]
  In this paper, we study whether sequence-to-sequence (seq2seq) models are vulnerable to backdoor attacks. Specifically, we find by only injecting 0.2% samples of the dataset, we can cause the seq2seq model to generate the designated keyword and even the whole sentence. Extensive experiments on machine translation and text summarization have been conducted to show our proposed methods could achieve over 90% attack success rate on multiple datasets and models.
  arXiv  Detail & Related papers  (2023-05-03T20:31:13Z)
• A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
  We propose a variational quantum attack algorithm (VQAA) for classical AES-like symmetric cryptography. In the VQAA, the known ciphertext is encoded as the ground state of a Hamiltonian that is constructed through a regular graph.
  arXiv  Detail & Related papers  (2022-05-07T03:15:15Z)
• Malware Traffic Classification: Evaluation of Algorithms and an Automated Ground-truth Generation Pipeline [8.779666771357029]
  We propose an automated packet data-labeling pipeline to generate ground-truth data. We explore and test different kind of clustering approaches which make use of unique and diverse set of features extracted from this observable meta-data.
  arXiv  Detail & Related papers  (2020-10-22T11:48:51Z)
• Certified Robustness to Label-Flipping Attacks via Randomized Smoothing [105.91827623768724]
  Machine learning algorithms are susceptible to data poisoning attacks. We present a unifying view of randomized smoothing over arbitrary functions. We propose a new strategy for building classifiers that are pointwise-certifiably robust to general data poisoning attacks.
  arXiv  Detail & Related papers  (2020-02-07T21:28:30Z)

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.