How Authorities Sign What They Cannot See

The PRC construction turns the idea of a private certificate into a sequence of server-side operations. The focus here is how a Boolean-shared credential index becomes a secret-shared database record, then a hiding commitment and a signed result, without any authority reconstructing the selected index in cleartext. Following that path shows why the system uses different kinds of secret sharing, why the database is rearranged as a square table, and why a threshold signature improves verifiability without eliminating the need for trust.

The hidden index becomes a hidden record

The client begins with two private inputs that play different roles. One is the index embedded in the anonymous credential. The other is fresh randomness that will later hide the index and record inside a commitment. The client secret-shares the index as bits and shares the randomness as an arithmetic value. Each PRC server receives only its own share of each input.

The distinction between the shares is functional. Boolean sharing represents a value as individual bits combined by exclusive-or. It is convenient for selection logic: a protocol can combine bits with Boolean operations without revealing the underlying number. Arithmetic sharing represents values in a prime field and supports addition and multiplication. It is the form needed later for the homomorphic commitment, whose aggregation must correspond to adding the authorities' shares. Sending the same input in one representation would make one of those later stages less natural or more expensive.

A share is not a small encrypted copy of the original value. Taken alone, it is intended not to identify the value; only the prescribed combination of shares reconstructs it. That property is what lets the authorities participate in the calculation without each becoming a direct observer of the client's index. It also explains why the protocol needs interaction among the servers: they must combine their shares in carefully controlled operations while preserving the separation between a local view and the final result.

The servers know the database they maintain. Let it contain N records, each with l bits. They need to select one record without receiving a clear index from the client. A direct one-hot selector would have N positions, with a single 1 at the requested position. Constructing and transmitting that selector from the client would make the query grow with the database. The PRC construction instead lets the servers expand the shared index collaboratively.

The first step is a recursive Boolean-to-one-hot conversion. For a one-bit input, the selector is simply the two possibilities: the share for zero and the share for one. For a longer index, the servers split the bits into two halves, recursively construct a one-hot vector for each half, and combine every row choice with every column choice. The output has one position for each possible index, but the output is still secret-shared. The authorities can use the selector without learning which position contains the 1.

The construction avoids doing that expansion across all N positions at once. It rearranges the database into a two-dimensional table whose sides are roughly the square root of N. The hidden index is split into a row part and a column part. The servers expand each part separately.