pith. sign in

arxiv: 2604.22505 · v1 · submitted 2026-04-24 · 💻 cs.CR

Information-Theoretic Authenticated PIR: From PIR-RV To APIR

Pengzhen Ke , Yuxuan Qin , Liang Feng Zhang This is my paper

Pith reviewed 2026-05-08 11:26 UTC · model grok-4.3

classification 💻 cs.CR
keywords Private Information RetrievalAuthenticated PIRInformation-theoretic securityConversion theoremSelective-failure attacksResult verificationUnconditional security
0
0 comments X

The pith

Valid itPIR-RV schemes convert directly to secure itAPIR with no extra overhead.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines a full information-theoretic security model for authenticated PIR that requires statistical privacy against selective-failure attacks together with integrity. It shows that information-theoretic PIR with result verification is a relaxed special case sharing the same integrity guarantee but providing only basic query privacy. A conversion theorem is established proving that any itPIR-RV scheme meeting its relaxed conditions upgrades to the stronger itAPIR definition without added communication, computation, or storage cost. This removes the need to start from scratch when building unconditionally secure authenticated retrieval and supports its deployment against malicious servers.

Core claim

The paper proves that any valid itPIR-RV scheme can be turned into a secure itAPIR scheme by a direct conversion that adds statistical privacy against selective-failure attacks to the existing integrity property while introducing zero overhead. The proof rests on a hierarchical relation that treats itPIR-RV as a relaxed variant of itAPIR under the new information-theoretic definitions.

What carries the argument

The conversion theorem that upgrades any itPIR-RV scheme satisfying basic integrity and relaxed privacy to full itAPIR security against selective-failure attacks.

If this is right

  • Every existing itPIR-RV construction immediately yields a secure itAPIR protocol.
  • Authenticated PIR becomes possible using only statistical assumptions without computational hardness.
  • Quantum-resistant authenticated retrieval in malicious-server settings follows directly from the conversion.
  • itAPIR design effort reduces to checking the relaxed properties required of PIR-RV schemes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Implementers could apply the conversion to current PIR-RV libraries to obtain authenticated versions without redesign.
  • The same upgrade pattern may extend to other privacy protocols that already contain verification steps.
  • Research attention can shift toward strengthening the privacy side of PIR-RV constructions as a route to stronger authenticated variants.

Load-bearing premise

The starting itPIR-RV scheme must already satisfy the paper's definitions of integrity and relaxed privacy so the conversion preserves the statistical security bounds.

What would settle it

An itPIR-RV scheme that meets the relaxed privacy definition yet produces an itAPIR construction that leaks the retrieval index under a selective-failure attack would disprove the conversion theorem.

read the original abstract

Private Information Retrieval (PIR) allows clients to retrieve database entries without leaking retrieval indices, yet malicious servers seriously compromise retrieval correctness. Existing Authenticated PIR (APIR) schemes resist selective-failure attacks but rely on computational hardness assumptions. In contrast, information-theoretic PIR with Result Verification (itPIR-RV) achieves integrity without computational assumptions, yet only provides relaxed query privacy with no defense against selective-failure attacks. This paper focuses on unconditionally secure information-theoretic APIR (itAPIR) constructions. We propose the rigorous information-theoretic security definition for itAPIR with statistical privacy against selective-failure attacks and integrity as core properties, formalize the hierarchical relation between itAPIR and itPIR-RV as a relaxed variant with identical integrity but basic query privacy, and prove a conversion theorem that valid itPIR-RV schemes can be directly upgraded to secure itAPIR with no extra overhead. Our work bridges the theoretical gap, simplifies itAPIR design, and enables quantum-resistant PIR in malicious server environments.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper introduces a rigorous information-theoretic security definition for itAPIR that requires statistical privacy against selective-failure attacks together with integrity. It formalizes the hierarchical relation positioning itPIR-RV as a relaxed variant that shares the same integrity property but only basic query privacy. The central result is a conversion theorem showing that any valid itPIR-RV scheme can be directly upgraded to a secure itAPIR scheme with no extra overhead.

Significance. If the conversion theorem is correct, the work supplies a direct, overhead-free route from existing itPIR-RV constructions to full itAPIR, thereby simplifying the design of unconditionally secure authenticated PIR and enabling quantum-resistant solutions against malicious servers. The hierarchical security framework also offers a clean way to reason about the gap between relaxed and strong information-theoretic authentication.

