Audit

Summary

This audit confirms the parameter and noise-budget concerns that external reviewers (Yue et al.) raised in the VIA Security review thread.¹ In short: the shipped "realistic" parameters use the paper's draft gadget bases (not the authors' later erratum), the security level is a hard-coded unbacked 128 inconsistent with both the paper's claimed 110 and the reviewers' measured 72–88 bits, there is no correctness test under the paper's actual noise distributions and database dimensions, and the "realistic" Gaussian key distribution declared in the presets is inert: every test actually runs ternary keys. The follow-up parameterization work adds a scheme-level finding (A9): the paper's DMux/CMux noise bound omits the secret \(\mathbb E[s^2]\) factor, so its intended Gaussian-key parameters fail \(2^{-40}\): now confirmed empirically and analytically in-repo. A derived \(\ge120\)-bit SECURE_PARAMS preset now clears security with margin (estimator-gated), though its correctness margin is thin and ternary-dependent. On the credit side, two suspected issues are refuted: the VIA-C plaintext modulus is correctly \(p=16\), and the secret-dependent decode step is constant-time.

↑

VIA-C audit findings

Severity: critical breaks security/correctness · high serious flaw · medium hazard/coverage gap · low. Each states confidence. The crypto-core scope only; no HTTP/auth layer exists to review. Source links pinned to commit 9575286.

↑

VIA-B (batch)

