F-PIR — Verifiable private information retrieval, single server

F-PIR (Verifiable private information retrieval, single server) is part of Oblivious Transfer and Correlated Randomness in the UC functionality encyclopedia. Status: an emerging formulation, still an active area of research.

A client reads one entry of a server’s database without the server learning which. That is PIR; and stated as an ideal functionality it is almost trivial, which is why it took so long to get one worth printing. What makes this box a definition rather than a restatement is the second half of its name: verifiable. A single server is free to answer with garbage, and plain PIR gives a client no way to tell. This functionality binds the server to one database and hands the client either the right entry or an explicit failure — never a wrong entry it might believe.

The stub’s title was “Private information retrieval” and its status was “open — no accepted UC formulation exists yet”. Both are updated by this entry. The title now names the printed object, which is verifiable PIR; the status moves to “emerging”, because one functionality with two realizations is not yet a settled formulation. This page carried no citations at all before this entry.

Functionality

Reading the box: \(\mathsf{require}\) refuses the call; \(\mathcal{A}^{!}(\cdot)\) is a responsive call on the adversary slot — the answer comes back before anything else runs — and \(\mathsf{San}[\mathsf{Clean}]\) sanitizes it; \(\mathbf{C}\) is the corrupted set; \(\square\) is never-set. \(\Sigma\) is the alphabet of database entries, \(N\) the database size, \(S\) the server. A query id \(q\) is a triple \((\mathit{sid}, C, \mathit{nonce})\), so it names its own client. \(\mathcal{G}_{\mathsf{lib}}\) is a global code library — the same device this site already carries as \(\mathcal{F}_{\mathsf{Lib}}\) on F-AE and F-fsAEAD, printed there as local and here as global. That the same object appears under both types in two papers is the point G-ledger’s source makes in general: globality is a fact about use.

Functionality \(\mathcal{F}_{\mathsf{VPIR}}\)

\(\mathit{pid}\),   \(\mathbf{P}\),   \(\mathbf{N}\),   \(\mathbf{U} := \{(\mathcal{A},\mathsf{serves}),\,(\mathcal{G}_{\mathsf{lib}},\mathsf{serves})\}\),   \(\mathit{par} := (\Sigma, \ N, \ S)\)

Initialize():

1. \(\mathtt{init} \gets 0\);  \(\mathtt{DB} \gets \square\)
2. \(\mathtt{Q}[*] \gets \square\);  \(\mathtt{del}[*] \gets 0\);  \(\mathtt{res}[*] \gets 0\)// per query id: the index asked for, whether the server saw it, whether it answered
3. \(\mathtt{out}[*] \gets \square\)

id.Init(D)from id′

4. \(\textbf{require}\ \mathit{id}.P = S \ \wedge\ \mathtt{init} = 0 \ \wedge\ D \in \Sigma^{N}\)// one database per instance, and only from the server the process id names
5. \(V \gets \mathit{id}_{\mathcal{G}_{\mathsf{lib}}}.\mathsf{FullRetrieve}(\mathsf{DigestVerifyCode}) \text{ as } \mathit{id}\)
6. \(\textbf{if}\ V(\mathit{pid}, D) = \mathsf{reject}\ \textbf{then}\)
7. \(\textbf{return}\ \mathsf{invaliddigest}\)// the digest lives in the process id and the box cannot read it
8. \(\textbf{require}\ \mathsf{San}[\mathsf{Clean}_{i}]\bigl(\mathcal{A}^{!}(\mathsf{ReportInit}, D)\bigr) = \mathsf{ok}\)// the database is handed to the simulator entire, deliberately
9. \(\mathtt{init} \gets 1\);  \(\mathtt{DB} \gets D\);  \(\textbf{return}\) ok

id.Query(q, i)from id′

