Cryptanalysis of a Lattice-Based PIR Scheme for Arbitrary Database Sizes

• URL: http://arxiv.org/abs/2505.05934v1
• Date: Fri, 09 May 2025 10:25:03 GMT
• Title: Cryptanalysis of a Lattice-Based PIR Scheme for Arbitrary Database Sizes
• Authors: Svenja Lage,
• Abstract summary: In 2008, Melchor and Gaborit proposed a PIR scheme that achieves a balance between communication overhead and server-side computational cost.<n>Liu and Bi identified a vulnerability in the scheme using lattice-based methods.<n>We present a novel two-stage attack that extends the work of Liu and Bi to databases of arbitrary sizes.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Private Information Retrieval (PIR) schemes enable users to securely retrieve files from a server without disclosing the content of their queries, thereby preserving their privacy. In 2008, Melchor and Gaborit proposed a PIR scheme that achieves a balance between communication overhead and server-side computational cost. However, for particularly small databases, Liu and Bi identified a vulnerability in the scheme using lattice-based methods. Nevertheless, the rapid increase in computational cost associated with the attack limited its practical applicability, leaving the scheme's overall security largely intact. In this paper, we present a novel two-stage attack that extends the work of Liu and Bi to databases of arbitrary sizes. To this end, we employ a binary-search-like preprocessing technique, which enables a significant reduction in the number of lattice problems that need to be considered. Specifically, we demonstrate how to compromise the scheme in a matter of minutes using an ordinary laptop. Our findings are substantiated through both rigorous analytical proofs and comprehensive numerical experiments.

Related papers

• On the Security of a Code-Based PIR Scheme [1.3812010983144802]
  CB-cPIR is a pioneering effort to base PIR schemes on hard problems in coding theory.<n>Our research reveals a critical vulnerability in CB-cPIR, substantially diminishing its security levels.
  arXiv  Detail & Related papers  (2025-07-25T14:12:00Z)
• CB-cPIR: Code-Based Computational Private Information Retrieval [9.054540533394928]
  We present CB-cPIR, a single-server code-based computational private information retrieval (cPIR) scheme that derives security from code-based cryptography.<n>The scheme is heavily inspired by the pioneering code-based cPIR scheme proposed by Holzbaur, Hollanti, and Wachter-Zeh.
  arXiv  Detail & Related papers  (2025-05-06T10:34:44Z)
• Enhancing Resiliency of Sketch-based Security via LSB Sharing-based Dynamic Late Merging [6.601355678995729]
  We introduce a new sketch-oriented attack, which threatens a stream of state-of-the-art sketches and their security applications.<n>Siamese Counter delivers 47% accurate results than a state-of-the-art scheme, and demonstrates up to 82% more accurate estimation under normal measurement scenarios.
  arXiv  Detail & Related papers  (2025-03-14T18:12:14Z)
• 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)
• Private Counterfactual Retrieval [34.11302393278422]
  Transparency and explainability are two extremely important aspects to be considered when employing black-box machine learning models in high-stake applications.<n>Providing counterfactual explanations is one way of fulfilling this requirement.<n>We propose multiple schemes inspired by private information retrieval (PIR) techniques which ensure the emphuser's privacy when retrieving counterfactual explanations.
  arXiv  Detail & Related papers  (2024-10-17T17:45:07Z)
• Disparate Impact on Group Accuracy of Linearization for Private Inference [48.27026603581436]
  We show that reducing the number of ReLU activations disproportionately decreases the accuracy for minority groups compared to majority groups. We also show how a simple procedure altering the fine-tuning step for linearized models can serve as an effective mitigation strategy.
  arXiv  Detail & Related papers  (2024-02-06T01:56:29Z)
• Privacy-Preserving Distributed Learning for Residential Short-Term Load Forecasting [11.185176107646956]
  Power system load data can inadvertently reveal the daily routines of residential users, posing a risk to their property security. We introduce a Markovian Switching-based distributed training framework, the convergence of which is substantiated through rigorous theoretical analysis. Case studies employing real-world power system load data validate the efficacy of our proposed algorithm.
  arXiv  Detail & Related papers  (2024-02-02T16:39:08Z)
• SOCI^+: An Enhanced Toolkit for Secure OutsourcedComputation on Integers [50.608828039206365]
  We propose SOCI+ which significantly improves the performance of SOCI. SOCI+ employs a novel (2, 2)-threshold Paillier cryptosystem with fast encryption and decryption as its cryptographic primitive. Compared with SOCI, our experimental evaluation shows that SOCI+ is up to 5.4 times more efficient in computation and 40% less in communication overhead.
  arXiv  Detail & Related papers  (2023-09-27T05:19:32Z)
• ScionFL: Efficient and Robust Secure Quantized Aggregation [36.668162197302365]
  We introduce ScionFL, the first secure aggregation framework for federated learning. It operates efficiently on quantized inputs and simultaneously provides robustness against malicious clients. We show that with no overhead for clients and moderate overhead for the server, we obtain comparable accuracy for standard FL benchmarks.
  arXiv  Detail & Related papers  (2022-10-13T21:46:55Z)
• 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)
• Online Adversarial Attacks [57.448101834579624]
  We formalize the online adversarial attack problem, emphasizing two key elements found in real-world use-cases. We first rigorously analyze a deterministic variant of the online threat model. We then propose algoname, a simple yet practical algorithm yielding a provably better competitive ratio for $k=2$ over the current best single threshold algorithm.
  arXiv  Detail & Related papers  (2021-03-02T20:36:04Z)
• Neural Pruning via Growing Regularization [82.9322109208353]
  We extend regularization to tackle two central problems of pruning: pruning schedule and weight importance scoring. Specifically, we propose an L2 regularization variant with rising penalty factors and show it can bring significant accuracy gains. The proposed algorithms are easy to implement and scalable to large datasets and networks in both structured and unstructured pruning.
  arXiv  Detail & Related papers  (2020-12-16T20:16:28Z)
• Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond [171.07853346630057]
  Linear relaxation based perturbation analysis (LiRPA) for neural networks has become a core component in robustness verification and certified defense. We develop an automatic framework to enable perturbation analysis on any neural network structures. We demonstrate LiRPA based certified defense on Tiny ImageNet and Downscaled ImageNet.
  arXiv  Detail & Related papers  (2020-02-28T18:47:43Z)

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.