The findings above cover VIA-C at commit 9575286. This section covers the VIA-B batch variant merged later (upstream PR #10), and its source links are pinned to commit 62fe493. Same epistemic tags as above (paper / code / inference / unverified). Method: a fresh research + adversarial-review pass over the new code against paper §4.5–4.7 (Fig 9) and Appendix C.

What VIA-B adds, and how it answers a batch

code VIA-B is a thin batch shell over the VIA-C stack plus one new primitive layer, homomorphic repacking (the paper's §4.6; "Layer 7" in the code's own module numbering), all behind the via-b cargo feature (repack also needs alloc: the recursion holds a runtime Vec). The server answers T queries by running the VIA-C prefix (Fig 9 steps 1–6) once per query at the record-ring degree n3, repacking the T results into a single ciphertext (the one new step), then running response compression once, so T records cost roughly one answer.

flowchart TD
  Q["client: batch_query yields T compressed VIA-C queries"]
  Q --> AC["server: answer_through_crot x T  (Fig 9 steps 1-6, at record degree n3)"]
  AC --> RP["server: Repack to n2  (step 7) - recursive MLWEs-to-RLWE, depth log2(T n1 / n2)"]
  RP --> RC["server: RespComp x 1  (step 8)"]
  RC --> RV["client: recover then deinterleave_batch yields T records"]
  CK["query-compression cascade keys (at q1)"] -. borrowed, mod-switched to q2, no new offline payload .-> RP
  classDef s fill:#eaf2fb,stroke:#2b5dd1;
  classDef c fill:#e8f7ee,stroke:#1f9d6b;
  class AC,RP,RC s;
  class Q,RV c;
            

code Repack (repack.rs, Layer 7) realizes the paper's MLWEs-to-RLWE conversion: extract each input to an MLWE, then recursively pair-convert (mlwes_to_mlwe, d=2) over \(\log_2(T\,n_1/n_2)\) levels into one RLWE, reusing the VIA-C conversion cascade's own key-switch step (conv_step) and borrowing the query-compression cascade keys, so repacking adds no new public parameters (paper §4.6 Remark). The client's deinterleave_batch is a pure strided permutation that inverts the repack interleave. Construction verdict: code faithful to Fig 9 / §4.6 for the single-repack case; the paper's vectorization path (\(T > n_1/n_3\)) is not implemented (see VB-6).

Findings (VIA-B)

VIA-B build & test

• code Ran the toy batch suite: via_b_toy_batch_roundtrip + via_b_toy_batch_covers_cells_and_slots — 2/2 pass (cargo test -p via-integration --features via-b; ViaBToyParams, ternary keys, 2×2 DB).
• code The 4×8-grid and paper-scale (T=8 / n3=64) batch e2e tests exist but are #[ignore]d (ternary keys, 2×2 DB).
• unverified The production T=256 / n3=2 path has only #[ignore]d repack "spike" tests on fresh-encrypted inputs: no full-pipeline correctness e2e (VB-1).

↑

Open questions & uncertainties

• Does the code actually achieve \(2^{-40}\) correctness? Now computed analytically (via-estimator::noise, with Yue's \(\mathbb E[s^2]\) residual correction): the paper's intended Gaussian-key design does not (the DMux/CMux bound is too aggressive for a large-variance secret; confirmed empirically: a measured DMux at n4096 (dmux_noise_empirical) shows the residual scales as \(\mathbb E[s^2]\) to ~1%, so the \(\sigma{=}32\) design carries \(1519\times\) the ternary noise), but via-rs's ternary SECURE_PARAMS clears \(2^{-40}\) on a thin, model-sensitive margin: an optional DMux \(\ell\!:\!2\to3\) bump widens it (see Fix). Still open: an empirical paper-noise/paper-dimension test (the analytic budget is no longer the gap).
• Three-way paper↔Python↔Rust drift: the Rust cites a Python reference (client.py, server.py, resp_comp.py) that is not in this checkout, so only paper↔Rust drift is checkable here.¹⁸
• Reviewer proof issue #3 (the \(S^2\) message in RLWE→RGSW) remains a paper-proof soundness question that the code sidesteps by running ternary keys; it would bite if Gaussian keys were wired (A4).

↑

Audit-of-audit

Every finding on this page (both the VIA-C findings and the VIA-B follow-up above) was independently re-checked by a separate adversarial pass whose remit was to disconfirm: four fresh reviewers re-read the primary sources — the paper, the VIA Security thread, and the code read at the same pinned commits (9575286 / 62fe493, via git show) — and tried to break each claim rather than confirm it. inference No finding was refuted. Every core claim held; the corrections were precision-level (a few line numbers, one page number, and one cross-finding \(\sigma\) mislabel), and they are folded into the findings themselves.

↑

Footnotes

1. VIA Security review note (HackMD, evolving) — Yue et al. (Turan, Yue, Keewoo), "Issue Report", May 7: "for the big and small ring according to the paper's parameters, we got 110 bits of security, but for the implementation we achieved approximately 88 and 72 bits of security." (They reproduce the paper's 110 from the paper's parameters, and measure 88/72 from the implementation's parameters, via the OpenFHE estimator.) ↩ ↩
2. protocol/presets.rs:150 (DMux base 55879), :153 (CMux base 81), :156 (ring-switch base 8); conv length \(\ell=18\) is carried in the ViaCRealisticParams type alias (no separate runtime base field). Bases identical to paper Table 6 (App. B, p.23) as printed. ↩
3. VIA Security review note (HackMD, evolving) — VIA authors, "Response from the authors", May 11, §2 Corrected Gadget Parameters: VIA-C bases conv(\(\ell{=}18,B{=}11\)), dmux(\(2,18073\)), cmux/rot(\(2,307\)), rs(\(8,4\)), giving \(\log_2 P_{\text{fail}}\approx-43.4\); "the gadget base values listed in Table 6 … were inadvertently left at draft values." ↩
4. protocol/params.rs (security_param: u32); at the pinned tree it was read only in the constructor, the Debug impl, and a display test, with no lattice/estimator code. An in-repo estimator (the via-estimator crate) has since been added; security_param is still a separate hard-coded constant rather than derived from it. ↩
5. Liu et al. (2025) (local: via-paper.pdf) §5.1, p.16: "110 bits of classical security … using the lattice estimator [46]." ↩
6. integration/client_server_e2e_paper.rs (NUM_ROWS=2,NUM_COLS=2), :69-71 (Distribution::Ternary), :146 (#[ignore]). Both ignored tests pass in release (verified, 35.7s). The σ's are the paper's VIA-C values (§5.1, p.16): \(\sigma_{1,S}{=}32,\ \sigma_{1,E}{=}1024\) on the big ring and \(\sigma{=}26\) on the small ring (the paper prints the small-ring σ under a typo'd \(\sigma_{1,E}\) subscript). ↩
7. No Appendix-C noise recursion in code (grep for \(P_{\text{fail}}\)/noise-recursion returns only doc-comment prose); criterion bench dirs are all toy_* (pipeline_toy default, pipeline_paper opt-in timing only). ↩
8. protocol/params.rs (arg order: …key_dist_2, key_bound_2, key_sigma_1, key_sigma_2, error_sigma, security_param); protocol/presets.rs supplies Gaussian,Gaussian,26,Some(1.0),Some(1.0),Some(1.0),128. ↩
9. grep: key_sigma_*/error_sigma/key_dist_*/key_bound_2 read only inside PIRParams::new asserts; client/client.rs,138-139 takes key_dist_1/2: Distribution as separate args; all test call sites pass Distribution::Ternary. ↩
10. VIA Security review note (HackMD, evolving) — Yue Chen, "Observations", May 31, §(2) CMux/DMux problem: TFHE assumes a binary key, so the term \(nq^2/(12B^{2\ell})\) "should now be updated to \(n\mathbb E[s_i^2]q^2/(12B^{2\ell})\)." The \(\sigma=4960\) Yue pairs with this is the plain-VIA small-ring key σ (the \(p=256\) instantiation); the implemented variant is VIA-C, whose keys are \(\sigma_{1,S}=32\) on the big ring (where DMux/CRot live) and \(\sigma=26\) on the small ring (where CMux lives): so for VIA-C the missing \(\mathbb E[s_i^2]\) factor would use \(\approx 1024\) / \(\approx 676\), not \(4960^2\). The structural point — non-binary key ⇒ a missing variance factor in Lemma C.1/C.2 — holds regardless. Cross-ref Liu et al. (2025) (local: via-paper.pdf) Lemma C.1/C.2, p.24-25. ↩
11. primitives/rlwe.rs (rescale (*v*q4+q3_half)/q3, then decode at q4) and :297-308 (decode uses q = modulus_value(scaled) = q4). Δ = q4/p = 4096/16 = 256, so Δ/2 = 128. ↩
12. Liu et al. (2025) (local: via-paper.pdf) Appendix C.2, p.25-27: the per-step variance recursion (θctrl→θdmux→θms→θfirst→θcmux→θcrot→θrep→θans) and condition \(\lVert E_{\text{final}}\rVert_\infty\le\lfloor(q_3-q_4)/p\rceil/2-1\) (p.27). With q3=8380417, q4=4096, p=16 this is \(\approx 2.6\times10^5\). ↩
13. VIA Security review note (HackMD, evolving) — Yue Chen, "Observations", May 31, §(1) Decryption error: the threshold "should only be correct when the infinite norm of the final error is \(\le (q_4/p)/2-1\), or just \(<\Delta/2\)," citing SpiralPIR Thm 2.11 and SimplePIR Thm C.1. (His worked bit-budget intuition uses the plain-VIA numbers — q4 15-bit, p=256 — but the formula critique applies to VIA-C's q4=4096/p=16 too.) Ratio \(2.6\times10^5/128\approx2000\). ↩
14. primitives/basis.rs — ViaQ1Rns = ConstRnsBasis<268369921, 536608769> (two distinct primes, product ≈ 2^57), vs paper App. B (p.22) "VIA \(q_1 = 268369921 \cdot 268369921\)"; :315 ViaCQ1Rns = <137438822401, 274810798081> matches paper VIA-C exactly. ConstRnsBasis asserts the two moduli are distinct and coprime, so it cannot represent a true prime-square. Verified at source. ↩
15. protocol/format.rs (the only two WireFormat impls are both for Vec<u64>), :167-172 (PrgCompressed::serialize is todo!(); its deserialize / regenerate_masks side is implemented). No WireFormat for CompressedQuery/CompressedAnswer; no byte-size accounting anywhere. ↩
16. primitives/modulus.rs (ViaP = PowerOfTwoModulus<8> = 256, the VIA value), :467 (ViaCP = PowerOfTwoModulus<4> = 16); protocol/presets.rs (p=16); grep over the pinned tree finds no MODULUS_PC: the MODULUS_PC=256 bug the authors discussed (May 11) was in their own C++ owniai/VIA, not in this port (nor in the clean via-spec Python lineage it descends from). ↩
17. primitives/rlwe.rs — secret centring via to_centered_coeffs_ct (the constant-time companion to the non-CT to_centered_i64 at primitives/modulus.rs, which is confined to sampling/lift/public-value paths). ↩
18. protocol/presets.rs and many provenance comments (e.g. client.py:117, server.py:196, server/resp_comp.rs) reference a Python reference; find … *.py over the tree returns only a CI script — the Python source is not in this checkout. ↩