10. \(\textbf{require}\ q = (\mathit{pid}, \mathit{id}.P, \cdot) \ \wedge\ \mathtt{Q}[q] = \square \ \wedge\ i \in [N]\)// a query id names its own client and is used once
11. \(\mathtt{Q}[q] \gets i\)
12. \(\mathcal{A}^{!}(\mathsf{ReportQuery}, q)\)// the query id, never \(i\): this line is query privacy
13. \(\mathtt{del}[q] \gets 1\);  \(\textbf{return}\) ok

id.Response(q, D^{*})from id′

14. \(\textbf{require}\ \mathit{id}.P = S\)
15. \(\textbf{require}\ S \in \mathbf{C} \ \vee\ \mathtt{init} = 1\)// (a) an honest server must have initialized; a corrupt one need not
16. \(\textbf{require}\ \mathtt{del}[q] = 1\)// (b) every response answers a completed query
17. \(\textbf{require}\ \mathtt{res}[q] = 0\)// (c) one response per query, ever
18. \(\textbf{require}\ S \in \mathbf{C} \ \vee\ D^{*} = \mathtt{DB}\)// (d) an honest server is bound to the database it initialized with
19. \(\mathtt{res}[q] \gets 1\);  \(\mathcal{A}^{!}(\mathsf{ReportResponse}, q)\)
20. \(\textbf{if}\ S \in \mathbf{C} \ \wedge\ (\mathtt{init} = 0 \ \vee\ D^{*} \neq \mathtt{DB})\ \textbf{then}\)
21. \(\mathtt{out}[q] \gets \mathsf{verificationfail}\);  \(\textbf{return}\) ok// a server that forgot the database can produce nothing but this
22. \(\mathtt{out}[q] \gets \mathtt{DB}[\mathtt{Q}[q]]\);  \(\textbf{return}\) ok

id.Fetch(q)from id′

23. \(\textbf{require}\ q = (\mathit{pid}, \mathit{id}.P, \cdot) \ \wedge\ \mathtt{out}[q] \neq \square\)
24. \(\textbf{return}\ \mathtt{out}[q]\)

id.Leak()from id′

25. \(\textbf{if}\ \mathit{id}.P = S\ \textbf{then}\)
26. \(\textbf{return}\ (\mathtt{DB}, \mathtt{del}, \mathtt{res})\)// never \(\mathtt{Q}\): the server does not learn any index, at any corruption
27. \(\textbf{return}\ \{(q, \mathtt{Q}[q], \mathtt{out}[q]) : q = (\mathit{pid}, \mathit{id}.P, \cdot)\}\)// a corrupt client's own queries, and no one else's

Source: Algorithm 3, p. 10 of Julia Guskind, Ariel Hamlin, Ryan Little, Daniel S. Roche and Mayank Varia, “Single-Server Verifiable PIR with Updates and Universally Composable Security”, ePrint 2026/1651, revision 20260810:184710. The functionality is printed as a numbered Algorithm* rather than a figure, which is why a figure-caption sweep does not find it — the same false-negative mode f-dkg recorded for a numbered Functionality environment.*

