Code-Based Single-Server Private Information Retrieval: Circumventing the Sub-Query Attack

• URL: http://arxiv.org/abs/2402.02871v1
• Date: Mon, 5 Feb 2024 10:37:26 GMT
• Title: Code-Based Single-Server Private Information Retrieval: Circumventing the Sub-Query Attack
• Authors: Neehar Verma, Camilla Hollanti,
• Abstract summary: modified version of the first code-based single-server computational PIR scheme proposed by Holzbaur, Hollanti, and Wachter-Zeh. In the case of retrieving multiple files, the rate of the modified scheme is largely unaffected and at par with the original scheme.
• Score: 9.054540533394928
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Private information retrieval from a single server is considered, utilizing random linear codes. Presented is a modified version of the first code-based single-server computational PIR scheme proposed by Holzbaur, Hollanti, and Wachter-Zeh in [Holzbaur et al., "Computational Code-Based Single-Server Private Information Retrieval", 2020 IEEE ISIT]. The original scheme was broken in [Bordage et al., "On the privacy of a code-based single-server computational PIR scheme", Cryptogr. Comm., 2021] by an attack arising from highly probable rank differences in sub-matrices of the user's query. Here, this attack is now circumvented by ensuring that the sub-matrices have negligible rank difference. Furthermore, the rank difference cannot be attributed to the desired file index, thereby ensuring the privacy of the scheme. In the case of retrieving multiple files, the rate of the modified scheme is largely unaffected and at par with the original scheme.

Related papers

• The syzygy distinguisher [0.0]
  We present a new distinguisher for alternant and hence Goppa codes, whose complexity is subexponential in the error-correcting capability. In particular, it applies to the codes used in the Classic McEliece candidate for postquantum cryptography standardization.
  arXiv  Detail & Related papers  (2024-07-22T15:42:06Z)
• Cutting through buggy adversarial example defenses: fixing 1 line of code breaks Sabre [64.55144029671106]
  Sabre is a defense to adversarial examples that was accepted at IEEE S&P 2024. We first reveal significant flaws in the evaluation that point to clear signs of gradient masking. We then show the cause of this masking gradient: a bug in the original evaluation code.
  arXiv  Detail & Related papers  (2024-05-06T17:48:24Z)
• Coding-Based Hybrid Post-Quantum Cryptosystem for Non-Uniform Information [53.85237314348328]
  We introduce for non-uniform messages a novel hybrid universal network coding cryptosystem (NU-HUNCC) We show that NU-HUNCC is information-theoretic individually secured against an eavesdropper with access to any subset of the links.
  arXiv  Detail & Related papers  (2024-02-13T12:12:39Z)
• Bit-flipping Decoder Failure Rate Estimation for (v,w)-regular Codes [84.0257274213152]
  We propose a new technique to provide accurate estimates of the DFR of a two-iterations (parallel) bit flipping decoder. We validate our results, providing comparisons of the modeled and simulated weight of the syndrome, incorrectly-guessed error bit distribution at the end of the first iteration, and two-itcrypteration Decoding Failure Rates (DFR)
  arXiv  Detail & Related papers  (2024-01-30T11:40:24Z)
• 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)
• Iterative Sketching for Secure Coded Regression [66.53950020718021]
  We propose methods for speeding up distributed linear regression. Specifically, we randomly rotate the basis of the system of equations and then subsample blocks, to simultaneously secure the information and reduce the dimension of the regression problem.
  arXiv  Detail & Related papers  (2023-08-08T11:10:42Z)
• PEOPL: Characterizing Privately Encoded Open Datasets with Public Labels [59.66777287810985]
  We introduce information-theoretic scores for privacy and utility, which quantify the average performance of an unfaithful user. We then theoretically characterize primitives in building families of encoding schemes that motivate the use of random deep neural networks.
  arXiv  Detail & Related papers  (2023-03-31T18:03:53Z)
• PSTR: End-to-End One-Step Person Search With Transformers [140.32813648935752]
  We propose a one-step transformer-based person search framework, PSTR. PSS module contains a detection encoder-decoder for person detection along with a discriminative re-id decoder for person re-id. On the challenging PRW benchmark, PSTR achieves a mean average precision (mAP) score of 56.5%.
  arXiv  Detail & Related papers  (2022-04-07T10:22:33Z)
• Privacy-Preserving Federated Learning via System Immersion and Random Matrix Encryption [4.258856853258348]
  Federated learning (FL) has emerged as a privacy solution for collaborative distributed learning where clients train AI models directly on their devices instead of sharing their data with a centralized (potentially adversarial) server. We propose a Privacy-Preserving Federated Learning (PPFL) framework built on the synergy of matrix encryption and system immersion tools from control theory. We show that our algorithm provides the same level of accuracy and convergence rate as the standard FL with a negligible cost while revealing no information about clients' data.
  arXiv  Detail & Related papers  (2022-04-05T21:28:59Z)
• High-Rate Quantum Private Information Retrieval with Weakly Self-Dual Star Product Codes [16.23970875497387]
  In the quantum PIR (QPIR) setting, a user privately retrieves a classical file by receiving quantum information from the servers. In this paper, the QPIR setting is extended to allow for retrieval with high rate for any number of colluding servers $t$ with $1 leq tleq n-k$.
  arXiv  Detail & Related papers  (2021-02-04T09:44:10Z)
• Quantum Private Information Retrieval from Coded and Colluding Servers [16.23970875497387]
  In the quantum PIR (QPIR) setting, a user privately retrieves a classical file by receiving quantum information from the servers. In this paper, the QPIR setting is extended to account for maximum distance separable (MDS) coded servers. The rates achieved are better than those known or conjectured in the classical counterparts.
  arXiv  Detail & Related papers  (2020-01-16T15:19:08Z)

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.