Private Record Certification: Proving a Known Status
Private Record Certification is the central mechanism in the PRC-based anonymous-credential revocation system. The question here is narrower than “how do authorities store a status list?”: what can they certify when the holder already knows the candidate status but cannot reveal the database index at which that status is stored? Understanding that contract lets us distinguish PRC from private information retrieval and blind signatures, and lets us see why a binary revocation decision is a particularly natural use.
A certificate is evidence about a hidden pair
Suppose a revocation authority maintains a database of records. Each record sits at an index, and the holder's credential contains one of those indexes as a private attribute. The holder wants evidence about the pair formed by the index and its record, but does not want the authority to learn which pair they selected. A PRC protocol addresses exactly that situation.
A PRC certificate says, in substance, “the database record at this index has this value,” with the index and value bound together. The certificate is not just a reply saying “valid,” because a bare reply could be detached from the credential later. It is evidence tied to the hidden position. The protocol also includes auxiliary data, such as a timestamp, that can be covered by the certificate's signature. A verifier can later check that the certificate is authentic for the claimed pair, while a zero-knowledge proof can keep the pair itself out of the presentation.
The phrase private applies to the request and its contents, not to a fantasy in which the authorities have no database. The authorities operate the status database and know its records as part of their job. What they should not learn from a particular interaction is which index the holder queried or which record value the holder is trying to establish. A client-side query state—such as commitment randomness—allows the holder to check the returned certificate against their own hidden index and candidate record.
This gives PRC four linked properties. Correctness means an honest interaction produces a certificate that verifies. Unforgeability means a client cannot make a valid certificate appear to attest to a false record or alter associated auxiliary data. Unlinkability means the authorities should not be able to order or associate requests in a way that reveals which interactions came from the same client or record, under the stated threat model. Database privacy is an optional extension that prevents a client from learning records for which they have no authorization. The properties sound similar, but they defend different boundaries: one protects the truth of the certificate, another protects the query, and another limits what an authorized client may ask.
A small thought experiment makes the boundaries concrete. Imagine a database with many positions, one of which belongs to a holder's credential. The holder knows their private position and wants to establish the expected valid status. The authorities know the database and can see that many requests are arriving, but the shares they receive should not tell them which position was selected. The holder receives a certificate that can be checked using their own position and private query state. A later verifier sees the certificate's proof of consistency, not the position itself. Each participant therefore learns something useful without receiving the same complete view. PRC's value lies in coordinating those partial views, not in making the underlying status record unknown to the organization that maintains it.
The difference from private information retrieval is decisive. In PIR, a client wants to learn an unknown value, such as the contents of a database row, without revealing which row they selected. The protocol is successful when the client reconstructs the record. In PRC, the client already knows the candidate value and wants the server to attest that the value is present at the hidden index. Revealing the record to the client would not solve the main problem; the client needs a compact, signed object that can be shown or proved to somebody else.
A simple analogy is the difference between asking a librarian for a book and asking the librarian to certify a fact about a book without revealing which book was named. PIR protects the request while returning the book. PRC protects the request while returning a certificate about the server's own record. The analogy is limited—the cryptographic protocol has to bind the certificate to both the index and value—but it separates the goals cleanly.
PRC also differs from a blind signature. A blind-signature protocol lets a client obtain a signature on a message while hiding the message from the signer. That sounds close, but it leaves the client free to choose the message. In the revocation setting, the client must not be able to ask an authority to sign “this credential is valid” when the database actually says otherwise. The authority must attest to a value determined by the database at the requested index. PRC therefore combines hidden input with a server-side relation: the signed statement is constrained by the record the authorities maintain, not merely by a blinded message supplied by the client.
That constraint is what makes the certificate useful in a later proof. The commitment inside the certificate hides the index and record while binding them to one object. If a client later changes either value, they would need to open the same commitment in two different ways or forge the authority's signature. The paper gives this as the intuition for unforgeability, relying on a binding commitment and an unforgeable signature. The certificate can consequently become an input to a zero-knowledge proof instead of exposing a raw index to a verifier.
Hiding and binding solve opposite-looking problems that must coexist. If the commitment revealed the index, the authority or a later observer could use it as a stable handle. If it were not binding, a client could obtain a signature on one database fact and present it as evidence of another. The certificate is useful precisely because it hides the contents while making substitution difficult. The later proof does not need to reveal what is hidden; it needs to show that the prover knows values that satisfy the commitment and match the anonymous credential. This is why a PRC certificate is a bridge between a server-side database relation and a verifier-side privacy proof.
Why knowing the record changes the protocol
Revocation uses a small record domain. The paper's construction keeps a binary status for each credential, and its revocation integration uses the convention that a database value of 1 means the credential is valid. The holder does not need to learn a new arbitrary value from the authority. They need to establish the expected-valid case. If the authority's certificate attests to the other status, checking the certificate against the expected valid value fails and the holder does not produce a non-revocation presentation.
This may seem like a minor distinction, but it determines where the work happens. If a client were trying to retrieve a large unknown record, the servers would have to help them reconstruct that record or send encrypted shares. In the binary revocation case, the client can test a small candidate domain. They can attempt to verify the certificate as evidence of validity; the check succeeds only when the hidden record and hidden index match the client's credential and expected status. The protocol is therefore a certification test, not a general-purpose answer channel.
The signed object also avoids a costly naive design. One straightforward idea would be for the authorities to precompute a signed commitment for every database entry and let the client retrieve the corresponding signature through PIR. That would turn each binary record into a much larger object containing a signature and commitment randomness. More importantly, if the certificate includes changing auxiliary data such as a timestamp or expiration value, frequent database updates could force the authorities to re-sign every entry. The database would grow from a compact status array into a collection of proof objects, and preventing unauthorized clients from using the retrieval interface would require another privacy mechanism.
PRC reverses that cost pattern. The authorities retain the actual records and construct the certificate for a selected record when a request arrives. They pay the server-side computation and communication needed to process the hidden query, but they do not have to maintain a separately signed object for every possible index. A status update changes the underlying record rather than requiring the authority to rewrite a pre-signed certificate for every credential. The later performance chapter will ask whether that shift remains practical at very large database sizes; the conceptual point is that PRC is designed around an updateable relation, not a static cache of signatures.
The client's contract has two moments. First, they send a hidden request and receive a certificate with auxiliary data. Second, they use their local query state, their private index, and their candidate record to verify the certificate. In the basic PRC interface, verification checks a signature on a commitment to the index and record together with the auxiliary data. The client can therefore reject a response that does not certify the expected value before involving a verifier. This local check is important for the online revocation flow: a revoked credential should stop at the holder rather than become a presentation that the verifier must interpret.
The certificate does not, by itself, prove that the requester owns the index. That is the separate database-privacy problem. Without an authorization check, a malicious client might submit hidden requests for other indexes and learn their records by trying candidate values. The paper's extension adds an authorization credential and a zero-knowledge proof showing that the requester is entitled to the selected index. In the revocation system, the anonymous credential that contains the revocation index can serve as that authorization credential. The authorities can check the proof without learning the index, while an unauthorized client should be unable to produce a valid proof for a record they do not own.
This separation also explains why “the servers do not see the record” needs careful wording. The record is hidden as the target of the query and as the client's private candidate, but the authorities possess the database and perform the computation. The goal is that no individual server, or no protected colluding group under the protocol's assumptions, can connect the incoming shares to a clear index and target value. The certificate then carries a binding statement without reconstructing the sensitive pair for the servers. Database privacy adds a restriction on the client's authorization; it is not a substitute for query privacy.
The observer boundaries can be tested with three failure questions. If an authority learns the clear index, the query may become a usage signal even if the returned certificate is perfectly signed. If a client can obtain certificates for arbitrary indexes, the database's privacy is lost even if every query remains unlinkable. If a verifier receives a certificate that is not cryptographically tied to the presented credential, a malicious client could attach a valid status from one credential to another. PRC's design separates these cases so that the privacy of the request, the truth of the record, and the linkage to the credential are each addressed by a different part of the construction. It also makes the limits visible: a protocol can protect one boundary while leaving another to an extension or to deployment policy.
The sequence is deliberately asymmetric. The client sends shares rather than a clear index. The servers perform the database-dependent work and return a signed result, but the client retains the state needed to check what was certified. In the full construction, the authorities use secret sharing, homomorphic commitments, and threshold-signature operations to make this sequence possible; the important conceptual division is already visible here: the client chooses a hidden location, the database determines the record, and the certificate binds the two.
The known-record assumption has a clear boundary. For a binary validity status, testing the candidate value is cheap and the desired outcome is often simply “a certificate for the valid case exists.” For a richer record—an account balance, a score, or a multi-valued status—the client may not know the value in advance. The paper notes two directions: the client can test a small domain by repeated verification, or the servers can attach encrypted shares of the record, which moves the response toward PIR. PRC remains useful, but its cleanest client-side complexity and its revocation interpretation depend on the record being small or known.
That is the primitive's real contribution. It does not make a hidden query magically reveal a public fact. It makes the fact certifiable without separating it from the hidden location that gives it meaning. In an anonymous credential system, that is exactly the bridge needed between a private index and a later proof: the holder can establish current validity while the authorities do not learn which row was selected, and the verifier can check consistency without receiving the index.
The remaining challenge is to turn this certificate contract into a working anonymous presentation. The system must retrieve the record privately, convert the result into a binding signed object, and then prove that the object's hidden index is the same one carried by the credential. Only then can the promise of private certification become a real-time revocation decision.