VIA_2025_notes.md

VIA: Communication-Efficient Single-Server Private Information Retrieval — Engineering Notes

1. Lineage 2. Core Idea 3. Variants 4. Novel Primitives / Abstractions 5. Cryptographic Foundation 6. Ring Architecture / Modulus Chain 7. Key Data Structures 8. Database Encoding 9. Database Dimensions (Table 4) 10. Protocol Phases 11. Correctness Analysis

12. Gadget Parameters 13. Complexity 14. Performance Benchmarks 15. Comparison with Prior Work 16. Portable Optimizations 17. Implementation Notes 18. Deployment Considerations 19. Key Tradeoffs & Limitations 20. Related Papers in Collection 21. Open Problems 22. Uncertainties

Field	Value
Paper	VIA: Communication-Efficient Single-Server Private Information Retrieval (2025)
Archetype	Construction (multi-variant: VIA, VIA-C, VIA-B)
PIR Category	Group 1b — Stateless Client, Stateless Server; VIA-C and VIA-B variants are Group 1a (upload per-client eval keys)
Security model	Semi-honest single-server
Additional assumptions	Circular security / KDM (key-dependent message) for the underlying RLWE/MLWE encryption
Correctness model	Probabilistic (failure prob <= 2^{-40})
Rounds (online)	1 (non-interactive)
Record-size regime	Small (log p bits per record; 8 bits for VIA, 4 bits for VIA-C/VIA-B) / Variable via blinded extraction

Lineage ⤴

Field	Value
Builds on	Respire [Group 1b] (architecture: I x J matrix, ring switching, CMux selection, sample extraction), Spiral [Group 1a] (Regev+GSW composition, external products, ciphertext translation), HERMES [29] (MLWE packing concept)
What changed	Replaces coefficient expansion (used by Spiral, Respire, OnionPIR for generating encrypted unit vectors) with a DMux-CMux tree structure, eliminating offline communication entirely. VIA-C adds a novel LWE-to-RLWE conversion with O(n log n) noise variance (vs. O(n^3) in prior work [28]) for query compression.
Superseded by	N/A
Concurrent work	N/A

Core Idea ⤴

VIA addresses the high online communication cost of lattice-based PIR schemes that eliminate offline communication. Prior hintless schemes (YPIR, HintlessPIR) achieve O_lambda(sqrt(N)) online communication; VIA achieves O_lambda(1) -- specifically O(log N) online communication -- by replacing coefficient expansion with a DMux-CMux binary tree that generates the encrypted one-hot vector from only log I RGSW ciphertexts of control bits. ¹ The DMux-CMux architecture requires only logarithmically many ciphertexts to select among I rows and J columns, yielding the name "VIA" from the symmetric triangular layout of the DMux and CMux trees. ² VIA-C further compresses queries to O(log N) elements in Z_q via a novel LWE-to-RLWE conversion that introduces only O(n log n) noise variance, achieving 87.6x smaller queries than Respire for a 32 GB database. ³

Variants ⤴

Variant	Key Difference	Offline Comm	Online Query	Online Response	Best For
VIA	Base: DMux-CMux replaces coefficient expansion; fresh RGSW ciphertexts in query; p = 256	None	473--675 KB	15.5 KB	Hintless PIR; general use without offline phase
VIA-C	LWE-to-RLWE query compression + RLWE-to-RGSW on server + blinded extraction; p = 16	14.8 MB (eval keys)	0.57--0.66 KB	1.44 KB	Minimum communication; small-record databases
VIA-B	Batch extension of VIA-C; homomorphic repacking packs T answers into one RLWE ciphertext	14.8 MB (eval keys)	17--145 KB (batch T)	1.48--1.81 KB	Batch queries on tiny-record (1-byte) databases

Novel Primitives / Abstractions ⤴

DMux (Homomorphic Demultiplexer)

Field	Detail
Name	1-to-2^m DMux (Algorithm 2)
Type	Cryptographic primitive (homomorphic circuit)
Interface / Operations	Input: RGSW ciphertexts C_ctrl of m control bits b in {0,1}^m, RLWE ciphertext c = RLWE_S(M). Output: 2^m RLWE ciphertexts where the b-th position encrypts M and all others encrypt 0.
Security definition	Inherited from RLWE/RGSW security
Purpose	Generates encrypted one-hot vector from log I control bits, replacing coefficient expansion. Requires only log I RGSW ciphertexts instead of I RLWE ciphertexts.
Built from	External products (RGSW x RLWE -> RLWE)
Standalone complexity	2^m - 1 external products for m = log I control bits
Relationship to prior primitives	Dual of CMux: DMux routes one input to one of 2^m outputs; CMux selects one of 2^m inputs to one output. Together they form the "V" architecture.