• Line 4 is a call the functionality makes because it cannot do the job itself, and the paper says so. The database’s digest lives in the session id, and “the structure of the digest is abstracted out of the ideal \(\mathcal{F}_{\mathsf{VPIR}}\) functionality” — so the box fetches real-world verification code from \(\mathcal{G}_{\mathsf{lib}}\) and runs it at line 5. The problem it solves is stated in the source: “the ideal functionality \(\mathcal{F}_{\mathsf{VPIR}}\) must be convinced that a database is consistent with its own digest, but the digest is based on the real-world instantiation that the ideal functionality does not know.” This is what the internal-code device is for, and it is a cleaner example than the Signal papers’ because the need is stated in one sentence.
• Line 8 hands the whole database to the simulator, on purpose. Nothing here is hidden from the server or from the adversary — the source’s reason is that “we do not require the digest to provide a hiding property, and so it may reveal arbitrary information about the database”. PIR protects the query, not the data. A reader who wants both wants symmetric PIR, which this is not.
• Line 12 is query privacy, and it is one omission. The adversary is told \(q\) and is not told \(i\). Since \(q\) is a triple naming its client, the server learns exactly who asked and when, and nothing about what. Compare line 24: even on corruption, the server is never given \(\mathtt{Q}\).
• Lines 16 through 20 are four checks, and they are asymmetric in a way that carries the whole verifiability argument. Checks (a) and (d) are conditional on the server being honest: an honest server must have initialized and must answer with the database it initialized with. A corrupt server is allowed past both — and line 21 then guarantees that the only thing such a server can produce is \(\mathsf{verificationfail}\). That asymmetry is the definition doing real work: it does not forbid a malicious server from cheating, it forbids a malicious server from cheating undetectably. The source’s own gloss is that “this makes it possible to simulate a malicious server who does not know a valid \(DB\) and simply responds to queries with garbage, causing honest clients’ verification to fail”.
• Line 20 is proof of retrievability, stated as a binding condition. An honest server that does not still hold the database cannot pass check (d). Taken with line 21, “a server must remember the database used at initialization to successfully respond to” queries. The property is not proved about the box; it is the box.
• Line 25 is the correct answer, and note what it is not. It is \(\mathtt{DB}[\mathtt{Q}[q]]\) — the functionality’s own record, indexed by the client’s own stored index. The server’s \(D^{*}\) is used only in the check at line 20 and never to compute an answer. So a client that gets an answer at all gets the right one.
• Lines 17 and 18 make a query id a one-shot slot in both directions. Every response answers a completed query, and no query is answered twice. Combined with line 11’s freshness test, the query id is the only bookkeeping the box needs.
• Every adversary call here is responsive. Lines 8, 12 and 21 use \(\mathcal{A}^{!}\), because the source’s idiom is “send … and wait for” with the functionality’s own next step depending on the answer. That is a real restriction on the simulator and is why the source can let the adversary “prevent or delay the server’s output” — the delay is expressible precisely because the call blocks.
• Line 24 is the leak that decides whether this is PIR at all. Corrupting the server returns the database (already public by line 8) and the query bookkeeping, and never \(\mathtt{Q}\). A functionality that returned the index table on server corruption would offer no privacy against the one party PIR exists to hide from.

Mismatch register.

The source	This box	Why
output (Query, qid) to S and return (Answer, qid, DB[i]) to C — outputs to a party other than the caller	\(\mathtt{del}\) and \(\mathtt{out}\), read back by \(\mathsf{Fetch}\) at lines 26–27	Delivery is to the caller here. This is an added interface, and the addition is recorded rather than hidden: the source’s cross-party outputs become a recorded result and a poll. It is the same shape the ticked entries use, and it changes when a party learns, not what.
“End execution if …”	\(\mathsf{require}\)	A refusal. Distinct from line 6’s \(\mathsf{invaliddigest}\) and line 22’s \(\mathsf{verificationfail}\), which are values a caller receives. The source uses all three.
Send … to the simulator Sim. Wait for Sim to respond	\(\mathcal{A}^{!}(\cdot)\) under \(\mathsf{San}[\mathsf{Clean}]\)	Responsive, as above.
The session id contains the server’s party id and the digest material	The process id, with the guard at line 3 and the digest passed to \(V\) at line 5	The one place a session identifier is genuinely load-bearing on this site: line 5 hands \(\mathit{pid}\) to the fetched code because the digest is inside it.
\(\mathcal{G}_{\mathsf{lib}}\), a global functionality with Store and Retrieve	A used slot	Not transcribed here: the site’s \(\mathcal{F}_{\mathsf{Lib}}\) pages already carry the same object under a different type.
No leakage interface	\(\mathsf{Leak}\) at lines 23–25	Required here, and its content is a real decision; see the last bullet.
\(\mathcal{F}_{\mathsf{UVPIR}}\), the updatable extension of §6.1	Not transcribed	A different, larger object — it holds a DAG of database versions and lets clients sync along a path, with forking. Recorded as the successor, not blended.