minor comments (2)
  1. [Abstract] The abstract asserts the existence of the conversion theorem and the new security definition; the manuscript should include a short forward pointer (e.g., “see Theorem 4.3”) so readers can locate the proof immediately.
  2. [Security definitions] Notation for the statistical privacy and integrity predicates is introduced in the security-definition section; a compact table summarizing the differences between the itAPIR and itPIR-RV predicates would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their accurate summary of the paper and for recommending minor revision. The referee correctly identifies the core contributions: the information-theoretic security definition for itAPIR (statistical privacy against selective failures plus integrity), the hierarchical positioning of itPIR-RV as a relaxed variant with the same integrity but weaker query privacy, and the conversion theorem that upgrades any valid itPIR-RV scheme to itAPIR at no extra cost. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; definitional hierarchy with independent proof

full rationale

The paper defines itAPIR with statistical privacy against selective-failure attacks plus integrity, then positions itPIR-RV as a relaxed variant sharing integrity but with weaker query privacy. It proves a conversion theorem showing any valid itPIR-RV scheme upgrades directly to itAPIR with no overhead. This structure is a standard cryptographic definitional lifting and proof, not a reduction of the claimed result to its own inputs by construction, fitted parameters, or self-citation chains. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim depends on the appropriateness of the proposed security definition and the correctness of the conversion theorem, neither of which can be assessed from the abstract alone; no free parameters or invented entities are mentioned.

axioms (1)
  • standard math Standard information-theoretic security definitions based on statistical distance or probability bounds for privacy and integrity
    The paper builds on established notions from cryptography for defining statistical privacy and integrity guarantees.

