Implementation details

Summary

VIA is a lattice (RLWE/MLWE) single-server PIR family whose headline trick is to eliminate the offline/preprocessing phase while keeping online communication at \(\tilde O(\log N)\). It does this by replacing the usual "coefficient-expansion" query-expansion step with a DMux tree (logarithmic-depth homomorphic de-multiplexers) and, in the VIA-C variant, a new LWE→RLWE conversion that compresses the whole query into a handful of \(\mathbb Z_{q_1}\) elements.¹

The via-rs repository is a clean, no_std, layered Rust port of a Python reference.² Its primitive stack (algebra → sampling → encryption → switching → gates → conversion) maps faithfully to the paper's §2–§5, and a real Query→Answer→Recover round-trip passes at both toy and (release-only) paper-scale parameters: verified here, 693/693 tests green.³ VIA-C and VIA-B are implemented (VIA-B behind the via-b cargo feature, merged after the original audit); plain VIA is not.⁴

This page describes the codebase as built: the construction it implements, its crate/layer architecture, the primitive→paper map, and the build/test status. The correctness and security audit — severity-ranked findings for VIA-C and VIA-B, the paper-vs-code parameter and noise-budget divergences, and the open questions — now lives on its own page: Audit ↗. In brief it confirms the concerns external reviewers (Yue et al.) raised in the VIA Security thread, and refutes two suspected ones.

↑

The scheme