CRot (Controlled Rotation)

Field	Detail
Name	CRot (Controlled Rotation)
Type	Cryptographic primitive (homomorphic circuit)
Interface / Operations	Input: RGSW ciphertexts C_rot of rotation bits gamma_i in {0,1}, RLWE ciphertext c = RLWE_S(M). Output: RLWE_S(M * X^{-sum_i gamma_i * 2^i}).
Purpose	Homomorphic conditional rotation of the RLWE ciphertext to shift the target coefficient to position 0 for sample extraction. Used in VIA-C to avoid direct transmission of the rotation ciphertext.
Built from	External products (log(n_1/n_2) levels)

LWE-to-RLWE Conversion (Novel)

Field	Detail
Name	LWE-to-RLWE conversion via iterative MLWE-to-MLWE steps
Type	Cryptographic primitive (ciphertext format conversion)
Interface / Operations	Input: rank-n LWE ciphertext c = LWE_s(mu) in Z_q. Output: (1, n)-MLWE ciphertext (equivalent to RLWE) encrypting mu. Denoted LWEtoRLWE(c, c_hat_toRLWE).
Purpose	Converts LWE-format queries (compact) into RLWE format (processable by server). Enables VIA-C's O(log N) query compression.
Built from	MLWE-to-MLWE conversion (iterative doubling via MLWE embedding + key switching), RLWE-to-MLWE extraction
Standalone complexity	2 log n key-switching keys, 2 log n key-switching operations
Relationship to prior primitives	Functionally equivalent to HERMES [29] in the single-ciphertext case, but: (1) focuses on single-ciphertext settings (no multi-ciphertext overhead), (2) uses log n MLWE midpoints (HERMES uses few), (3) achieves O(n log n) noise variance vs. O(n^3) in [28].

Cryptographic Foundation ⤴

Layer	Detail
Hardness assumption	RLWE (base VIA) and MLWE (VIA-C, VIA-B). The (m, n, q, chi_S, chi_E)-MLWE problem reduces to the LWE assumption when n = 1 and to the RLWE assumption when m = 1. Security reduced to RLWE over R_{n_1,q_1} via the reduction: (m,n)-MLWE is at least as hard as (mn, q, chi_S, chi_E)-RLWE. 4
Encryption/encoding schemes	(1) RLWE encoding: c = (A, AS + E + DeltaM) for polynomial ring R_{n,q}, with Delta = ceil(q/p). (2) RGSW encoding: C = (RLev_S(-SM), RLev_S(M)) -- pair of RLev ciphertexts. (3) MLWE encoding (VIA-C): (A, <A, S> + E + M) in R_{n,q}^{m+1}.
Ring / Field	Multi-ring: R_{n_1,q_1} (large ring, n_1 = 2048), R_{n_2,q_2} (small ring, n_2 = 512), plus auxiliary moduli q_3, q_4. See Ring Architecture table.
Key structure	Two independent RLWE secret keys: S_1 from chi_{S,1} over R_{n_1,q_1} (control/rotation ciphertexts), S_2 from chi_{S,2} over R_{n_2,q_2} (selection bits, ring-switching target). Ring-switching key rsk maps S_1 to S_2. In VIA, S_1 is uniform on [-2, 2]; in VIA-C/VIA-B, S_1 is discrete Gaussian with sigma_{1,S} = 32. 5
Correctness condition	Probabilistic:

Ring Architecture / Modulus Chain ⤴

VIA Parameters

Ring	Dimension	Modulus (bits)	Value	Role / Phase
R_{n_1,q_1}	n_1 = 2048	57-bit	q_1 = q_{1,1} * q_{1,2} ~ 2^57	Query encryption (control bits, rotation ct), DMux, first-dimension folding
R_{n_2,q_2}	n_2 = 512	35-bit	q_2 ~ 2^35	Selection bits (RGSW), CMux, ring-switching target
R_{n_2,q_3}	n_2 = 512	31-bit	q_3 ~ 2^31	Response compression (modulus-switched output)
Z_{q_4}	--	15-bit	q_4 = 2^15	Final extraction modulus
R_{n_1,p} / R_{n_2,p}	n_1 / n_2	--	p = 256	Plaintext space (VIA)