pith-pipeline@v0.9.0 · 5478 in / 1245 out tokens · 56434 ms · 2026-05-08T11:26:22.068617+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    Private infor- mation retrieval,

    B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan, “Private infor- mation retrieval,”Journal of the ACM (JACM), vol. 45, no. 6, pp. 965–981, 1998

    work page 1998

  2. [2]

    Information-theoretic private information retrieval: A unified construction,

    A. Beimel and Y . Ishai, “Information-theoretic private information retrieval: A unified construction,” inAutomata, Languages and Pro- gramming: 28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings 28. Springer, 2001, pp. 912–926

    work page 2001

  3. [3]

    Robust information-theoretic private infor- mation retrieval,

    A. Beimel and Y . Stahl, “Robust information-theoretic private infor- mation retrieval,” inInternational Conference on Security in Commu- nication Networks. Springer, 2002, pp. 326–341

    work page 2002

  4. [4]

    Private information retrieval in the presence of malicious failures,

    E. Y . Yang, J. Xu, and K. H. Bennett, “Private information retrieval in the presence of malicious failures,” inProceedings 26th Annual International Computer Software and Applications. IEEE, 2002, pp. 805–810

    work page 2002

  5. [5]

    Improving the robustness of private information re- trieval,

    I. Goldberg, “Improving the robustness of private information re- trieval,” in2007 IEEE Symposium on Security and Privacy (SP’07). IEEE, 2007, pp. 131–148

    work page 2007

  6. [6]

    Towards 3-query locally decodable codes of subexpo- nential length,

    S. Yekhanin, “Towards 3-query locally decodable codes of subexpo- nential length,”Journal of the ACM (JACM), vol. 55, no. 1, pp. 1–16, 2008

    work page 2008

  7. [7]

    3-query locally decodable codes of subexponential length,

    K. Efremenko, “3-query locally decodable codes of subexponential length,” inProceedings of the forty-first annual ACM symposium on Theory of computing, 2009, pp. 39–44

    work page 2009

  8. [8]

    Optimally robust private information retrieval,

    C. Devet, I. Goldberg, and N. Heninger, “Optimally robust private information retrieval,” in21st USENIX Security Symposium (USENIX Security 12), 2012, pp. 269–283

    work page 2012

  9. [9]

    Verifiable multi-server private information retrieval,

    L. F. Zhang and R. Safavi-Naini, “Verifiable multi-server private information retrieval,” inInternational Conference on Applied Cryp- tography and Network Security. Springer, 2014, pp. 62–79

    work page 2014

  10. [10]

    The capacity of private information retrieval,

    H. Sun and S. A. Jafar, “The capacity of private information retrieval,” IEEE Transactions on Information Theory, vol. 63, no. 7, pp. 4075– 4088, 2017

    work page 2017

  11. [11]

    The capacity of robust private information retrieval with col- luding databases,

    ——, “The capacity of robust private information retrieval with col- luding databases,”IEEE Transactions on Information Theory, vol. 64, no. 4, pp. 2361–2370, 2017

    work page 2017

  12. [12]

    The capacity of private information retrieval from byzantine and colluding databases,

    K. Banawan and S. Ulukus, “The capacity of private information retrieval from byzantine and colluding databases,”IEEE Transactions on Information Theory, vol. 65, no. 2, pp. 1206–1219, 2018

    work page 2018

  13. [13]

    How to correct errors in multi-server pir,

    K. Kurosawa, “How to correct errors in multi-server pir,” inInterna- tional Conference on the Theory and Application of Cryptology and Information Security. Springer, 2019, pp. 564–574

    work page 2019

  14. [14]

    Verifiable single-server private in- formation retrieval from lwe with binary errors,

    L. Zhao, X. Wang, and X. Huang, “Verifiable single-server private in- formation retrieval from lwe with binary errors,”Information Sciences, vol. 546, pp. 897–923, 2021

    work page 2021

  15. [15]

    Verifiable private infor- mation retrieval,

    S. Ben-David, Y . T. Kalai, and O. Paneth, “Verifiable private infor- mation retrieval,” inTheory of Cryptography Conference. Springer, 2022, pp. 3–32

    work page 2022

  16. [16]

    On the optimal commu- nication complexity of error-correcting multi-server pir,

    R. Eriguchi, K. Kurosawa, and K. Nuida, “On the optimal commu- nication complexity of error-correcting multi-server pir,” inTheory of Cryptography Conference. Springer, 2022, pp. 60–88

    work page 2022

  17. [17]

    Two-server private information retrieval with result verification,

    P. Ke and L. F. Zhang, “Two-server private information retrieval with result verification,” in2022 IEEE International Symposium on Information Theory (ISIT). IEEE, 2022, pp. 408–413

    work page 2022

  18. [18]

    Byzantine-robust private information retrieval with low communication and efficient decoding,

    L. F. Zhang, H. Wang, and L.-P. Wang, “Byzantine-robust private information retrieval with low communication and efficient decoding,” inProceedings of the 2022 ACM on Asia Conference on Computer and Communications Security, 2022, pp. 1079–1085

    work page 2022

  19. [19]

    Post-quantum cheating detectable private information retrieval,

    L. Zhu, C. Lin, F. Lin, and L. F. Zhang, “Post-quantum cheating detectable private information retrieval,” inIFIP International Con- ference on ICT Systems Security and Privacy Protection. Springer, 2022, pp. 431–448

    work page 2022

  20. [20]

    Authenticated private information retrieval,

    S. Colombo, K. Nikitin, H. Corrigan-Gibbs, D. J. Wu, and B. Ford, “Authenticated private information retrieval,” in32nd USENIX security symposium (USENIX Security 23), 2023, pp. 3835–3851

    work page 2023

  21. [21]

    Private information retrieval with result verification for more servers,

    P. Ke and L. F. Zhang, “Private information retrieval with result verification for more servers,” inInternational Conference on Applied Cryptography and Network Security. Springer, 2023, pp. 197–216

    work page 2023

  22. [22]

    Two-server private information retrieval with optimized download rate and result verification,

    S. Kruglik, S. H. Dau, H. M. Kiah, and H. Wang, “Two-server private information retrieval with optimized download rate and result verification,” in2023 IEEE International Symposium on Information Theory (ISIT). IEEE, 2023, pp. 1354–1359

    work page 2023

  23. [23]

    Efficient and generic meth- ods to achieve active security in private information retrieval and more advanced database search,

    R. Eriguchi, K. Kurosawa, and K. Nuida, “Efficient and generic meth- ods to achieve active security in private information retrieval and more advanced database search,” inAnnual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2024, pp. 92–121

    work page 2024

  24. [24]

    On the definition of malicious private information retrieval,

    B. Alon and A. Beimel, “On the definition of malicious private information retrieval,” in6th Conference on Information-Theoretic Cryptography (ITC 2025). Schloss Dagstuhl–Leibniz-Zentrum f ¨ur Informatik, 2025, pp. 8–1

    work page 2025

  25. [25]

    Efficient information-theoretic dis- tributed point functions with general output groups,

    J. Li, P. Ke, and L. F. Zhang, “Efficient information-theoretic dis- tributed point functions with general output groups,”Designs, Codes and Cryptography, vol. 93, no. 5, pp. 1501–1530, 2025

    work page 2025

  26. [26]

    A unified framework for constructing information- theoretic private information retrieval,

    L. F. Zhang, “A unified framework for constructing information- theoretic private information retrieval,”Pragmatic Cybersecurity, vol. 1, no. 1, p. 3, 2025

    work page 2025

  27. [27]

    Efficient DPF-based error-detecting information-theoretic private information retrieval over rings,

    P. Ke, L. F. Zhang, H. Wang, and L.-P. Wang, “Efficient DPF-based error-detecting information-theoretic private information retrieval over rings,”Cybersecurity, vol. 9, no. 1, p. 149, 2026

    work page 2026