Known realizations

Two, and both restrict the adversary’s control of the network.

• \(\Pi_{\mathsf{Triv\text{-}VPIR}}\) (Theorem 1): given a collision-resistant hash function family, it UC-realizes this functionality in the presence of the global \(\mathcal{G}_{\mathsf{lib}}\) and \(\mathcal{G}_{\mathsf{CRS}}\), “with static corruptions, and against an adver[s]ary who cannot forge or modify network traffic”. Trivial PIR — the server sends the whole database — with a digest check.
• \(\Pi_{\mathsf{VeriSimplePIR}}\) (Theorem 2): given a semantically secure linearly homomorphic encryption scheme and hardness of \(\mathsf{SIS}_{\lambda,m,q,4B}\), it UC-realizes this functionality in the presence of \(\mathcal{G}_{\mathsf{lib}}\) and \(\mathcal{G}_{\mathsf{CRS}}\) and the local \(\mathcal{F}_{\mathsf{NIZK}}\) — this site’s F-NIZK. Here the adversary “may statically corrupt all parties, and may arbitrarily delay or drop network messages, but cannot modify or spoof them”.

The network restriction is the caveat to carry away. Neither theorem holds against an adversary that can modify or spoof traffic. That is a genuine weakening of the usual UC quantification and it is stated in the theorems rather than in the functionality, so a reader looking only at the box will not see it.

An updatable extension exists in the same paper. \(\mathcal{F}_{\mathsf{UVPIR}}\) (§6.1) is built generically from this functionality: it stores the global state as a directed acyclic graph of database versions, lets a client sync forward along a path, and supports forking. Realized by \(\Pi_{\mathsf{UVPIR}}\) (Theorem 3) treating the underlying VPIR as a black box — which is the composition argument the paper is arranged to make.

Properties

• Query privacy against the server, with advantage exactly \(0\). Lines 12 and 24: the index reaches the adversary at no point, in no interface, at any corruption level.
• Correctness, with probability exactly \(1\), for any answer at all. Line 25 answers from the functionality’s own record. A client never receives a wrong entry — only the right one or \(\mathsf{verificationfail}\).
• Database binding for an honest server, with probability exactly \(1\). Line 20.
• Detectability of a cheating server, with probability exactly \(1\). Line 21. A corrupt server that does not hold the database can produce nothing but a failure.
• No data privacy whatsoever. Line 8 gives the adversary the database. This is PIR, not symmetric PIR.
• One response per query and one query per id. Lines 11, 17 and 18.
• No liveness. Nothing obliges the server to respond, and the responsive adversary calls let the simulator delay each step.

Formal artifacts

No machine-checked formalization yet.

References:

• Guskind, Hamlin, Little, Roche, and Varia. Single-server verifiable PIR with updates and universally composable security. 2026. The source of the box above: Algorithm 3, p. 10 of ePrint revision 20260810:184710, with the design discussion in §5.1. The global code library \(\mathcal{G}_{\mathsf{lib}}\) is Algorithm 2, p. 9; the realizations are Theorems 1 and 2; the updatable extension \(\mathcal{F}_{\mathsf{UVPIR}}\) and its Theorem 3 are §6. Added to this page’s references by this entry — the page previously cited nothing. Printed as a numbered Algorithm rather than a figure, so a figure-caption sweep does not find it.
• Apon, Katz, Shi, and Thiruvengadam. Verifiable oblivious storage. In Public-Key Cryptography (PKC), 2014. The nearest predecessor, and the source of the ideal functionality on F-ORAM. It generalizes ORAM by allowing server computation and adds integrity and freshness — the same combination of privacy and verifiability this page’s box has, over a read-write store rather than a read-only database. Cited for the lineage; its functionality is a different object and is not blended in. Added by this entry.