The Compression Trick: Turn a Decryption Phase into a Small Response

ZipPIR’s technical contribution begins with a structural observation about the encrypted query material that a high-throughput PIR system already uses. The LWE ciphertext is large, but the part the client ultimately needs for decryption is a smaller linear phase. This chapter explains how ZipPIR evaluates that phase over encrypted secret-key material, why Paillier makes the response smaller without making the computation cheap, and how batching and parameter choices define the useful boundary of the trick.

The useful part of an LWE ciphertext is the phase

Learning With Errors, or LWE, is the basis of the ciphertext format used by several modern private-retrieval systems. An LWE ciphertext can be understood, at a high level, as a pair: a vector of apparently random values and another value that combines that vector with a secret key, a message, and a small amount of noise. The vector is important for security, but it also makes the ciphertext large. In the paper’s notation, the ciphertext is (a, b), where a has one entry for each coordinate of the secret key.

Decryption does not treat that pair as an indivisible object. The client computes a phase by subtracting the inner product of a and the secret key from b. In simplified form, the phase is b − sum(a[i] · sk[i]) modulo the ciphertext modulus. The client then divides by a scale and rounds to recover the message. The phase is the useful intermediate value: it is where the encrypted message becomes recognizable, but before the final rounding step removes the noise.

That sequence creates an opportunity. The phase is a linear function of the secret-key coordinates. If the server could evaluate that linear function without learning the secret key, it could return the phase rather than the original high-expansion ciphertext representation. The client would still perform the final private decryption step, but the network would carry a smaller object.

The algebra fits the privacy boundary because the server already knows the ciphertext components but not the client’s secret key. Suppose the key has several coordinates. The client can provide an additive-encrypted representation of each coordinate. The server then uses the known ciphertext coefficients as scalars, combines the encrypted coordinates, and adds the known b term. In the paper’s equivalent form, a coefficient such as q − a[i] is used so that the resulting plaintext is the same phase modulo q. The server performs the linear combination without opening any encrypted key coordinate.

The client’s final operation is correspondingly simple. It decrypts the additive ciphertext with the additive scheme’s secret key, reduces the result modulo the LWE modulus, and applies the same scale-and-round step used by ordinary LWE decryption. The server has computed an encrypted intermediate value, not the plaintext answer for itself. If the arithmetic stays within the additive plaintext space and the LWE noise stays within the decoding margin, the client recovers the same message that it would have recovered from the uncompressed ciphertext.

The server cannot simply ask the client to send the secret key. That would destroy the privacy property the encryption is meant to provide. ZipPIR instead uses an additive homomorphic encryption scheme, principally Paillier in the paper’s construction, to carry encrypted secret-key material.