PIR Security Parameters for Zcash Voting

Before Zcash coinholder voting went live, we doubled the lattice dimension after conservative estimates for YPIR's defaults fell below our 128-bit target.

Duotone portrait of computer scientist Oded Regev on a pale pink disc, beside the dotted matrix equation A s plus e equals b modulo q, with the error vector highlighted in pink. — Oded Regev introduced Learning With Errors, the hardness assumption underlying YPIR's encryption. The matrix at left writes a batch of LWE samples as *A s + e = b* modulo q, with the error vector highlighted in pink. Portrait: Simons Foundation.

Over the past few weeks, several events have highlighted the risks of lattice-based cryptography. Notably, papers have claimed to find weaknesses that reduce the security margins of schemes that were previously considered established and well-understood.

On the flip side, some of these attacks applied only under narrow parameters, and in others they were formally retracted. None of the new attacks demonstrated a practical break of Private Information Retrieval (PIR).

Still, we decided to be conservative.

With the Zcash coinholder vote going live, lattice-based PIR is moving into production. We proactively analyzed the latest research and updated our parameters to retain a major security buffer, including against quantum attacks.

This post explains what concerned us, how we evaluated it, and why we doubled the main security parameter before launch.

Private Voting

First, let's discuss the application.

The Zcash voting system allows coinholders to express their opinions on the future of the protocol. The rule is 1 ZEC = 1 vote. Users ZK-prove their balance at a snapshot height, attesting that the corresponding note has not been spent.

Users already routinely prove their notes have not been spent before through the use of an unrepeatable nullifier. And so, to assert they haven't spent their money, we could require them to obtain a Merkle non-existence proof for it.

The problem: if a user directly queried the server for their nullifier, the server could later link it to the nullifier published on Zcash mainnet as part of a spend.

Sequence diagram of the nullifier PIR protocol. A client encrypts a nullifier and sends the encrypted query to a server, which prepares the nullifier database, evaluates the query, and returns an encrypted response for the client to decrypt. — The nullifier PIR protocol lets a client retrieve a proof without revealing which nullifier it queried.

We solve this with YPIR+SP, a lattice-based PIR scheme.

Its rough intuition: homomorphically matrix-vector multiply an encrypted client query against a public database. The response remains encrypted. Use another cryptography trick to compress it. The client decrypts their Merkle proof, while the requested row remains computationally hidden from the server.

We previously covered the underlying LWE and RLWE cryptography and the broader YPIR security model. Here, we will focus only on the security parameters.

Measuring Security

YPIR uses Regev encryption, whose security is based on the Learning With Errors (LWE) problem.

We use the Lattice Estimator to model applicable known attacks against the exact parameter set and take the lowest result. We then require additional margin because the models are incomplete and attacks can improve.

Lattice dimension is a key variable, but not the only one. The modulus, noise, secret distribution, available samples, and algebraic structure all influence the security argument.

The YPIR paper claims 128-bit security for its default parameters. Roughly, this means that no known modeled attack is expected to cost less than work. It is an estimate, not a proof or a permanent guarantee.

Interestingly, the result also depends on how you count the "work." There are several cost models. Two examples:

Core-SVP prices calls to the hardest underlying lattice operation. This makes schemes easy to compare, but omits many real attack costs and is deliberately conservative.
MATZOV is a more concrete model. It accounts for more of the work performed by an attack, including variables such as lattice dimension and available LWE samples.

Both are estimators rather than deterministic measures of security. Their outputs should not be read as equivalent wall-clock costs.

Our rerun produced estimates from 94.3-bit quantum Core-SVP to 131-bit MATZOV. The lower result is conservative model output, not a demonstrated attack. It nevertheless fell below our 128-bit target, so the defaults did not provide the margin we wanted for production.

This did not meet our confidence bar, so we kept digging.

More Structure: RLWE

YPIR does not use only unstructured LWE.

LWE is efficient for the server's first matrix-vector multiplication. However, sending the result naively would require the client to download a large database-dependent hint. Prior PIR schemes required a 121 MB hint for a 1 GB database. Completely impractical for production.

YPIR solves this through another trick: it embeds the LWE results into the negacyclic structure of a polynomial ring and compresses them into an RLWE ciphertext. This homomorphic trick is called the CDKS transformation.

That structure is useful, but structure can also give an attacker more to work with.

Security estimates for RLWE and Module-LWE are commonly obtained by translating the parameters into an "equivalent" unstructured LWE instance. A recent paper challenged the assumption that the additional ring structure is free. It showed that cyclotomic rotations can strengthen hybrid attacks, reporting a consistent 2–3 bit gap for ML-KEM and larger gaps for some sparse-secret RLWE parameters.

These results do not directly break YPIR, and the parameters are not identical. However, they demonstrate why an unstructured LWE estimate should not be treated as the final word for a ring-based construction.

The default estimates already ranged from 94 to 131 bits, depending on the cost model. Recent research introduced more uncertainty around the structured part used for compression. This wasn't appropriate by our standards.

Updated Security

For launch, we chose to double the lattice dimension from the default 2048 to 4096.

Horizontal bar chart comparing modeled quantum Core-SVP security. The original 2048-degree parameters are labeled 94.3 bits, the deployed 4096-degree parameters are labeled 238.5 bits, and a vertical line marks the 128-bit target. — Doubling the lattice dimension moves the conservative modeled estimate well past the 128-bit target.

Rerunning the same conservative baseline produced:

Quantum Core-SVP: 238.5 bits
Classical Core-SVP: 262.8 bits

These numbers should not be interpreted as a proof that breaking the scheme requires exactly or operations. They are modeled estimates against known attacks.

The important outcome is the margin. Even if future work improves attacks, exploits more of the ring structure, or changes how costs are modeled, the updated parameters leave substantially more room than the defaults.

Performance Impact and Production Deployment

The larger parameters increased upload per query from 544 KB to 1.53 MB, about 2.8 times as much. A vote padded to five notes sends five queries, for 7.65 MB total. Server compute per query rose from 150 ms to 182 ms, an increase of 32 ms or 21%.

Two comparison charts. Query upload increases from 544 KB at degree 2048 to 1.53 MB at degree 4096, labeled 2.8 times and approximately one additional megabyte. Server compute per query increases from 150 milliseconds to 182 milliseconds, labeled plus 21 percent and plus 32 milliseconds. — The larger parameters primarily increase client upload; measured server work rises by 32 milliseconds per query.

The new Ironwood pool gave us room to make that trade. The previous PIR design was sized for roughly 67 million Orchard nullifiers. At voting system launch, Ironwood had only about 31,000. Our redesigned tree reduced the private database to 48 MiB and replaced two sequential PIR queries with one. We chose to spend part of that performance dividend on security margin.

The resulting system remained practical. In a 60-second load test at eight concurrent requests, the 4096-degree configuration completed 689 proofs with zero errors: 11.48 proofs per second, 685 ms median latency, and 975 ms p99 latency.

We optimized for a security margin that would prioritize making the system private and secure for the end user. In future deployments, efforts will be made to improve PIR UX by making it faster, with no security compromise. You can read more about our performance improvements across the stack.

Closing Thoughts

No parameter choice makes lattice cryptography permanently secure. Security estimates evolve as attacks, implementations, and cost models improve.

There is a need to proactively and regularly update the security model behind your protocol. That is the standard our team at Zakura applies to all software we develop.

To test out the PIR protocol in production, download Vizor wallet and participate in the ongoing NU7 coinholder vote.

Credits

The voting system was developed by Valar Group.

Stardust Staking operates production PIR vote servers alongside Valar Group.