VIA-C / VIA-B Parameters

Ring	Dimension	Modulus (bits)	Value	Role / Phase
R_{n_1,q_1}	n_1 = 2048	75-bit	q_1 = q_{1,1} * q_{1,2} ~ 2^75	LWE-to-RLWE conversion, RLWE-to-RGSW, query decompression
R_{n_2,q_2}	n_2 = 512	34-bit	q_2 ~ 2^34	Selection bits, CMux, ring-switching target
R_{n_2,q_3}	n_2 = 512	23-bit	q_3 ~ 2^23	Response compression
Z_{q_4}	--	12-bit	q_4 = 2^12	Final extraction modulus
R_{n_1,p} / R_{n_2,p}	n_1 / n_2	--	p = 16	Plaintext space (VIA-C/VIA-B)

Security level: 110 bits of classical security, estimated using the Lattice Estimator [46]. RLWE and MLWE parameters are aligned so that MLWE security reduces to RLWE over R_{n_1,q_1}. ⁶

Key Data Structures ⤴

• Database: X in R_{n_2,p}^N, structured as an I x J matrix over R_{n_1,p} where Nn_2 = IJ*n_1. Each entry db[i,j] = iota^{n_2->n_1}((db_{kIJ+iJ+j}){k in [n_1/n_2]}) packs n_1/n_2 = 4 elements of R{n_2,p} into one element of R_{n_1,p} via subring embedding. ⁷
• Query (VIA): Four components: c_rot = RLWE_{S_1}(X^{-gamma}) (rotation), C_ctrl = RGSW_{S_1}(alpha) (log I control bits), C_sel = RGSW_{S_2}(rev(beta)) (log J selection bits), rsk (ring-switching key from S_1 to S_2).
• Query (VIA-C): l * log N LWE ciphertexts in Z_{q_1} (each encrypting one bit of index scaled by q_1/B^i), where l is gadget length. Total query size: l * log(IJn_1/n_2) elements of Z_{q_1}. ⁸
• Public parameters (VIA-C): pp_qck = (c_hat_toRLWE, c_hat_toRGSW) for LWE-to-RLWE and RLWE-to-RGSW conversion; pp_rck for response compression. Uploaded offline. Total: ~14.8 MB. ⁹

Database Encoding ⤴

• Representation: I x J matrix over R_{n_1,p}. Each matrix entry packs d = n_1/n_2 = 4 records from R_{n_2,p}.
• Record addressing: Index idx decomposes as idx = gamma * IJ + alpha * J + beta, where (alpha, beta, gamma) in [I] x [J] x [n_1/n_2]. Binary representations of alpha and beta serve as DMux control bits and CMux selection bits respectively.
• Preprocessing required: NTT conversion of the database over R_{n_1,p}. For VIA, only an NTT per n_1 = 2048 elements is needed (no polynomial interpolation). VIA and VIA-C share the same database encoding. ¹⁰
• Record size equation: Each record is log_2(p) bits. VIA: p = 256 so 8 bits/record. VIA-C/VIA-B: p = 16 so 4 bits/record. Variable-size records supported via blinded extraction (multiple sample extractions). ¹¹

Database Dimensions (Table 4) ⤴

Database Size	VIA (I, J)	VIA-C (I, J)
1 GB	(2^6, 2^13)	(2^8, 2^12)
4 GB	(2^8, 2^13)	(2^9, 2^13)
32 GB	(2^9, 2^15)	(2^11, 2^14)

Protocol Phases ⤴

VIA Protocol (Figure 4, p.10)