Sources: paper Figures 4 (VIA), 8 (VIA-C), 9 (VIA-B).¹ Implementation scope confirmed by grep: the pipeline is monomorphised against VIA-C presets and no Figure-4 / repacking code paths exist at the audited commit 9575286 — VIA-B repacking landed later (PR #10).⁴

Database layout & query decomposition

paper The database \(X\) is encoded as an \(I\times J\) grid of \(R_{n_1,p}\) polynomials, each cell packing \(d = n_1/n_2\) records.⁵ code The client splits an index as \(\texttt{idx} = \gamma\,(IJ) + \alpha J + \beta\) into \((\alpha,\beta,\gamma)\) = (row, column, slot); \(\alpha\) drives DMux (MSB-first), \(\beta\) drives CMux (LSB-first), \(\gamma\) drives CRot.⁶

↑

Architecture

Crate & layer dependency graph

graph TD
  subgraph PRIM["via-primitives (no_std)"]
    L0["Layer 0 algebra: zq, rns CRT, ring NTT"]
    L1["Layer 1 sampling: SHAKE-256 PRG, uniform, ternary, Gaussian"]
    L2["Layer 2 encryption: SecretKey, RLWE, RLev, RGSW, MLWE, gadget, keyswitch"]
    L3["Layer 3 switching: mod-switch, ring-switch, rekey"]
    L4["Layer 4 gates: CMux, DMux, trees, CRot, RLWE-to-RGSW"]
    L5["Layer 5 conversion: LWE-to-RLWE cascade, MLWE embed, Extr_d"]
    L0 --> L1 --> L2 --> L3 --> L4 --> L5
    L2 --> L4
  end
  subgraph PROTO["via-protocol"]
    P1["PIRParams and presets TOY / REALISTIC"]
    P2["wire: Query, Answer, keys (serialization partial)"]
  end
  CL["via-client: setup, query idx, recover"]
  SV["via-server: setup_db, query_decomp, first_dim, answer, resp_comp"]
  INT["via-integration: e2e tests, KATs, benches"]
  PRIM --> PROTO
  PROTO --> CL
  PROTO --> SV
  PRIM --> CL
  PRIM --> SV
  CL --> INT
  SV --> INT
  

VIA-C end-to-end sequence

sequenceDiagram
  participant C as Client
  participant S as Server DB I x J
  Note over C: setup yields keys s, S1, S2 and public params pp_qck, pp_rck
  C->>C: split idx into alpha row, beta col, gamma slot, then encrypt bits as LWE at q1
  C->>S: query = L log N LWE ciphertexts
  Note over S: Answer pipeline, Figure 8
  S->>S: 1. QueryDecomp LWE to RLWE to RGSW yields C_ctrl, C_sel, C_rot
  S->>S: 2. DMux tree on C_ctrl yields one-hot rows at q1
  S->>S: 3. ModSwitch q1 to q2
  S->>S: 4. First dimension sum over i of c_i times db at i,j at q2
  S->>S: 5. CMux tree on C_sel selects column
  S->>S: 6. CRot on C_rot rotates to slot gamma
  S->>S: 7. RespComp ModSwitch q2 to q3, RingSwitch n1 to n2, scale to q4
  S->>C: answer = mask at q3, body at q4
  C->>C: Recover m = round of p times B' minus round of q4 A' S2 / q3, all over q4, mod p
  

Answer noise/modulus journey

flowchart TD
  A["LWE at q1 (compressed query bits)"]
  B["RGSW gate keys at q1: C_ctrl, C_sel, C_rot"]
  C["one-hot rows at q1 (noise + theta_DMux times log I)"]
  D["rows at q2"]
  E["column sums at q2 (noise times I n1 p^2 / 4, dominant term)"]
  F["selected column at q2 (noise + theta_CMux times log J)"]
  G["rotated to slot at q2"]
  H["answer, small ring n2 at q4 (decodes iff theta_ans under Delta/2 = 128)"]
  A -->|"LWE-to-RLWE-to-RGSW decompress"| B
  B -->|"DMux tree x log I"| C
  C -->|"ModSwitch q1 to q2"| D
  D -->|"FirstDim sum of c times db, x I"| E
  E -->|"CMux tree x log J"| F
  F -->|"CRot"| G
  G -->|"RespComp: q2 to q3, RingSwitch n1 to n2, q3 to q4"| H
  style E fill:#fdecea,stroke:#c0392b
  style H fill:#eafaf1,stroke:#1f9d6b
  

Modulus chain \(q_1{>}q_2{>}q_3{>}q_4{>}p\); step labels follow Appendix C's variance recursion.⁸ The first-dimension \(\times I\,n_1\,p^2/4\) term (red) and the per-level \(\log I,\log J\) additions are where the budget is spent; the answer (green) decodes only if the accumulated variance stays under \(\Delta/2\).

Primitive → paper map

↑

Build & test status

code Built and run on Rust stable 1.96.0. cargo test --workspace: 693 passed, 0 failed, 4 ignored.⁹

• code Toy-parameter Query→Answer→Recover round-trips pass and assert recovered == record[i] across all indices (e2e_toy.rs, client_server_e2e.rs).³
• code Cross-language byte-parity KATs (layer3/4/5/6_kats) pin primitive outputs against Python-generated constants — all pass.¹⁰
• code The ignored tests are the heavy paper-scale (n2048 RNS) cases; cargo test --release -p via-integration --test client_server_e2e_paper -- --ignored → 2 passed in 35.7s (client_server_e2e_paper_scale_index_15 recovers the right record at n1=2048/n2=512, q1≈2^75).¹¹
• code A cargo-fuzz harness covers 9 areas (zq, rns, sampling, switching, encryption, gates, conversion, ring, protocol).¹²
• inference The green paper-scale round-trip confirms the pipeline computes correctly at paper dimensions, but it runs ternary keys on a 2×2 DB, so it does not witness the \(2^{-40}\) noise-budget claim at paper σ/dimensions (A3).
• inference The crate graph above is the layout at the audited commit 9575286 (five workspace crates). A sixth crate, via-estimator (a calibrated core-SVP lattice estimate plus the Appendix-C noise/\(P_\text{fail}\) calculator), was added afterwards and is now the in-repo source of trust for the security-bit and \(2^{-40}\) correctness numbers used on the Parameters and Audit pages (cargo run -p via-estimator).¹³

↑

Footnotes

1. Liu et al. (2025) (local: via-paper.pdf) §1 Introduction & §3.1, p.1,8 — "VIA substitutes coefficient expansion techniques with DMux … introducing only logarithmic noise variance"; Figures 4/8/9 give the three constructions. ↩ ↩
2. 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. ↩
3. server/e2e_toy.rs and integration/client_server_e2e.rs — full-index assert_eq!(recover(query(i)), record[i]) at toy params. ↩ ↩
4. grep over crates/{client,server,protocol}: pipeline monomorphised against ViaCPublicParams; no Figure-4 (ring-switch-before-CMux) path, no repack/via_b/MLWEs→RLWE. "VIA-B (Layer 7) will wrap it" — server/answer.rs. Accurate as of commit 9575286; VIA-B repacking (repack/via_b) was subsequently merged in PR #10 and postdates this audit. ↩ ↩
5. Liu et al. (2025) (local: via-paper.pdf) §3.1 (Database structure), p.8 — \(db[i,j]=\iota_{n_2\to n_1}((X_{kIJ+iJ+j})_k)\), grid \(I\times J\). ↩
6. client/decompose.rs — index = γ·(I·J)+α·J+β; DMux bits MSB-first, CMux/CRot bits LSB-first. ↩
7. primitives/gadget.rs — "signed-balanced digits in \((-B/2,B/2]\) … the '≈' hides a reconstruction error bounded by \(\mathrm{round}(q/B^L)/2\)." ↩
8. 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\). ↩
9. Executed in this environment after installing rustup/stable (1.96.0): cargo test --workspace → 693 passed / 0 failed / 4 ignored across the workspace crates' unit, integration, and doctest targets. ↩
10. crates/via-primitives/tests/{layer3,layer4,layer5}_kats.rs and crates/via-integration/tests/layer6_kats.rs — byte-equality vs embedded Python-generated constants. ↩
11. 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). ↩
12. via-rs/fuzz/fuzz_targets/{zq,rns,sampling,switching,encryption,gates,conversion,ring,protocol} and fuzz/Cargo.toml target list. ↩
13. estimator/main.rs — the via-estimator crate postdates the audited commit 9575286 (so it is absent from the crate graph above, which is pinned to that commit); per the workspace source-of-trust rule it is the authoritative in-repo derivation for every security-bit and \(2^{-40}\)-correctness figure. ↩