On the privacy of a code-based single-server computational PIR scheme

DOI10.1007/S12095-021-00477-ZMaRDI QIDQ2120986zbMATH OpenOpenAlexFDO

Authors Sarah Bordage, Julien Lavauzelle

Publication date 1 April 2022

Published in Cryptography and Communications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.00509

zbMATH Keywords

linear codesprivacyprivate information retrieval

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Privacy of data (68P27) Authentication, digital signatures and secret sharing (94A62) Linear codes (general theory) (94B05)

Abstract: We show that the single-server computational PIR protocol proposed by Holzbaur, Hollanti and Wachter-Zeh in 2020 is not private, in the sense that the server can recover in polynomial time the index of the desired file with very high probability. The attack relies on the following observation. Removing rows of the query matrix corresponding to the desired file yields a large decrease of the dimension over $mathbb{F}_q$ of the vector space spanned by the rows of this punctured matrix. Such a dimension loss only shows up with negligible probability when rows unrelated to the requested file are deleted.

Recommendations

• A survey on single server private information retrieval in a coding theory perspective
• The Role of Coded Side Information in Single-Server Private Information Retrieval
• Reducing the servers' computation in private information retrieval: PIR with preprocessing
• scientific article; zbMATH DE number 1759771
• On computational shortcuts for information-theoretic PIR
• On locally decodable codes, self-correctable codes, and \(t\)-private PIR
• On Locally Decodable Codes, Self-correctable Codes, and t-Private PIR
• New code-based privacy-preserving cryptographic constructions
• Verifiable single-server private information retrieval

Cites work

• A simpler rate-optimal CPIR protocol
• Automata, Languages and Programming
• Communication optimal Tardos-based asymmetric fingerprinting
• scientific article; zbMATH DE number 1261806 (Why is no real title available?)
• scientific article; zbMATH DE number 1304086 (Why is no real title available?)
• scientific article; zbMATH DE number 1559546 (Why is no real title available?)
• Private Streaming With Convolutional Codes

Cited in

(3)

• PIR Array Codes With Optimal Virtual Server Rate
• A survey on single server private information retrieval in a coding theory perspective
• Single server private information retrieval protocols with codes over rings

This page was built for publication: On the privacy of a code-based single-server computational PIR scheme

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2120986)