Phase	Actor	Operation	Communication	When / Frequency
DB Encoding	Server	Compute db[i,j] via subring embedding + NTT	--	Once per DB update
Query	Client	Encrypt index as (c_rot, C_ctrl, C_sel, rsk); compress via PRG seed	473--675 KB up	Per query
Answer Step 1: DMux	Server	DMux(C_ctrl, c_rot) -> I one-hot RLWE ciphertexts	--	Per query
Answer Step 2: ModSwitch	Server	ModSwitch_{q_2,q_2}(c_i^{(0)}) for each i in [I]	--	Per query
Answer Step 3: First dim	Server	c_j^{(2)} = sum_{i in [I]} c_i^{(1)} * db[i,j] for each j in [J]	--	Per query
Answer Step 4: Ring switch	Server	RingSwitch(rsk, c_j^{(2)}) from R_{n_1} to R_{n_2}	--	Per query
Answer Step 5: CMux	Server	CMux(C_sel, (c_j^{(3)})_{j in J}) -> single RLWE ciphertext	--	Per query
Answer Step 6: ModSwitch	Server	ModSwitch_{q_3,q_4}(ans') -> final answer	15.5 KB down	Per query
Decode	Client	Dec_{st}(ans) -> record d	--	Per query

VIA-C Protocol (Figure 8, p.14)

Phase	Actor	Operation	Communication	When / Frequency
Setup (offline)	Client	Generate pp_qck (LWE-to-RLWE + RLWE-to-RGSW keys) and pp_rck (response compression key)	14.8 MB up	Once per key
DB Encoding	Server	Same as VIA	--	Once per DB update
Query	Client	QueryComp(s, b_ctrl, b_sel, b_rot) -> l*log N LWE ciphertexts in Z_{q_1}	0.57--0.66 KB up	Per query
Answer Step 1: QueryDecomp	Server	LWEtoRLWE + RLWEtoRGSW -> C_ctrl, C_sel, C_rot	--	Per query
Answer Steps 2-6: DMux through CMux	Server	Same pipeline as VIA (DMux -> ModSwitch -> FirstDim -> CMux)	--	Per query
Answer Step 7: CRot	Server	CRot(C_rot, c^{(3)}) -> homomorphic rotation	--	Per query
Answer Step 8: RespComp	Server	ModSwitch + RingSwitch + truncation	1.44 KB down	Per query
Decode	Client	RespCompRecover(S_2, ans) -> record d	--	Per query

VIA-B Protocol (Figure 9, p.15)

Phase	Actor	Operation	Communication	When / Frequency
Setup (offline)	Client	Same as VIA-C plus repacking keys	14.8 MB up	Once per key
Query	Client	QueryComp for each of T batch indices	17--145 KB up (batch)	Per batch
Answer Steps 1-6	Server	VIA-C answer pipeline for each of T queries independently	--	Per batch
Answer Step 7: Repack	Server	Repack_{n_2}({c^{(4),t}}_{t in [T]}, pp_qck) -> single RLWE ciphertext	--	Per batch
Answer Step 8: RespComp	Server	Response compression	1.48--1.81 KB down	Per batch
Decode	Client	Recover T records	--	Per batch

Correctness Analysis ⤴

Option A: FHE Noise Analysis

VIA-B's correctness analysis (Appendix C.2, which subsumes VIA and VIA-C) tracks variance-based noise through 8 phases.

Phase	Noise parameter	Growth type	Notes
1. Query decompression	theta_ctrl, theta_sel, theta_rot	Additive (from LWE-to-RLWE + RLWE-to-RGSW)	theta_ctrl depends on l_conv, B_conv, theta_{1,E}, theta_{toRLWE}, theta_{toRGSW}
2. DMux	theta_dmux = theta_ctrl + theta_DMux * log I	Logarithmic in I	theta_DMux depends on gadget params (l_{ctrl}, B_{ctrl}) and theta_ctrl
3. Modulus switching	theta_ms = theta_dmux * q_2^2 / q_1^2 + (1 + n_1 * theta_{1,S})/12	Multiplicative (q_2/q_1 ratio) + additive	Reduces noise by (q_2/q_1)^2 factor
4. First dimension	theta_first = I * n_1 * theta_ms * p^2/4	Linear in I, quadratic in p	Dominant cost: plaintext-ciphertext multiply across I rows
5. CMux	theta_cmux = theta_first + theta_CMux * log J	Logarithmic in J	theta_CMux depends on gadget params (l_{sel}, B_{sel}) and theta_sel
6. CRot	theta_crot = theta_cmux + log(n_1/n_3) * theta_CRot	Logarithmic in n_1/n_3	theta_CRot depends on gadget params (l_{rot}, B_{rot}) and theta_rot
7. Repacking	theta_rep = theta_crot + 2 * theta_ks * log n_2	Logarithmic in n_2	MLWEs-to-RLWE conversion adds 2theta_kslog n_2
8. Response compression	theta_ans (final)	Additive	Modulus switch + ring switch + key switch

• Correctness condition: ||E_final||_inf <= floor((q_3 - q_4)/p)/2 - 1. Pr[correct] >= erfc((floor((q_3 - q_4)/p)/2 - 1) / sqrt(2 * theta_ans)).
• Independence heuristic used? Yes -- noise terms from different operations are assumed independent (variance-based tracking).
• Dominant noise source: First-dimension folding (theta_first = I * n_1 * theta_ms * p^2/4), which is linear in I and quadratic in the plaintext modulus p. This explains why VIA-C uses p = 16 (vs. VIA's p = 256) -- smaller p drastically reduces first-dimension noise, enabling the larger q_1 needed for query compression. ¹²

Gadget Parameters ⤴

VIA (Table 5)

Component	Gadget Length (l)	Gadget Base (B)
DMux	(2, 2)	(370758, 370758)
CMux	(4, 3)	(24, 24)
Ring-Switching Key	4	24

VIA-C / VIA-B (Table 6)

Component	Gadget Length (l)	Gadget Base (B)
DMux	(2, 2)	(55879, 55879)
CMux	(2, 2)	(81, 81)
Conversion Key	18	18
Ring-Switching Key	8	8

Complexity ⤴

Core metrics

Metric	Asymptotic	Concrete (32 GB)	Phase
VIA
Query size	O_lambda(log N)	674.75 KB	Online
Response size	O_lambda(1)	15.5 KB	Online
Server computation	O_lambda(N)	10.286 s	Online
Throughput	--	3.11 GB/s	Online
VIA-C
Query size	O_lambda(log N)	0.659 KB	Online
Response size	O_lambda(1)	1.439 KB	Online
Server computation	O_lambda(N)	20.307 s	Online
Throughput	--	1.58 GB/s	Online
Offline communication	O_lambda(1)	14.8 MB up	Offline (once)
Offline computation	O_lambda(N)	67.539 s	Offline (once)
VIA-B (T=256, 1 GB, 1-byte records)
Query size	--	145.31 KB	Online
Response size	--	1.81 KB	Online
Offline communication	--	14.8 MB up	Offline (once)

FHE-specific metrics

Metric	VIA	VIA-C
Expansion factor (F)	q_3/p = 2^31/256 ~ 2^23 (pre-extraction); effective ~ 15.5 KB / (log_2(256)/8) = 15.5 KB per byte	q_4/p = 2^12/16 = 256; effective ~ 1.44 KB per 0.5 byte
Multiplicative depth	1 (first-dim is plaintext-ciphertext multiply, DMux/CMux are external products)	Same
Security level	110-bit classical	110-bit classical

Performance Benchmarks ⤴

Hardware: AMD 9950X CPU, 128 GB RAM, Ubuntu 22.04.5. Compiler: clang 19.1.7 with AVX-512DQ and AVX-512IFMA52 instruction sets. Single-threaded execution. All measurements averaged over at least 5 trials with standard deviation at most 5%. ¹³

Table 1: VIA and VIA-C vs. prior work (single query, record size = log_2(p) bits)

Metric	HintlessPIR	YPIR	VIA	SimplePIR	Respire	VIA-C
1 GB database
Offline Comm	--	--	--	128 MB	3.9 MB	14.8 MB
Offline Comp	--	12.18 s	1.06 s	94.1 s	33.75 s	2.09 s
Query Size	453 KB	846 KB	473.1 KB	128 KB	7.66 KB	0.568 KB
Response Size	3080 KB	12 KB	15.5 KB	128 KB	2 KB	1.439 KB
Online Comp	2.193 s	0.465 s	0.442 s	0.064 s	1.871 s	0.83 s
Throughput	466.9 MB/s	2.15 GB/s	2.26 GB/s	15.63 GB/s	547.3 MB/s	1.2 GB/s
32 GB database
Offline Comm	--	--	--	724 MB	3.9 MB	14.8 MB
Offline Comp	9252.3 s	315.231 s	33.34 s	3376.47 s	1101.33 s	67.539 s
Query Size	1064 KB	2560 KB	674.75 KB	724 KB	57.77 KB	0.659 KB
Response Size	17514 KB	12 KB	15.5 KB	724 KB	2 KB	1.439 KB
Online Comp	17.391 s	7.086 s	10.286 s	2.674 s	45.851 s	20.307 s
Throughput	1.84 GB/s	4.52 GB/s	3.11 GB/s	11.97 GB/s	714.66 MB/s	1.58 GB/s

Table 2: VIA-B vs. Respire-B (batch, 1-byte records)

DB	Metric	Respire (T=32)	VIA-B (T=32)	Respire (T=256)	VIA-B (T=256)
256 MB	Offline Comm	4.6 MB	14.8 MB	4.6 MB	14.8 MB
	Query Size	67 KB	17 KB	326 KB	135.9 KB
	Response Size	31.8 KB	1.48 KB	234 KB	1.81 KB
1 GB	Offline Comm	4.6 MB	14.8 MB	4.6 MB	14.8 MB
	Query Size	113 KB	18.16 KB	513 KB	145.31 KB
	Response Size	31.8 KB	1.48 KB	230 KB	1.81 KB

Comparison with Prior Work ⤴

Without offline communication (32 GB)

Metric	VIA	YPIR	HintlessPIR
Query size	674.75 KB	2560 KB	1064 KB
Response size	15.5 KB	12 KB	17514 KB
Total online comm	690.25 KB	2572 KB	18578 KB
Throughput	3.11 GB/s	4.52 GB/s	1.84 GB/s
Offline comp	33.34 s	315.231 s	--
Comm reduction vs. YPIR	3.7x	--	--

With offline communication (32 GB)

Metric	VIA-C	Respire	SimplePIR
Query size	0.659 KB	57.77 KB	724 KB
Response size	1.439 KB	2 KB	724 KB
Total online comm	2.098 KB	59.77 KB	1448 KB
Throughput	1.58 GB/s	714.66 MB/s	11.97 GB/s
Offline comm	14.8 MB	3.9 MB	724 MB
Offline comp	67.539 s	1101.33 s	3376.47 s
Comm reduction vs. Respire	28.5x	--	--
Comm reduction vs. SimplePIR	690x	--	--

Key takeaway: VIA is the preferred hintless scheme when minimizing total online communication is paramount and throughput requirements are in the low-GB/s range. It dominates HintlessPIR in all metrics and reduces YPIR's communication by 3.7x while maintaining comparable throughput (3.11 vs. 4.52 GB/s). VIA-C is preferred when offline communication is acceptable and ultra-low online communication is needed -- it achieves 2.1 KB total online for 32 GB, making it suitable for bandwidth-constrained clients. VIA-B extends VIA-C to batch queries on tiny-record databases, achieving 127x response reduction over Respire-B.

Portable Optimizations ⤴

• DMux-CMux architecture: Applicable to any RLWE-based PIR scheme that currently uses coefficient expansion to generate encrypted one-hot vectors. Reduces the required number of query ciphertexts from O(I) to O(log I), eliminating the need for automorphism-based expansion and client-specific public parameters. The key insight is that logarithmically many RGSW control bits suffice to propagate a single RLWE ciphertext to the target position via a binary tree of external products. ¹⁴
• LWE-to-RLWE conversion via iterative MLWE-to-MLWE: Generalizable to any scheme needing LWE-to-RLWE format conversion. Achieves O(n log n) noise variance vs. O(n^3) in [28], with compact (logarithmic) public parameters. Can replace the LWE-to-RLWE step in YPIR, Respire, HintlessPIR, InsPIRe. ¹⁵
• Modulus switching before first-dimension folding: Reduces computational cost of the plaintext-ciphertext multiply phase by operating under a smaller modulus. Applicable to any scheme with a first-dimension folding step (Spiral, Respire, WhisPIR). ¹⁶
• Homomorphic repacking (MLWEs-to-RLWE): Generalizes LWE-to-RLWE to pack multiple MLWE ciphertexts into one RLWE ciphertext with logarithmic noise variance. Useful for batch PIR constructions beyond VIA-B. ¹⁷
• MLWE as a portable concept: MLWE bridges LWE (m=1) and RLWE (n=1), parameterized by module rank m. The conversion chain LWE -> (n/2, 2)-MLWE -> (n/4, 4)-MLWE -> ... -> (1, n)-MLWE = RLWE provides a smooth interpolation with controllable noise at each step.

Implementation Notes ⤴

• Language / Library: C++, approximately 4,000 lines of code. Custom implementation (no SEAL/OpenFHE dependency). ¹⁸
• Polynomial arithmetic: NTT-based. CRT decomposition used for multi-prime moduli (q_1 = q_{1,1} * q_{1,2}).
• SIMD / vectorization: AVX-512DQ and AVX-512IFMA52 instruction sets enabled for all schemes.
• Parallelism: Single-threaded for all benchmarks.
• Open source: https://anonymous.4open.science/r/VIA-8888/ (anonymized at time of writing). ¹⁹

Deployment Considerations ⤴

• Database updates: Re-encode via NTT (lightweight); no hint invalidation for VIA. VIA-C/VIA-B: offline evaluation keys are independent of the database, so database updates do not require re-uploading keys.
• Sharding: Not discussed, but the I x J matrix structure is naturally shardable by rows.
• Key rotation / query limits: Not discussed. Circular security / KDM assumption required.
• Anonymous query support: VIA: yes (fully stateless, no offline communication). VIA-C/VIA-B: limited -- the client must upload evaluation keys in an offline phase, which is per-client and secret-key-dependent.
• Cold start suitability: VIA: excellent (no offline phase). VIA-C: requires 14.8 MB offline upload before first query.
• Record size flexibility: Blinded extraction (Section 3.2) allows retrieving any coefficient position in [n_1], supporting variable record sizes. Multi-sample extraction generalizes further. ²⁰

Key Tradeoffs & Limitations ⤴

• VIA vs. YPIR throughput: VIA's throughput (3.11 GB/s at 32 GB) is lower than YPIR's (4.52 GB/s) because YPIR's memory-bandwidth-bound architecture (plain LWE matrix-vector multiply) is fundamentally faster for the first-dimension step. VIA trades throughput for 3.7x lower communication.
• VIA-C's smaller plaintext modulus: To accommodate query compression noise (LWE-to-RLWE + RLWE-to-RGSW), VIA-C uses p = 16 (4-bit records) vs. VIA's p = 256 (8-bit records). This means VIA-C requires more queries per byte of useful data for records > 4 bits.
• VIA-C's larger q_1: VIA-C requires a 75-bit q_1 (vs. VIA's 57-bit) to accommodate query decompression noise. This increases first-dimension computation cost by approximately 2x. ²¹
• Offline communication for VIA-C/VIA-B: 14.8 MB of evaluation keys must be uploaded per client, making VIA-C unsuitable for anonymous or ephemeral access patterns.
• Security level: All variants target 110-bit classical security (not the standard 128-bit), which may be insufficient for some deployment scenarios.
• Preprocessing time advantage: VIA's preprocessing (33.34 s for 32 GB) is 9.5x faster than YPIR and 50x faster than SimplePIR, consisting solely of database NTT encoding with a small modulus.

Related Papers in Collection ⤴

• Spiral [Group 1a]: VIA inherits the Regev+GSW composition and external product framework. VIA's DMux-CMux replaces Spiral's coefficient expansion + ciphertext translation.
• Respire [Group 1b]: VIA's direct predecessor in architecture (I x J matrix, ring switching, CMux, sample extraction). VIA replaces Respire's coefficient expansion with DMux, eliminating Respire's offline communication.
• YPIR [Group 1b]: Closest hintless competitor. YPIR uses CDKS ring packing for query compression; VIA uses DMux. VIA achieves 3.7x lower communication but ~1.5x lower throughput at 32 GB.
• HintlessPIR [Group 1b]: VIA reduces communication by 26.9x vs. HintlessPIR at 32 GB while maintaining comparable throughput.
• SimplePIR [Group 2a]: SimplePIR achieves highest throughput (11.97 GB/s) but requires 724 MB offline communication. VIA-C achieves 690x lower online communication at 1.58 GB/s throughput.
• HERMES [ref 29]: MLWE packing technique. VIA's LWE-to-RLWE conversion is functionally equivalent in the single-ciphertext case but differs in implementation details (log n midpoints, single-ciphertext focus).

Open Problems ⤴

• Can the throughput gap between VIA and YPIR/SimplePIR be closed while maintaining logarithmic communication?
• Can VIA-C's plaintext modulus be increased (e.g., to p = 256) without prohibitive noise growth from query decompression?
• Can the DMux-CMux technique be adapted to multi-server settings or combined with preprocessing for further communication reduction?

Uncertainties ⤴

• Subscript conventions for theta: The paper uses multi-level subscripts extensively (theta_ctrl, theta_DMux, theta_cmux, theta_crot, etc.). The correctness analysis in Appendix C.2 defines each per-phase noise variance, but some symbols (e.g., theta_ctrl for the RGSW ciphertext noise vs. theta_ctrl for the overall control-bit phase noise) are overloaded between the VIA direct-query case and the VIA-C query-decompression case.
• Record size ambiguity for VIA benchmarks: Table 1 does not explicitly state the record size in bytes. From the parameters: VIA retrieves log_2(256) = 8 bits per query; VIA-C retrieves log_2(16) = 4 bits per query. The "record" is a single element of R_{n_2,p}, but the paper also discusses blinded extraction for larger records. Benchmark figures appear to measure single-element retrieval.
• VIA-B vectorization threshold: Section 4.7 (p.15-16) states VIA-B "eliminates vectorization entirely for batch sizes below 2048" but this is only explicitly benchmarked for T = 32 and T = 256.
• ePrint number: The paper is referenced as ePrint 2025/2074 in the file path but the actual ePrint URL should be verified.

Footnotes

1. Abstract (p.1): "we propose VIA, a single-server PIR scheme that eliminates offline communication while achieving O_lambda(log N) online communication complexity." ↩

2. Section 1.1 (p.3): The DMux-CMux architecture resembles a symmetric triangular configuration (a "V" shape), which inspired the name VIA. ↩

3. Section 5.2 (p.17): VIA-C's LWE-to-RLWE conversion reduces queries to llog(IJn_1/n_2) = llog N elements in Z_{q_1}. For a 32 GB database, VIA-C's query size is only 0.659 KB vs. Respire's 57.77 KB. ↩

4. Section 4 (p.10): The (m, n, q, chi_S, chi_E)-MLWE problem is at least as hard as the (mn, q, chi_S, chi_E)-RLWE problem. ↩

5. Section 5.1 (p.16): VIA uses chi_{1,S} uniform on [-2, 2] with sigma_{1,E} = 1 (Gaussian). VIA-C/VIA-B use sigma_{1,S} = 32, sigma_{1,E} = 1024 (both Gaussian). ↩

6. Section 5.1 (p.16): "We choose the lattice parameters to ensure that each of the underlying RLWE/MLWE assumptions which we require for security provides 110 bits of classical security. We use the lattice estimator tool [46] for our security estimates." ↩

7. Section 3.1 (p.8-9), Figure 3 (p.9): The encoding packs d = n_1/n_2 = 4 database records per ring element using the subring embedding iota^{n_2->n_1}. ↩

8. Section 4.2 (p.13): VIA-C queries are l * log(IJn_1/n_2) LWE ciphertexts. Each LWE ciphertext contains precisely one non-random element, and pseudorandomness permits further reduction, requiring merely l * log N elements in Z_{q_1}. ↩

9. Table 1 (p.18): VIA-C offline communication is 14.8 MB for all database sizes tested (1 GB, 4 GB, 32 GB). ↩

10. Section 5.1 (p.16): "Database encoding in the Setup database phase is not required; only an NTT is performed per n_1 = 2048 elements." ↩

11. Section 3.2 (p.9): Blinded extraction allows the client to send c_rot = Enc(x^{-t}) for any t in [n_1], enabling retrieval of any coefficient. Multi-sample extraction generalizes to variable-sized records. ↩

12. Section 5.1 (p.16) and Figure 11 (p.19): First dimension processing is the dominant computational overhead. VIA uses p = 256 (8-bit records), VIA-C uses p = 16 (4-bit records). The smaller p in VIA-C reduces first-dimension noise but also reduces per-query record size. ↩

13. Section 5.2 (p.17): Experimental setup details. ↩

14. Section 1.1 (p.3) and Section 3.1 (p.8): "VIA substitutes coefficient expansion techniques with DMux for generating the encrypted one-hot vector, introducing only logarithmic noise variance in the one-hot vector length." ↩

15. Lemma 4.2 (p.12): "The LWE-to-RLWE conversion algorithm introduces O(n log n) noise variance," compared to O(n^3) for the approach in [28]. ↩

16. Section 3.1 (p.8): "We implement modulus switching before first-dimensional folding. This optimization significantly reduces computational overhead for first-dimensional folding while incurring negligible additional error." ↩

17. Section 1.1 (p.4): The homomorphic repacking algorithm "introduces only logarithmic noise variance, making it suitable for large-scale ciphertext repacking scenarios." ↩

18. Section 5.2 (p.17): "Our implementation of VIA and VIA-C contains roughly 4,000 lines of C++." ↩

19. Section 1.2 (p.4): Code anonymously open-sourced. ↩

20. Section 3.2 (p.9): Blinded extraction allows c_rot = Enc(x^{-t}) for arbitrary t in [n_1], and multi-sample extraction extends to variable-sized records. ↩

21. Section 5.2 (p.19): "VIA employs a 256-bit modulus, whereas VIA-C utilizes a 16-bit modulus. This disparity necessitates twice the computational cost for VIA-C relative to VIA at equivalent database scales." ↩