betaFeedback

WorksComputer Science

Retained Encrypted Search with Certified Split Joins

Abstract

Retaining encrypted search across data edits and worker replacement requires separating computational validity from current release authority. We give exact Hamming search with at most one authorized decryption and decoding attempt per query preparation. Under authenticated prescribed execution, exclusive nonrollback owner state, an ideal public seed-expansion interface and a stated observation model, we reduce bounded adaptive privacy to ordinary ring learning with errors (Ring-LWE). Expanded second components depend only on public masks and fixed maps, independently of queries and the fresh database key. This compiler invariant permits a retained split join against a smaller-modulus encrypted database. A simultaneous bound on the completed circuit covers a finite honest reservation family, including adaptive queries and slot selection, with explicit statistical correctness and privacy losses. In three post-calibration local CPU comparisons on 32,768 vectors of 512 bits, the 60-bit-join construction takes a median 9.825 s for an end-to-end two-query workload, versus 12.159 s for the optimized full-source-modulus baseline. These times include setup, transfers, preparation and private completion. They are local implementation results, not deployment or concrete-security claims.

Introduction

Encrypted exact search hides database rows and queries from the storage host while outsourcing Hamming-distance evaluation. Keys and the encrypted database serve multiple queries, but each query-independent preparation permits at most one issuance. The owner retains a private mask and noise, while the server retains matching prepared ciphertexts. Private completion is the owner’s decryption and decoding of an authenticated complete result.

We study retained search under an active host and an integrity-protected executor holding encrypted inputs and confined signing authority, but no homomorphic-encryption (HE) secrets. It authenticates complete prescribed results before private completion, addressing the reaction-attack risk from malicious ciphertexts [1]. The owner retains truthful history and may keep all plaintext data, making plaintext caching a permitted control.

The owner corrects scores from immutable computation base K to the current data head H at serialized release. Reconstruction changes worker generation G and transfers only held unused preparations. Durable records prevent repeated issuance or compaction. We instantiate this protocol using projected Brakerski–Gentry–Vaikuntanathan (BGV) queries.

Can a retained preparation be combined with a reference database encrypted at a smaller modulus while preserving these guarantees? We call this encrypted reference database the gallery, and the sum of query–column ciphertext products the join. Separate rounding of the retained and late first components is not additive, so we bound the completed split circuit rather than its incomplete preparation. The expansion compiler translates coefficient-extraction maps into key switching, with second components independent of the query and fresh gallery secret. This invariant permits a simultaneous rounding bound over all reserved seeds, covering adaptive choices.

We make two contributions.

  1. A retention-preserving exact-search protocol and security composition. Its current-output invariant couples unique projected issuance, authenticated whole-result admission, durable consumption, correction and reconstruction. An acyclic independent-recipient reduction handles delayed adaptive queries under ordinary Ring-LWE and explicit lifetime accounting.

  1. A certified retained split join based on the second-component compiler invariant and a finite-family rounding bound. Its exact output contract and statistical loss compose with the same owner authority. The implementation measures full-lifetime local costs.

Offline/online HE computation and one-query seeds have recent examples in ZipPIR and FlashPIR [2], [3]. Attested or verified evaluation appears in Argos and vFHE [4], [5]. Current authenticated data also underlies dynamic verification [6], [7]. BGV modulus switching, hoisting, Bernstein concentration and finite union bounds are established tools. Our contribution is their composition with a retained split join, adaptive selection and one-use current release, not a new probability inequality or optimality result. Evaluation compares complete construction profiles rather than an isolated optimization.

Functionality and Execution Model

Let D0∈{0,1}n×dD_0 \in\{0,1\}^{n \times d} be the initial database of n≥3n \ge3 binary vectors of dimension d≥1d \ge1, with ordered distinct row identifiers I=(i0,…,in−1)\mathcal{I}=(i_0,\ldots,i_{n-1}). A query is q∈{0,1}dq \in\{0,1\}^d. A truthful authorized edit uℓ=(iℓ,jℓ,bℓ,bℓ′)u_\ell=(i_\ell,j_\ell,b_\ell,b'_\ell) satisfies Dℓ−1[iℓ,jℓ]=bℓD_{\ell-1}[i_\ell,j_\ell]=b_\ell and bℓ′=1−bℓb'_\ell=1-b_\ell. Its application produces DℓD_\ell. Repeated coordinates and reversions are allowed. Let Ue=(u1,…,ue)\mathcal{U}_e=(u_1,\ldots,u_e) be the ordered edit log and He=(e,he)H_e=(e,h_e) its endpoint identifier. For a fixed base and a single nonrollback history, the counter ee identifies the prefix. The optional metadata heh_e is a fresh opaque owner label, or a fixed public placeholder if unused. Reversions advance the head even when they restore earlier contents.

Definition 2.1 (Current-search functionality): At a serialized release with head HeH_{\mathrm{e}}, define

ve(q)[i]=Ham⁡(De[i],q)=∑j=0d−1(De[i,j]⊕q[j]),(1)v_{\mathrm{e}}(q)[i] = \operatorname{Ham}(D_{\mathrm{e}}[i],q) = \sum_{j=0}^{d-1}(D_{\mathrm{e}}[i,j] \oplus q[j]), \tag*{(1)}
F(De,q,I)=(He,ve(q),Top⁡3(ve(q),I)).(2)\mathcal{F}(D_{\mathrm{e}},q,\mathcal{I}) = (H_{\mathrm{e}},v_{\mathrm{e}}(q),\operatorname{Top}_3(v_{\mathrm{e}}(q),\mathcal{I})). \tag*{(2)}

Top⁡3\operatorname{Top}_3 sorts rows lexicographically by (ve(q)[i],i)(v_{\mathrm{e}}(q)[i],i) and returns the first three distances and their bound identifiers. The owner may release just the top three.

Answers are current at release. Later edits do not invalidate them. Ranking is private. Associated-record retrieval and encrypted server-side top-kk are separate functionalities.

Encrypted evaluation uses the sign map χ(b)=1−2b\chi(b)=1-2b. For x,q∈{0,1}dx,q\in\{0,1\}^d, the sign-correlation identity is

Ham⁡(x,q)=d−∑j=0d−1χ(xj)χ(qj)2.(3)\operatorname{Ham}(x,q)=\frac{d-\sum_{j=0}^{d-1}\chi(x_j)\chi(q_j)}{2}. \tag*{(3)}

Parties and Trust Boundary

In a client-server deployment, source and owner roles may share one client, while the server runs the worker. The honest source encrypts D0D_0, authenticates its ordered identifiers and layout, and provisions the owner’s private roles. The owner holds HE secrets, queries, and truthful edit history, and may retain all plaintext data and prior scores. One serialized owner authority governs issuance and release, with faithful storage of monotone reservation and consumption records.

The worker’s executor E\mathcal{E} is an integrity-protected interface for computation and signing. It holds the public key graph, encrypted index, approved evaluation, a codec (encoding and decoding rule), and a confined receipt-signing key. On authenticated requests, it runs only the bound computation and signs only complete prescribed results, with no arbitrary-result signing interface. The untrusted host controls external storage, packet delivery, scheduling, replay, omission, and public worker-state cloning.

Enrollment is the authenticated registration that binds E\mathcal{E}’s verification key and generation to the prescribed program and assets. Attested execution can instantiate this interface, or sound verification can replace it with its corresponding error term. An unconstrained server signature does not suffice. The source and owner are honest, the executor’s signing key remains confined, and the owner authority is exclusive and nonrollback. Private provisioning and plaintext transport require faithful confidential authenticated boundaries. Availability and recovery of lost private RAM state are not required.

Observations and Adaptive Inputs

Definition 2.2 (Public leakage L\mathcal{L}): The host observes dimensions and packing layout, ordered identifiers, output ciphertext type and wire profile (response modulus, coefficient width and codec), public encrypted assets, ciphertext-derived bindings, message lengths, head counters, optional opaque head labels, generations, reservation identities, routing, and the logical schedule of preparation, issuance, updates, rejection, finalization, reconstruction, and cache selection. Public policy outcomes are included.

Rows, query words, edit contents, scores, and private masks remain in the owner/source boundary. Cache hits or avoided traffic may disclose equality and reuse patterns. These observations are included in the leakage. Secret-dependent execution durations, memory addresses, residual private buffers, and microarchitectural observations are outside the observation model. Host-chosen delivery delays remain observable. The computational theorem therefore concerns logical protocol events. It does not claim that the current variable-time implementation hides private execution time.

An honest input policy is the client’s operation-selection procedure. Its interface exposes data and earlier authorized answers, but not HE secrets, hidden phases or private encryption randomness. We compare paired policies that are causally L\mathcal{L}-compatible: given any common public transcript, they propose valid private operations with the same next public event, dimensions, layout, routing, lengths, and public decision. Private ideal answers may differ. An incompatible proposal terminates both worlds with the same neutral observation. Ciphertext hashes are computed from each game’s actual bytes. Compatibility does not demand equality of hashes from different games.

Encrypted Representation and Retained Evaluation

The baseline expands queries and joins database columns at QQ. Response compression uses pp (Section VI). The split join adds an intermediate modulus PP (Section VII), giving Q→P→pQ \to P \to p at unchanged ring dimension.

An Independent Recipient Graph

Let m=2⌈log⁡2d⌉m=2^{\lceil\log_2 d\rceil} be the padded query length, the smallest power of two at least dd. Choose an odd plaintext modulus t>2mt>2m. Since m≥dm\ge d, every sign correlation in [−d,d][-d,d] has a unique centered representative modulo tt, allowing exact recovery from its plaintext residue.

Let N=2L≥2mN=2^L\ge2m be the ring dimension with m∣Nm\mid N, and r=N/mr=N/m the projection stride. For any integer modulus u>1u>1, define

R=Z[X]/(XN+1),Ru=R/uR.R=\mathbb{Z}[X]/(X^N+1),\qquad R_u=R/uR.

The source ciphertext modulus Q>1Q>1 is odd, with gcd⁡(t,Q)=gcd⁡(t,N)=1\gcd(t,Q)=\gcd(t,N)=1. We use coefficient ℓ1\ell_1, Euclidean and maximum norms, denoted ∥⋅∥1\lVert\cdot\rVert_1, ∥⋅∥2\lVert\cdot\rVert_2 and ∥⋅∥∞\lVert\cdot\rVert_\infty. Products are negacyclic, with XN=−1X^N=-1. We use the leveled BGV scheme [8]. Each secret has independent uniform coefficients in {−1,0,1}\{-1,0,1\}. For an integer η≥1\eta\ge1, each error coefficient has centered binomial distribution CBD⁡η=∑j=1η(Uj−Vj)\operatorname{CBD}_{\eta}=\sum_{j=1}^{\eta}(U_j-V_j) for independent fair bits. We call a fresh secret-key ciphertext a parent, and its decryption key its recipient. A recipient is a key role, not an additional protocol participant. A fresh secret-key ciphertext is sampled as

C=(c0,c1)=(μ+te−as,a)∈RQ2.(4)C=(c_0,c_1)=(\mu+te-as,a)\in R_Q^2. \tag*{(4)}

Here μ\mu has centered plaintext coefficients modulo tt, ee is the error polynomial, ss is secret, and aa is an independent uniform public mask in RQR_Q. The phase Φs(C)=c0+c1s≡μ+te(modQ)\Phi_s(C)=c_0+c_1s\equiv\mu+te\pmod Q cancels the mask. An integer lift represents this residue with integer coefficients, not necessarily centered, and must be bounded before decoding.

Sample independent secrets s0,…,sLs_0,\ldots,s_L and, when needed, a final sfs_f, with f=L+1f=L+1. In this sequential graph, g=Lg=L denotes the gallery key role. Public key-switching keys, called hints, contain encrypted secret-derived terms used to change a ciphertext’s recipient without decryption. At each level ℓ<L\ell<L, publish identity and automorphism hints addressed to sℓ+1s_{\ell+1}. For an integer gadget radix β≥2\beta\ge2 and k=⌈log⁡βQ⌉k=\lceil\log_\beta Q\rceil, a column with target τ\tau is

(bj,aj)=(βjτ+tej−ajsℓ+1,aj),0≤j<k,(5)(b_j,a_j)=(\beta^j\tau+te_j-a_js_{\ell+1},a_j),\qquad0\le j<k, \tag*{(5)}

where aja_j and eje_j are fresh mask and error draws, τ=sℓ\tau=s_\ell or τ=σℓ(sℓ)\tau=\sigma_\ell(s_\ell) and σℓ(f)(X)=f(X1+N/2)\sigma_\ell(f)(X)=f(X^{1+N/2}). Final hints use the same sampling rule with recipient sfs_f and target sgs_g or sg2s_g^2, as required by the terminal type below. Each role also publishes one independent parent with μ=0\mu=0 as its public-key record. It counts as an exposed sample, although queries and gallery entries use secret-key encryption.

For w=∑j<kβjdj mod Qw=\sum_{j<k}\beta^jd_j\bmod Q, use coefficientwise base-β\beta digits of representatives in [0,Q)[0,Q). With hints addressed to svs_v, define

KS⁡τ→v(w)=(∑jdjbj,∑jdjaj).(6)\operatorname{KS}_{\tau\to v}(w)=\left(\sum_jd_jb_j,\sum_jd_ja_j\right). \tag*{(6)}

Its phase under svs_v is wτ+t∑jdjejw\tau+t\sum_jd_je_j modulo QQ. This graph uses independent leveled switching as in BGV [8]. Its key-dependency graph is acyclic: every hint target depends only on keys earlier than its recipient.

Projected Queries

We encode and mask a compact query, expand it into encrypted signs, and compute database correlations. For f=∑ifiXif=\sum_i f_iX^i, projection πr(f)=(f0,fr,…,f(m−1)r)\pi_r(f)=(f_0,f_r,\ldots,f_{(m-1)r}) extracts mm coefficients at stride rr. The embedding ιr\iota_r reverses this placement, inserting zeros elsewhere. Let α∈{1,…,t−1}\alpha\in\{1,\ldots,t-1\} be the canonical inverse of NN modulo tt, which compensates for the expansion factor NN, and encode the query as

μq=ιr(αχ(q0),…,αχ(qd−1),0,…,0),(7)\mu_q=\iota_r\bigl(\alpha\chi(q_0),\ldots,\alpha\chi(q_{d-1}),0,\ldots,0\bigr), \tag*{(7)}

with coefficients centered modulo tt. A fresh public seed zz yields uniform az∈RQa_z\in R_Q. The owner prepares the private mask MzM_z and issues the masked first-component row:

Mz=πr(azs0),xz(q)=πr(μq)+tez−Mz mod Q.(8)M_z=\pi_r(a_zs_0),\qquad x_z(q)=\pi_r(\mu_q)+te_z-M_z\bmod Q. \tag*{(8)}

Only (z,xz(q))(z,x_z(q)) is sent. The secret s0s_0 still has NN coefficients. The transmitted row has the same distribution as the selected first-component coefficients of a fresh ciphertext in the full NN-dimensional ring. The private noise row ez∈Zme_z\in\mathbb{Z}^m has independent CBD⁡η\operatorname{CBD}_\eta coefficients. The owner holds the query-independent (z,Mz,ez)(z,M_z,e_z) preparation until a single issuance.

For x=(x0,…,xm−1)∈(Z/QZ)mx=(x_0,\ldots,x_{m-1})\in(\mathbb{Z}/Q\mathbb{Z})^m, define Expand⁡(x,az)\operatorname{Expand}(x,a_z) from (ιr(x),az)(\iota_r(x),a_z) using log⁡2r\log_2 r sum-only algebraic trace levels, then L−log⁡2rL-\log_2r two-way expansion levels. Level ℓ\ell switches identity and automorphic branches to the same new recipient, and adds them. Two-way levels also subtract them, shifting the difference by X−2ℓX^{-2^\ell}. Lower outputs precede upper outputs. Its mm output ciphertext pairs, called leaves, under sgs_g encode query signs as constants for x=xz(q)x=x_z(q).

Lemma 3.1 (Projection and retained affine identity): In error-free phase algebra, leaf jj is NN times the selected input phase coefficient at rjrj. Unselected coefficients cancel. With fixed hints and aza_z, the complete component identity is

Expand⁡(x,az)j=Expand⁡(0,az)j+(Nxj,0).(9)\operatorname{Expand}(x,a_z)_j=\operatorname{Expand}(0,a_z)_j+(Nx_j,0). \tag*{(9)}

Proof. On support at multiples of 2ℓ2^\ell, σℓ\sigma_\ell multiplies coefficient ii by (−1)i/2ℓ(-1)^{i/2^\ell}. The sum selects and doubles even positions, while the shifted difference selects and doubles odd positions. Induction eliminates coordinates outside multiples of rr, then isolates rjrj in source order, with total multiplier 2L=N2^L=N. Switching decomposes only the second component and adds the transformed first component afterward. Its second component is therefore independent of the original first component, whose subsequent additions and shifts are linear. The same induction on ιr(x)\iota_r(x) proves (9) exactly in RQR_Q. ☐

Here Expand⁡(0,az)\operatorname{Expand}(0,a_z) has a zero input first component, rather than zero plaintext. It depends only on the seed and fixed switching hints.

Partition the database into gn=⌈n/N⌉g_n=\lceil n/N\rceil groups of at most NN rows. Within each group, encrypt feature column Aj(X)=∑iχ(D0[i,j])XiA_j(X)=\sum_i\chi(D_0[i,j])X^i under sgs_g, with local row indices 0≤i<N0\le i<N and zero padding. We suppress the group index and use D0[i,j]D_0[i,j] for its local rows. Decoded groups are concatenated in original row order. Write its encrypted pair as Bj=(Bj0,Bj1)B_j=(B_{j0},B_{j1}). Multiplying each column by its query-sign leaf and summing places row ii’s sign correlation at coefficient ii, for conversion to distance by (3). Use (u,v)⊗(b,c)=(ub,uc+vb,vc)(u,v)\otimes(b,c)=(ub,uc+vb,vc) for unlinearized pair multiplication. Let Tz=(T1,T2)=∑j<dExpand⁡(0,az)j⊗BjT_z=(T_1,T_2)=\sum_{j<d}\operatorname{Expand}(0,a_z)_j\otimes B_j be the server’s query-independent prepared tensor, a three-component product ciphertext. The arriving first-component coefficient row supplies the late correction

ΔT=(∑j<dNxjBj0,∑j<dNxjBj1,0).(10)\Delta T=\left(\sum_{j<d}Nx_jB_{j0},\sum_{j<d}Nx_jB_{j1},0\right). \tag*{(10)}

The complete tensor Tz+ΔTT_z+\Delta T uses decryption multipliers (1,sg,sg2)(1,s_g,s_g^2). Its unchanged quadratic component can be switched in advance, using input equality rather than additive gadget switching.

Typed Terminals and Phase Bounds

A terminal is a completed output ciphertext. The three types encode the same correlations, trading final switching work against component count and decoding requirements. Their decryption multipliers are

wpair=(1,sf),wmixed=(1,sg,sf),wtensor=(1,sg,sg2).(11)w_{\mathrm{pair}}=(1,s_f),\qquad w_{\mathrm{mixed}}=(1,s_g,s_f),\qquad w_{\mathrm{tensor}}=(1,s_g,s_g^2). \tag*{(11)}

Pair switches both linear and quadratic tensor terms to sfs_f. Mixed switches only the quadratic term and retains the linear term under sgs_g. Tensor retains the unrelinearized product and needs no final role. Pair performs its linear switch after Equation (10). Mixed and tensor need no online terminal switch. An ordinary (1,s,s2)(1,s,s^2) decoder cannot decode the mixed terminal. For each type, the phase is ∑iCiwi\sum_i C_iw_i modulo the ciphertext modulus, where CiC_i are the terminal components.

Define the fresh phase bound FF, single-switch error bound SS, complete expanded-leaf bound EE, and terminal phase bound BνB_\nu by

F=⌊t/2⌋+tη,S=tNηk(β−1),F=\lfloor t/2\rfloor+t\eta,\qquad S=tN\eta k(\beta-1),
E=NF+2(N−1)S,Bν=NdFE+(2−ν)S,(12)E=NF+2(N-1)S,\qquad B_\nu=NdFE+(2-\nu)S, \tag*{(12)}

for pair, mixed, tensor indices ν=0,1,2\nu=0,1,2 respectively.

Lemma 3.2 (Complete source-phase bound). Each complete authorized terminal has an integer phase lift vv such that ∥v∥∞≤Bν\lVert v\rVert_\infty\le B_\nu and

vi≡∑j<dχ(D0[i,j])χ(qj)(modt)v_i\equiv\sum_{j<d}\chi(D_0[i,j])\chi(q_j)\pmod t

on actual rows, with zero plaintext on padding. If 2Bν<Q2B_\nu<Q, centered source decryption recovers those plaintexts exactly.

Proof. Canonical digits satisfy ∥dj∥∞≤β−1\lVert d_j\rVert_\infty\le\beta-1, so each switching error is bounded by SS, using ∥uv∥∞≤N∥u∥∞∥v∥∞\lVert uv\rVert_\infty\le N\lVert u\rVert_\infty\lVert v\rVert_\infty. Automorphisms and monomial shifts are signed permutations and preserve the coefficient infinity norm. Each output combines two switching errors. Their propagated total after LL levels is 2S(1+2+⋯+2L−1)=2(N−1)S2S(1+2+\cdots+2^{L-1})=2(N-1)S. Lemma 3.1 eliminates unselected input coordinates before applying the fresh bound FF to the selected ones, giving EE. No fresh bound is assigned to the sparse restored phase or the zero-first preparation alone. Gallery phases have bound FF. Their dd negacyclic products with complete leaves have aggregate bound NdFENdFE. The typed final switches add zero, one, or two errors SS. Every error is divisible by tt in its integer lift. Since Nα≡1(modt)N\alpha\equiv1\pmod t, the plaintext is the sign correlation. The bound below Q/2Q/2 makes this lift the unique centered phase. Only then is reduction modulo tt applied. Centering that residue gives the integer correlation in Equation (3), since t>2dt>2d. □

Protocol and Correctness

Computation, Authority, and State

KK binds the encrypted base, independent key graph, ordered identifiers, layout, terminal type, permitted wire profiles, their selection rule and prescribed program. HeH_e authorizes current answers. GG names the enrolled worker and its receipt/channel keys, not the physical server. Correct computation under KK authorizes no release at an obsolete head or generation. An original o=(z,xz(q))o=(z,x_z(q)) is an issued query message.

The authority and capability state is

S=(K,H,G,U,I,R,P,C),(13)\mathcal{S}=(K,H,G,\mathcal{U},\mathcal{I},\mathcal{R},\mathcal{P},\mathcal{C}), \tag*{(13)}

Here U\mathcal{U} is the truthful edit log, I\mathcal{I} the durable lifetime ledger charging one slot per preparation attempt, R\mathcal{R} exclusively held unused preparations, P\mathcal{P} pending originals, and C\mathcal{C} consumed or retired originals. Sans-serif symbols denote identifiers, calligraphic symbols state collections. Pending entries bind queries to issue-time metadata:

γo=(K,Go,Ho,no,zo,ℓo,Hash⁡(o)).(14)\gamma_o=(K,G_o,H_o,n_o,z_o,\ell_o,\operatorname{Hash}(o)). \tag*{(14)}

The fresh nonce non_o names the issued instance, with subscripts oo denoting issue-time values. KK fixes admissible formats and complete payload extent for each profile. Preparation, original and result messages have distinct signed domains. Identifiers are initially distinct ideal names, realized by random labels (§ 5). Owner closure invalidates R\mathcal{R}, P\mathcal{P} and completion permissions, halting use without refunds. Durable failure closes before dependent work.

Algorithms 1–2 implement serialized owner transitions. Prepare⁡(K,G,z,ℓ)\operatorname{Prepare}(K,G,z,\ell) authenticates the owner, checks K,GK,G, regenerates aza_z from zz, and registers per-group seed-only state from TzT_z (Section III or § 7), with permitted quadratic switching. Its authenticated acknowledgment binds these four arguments. Plaintext queries, MzM_z and eze_z remain private. Finish⁡(y)\operatorname{Finish}(y) decrypts all groups of the admitted payload with multipliers (11) and the enrolled codec. It checks zero padding and returns base distances v0(q)v_0(q) via (3), without correction, ranking or release.

Algorithm 1. Private preparation and unique issue

Input: open owner state S\mathcal{S} and enrolled executor E\mathcal{E}.

  1. Prepare: durably charge a fresh slot ℓ\ell in I\mathcal{I}. Draw fresh z,ez,e and compute MzM_z by (8). Request Prepare⁡(K,G,z,ℓ)\operatorname{Prepare}(K,G,z,\ell) from E\mathcal{E}.

  2. On an authenticated acknowledgment matching the preparation binding, store ℓ↦(z,Mz,ez)\ell\mapsto(z,M_z,e_z) in R\mathcal{R}. Failure closes the owner without refund.

  3. Issue (ℓ,q)(\ell,q): require a ready slot ℓ\ell, take its tuple R[ℓ]\mathcal{R}[\ell] and delete that entry before validating qq and forming o=(z,xz(q))o=(z,x_z(q)).

  4. Choose non_o, form γo\gamma_o, durably mark ℓ\ell issued, and store no↦(q,γo)n_o\mapsto(q,\gamma_o) in P\mathcal{P}.

  5. Send the owner-signed (γo,o)(\gamma_o,o).

Any partial failure closes the owner without refund.

The executor verifies the bound original and matching preparation, retires the latter, adds (10) or (28), then performs required switches and canonical encoding. It signs γo\gamma_o, the selected wire profile and the complete payload under GG. Subsets cannot authorize Finish.

Ordered Local Correction

Keeping the encrypted base at D0D_0, correct row ii’s distance by

Δe(q)[i]=∑1≤ℓ≤eiℓ=i((bℓ′⊕q[jℓ])−(bℓ⊕q[jℓ])).(15)\Delta_e(q)[i]=\sum_{\substack{1\le\ell\le e\\ i_\ell=i}}\left((b'_\ell\oplus q[j_\ell])-(b_\ell\oplus q[j_\ell])\right). \tag*{(15)}

Algorithm 2. Authenticated completion and current release

Input: state SS, nonce non_o identifying original oo, and response yy. All steps run under the owner’s release/edit lock, with current head HeH_e.

  1. Reject and stop unless non_o has an issued, unconsumed entry in P\mathcal{P}. Read (q,γo)(q,\gamma_o) and check the complete public frame, signature and binding.

  2. If public admission fails, retire oo durably, remove entry non_o from P\mathcal{P}, and stop without private completion.

  3. Durably mark oo consumed in C\mathcal{C} and remove entry non_o from P\mathcal{P} before any private arithmetic.

  4. If Ho≠HH_o \ne H, Go≠GG_o \ne G, or a cache answer has superseded oo, stop without Finish or release.

  5. Create and spend an internal one-use permission before v←Finish⁡(y)v \leftarrow\operatorname{Finish}(y). Partial calls cannot be retried.

  6. Compute ve←v+Δe(q)v_e \leftarrow v + \Delta_e(q) using (15). Release (He,ve,Top3⁡(ve,I))(H_e,v_e,\operatorname{Top3}(v_e,\mathcal{I})). Private failure closes the owner without release or refund.

Lemma 4.1 (Telescoping correction): For every truthful ordered history, v0(q)+Δe(q)=ve(q)v_0(q) + \Delta_e(q) = v_e(q).

Proof. Each edit changes one summand of Equation (1) by its term in Equation (15). Summing telescopes, including repeated edits and reversions. □

Short histories reduce the O(e)O(e) scan cost per fresh query, but exactness requires no sparsity assumption. The owner advances HH before dependent work and applies the same row correction to cached exact score vectors. The baseline corrects edits preceding issuance but retires a query overtaken by a later edit, despite its valid cryptographic base. Appendix G permits completion across in-flight edits under additional live correction checks. For comparison, server correction can add encrypted feature contributions before one complete terminal conversion. Independent rounding of each contribution is a different graph and does not follow from ring linearity.

Reconstruction and Permitted Caching

Reconstruction enrolls a rebuilt or replacement worker, possibly on the same machine, preserving KK, HH, J\mathcal{J}, C\mathcal{C} while advancing GG and revoking old pending originals. Only held unused preparations transfer. They remain unready until the new executor acknowledges Prepare⁡(K,G,z,ℓ)\operatorname{Prepare}(K,G,z,\ell). Imports and public preparation remain necessary. Private objects are not recreated from seeds or journals, and lost capabilities are not restored.

A ready authenticated plaintext cache may answer from exact current rows under the same authority without issuing an HE original. If acquisition overlaps a pending HE original, a cache win supersedes it. Later finalization performs no private completion and retains the charge, preventing a second decryption attempt.

Lemma 4.2 (Monotone capability invariant): For every allowed trace, each private preparation issues at most one original, and each original invokes at most one whole-result private completion. Edits, reconstruction, rejection, and cache finalization refund neither.

Proof. Algorithm 1 charges before creating R[ℓ]\mathcal{R}[\ell] and removes it before fallible issuance. Issued entries never return. Reconstruction transfers only unused entries. Algorithm 2 consumes the pending entry durably before creating and spending its one-use completion permission. Missing entries prevent repeat admission, even after partial work. Charges remain spent. Induction proves all three assertions. □

Definition 4.3 (Retention and release invariant): For a protocol trace prefix τ\tau, let iss⁡τ(ℓ)\operatorname{iss}_{\tau}(\ell) count originals issued from slot ℓ\ell and fin⁡τ(o)\operatorname{fin}_{\tau}(o) count whole-result private completion attempts for original oo. The predicate Inv⁡ret(τ)\operatorname{Inv}_{\mathrm{ret}}(\tau) requires all of the following:

  1. iss⁡τ(ℓ)≤1\operatorname{iss}_{\tau}(\ell) \le1 and fin⁡τ(o)≤1\operatorname{fin}_{\tau}(o) \le1. The charged-slot set and consumed or retired originals grow monotonically.

  2. Each completion follows durable consumption and whole-result admission under the exact binding γo\gamma_o. Its issue head and generation equal the current HH and GG at the serialized completion transition.

  3. Every release agrees with the authorized projection of F(De,q,I)\mathcal{F}(D_e,q,\mathcal{I}) at its serialized release head HeH_e.

  4. An edit preserves KK and all prior charges and consumption marks. Reconstruction additionally preserves HH, revokes old pending originals, and transfers only actually held unused preparations, made ready by a matching acknowledgment from the new executor.

Thus retention preserves computational validity without replenishing private authority. Public cloning alone creates no unused private preparation.

a) Why the clauses must be coupled: Consider a modified issuance rule that reuses (z,Mz,ez)(z,M_z,e_z) for queries qq and q′q'. Equation (8) then gives xz(q)−xz(q′)=πr(μq−μq′) mod Qx_z(q)-x_z(q')=\pi_r(\mu_q-\mu_{q'}) \bmod Q. Both evaluations can be correctly authenticated, yet the query messages are no longer hidden by independent phases. Similarly, correct evaluation of an earlier database version does not establish current release authority, and restoring a pending entry without its consumption mark permits a second private attempt on an identical authenticated result. These examples concern altered transitions of our protocol. The invariant excludes them jointly, rather than treating evaluation validity as sufficient release authority.

Theorem 4.4 (Exact current-output correctness): Assume an honest source, honest input policies, the execution and owner model of Section II, and the source bounds of Lemma 3.2 with 2Bν<Q2B_\nu< Q for every allowed terminal type ν\nu. Assume also that the terminal codec decodes every authorized result exactly. Before an authentication or binding failure, every released output equals the authorized projection of F(De,q,I)\mathcal{F}(D_e,q,\mathcal{I}) at its release head. Private completion is at most once per original, and neither data edits nor worker reconstruction can restore an attempted capability.

Proof. Setup fixes the honest base and empty history and ledgers. Algorithms 1–2 and Lemma 4.2 preserve exclusive custody and monotone consumption. Edits mark older candidates stale, and reconstruction revokes old generation authority.

An admitted result is the complete prescribed computation for its bound original. Lemmas 3.1 and 3.2, with exact decoding, give Finish⁡(y)=v0(q)\operatorname{Finish}(y)=v_0(q) by Equation (3). Lemma 4.1 therefore makes Algorithm 2’s corrected vector exact at HeH_{\mathrm e}. Top3⁡\operatorname{Top3} supplies the bound identifiers with row-index tie breaking. Exact cached scores yield the same answer. The lock serializes admission, correction, cache selection, edits and release. An edit after issuance stales its candidate. A release before an edit linearizes at the earlier head. Stale or superseded requests and failures release nothing. Induction proves exactness, and Lemma 4.2 gives the capability claim.

Adaptive Security

Games and Primitive Assumptions

The integrity adversary controls the public host and packet delivery, and observes the honest owner’s public admission outcomes. Bad occurs if an unauthorized value reaches private completion, an original invokes private completion more than once, or a released answer is incorrect or stale for its linearization head. The finite multi-session EUF-CMA and binding-collision losses sum to

εauth=εownerSig+εworkerSig+εhash(16)\varepsilon_{\mathrm{auth}}=\varepsilon_{\mathrm{ownerSig}}+\varepsilon_{\mathrm{workerSig}}+\varepsilon_{\mathrm{hash}} \tag*{(16)}

The hash term covers complete originals, assets, and signed payloads. Signatures need ordinary unforgeability, not strong unforgeability: a new signature on an already authorized identical message causes no false binding.

For privacy, the environment supplies two causally L\mathcal{L}-compatible adaptive policies. In world bb, the source and owner use policy bb. The host sees only the declared public view and outputs a bit. Its public-view distinguishing advantage is

Adv⁡priv(A)=∣Pr⁡[A(View0)=1]−Pr⁡[A(View1)=1]∣.(17)\operatorname{Adv}_{\mathrm{priv}}(\mathcal{A})=\left|\Pr[\mathcal{A}(\mathrm{View}_0)=1]-\Pr[\mathcal{A}(\mathrm{View}_1)=1]\right|. \tag*{(17)}

Both policies use exact private ideal outputs for subsequent decisions and remain independent of secret-key state and hidden encryption randomness.

For recipient vv, let εv(Mv,τv)\varepsilon_v(M_v,\tau_v) bound the decisional Ring-LWE advantage between at most MvM_v ordinary samples

(a,−asv+e)and(a,u),(a,-as_v+e)\qquad\text{and}\qquad(a,u),

where a,ua,u are independent uniform elements of RQR_Q, svs_v has the specified ternary distribution, and ee has independent CBD⁡η\operatorname{CBD}_{\eta} coefficients. τv\tau_v includes the reduction’s complete simulation time. The invertible map (a,b)↦(ta,tb)(a,b)\mapsto(ta,tb) gives the exact scaled-error distribution (a,−asv+te)(a,-as_v+te) used in Equation (4). After scaling, the sample coordinates supply the mask and zero-message first component. Adding μ\mu to the latter gives the ciphertext. This assumption is for the actual ring and distributions. A concrete security estimate is a separate parameter-selection question.

Public expansion uses a domain-separated ideal classical extendable-output function (XOF) with independent uniform byte streams per input. Its low-bit rejection sampler produces uniform coefficients below QQ. Let κ\kappa be the bit length of fresh seeds and random protocol names, PsP_s count all fresh parent seeds, and hh count adversarial XOF input queries. Let VV count the remaining fresh random names. Coupling to ideal interfaces with distinct identifiers gives

δX≤Psh2κ+Ps(Ps−1)2κ+1,(18)\delta_X\leq\frac{P_sh}{2^\kappa}+\frac{P_s(P_s-1)}{2^{\kappa+1}}, \tag*{(18)}
δnames≤V(V−1)2κ+1.(19)\delta_{\mathrm{names}}\leq\frac{V(V-1)}{2^{\kappa+1}}. \tag*{(19)}

Failed and unused reservations count. Identical republishing does not. For a strict fair-bit polynomial-time reduction, cap each rejection stage at ρ\rho candidates. With Sall=∑vMvS_{\mathrm{all}}=\sum_v M_v samples and RsR_s fresh role-secret draws,

δcut≤Csamp2−ρ,Csamp=N(2Sall+Ps+Rs).(20)\delta_{\mathrm{cut}}\leq C_{\mathrm{samp}}2^{-\rho},\qquad C_{\mathrm{samp}}=N(2S_{\mathrm{all}}+P_s+R_s). \tag*{(20)}

This conservative count includes uniform sample components, conditional XOF streams, and ternary draws. CBD draws have fixed length. Appendix A details the exact stream distributions and sampling cutoff rules.

Integrity and Ideal Private Completion

Lemma 5.1 (Admission and ideal private completion): Assume the correctness hypotheses of Theorem 4.4, including 2Bv<Q2B_v<Q for every allowed terminal type and pointwise exact terminal decoding, together with the authentication and binding games above. Then

Pr⁡[Bad]≤εauth+δnames.\Pr[\mathrm{Bad}]\leq\varepsilon_{\mathrm{auth}}+\delta_{\mathrm{names}}.

Before such failure, substituting exact v0(q)v_0(q) for authorized Finish⁡(y)\operatorname{Finish}(y) calls, with Algorithm 2’s correction and release unchanged, preserves the declared distribution of public traces. Proof. Accepting an unauthorized owner request gives a signature forgery or binding collision. The confined executor signs only complete prescribed results, so an accepted nonprescribed result implies a worker forgery or binding collision. Extent, domain and pending nonce exclude partial-result and cross-original substitution. Theorem 4.4 and Lemma 4.2 preclude duplicate completion and incorrect or stale release. Name coupling adds δnames\delta_{\mathrm{names}}.

Source bounds and exact decoding give v0(q)v_0(q). Lemma 4.1 gives the ideal current answer. Public rejection and stale/cache finalization inspect only public bindings and lifecycle state, without private decoding. Represent delayed preparation by an opaque parent-sample handle, exposing only aza_z until unique issue, then adding the honest message to its hidden first component and exposing the projection. Unsent error coordinates are independent and integrate out. Policies cannot inspect masks or errors, so early and issue-time sampling have identical observations. Induction preserves public state, pending bindings and private ideal answers, including adaptive decisions. Later ciphertext hybrids use this ideal owner without decrypting changed ciphertexts.

Invalid host bytes never reach a secret-dependent decoder. Prescribed honest results meet the decoding bound for every allowed secret and error. Rejection therefore depends on public validity and authority, not attacker-selected phase tests. This reaction-attack defense relies on the execution and owner premises. It does not make BGV generally CCA-secure.

Descending Recipient Reduction

Theorem 5.2 (Bounded adaptive input privacy). For the acyclic independent-recipient protocol, assume the correctness hypotheses of Theorem 4.4, including 2Bν<Q2B_{\nu}<Q for every allowed terminal type and pointwise exact terminal decoding. Under Section II’s execution premises and the games above,

Adv⁡priv(A)≤2(εauth+∑vεv(Mv,τv)+δX+δnames+δcut).(21)\operatorname{Adv}_{\mathrm{priv}}(\mathcal{A}) \le2\left(\varepsilon_{\mathrm{auth}}+\sum_{v}\varepsilon_v(M_v,\tau_v)+\delta_X+\delta_{\mathrm{names}}+\delta_{\mathrm{cut}}\right). \tag*{(21)}

Proof. In each world, stop on authentication/binding failures and couple names and bounded samplers at the displayed cost. Apply Lemma 5.1 before changing any ciphertext distribution. All completions now use ideal private answers.

For descending replacement, let HybH_{\mathrm{yb}} keep recipients v≤cv\le c real and replace parent and hint first components addressed to v>cv>c by independent uniform elements of RQR_Q. For the adjacent reduction at cc, draw all other secrets independently and obtain cc’s samples from its ordinary Ring-LWE oracle, followed by the invertible tt map. Every still-real target incoming to cc depends only on known lower secrets, so the reduction adds it to the oracle’s masked component. All outgoing hints involving the unknown scs_c have higher recipients and are already uniform. No unknown target is evaluated. Zero parents and honest gallery messages are simulated by the same operation.

For a query-preparation reservation, expose the oracle’s uniform aa using a fresh programmed XOF input and keep its zero-message ciphertext component hidden. Programming samples the complete conditional byte stream, including rejected candidates, discarded high bits, and later suffix, so the real-oracle distribution equals that of the actual seeded parent. Prequeries and repeated fresh inputs cost δX\delta_X. Retained preparations use only aa and public assets. At unique issue the policy fixes its message without inspecting that component. In the uniform-oracle case, translation by this adaptive message preserves conditional uniformity. Each projected row has the same number of preimages. The real-oracle case gives exactly the projected parent marginal.

Public arithmetic, terminal conversion, hashes, and signatures are postprocessing of these simulated samples. Namespaces are computed from their actual bytes in each hybrid. The same ideal owner and causal policy interfaces continue all later events. Hence the adjacent gap is at most εc(Mc,τc)\varepsilon_c(M_c,\tau_c).

When all recipients are uniform, every exposed first component is independent of the data/query messages. A common simulator maintains public ledgers, generation/head names, bindings, and public evaluations from the declared actions and leakage. Ideal owners receive their respective exact private answers. Compatibility gives the same distribution of the next public transition. The simulator never decodes uniformized results. Summing adjacent gaps bounds each world’s distance to this common view. The triangle inequality gives Equation (21).

The two structural requirements are essential to this reduction. Secret-dependent same-key targets are not covered by the descending-recipient argument and require a separate key-dependent-message security argument. Issuing a reserved parent twice lets two chosen messages share one mask/error, revealing their difference. Independent recipients and one-use issuance remove these obstacles in the stated construction.

Key Lifetimes and Composition

For gadget width k=⌈log⁡3Q⌉k=\lceil\log_3 Q\rceil, fresh gallery parents AgA_g, and query-preparation reservations TqT_q, the sequential per-recipient sample budgets are

M0=1+Tq,Mv=1+2k(0<v<L),M_0=1+T_q,\qquad M_v=1+2k\quad(0<v<L),
ML=1+2k+Ag,Mf={1+2kpair,1+kmixed.(22)M_L=1+2k+A_g,\qquad M_f= \begin{cases} 1+2k & \text{pair},\\ 1+k & \text{mixed}. \end{cases} \tag*{(22)}

Tensor has no final role. With gng_n gallery groups, one encryption per feature and group gives Ag=gndA_g=g_n d at initial setup. Across JgJ_g generations reusing the graph and admitting at most TgenT_{\mathrm{gen}} fresh reservations per generation, use Tq≤JgTgenT_q\le J_gT_{\mathrm{gen}} and count every fresh gallery reencryption. Reconstruction that only republishes existing encrypted assets and truthful local correction create no new HE parent by themselves. The budget counts abandoned and unused reservations as well as issued queries.

a) Security-parameter interpretation: Theorem 5.2 is a finite reduction, stated for arbitrary admissible parameters and lifetime budgets. For a family indexed by λ\lambda with polynomially many recipients and polynomial lifetime budgets, it establishes negligible privacy advantage if the actual Ring-LWE sample games and the authentication primitives have negligible advantages, the aggregate coupling terms are negligible, and complete simulation time is polynomial. The Ring-LWE assumption must hold for the chosen ring, modulus, secret and error distributions, and sample budgets. No numerical hardness estimate is needed to state this conditional result. For example, choosing ρ≥λ+⌈log⁡2Csamp⌉\rho\ge\lambda+\lceil\log_2 C_{\mathrm{samp}}\rceil makes δcut≤2−λ\delta_{\mathrm{cut}}\le2^{-\lambda}. The seed/name length κ\kappa must likewise accommodate the lifetime counts in Equations (18)–(19). These statistical budgets do not assign a computational security level to a fixed Ring-LWE tuple.

A deployment with cryptographic confidential channels or an encrypted plaintext-cache transfer adds their multi-session distinguishing and authentication terms. Faithful enrollment and nonrollback owner state are explicit execution assumptions, rather than consequences of Ring-LWE.

Key-Capped Terminal Representation

Pointwise Rounding and Conservative Fallback

We round complete results from computation modulus qcq_c to wire modulus pp, retaining tt and using ⌈log⁡2p⌉\lceil\log_2 p\rceil bits per coefficient. Let BB bound the complete integer phase, including scores and noise. The baseline uses (qc,B)=(Q,Bν)(q_c,B)=(Q,B_\nu) from Equation (12). § 7 uses qc=Pq_c=P with its own complete-phase bound. Let ww be the decryption multiplier vector from Equation (11). Its aggregate coefficient norm Λ=∑i∥wi∥1\Lambda=\sum_i\lVert w_i\rVert_1, summed over terminal components, measures rounding-error amplification.

Choose an odd wire modulus 1<p<qc1 < p < q_c with p≡qc(modt)p \equiv q_c \pmod t. For a canonical coefficient 0≤c<qc0 \le c < q_c, select the nearest integer to (p/qc)c(p/q_c)c in c+tZc+t\mathbb{Z}, rounding halfway ties upward:

rp(c)=t⌊2(pc−qc(c mod t))+qct2qct⌋+c mod t.(23)r_p(c)=t\left\lfloor\frac{2(pc-q_c(c\bmod t))+q_ct}{2q_ct}\right\rfloor+c\bmod t. \tag*{(23)}

This BGV terminal modulus switching [8] preserves rp(c)≡c(modt)r_p(c)\equiv c\pmod t. Eligible integers are spaced tt apart, giving ∣rp(c)−(p/qc)c∣≤t/2\lvert r_p(c)-(p/q_c)c\rvert\le t/2. The wire stores rp(c) mod pr_p(c)\bmod p.

Lemma 6.1 (Whole-phase terminal correctness): Suppose an authorized source terminal has centered phase lift vv with ∥v∥∞≤B<qc/2\lVert v\rVert_\infty\le B<q_c/2. If

B′=⌈pB/qc⌉+⌈tΛ/2⌉<p/2,(24)B'=\lceil pB/q_c\rceil+\lceil t\Lambda/2\rceil<p/2, \tag*{(24)}

then the reduced terminal has the same plaintext at every coefficient.

Proof. Let CC be the integer canonical component lifts. Then

∑iCiwi=v+qck0,\sum_i C_iw_i=v+q_ck_0,

with carry polynomial k0∈Rk_0\in R. Set C~i=rp(Ci)\widetilde{C}_i=r_p(C_i) coefficientwise and

v′=∑iC~iwi−pk0.v'=\sum_i\widetilde{C}_iw_i-pk_0.

The rounding errors have coefficient bound t/2t/2, so ∥v′∥∞≤pB/qc+tΛ/2\lVert v'\rVert_\infty\le pB/q_c+t\Lambda/2. The canonical wire phase is congruent to v′v' modulo pp. Equation (24) makes v′v' its unique centered lift. Since each rounded lift preserves its residue modulo tt and p≡qc(modt)p\equiv q_c\pmod t, v′≡v(modt)v'\equiv v\pmod t. Individual wire components need not preserve that residue. The argument applies to the complete phase including its carries. □

The guard prevents wraparound modulo pp. Appendix D illustrates both terms of B′B' and distinguishes rounded lifts from stored residues.

At setup, privately compare Λ\Lambda with the public type-specific cap Λλ⋆\Lambda^\star_\lambda (Appendix B). Select the smaller wire profile if it passes, otherwise the worst-case fallback. Bind the type and profile in K\mathcal{K} and enrollment, without resampling the key. Both profiles satisfy Equation (24) for every authorized query at their admitted keys, without independence assumptions on ciphertexts or rounding errors. A failed cap selects a larger response without a decryption failure.

A pair can instead select a profile per response using a public residual certificate, a sufficient rounding-error check under an admitted key-support bound, not an execution-authentication proof. Enrollment fixes the permitted profiles, selection rule and support cap. For canonical component polynomials cic_i, form the residual bounds ρi=⌈∣rp(ci)−(p/qc)ci∣⌉\rho_i=\lceil\lvert r_p(c_i)-(p/q_c)c_i\rvert\rceil coefficientwise. Let TopSum⁡K\operatorname{TopSum}_{K} sum the KK largest entries, where K∈{0,…,N}K\in\{0,\ldots,N\} is the registered support cap. At a ternary recipient with ∥sf∥1≤K\lVert s_f\rVert_1\le K, the sufficient guard is

2(⌈pB/qc⌉+∥ρ0∥∞+TopSum⁡K(ρ1))<p.2\left(\lceil pB/q_c\rceil+\lVert\rho_0\rVert_\infty+\operatorname{TopSum}_{K}(\rho_1)\right)<p.

Negacyclic shifts use at most KK residual entries in each phase coefficient. Appendix F proves the certificate. A conservative fallback from Lemma 6.1 makes the registered selector a total function on canonical inputs of the enrolled shape. One profile must pass every group and bind the complete signed body, without changing KK. Malformed frames are rejected publicly. Totality also holds on uniformized hybrid inputs, without asserting their plaintext correctness.

Profile Exposure and Privacy

For pair terminals, Λ=1+∥sf∥1\Lambda=1+\lVert s_f\rVert_1. Choose a public threshold Ks>2N/3K_s>2N/3. Since ∥sf∥1\lVert s_f\rVert_1 is Bin⁡(N,2/3)\operatorname{Bin}(N,2/3), Hoeffding bounds the fallback probability by

δ0≤exp⁡(−2(Ks−2N/3)2/N).\delta_0\le\exp\left(-2(K_s-2N/3)^2/N\right).

Appendix B gives the corresponding mixed/ten­sor bounds. The bound concerns public profile exposure, not computational Ring-LWE hardness. A profile predicate is evaluated once without resampling the key.

Corollary 6.2 (Profile selection and adaptive privacy): Predeclare the terminal types and a maximum fresh-key lifetime. Let K\mathcal{K} index the allowed fresh family/type pairs, with terminal-type index ν(ξ)\nu(\xi) for pair ξ\xi. Bound lifetime profile exposure by

Δcap=∑ξ∈Kδν(ξ).\Delta_{\mathrm{cap}}=\sum_{\xi\in\mathcal{K}}\delta_{\nu(\xi)}.

Count each distinct pair once, including allowed pairs when their actual exposure is adaptive. Reusing an already exposed pair adds no event. The key-capped protocol retains the integrity bound of Lemma 5.1 and satisfies

Adv⁡priv≤2(εauth+∑vεv+δX+δnames+δcut+Δcap).(25)\operatorname{Adv}_{\mathrm{priv}}\le2\left(\varepsilon_{\mathrm{auth}}+\sum_v\varepsilon_v+\delta_X+\delta_{\mathrm{names}}+\delta_{\mathrm{cut}}+\Delta_{\mathrm{cap}}\right). \tag*{(25)}

Proof. Both actual profiles decode exactly by Lemma 6.1, so the integrity argument is unchanged. For privacy, we first idealize authorized private completion and couple actual selection to a virtual always-capped public profile with ideal private completion. Outside any exposed bad-cap event the public trace is identical, so the one-world statistical distance is at most Δcap\Delta_{\mathrm{cap}}. The virtual owner uses ideal answers even on keys that would require fallback, without decoding their reduced terminals. We apply the recipient-hybrid argument from Theorem 5.2’s proof to this virtual protocol with its unchanged, unconditional secret distributions. The reduction does not condition a Ring-LWE challenge on passing a secret predicate. All compression is public postprocessing. The two-world triangle inequality adds 2Δcap2\Delta_{\mathrm{cap}}. The union bound covers shared-key correlations. □

Theorem 6.3 (Retention-preserving security composition): Fix arithmetic parameters, terminal types and wire profiles satisfying Theorem 4.4’s correctness hypotheses, and finite lifetime budgets. Under the execution model and primitive assumptions of Theorem 5.2 and Corollary 6.2, the key-capped protocol maintains Definition 4.3’s invariant except with probability

Pr⁡[∃τ:¬Inv⁡ret(τ)]≤εauth+δnames.(26)\Pr[\exists\tau:\neg\operatorname{Inv}_{\mathrm{ret}}(\tau)]\le\varepsilon_{\mathrm{auth}}+\delta_{\mathrm{names}}. \tag*{(26)}

For causally L\mathcal{L}-compatible adaptive policies, its privacy advantage is bounded by Equation (25) over the same lifetime. Retained recomputation, edits, and worker replacement introduce no additional term, provided all fresh samples, signing generations, and exposed family/type pairs are counted in the stated games and budgets. Proof. Outside the authentication, binding, and name-collision events of Lemma 5.1, Lemma 4.2 proves the first invariant clause. Whole-result binding and consumption before completion prove the second. Theorem 4.4, Lemma 4.1, and the pointwise terminal bound prove the third under either selected profile. The specified edit and reconstruction transitions prove the fourth, including revocation of old pending originals and the transfer of unused objects rather than reconstruction of private capability from public records.

These clauses justify ideal private completion before recipient hybrids. Unique issuance exposes each delayed parent first component once, and exact current answers drive later adaptive policies. Recomputing from public assets is postprocessing, not a fresh sample. Corollary 6.2 charges selection once per allowed family/type pair. Retention and reconstruction therefore add no loss.

Retained Joins at a Smaller Modulus

Expansion at QQ precedes a retained ciphertext–ciphertext join at P<QP < Q. Ordinary BGV modulus switching [8], [9] can incur rounding loss that prevents a useful smaller PP. Our compiler invariant permits a simultaneous bound valid after adaptive query and reservation selection, while preserving the original’s completion authority.

Split Construction and Retained Equality

For the split join, choose 1<P<Q1 < P < Q with integer ratio a=Q/P>1a = Q/P > 1 odd, a≡1(modt)a \equiv1 \pmod{t}, and gcd⁡(t,Q)=1\gcd(t,Q) = 1. Thus P≡Q(modt)P \equiv Q \pmod{t}. Write x=xz(q)x = x_z(q) and Cj(x,z)=Expand⁡(x,az)jC_j(x,z) = \operatorname{Expand}(x,az)_j for a complete source leaf. Denote by rQ→Pr_{Q\to P} the unreduced integer rounding map of Equation (23), extended to integer inputs. It preserves residues modulo tt, has residual magnitude at most t/2t/2, and satisfies rQ→P(c+Qk)=rQ→P(c)+Pkr_{Q\to P}(c + Qk) = r_{Q\to P}(c) + Pk for integers c,kc,k. Lemma 3.1 gives

Cj(x,z)=Cj(0,z)+(δj,0)(modQ),δj=Nxj‾ QC_j(x,z) = C_j(0,z) + (\delta_j,0) \pmod{Q}, \qquad\delta_j = \overline{N x_j}^{\,Q}

where u‾ Q∈{0,…,Q−1}\overline{u}^{\,Q} \in\{0,\ldots,Q-1\} is the canonical residue and δj\delta_j is inserted at coefficient zero. Define on canonical lifts, coefficientwise,

Uj(z)=(rQ→P(Cj0(0,z)),rQ→P(Cj1(0,z)))(modP),γj(x)=rQ→P(δj)(modP),Lj(x,z)=Uj(z)+(γj(x),0)(modP).(27)\begin{aligned} U_j(z) &= (r_{Q\to P}(C_{j0}(0,z)),r_{Q\to P}(C_{j1}(0,z))) \pmod{P},\\ \gamma_j(x) &= r_{Q\to P}(\delta_j) \pmod{P},\\ L_j(x,z) &= U_j(z) + (\gamma_j(x),0) \pmod{P}. \tag*{(27)} \end{aligned}

Here UjU_j is the retained seed-only pair, γj\gamma_j is the late rounded scalar, and LjL_j is the completed query leaf. This enrolled circuit generally differs from rounding Cj(x,z)C_j(x,z) as a whole, since rounding is not additive. The incomplete UjU_j is never privately decoded and has no fresh-phase bound. The late first component cancels the mask to yield the bounded complete phase.

Encrypt each gallery feature freshly at PP under the same integer secret polynomial sgs_g, with fresh randomness, giving Bj∈RP2B_j \in\mathbb{R}_P^2. Final hints also use modulus PP, with targets sgs_g, sg2s_g^2 and recipient sfs_f. The seed-only database join is Tz=∑j<dUj(z)⊗BjT_z = \sum_{j<d} U_j(z) \otimes B_j. Its completed value obeys the exact identity

∑j<dLj(x,z)⊗Bj=Tz+(∑j<dγjBj0,∑j<dγjBj1,0).(28)\sum_{j<d} L_j(x,z) \otimes B_j = T_z + \left(\sum_{j<d} \gamma_j B_{j0},\sum_{j<d} \gamma_j B_{j1},0\right). \tag*{(28)}

The unchanged quadratic component is switchable during preparation. For a pair terminal, the linear component is switched after the late update. Both moduli, gadget radices, graph, scalar map, terminal type and codec are enrolled in KK. An original authorizes this complete circuit once.

Query-Independent Rounding Family

A catalog bundles authenticated public assets for a fresh key family, including hints and the encrypted index. An admitted catalog fixes a base KK. Worker reconstruction reuses it under a new GG. The owner’s internal lifecycle controller fixes positive integer limits CC on catalog draws and HH on query-preparation reservations per catalog, including failed, unused and retired draws. The source fixes the expansion graph and join profile, then samples sgs_g with independent uniform ternary coefficients, independently of its pre-draw history. Here gg indexes the graph’s gallery recipient, equal to LL in the sequential graph. Let A\mathcal{A} collect all hint second components, sampled independently of the secrets. The implementation also supports a blocked graph, grouping one or two adjacent expansion levels under one new recipient while preserving the sequential extraction map (Appendix E). Both compilers decompose only the input second component. The recurrence uses these digits, hint second components and public signed automorphisms or monomial maps, never first components, errors or query bits. Thus, for every honestly reserved seed zhz_h, its leaf’s second component is

Cj1(h):=Cj1(0,zh)=fj(A,zh,graph⁡),(29)C_{j1}^{(h)} := C_{j1}(0,z_h) = f_j(\mathcal{A},z_h,\operatorname{graph}), \tag*{(29)}

Here fjf_j is the deterministic public recurrence, and the mask family (A,z1,…,zH)(\mathcal{A},z_1,\ldots,z_H) is independent of sgs_g. Seed expansion uses only its fixed domain, seed, public dimensions and layout, modulus and counter, never a secret-dependent catalog hash.

There are no free resets, peer-selected seeds or searches using sgs_g. Final-recipient admission does not filter sgs_g. A graph or join-modulus change requires a fresh charged catalog and sgs_g. Enrolled wire-profile selection leaves this circuit unchanged. These constrain honest sampling, not secret-coefficient independence after public observations or slot selection. The reservoir is the conceptual family of all HH permitted reservation seeds per catalog, sampled independently of sgs_g. A run need only generate its consumed prefix. Unlike Section VI’s larger-profile fallback, a failed setup cap on the final recipient may abort its charged catalog without refund. This admission check precedes any per-response residual selection. We couple admission to a virtual source that always admits the unconditioned final recipient and uses ideal completion. Transcripts agree outside failed caps. Counting aborted draws, at most Cδ0C\delta_0 per world enters Δcap\Delta_{\mathrm{cap}}. This extends Corollary 6.2’s profile coupling without oracle conditioning or within-catalog retries.

We recompute Equation (22)’s sample counts for the enrolled graph, charging every fresh zero parent, hint column, gallery parent and reservation to its recipient. Each direct-PP sample requires a distinct source-QQ oracle call.

Lemma 7.1 (Simultaneous rounding under adaptive selection): For reservation hh and feature leaf j<dj<d, suppress (h,j)(h,j) in the residual notation and let ϵi=rQ→P(Cj1,i(h))−(P/Q)Cj1,i(h)\epsilon_i=r_{Q\to P}(C^{(h)}_{j1,i})-(P/Q)C^{(h)}_{j1,i}, ρi=⌈∣ϵi∣⌉\rho_i=\lceil|\epsilon_i|\rceil, S2=∑iρi2S_2=\sum_i\rho_i^2 and M=max⁡iρiM=\max_i\rho_i. Thus MM bounds the largest residual and S2S_2 bounds their squared weight sum. For tail parameter ℓJ>0\ell_J>0, bound convolution magnitudes by

Z=⌈MℓJ+M2ℓJ2+12ℓJS23⌉.(30)Z=\left\lceil\frac{M\ell_J+\sqrt{M^2\ell_J^2+12\ell_JS_2}}{3}\right\rceil. \tag*{(30)}

Under the source sampling assumptions above, every coefficient of the error polynomial ϵ∗sg\epsilon^*s_g for every honestly reserved feature leaf is bounded by its corresponding ZZ, except with probability at most

δJ=2CHdNe−ℓJ.(31)\delta_J=2CHdNe^{-\ell_J}. \tag*{(31)}

Here ∗* denotes negacyclic convolution. The event covers adaptive binary queries and selection of reserved slots.

Proof. For one catalog, we condition on its pre-draw history, fixed graph and independent mask family. A coefficient of ϵ∗sg\epsilon*s_g is a signed sum of independent mean-zero ternary variables with fixed weights ϵi\epsilon_i. Its variance is at most 2S2/32S_2/3 and each summand has magnitude at most MM. Bernstein’s two-sided bound is

2exp⁡(−Z24S2/3+2MZ/3)≤2e−ℓJ.2\exp\left(-\frac{Z^2}{4S_2/3+2MZ/3}\right)\leq2e^{-\ell_J}.

For M=0M=0 the coefficient is zero. We apply a union bound over reservations, features and coefficients, remove conditioning, then sum unconditional catalog bounds. We do not condition these bounds on later secret-dependent choices. Only the dd join leaves contribute. Coefficients and leaves need not be independent. Queries change only first components and all honest slots are covered, so adaptive selection adds no failure event and requires no assumption about the resulting conditional secret distribution. □

For a target λ>0\lambda>0, choosing ℓJ≥λln⁡2+ln⁡(2CHdN)\ell_J\geq\lambda\ln2+\ln(2CHdN) gives δJ≤2−λ\delta_J\leq2^{-\lambda}. Dependence between reused secrets and residuals can invalidate average-case noise estimates [10]. The property used here is the explicit recurrence (29) and finite honest family. Bernstein and the union bound themselves are standard.

Complete Phase and Security Composition

Let βQ,βP≥2\beta_Q,\beta_P\geq2 be the source and final gadget radices. The selected query coefficient has phase bound Fo=min⁡(α,t−α)+tηF_o=\min(\alpha,t-\alpha)+t\eta from Equation (8). Put kQ=log⁡βQQk_Q=\log_{\beta_Q}Q and SQ=tNηkQ(βQ−1)S_Q=tN\eta k_Q(\beta_Q-1) for one source switch. A two-level block maps an incoming switching-error bound VV to 4(V+SQ)4(V+S_Q), no larger than the sequential 4V+6SQ4V+6S_Q. It preserves the extraction operator, so complete source leaves admit EQ=NFo+2(N−1)SQE_Q=NF_o+2(N-1)S_Q in either graph. Appendix E gives the maps. Let Z∗Z_* be an enrolled upper bound on every ZZ in the finite family, including as-yet undrawn reservations, not merely an observed maximum. M≤⌈t/2⌉M\leq\lceil t/2\rceil and S2≤N⌈t/2⌉2S_2\leq N\lceil t/2\rceil^2 give a uniform choice. The final-switch error bound is SP=tNη⌈log⁡βPP⌉(βP−1)S_P=tN\eta\lceil\log_{\beta_P}P\rceil(\beta_P-1). Define the complete split-leaf and joined-pair bounds by

EJ=⌈PEQ/Q⌉+t+Z∗,BJ=Nd(1+tη)EJ+2SP.(32)E_J=\left\lceil P E_Q/Q\right\rceil+t+Z_*, \qquad B_J=Nd(1+t\eta)E_J+2S_P. \tag*{(32)}

The leaf bound adds scaled source phase, two first-component rounding errors and the secret-weighted residual. Joining dd gallery columns and switching two tensor components gives BJB_J.

The final wire modulus is p<Pp<P, distinct from the join modulus. Section VI applies with qc=Pq_c=P and complete bound BJB_J: for example, ⌈pBJ/P⌉+⌈tΛ/2⌉<p/2\lceil pB_J/P\rceil+\lceil t\Lambda/2\rceil<p/2 suffices. A registered public-residual selector checks every complete group, binds one profile and whole extent before signing, and has a total conservative fallback on canonical inputs. For support cap KK, registering pfp_f with

⌈pfBJ/P⌉+(K+1)⌈t/2⌉<pf/2\lceil p_fB_J/P\rceil+(K+1)\lceil t/2\rceil<p_f/2

ensures totality by the residual guard of Section VI, even on canonical hybrid inputs. It does not assert that hybrid phases obey BJB_J. Selection does not consult private decoding success.

Theorem 7.2 (Retention-preserving split join): For the pair-terminal split construction, assume the ring and extraction conditions of Section III and the source sampling assumptions of Lemma 7.1. Let EQE_Q be a valid complete source-leaf phase bound and Z∗Z_* an enrolled uniform upper bound on Equation (30) over all allowed reservations. For BJB_J in Equation (32), assume 2BJ<P2B_J<P, enrolled terminal conversion exact for phases bounded by BJB_J, and the custody, prescribed-execution, truthful-history, monotone-consumption and observation premises of Theorem 6.3. Replacing its expansion and join by Equations (27)–(28) preserves its authorized current-output invariant except with additional probability δJ\delta_J. Its adaptive privacy bound gains at most 2δJ2\delta_J. All sample and exposure budgets are recomputed for the actual enrolled graph and charged lifetime, using ordinary Ring-LWE games at QQ.

Proof. For integer component lifts, the complete source identity is Cj0(0,z)+δj+Cj1(0,z)sg=v+QkC_{j0}(0,z)+\delta_j+C_{j1}(0,z)s_g=v+Qk with carry k∈Rk\in R and ∥v∥∞≤EQ\lVert v\rVert_\infty\leq E_Q. Scale it by P/QP/Q. The split phase differs by the two first-component residuals of magnitude at most t/2t/2 and ϵ∗sg\epsilon*s_g, giving EJE_J outside the lemma’s event. Subtracting PkPk and using P≡Q(modt)P\equiv Q\pmod t preserves its plaintext. Gallery phases have bound 1+tη1+t\eta. Their join and two final switches give BJB_J. The strict guard makes centering unique. The enrolled terminal certificate, telescoping edit repair and serialized release give exact current answers. Spend-before-completion and revocation preserve one-use authority.

In each privacy world, first couple private completion to its exact authorized ideal output, paying δJ\delta_J. Then apply the descending recipient hybrids of Theorem 5.2. The public terminal selector is total, including fallback, on each hybrid’s own canonical inputs. No statistical phase claim about hybrid ciphertexts is needed. Scaling an ordinary QQ sample by the invertible tt map gives the required scaled-error distribution. Reducing a fresh such sample modulo P∣QP \mid Q gives exactly a fresh direct PP sample under the same integer secret. Uniform samples remain uniform with equal numbers of preimages. Every direct PP sample uses a separate QQ oracle call, distinct from exposed QQ samples. Earlier-recipient target shifts commute with reduction, so the mixed-modulus graph introduces no key cycle. The two-world inequality adds 2δJ2\delta_J to the existing authentication, naming, sampler, seeded-mask and final-admission terms. Concrete randomness and XOF substitutions retain their separate obligations. □

Implementation and Evaluation

Construction Profiles and Timing Boundary

The prototype implements the BGV arithmetic and retained construction in custom Python/C++ code, including independent-recipient switching, native completion, and authenticated terminal encoding. A construction profile fixes arithmetic, retained state, wire-profile policy and completion path. We compare three: Q120 evaluates at a 120-bit source modulus, P64 joins at a 64-bit modulus using a deterministic worst-case rounding bound, and P60 joins at a 60-bit modulus using the simultaneous statistical bound of Section VII. All use blocked independent-recipient expansion and the same dimensions and packing layout: N=16384N = 16384, d=512d = 512, two groups, and 32,768 ordered binary records. Q120 and P64 use a fixed 24-bit terminal codec. P60 uses a 116-bit source modulus, a 60-bit join modulus, t=1031t = 1031, error parameter η=21\eta= 21, source radix 2302^{30}, and final radix 2202^{20}. Its public residual selector chooses among prescribed 23-, 24-, and 25-bit representations. The honest family declares C=10C = 10 catalogs and H=16H = 16 reservation seeds per catalog, counting failed and unused draws. These budgets are premises on honest construction, rather than a limit on arbitrary adversarial processes.

Each profile creates a fresh source, transfers and verifies its complete signed seeded catalog, imports the assets and prepares two independent slots consumed by distinct queries. The paid time is wall-clock time from before source creation through finalization and cleanup of native handles, transports and threads. It covers this two-query workload, not the permitted key lifetime. Setup has five framed transfers: the signed publication, public keys, switching hints, seeded index, and ordered identifiers. Input-fixture acquisition and independent plaintext correctness checks are outside the measured interval. No profile receives cloned source custody or free preparations.

Measurements use a Linux Ryzen 7 5800X host with eight physical cores and sixteen logical CPUs, including asset and result exchange over unpaced local Unix sockets. A cohort runs all three profiles once. One calibration freezes the execution policy before three held-out cohorts with rotated profile order.

Complete Costs and Representation

Table 1 shows that P60’s reduced source construction, import, and public evaluation costs survive its additional preparation and private-path costs in this two-query workload. The median within-cohort Q120/P60 paid ratio is 1.237 [1.229, 1.262].

ProfilePrep. (s)Public (ms)Private (ms)Paid (s)
Q120 fixed243.514217.62525.07912.159
P64 fixed247.205213.31225.14514.228
P60 residual4.635116.15539.6359.825

Table 1. Medians across three held-out cohorts. Preparation is the total for two preparations. Public and private entries are medians of the cohort means over two queries. Public includes evaluation and exchange. Private includes authorization, completion, and ranking. Paid covers the complete workload, including setup and cleanup.

Implementation Soundness

P64/P60 is 1.443 [1.438, 1.464]. These are three paired ratios and their full observed ranges, rather than ratios of table medians or confidence intervals. After preparation, first-answer latency runs from the start of query issuance to delivery of its authorized ranked output. It is 243.878 ms, 239.789 ms, and 156.139 ms for Q120, P64, and P60. The paired first-answer ratios are 1.569 and 1.536, respectively. Preparation remains slower than Q120, and authorization, private completion, and ranking are slower than both controls.

Actual setup wire uploads are 300.75 MiB, 186.56 MiB, and 186.06 MiB. Every observed P60 response selects 24 bits, giving the same 192 KiB encrypted body as both controls. Its authenticated wire profile adds 100 bytes to the framed signed response relative to both controls. The current native gallery stores 256 MiB of residue payload for P60 versus 512 MiB in the two controls. The latter extents follow their frozen 64-bit-word layouts. Peak retained residue payload for two preparations is 1.5 MiB versus 3.0 MiB. These figures describe native residue storage, excluding process overhead, rather than peak process memory or seeded wire sizes.

Arithmetic, retained state, wire profiles and completion paths differ, so this is not a pure modulus ablation. A stronger capped Q120 residual codec can produce a 23-bit, 184 KiB body, 8 KiB smaller than the observed P60 body. It is not the paid control here. Packing P64’s two residues into 32-bit arrays could also match P60’s gallery payload. The comparison establishes neither optimality nor amortization at other query counts, and does not show an advantage over permitted plaintext retention. It measures CPU execution, not WAN, GPU, or attested deployment latency. With ℓJ=111\ell_J = 111, the declared reservoir gives statistical correctness bound δJ<2−128\delta_J < 2^{-128}. Computational security remains conditional on the stated Ring-LWE family.

Implementation Soundness

Completion authenticates the whole result and profile, rejects noncanonical encodings and durably consumes the original before decoding. Separate functional tests cover repair across edits, edits concurrent with completion, plaintext-cache handoff and retirement of cache-superseded results without decoding. They exercise the baseline and Appendix G’s variant, which replaces issue-head equality with live correction authority rather than preserving the unchanged baseline invariant. The timed comparison instead uses a fixed head without edits or cache races. These tests do not replace the proof’s execution-integrity and observation assumptions.

Related Work

Encrypted Search and Retained Preparation

HERS [11] searches encrypted compressed embeddings. PPMI [12] caches encrypted representations and studies query transformations and update-related invalidation. Litchev and Ouyang [13] accelerate binary Hamming-distance evaluation using carry-separated Paillier encoding, lookup encryption, reduced-exponent decoding and CUDA. Beyond encrypted similarity and reusable representations, our functionality requires exact current scores with row-index tie breaking under changing completion authority.

ZipPIR [2] moves encrypted computation offline and reconstructs server hints after database updates without client interaction. FlashPIR [3] prepares message-independent key switching for expansion, folding and packing, using each offline seed once. Offline affine decomposition and one-query seeds therefore have predecessors. Our invariant specifies what survives edits or executor replacement without renewing issuance rights, and which current owner state authorizes completion. The smaller-modulus construction bounds the completed split join, retaining its quadratic tensor while separately rounding the late first-component correction.

Evaluation Integrity and Current Completion

Viand et al. [1] analyze FHE integrity and reaction attacks. The later vFHE framework [5] provides integrity tools and comparisons. Argos [4] verifies FHE execution on commodity hardware, binding inputs and multi-round transcripts and checking results before decryption, separately from secret-key custody. Slalom [14] combines trusted hardware, masked delegation and randomized verification. Our executor adopts this established boundary, not a stronger attestation primitive.

BioZKFHE [15] combines encrypted similarity, specialized BGV packing, public verification and committee-governed release. Current authenticated data already underlies verifiable retrieval and updates [6], IntegriDB’s query verification against a current digest [7], and Hyperproofs’ dynamic vector-commitment proofs [16]. Our construction combines immutable-base encrypted evaluation and owner-side repair with one-use projected issuance, consumption before private arithmetic and serialized current release. AGATE [17] provides a general attested-functionality framework. Our result specifies the custody and observation obligations for this search protocol.

Noise Bounds and the Completed Join

BGV [8] supplies leveled key switching and compatible modulus conversion. Biasioli et al. [9] analyze secret-weighted rounding and key dependencies using uniform-residual and central-limit approximations under a rounding-dominance condition. Gao and Zheng [10] identify failures of independence and Gaussian assumptions under shared keys and ciphertext reuse. ILA [18] proves functional correctness through quantitative typing with noise and wraparound bounds. Our deterministic downstream bounds specialize these concerns to the retained circuit.

Our compiler makes second components functions of independent public masks, reserved seeds and fixed maps, not queries or the gallery secret. The bounded honest family then permits simultaneous Bernstein and union bounds over adaptive queries and slots, without assuming independent convolution coefficients or secret-coefficient independence after public observations. Composing this event with completed split rounding and one-use current authority permits a smaller gallery modulus at an explicit statistical cost to the ordinary Ring-LWE reduction. The contribution is this composition, not retention, verification or concentration bounds alone.

Discussion

Security and Execution Scope

The reductions assume faithful source and execution, exclusive nonrollback owner custody, truthful history, and the declared entropy/XOF interfaces. A deployed executor requires sound enrollment and confined computation/signing. Local processes establish neither hardware attestation nor protection against physical or microarchitectural observations of private variable-time arithmetic.

Lifetime budgets include failed and unused key families and reservations. Worker reconstruction, owner restarts and additional controllers cannot reset them. Public recomputation creates no fresh reservation. Concrete public-XOF and private-sampler realizations require justification. Computational security rests on the actual source-modulus Ring-LWE games and lifetime budgets, not statistical tails.

Performance and Ethics

Permitted plaintext caching remains a faster cold-service alternative. Historical-completion and blocked-expansion measurements retain separate scopes (Appendices G and H).

Experiments use synthetic rows and local workloads, not personal records or production services. Outputs are authorized only to an honest owner under the stated model. Deployment outside it can expose sensitive information. These checks do not establish production assurance.

Conclusion

The retention invariant and independent-recipient reduction preserve one-use completion and exact current release. Second-component independence permits simultaneous bounds for completed split joins at a smaller gallery modulus. The implementation reduces end-to-end two-query cost despite slower preparation and private completion, under the stated security and measurement scope.

Section V states the games, hybrid order, and bounds.

Appendix A: Exact Sampling and Public-XOF Simulation

We match the exact sample distributions to Ring-LWE, then simulate complete public byte streams with bounded runtime.

CBD and Scaled Samples

The noise distribution and invertible scaling map specify the oracle-to-ciphertext correspondence. For an arbitrary positive integer η\eta, a coefficient has

Pr⁡[e=j]=2−2η(2ηη+j),−η≤j≤η.\Pr[e=j] = 2^{-2\eta}\binom{2\eta}{\eta+j}, \qquad-\eta\le j \le\eta.

Indeed ∑Ui−∑Vi=∑Ui+∑(1−Vi)−η\sum U_i-\sum V_i=\sum U_i+\sum(1-V_i)-\eta is a centered 2η2\eta-bit binomial. Independent disjoint bit blocks give the joint product distribution. The secret is coefficientwise uniform ternary, including the possibility that independently drawn role secrets have equal values. Role namespaces are distinct. Secret values are not conditioned to differ.

Since tt is invertible modulo QQ, multiplication of both ordinary sample components by tt is a bijection on RQ2R_Q^2. It maps (a,−as+e)(a,-as+e) to (ta,−(ta)s+te)(ta,-(ta)s+te) and uniform pairs to uniform pairs. It therefore gives the scaled-error sample reduction exactly.

Complete Conditional Byte Streams

Conditioning on accepted coefficients must preserve rejected bytes and every later XOF read. Let bQ=bitlength⁡(Q)b_Q=\operatorname{bitlength}(Q) and pacc=Q/2bQp_{\mathrm{acc}}=Q/2^{b_Q}. A width-ww candidate word, with w≥bQw\ge b_Q, contributes its low bQb_Q bits. Values at least QQ are rejected. For a prescribed accepted coefficient c∈[0,Q)c\in[0,Q), sample a geometric rejection count JJ with Pr⁡[J=j]=(1−pacc)jpacc\Pr[J=j]=(1-p_{\mathrm{acc}})^jp_{\mathrm{acc}}, then jj independent rejected low-bit values uniform in [Q,2bQ)[Q,2^{b_Q}). Include independent discarded high bits for every word, including the accepted word, and an independent suffix after the final accepted coefficient.

If the accepted coefficient is also uniform, the probability of a segment with jj specified rejects and one specified acceptance is

(1−pacc)jpacc(2bQ−Q)−jQ−1=(2bQ)−(j+1).(1-p_{\mathrm{acc}})^jp_{\mathrm{acc}}(2^{b_Q}-Q)^{-j}Q^{-1}=(2^{b_Q})^{-(j+1)}.

Including high bits gives exactly the original uniform-word probability. Repeat for all NN coefficients and append the suffix. A direct realization draws candidate words, keeps their rejected words, and replaces only the low bits of the first accepted word by the prescribed cc. This generates the same conditional stream without a second rejection routine for the rejected interval. All later XOF reads see this complete stream. Programming accepted words alone would omit observable randomness. For direct-PP samples, the same construction uses PP in place of QQ.

The domain includes the fixed tag, public role identity, and fresh seed. Over PsP_s fresh invocations and hh adversarial inputs, the union bound for prequeries and seed collisions is (18). Gallery source expansions count even when only the expanded polynomial is published. Republishing an identical asset does not allocate a new programmed input.

Finite Runtime and Sampling Cutoffs

Bounded sampling introduces an abort loss without biasing successful values. Because Q>1Q > 1 is odd, pacc>1/2p_{\mathrm{acc}} > 1/2, and each accepted coefficient needs fewer than two candidates in expectation. Capping every rejection stage at ρ\rho costs at most 2−ρ2^{-\rho} per stage. The conservative CsampC_{\mathrm{samp}} counts both uniform components in all-uniform samples, each conditional parent stream, and secret draws. Apply this coupling once before the recipient chain, with the same distribution of cutoff events in every hybrid. For a finite-set rejection sampler, the abort probability depends on acceptance probability, not on the eventual accepted value. The capped interface can therefore draw that exact value and independently abort, even at an unknown-secret challenge interface.

A fixed-work ternary-key sampler may scan bsb_s two-bit candidates per coefficient, using the first candidate below three and aborting if none exists. For each x∈{−1,0,1}x \in\{-1,0,1\} its subprobability is

Pr⁡[output x]=(1−4−bs)/3.\Pr[\mathrm{output}\ x] = (1-4^{-b_s})/3.

This is exactly uniform ternary coupled to an independent exhaustion event. The union bound over RsR_s fresh role-secret draws is RsN2−2bsR_sN2^{-2b_s}. For the concrete choice bs=96b_s = 96, 16 draws, and N=214N = 2^{14}, it is 2−1742^{-174}. When this interface is used, account for its coupling within the sampler term or as a separate term, once. OS entropy failure and private execution are governed by their explicit interface assumptions.

Key-Norm Cap Bounds

Parameterized Ternary-Key Bounds

Support and spectral tails certify wire profiles over a finite key lifetime. Choose thresholds Ks>2N/3K_s > 2N/3 for ∥s∥1\lVert s\rVert_1 and Us>0U_s > 0 for max⁡ωN=−1∣s(ω)∣\max_{\omega^N=-1}|s(\omega)|, with xs=3Us2/(2N)>1x_s = 3U_s^2/(2N) > 1. Define Js=⌈NKsUs2⌉J_s = \left\lceil\sqrt{NK_sU_s^2}\right\rceil and set

(Λ0∗,Λ1∗,Λ2∗)=(1+Ks, 1+2Ks, 1+Ks+Js).(33)(\Lambda_0^*,\Lambda_1^*,\Lambda_2^*)=(1+K_s,\ 1+2K_s,\ 1+K_s+J_s). \tag*{(33)}

The support and spectral failure budgets are

δH=exp⁡(−2(Ks−2N/3)2/N),δsp=Nxsexp⁡(1−xs).(34)\delta_H=\exp\left(-2(K_s-2N/3)^2/N\right), \qquad \delta_{\mathrm{sp}}=Nx_s\exp(1-x_s). \tag*{(34)}

These quantities depend on the key distribution and the thresholds, rather than on the plaintext modulus or the source ciphertext modulus.

Lemma B.1 (Cap-failure bounds): For fresh ternary roles with independent uniform coefficients, the pair, mixed, and tensor cap-failure probabilities satisfy

δ0≤δH,δ1≤2δH,δ2≤δH+δsp.(35)\delta_0 \le\delta_H,\qquad\delta_1 \le2\delta_H,\qquad\delta_2 \le\delta_H+\delta_{\mathrm{sp}}. \tag*{(35)}

The mixed-type union bound does not require independence between its two role secrets, provided each has the stated marginal distribution.

Proof. For one ternary secret, Hs=∥s∥1=∥s∥22H_s=\lVert s\rVert_1=\lVert s\rVert_2^2 is Bin⁡(N,2/3)\operatorname{Bin}(N,2/3), so Hoeffding gives Pr⁡[Hs>Ks]≤δH\Pr[H_s>K_s]\le\delta_H. This proves pair and, by a union bound, mixed. The Gaussian exponential argument in Appendix C gives

Pr⁡[max⁡ωN=−1∣s(ω)∣>Us]≤Nxse1−xs,xs=3Us22N.(36)\Pr\left[\max_{\omega^N=-1}|s(\omega)|>U_s\right]\le Nx_s e^{1-x_s},\qquad x_s=\frac{3U_s^2}{2N}. \tag*{(36)}

On Hs≤KsH_s\le K_s and the spectral event’s complement, ∥s2∥1≤NKsUs2≤Js\lVert s^2\rVert_1\le\sqrt{NK_sU_s^2}\le J_s by the norm implication proved in Appendix C. The two bad events have union probability at most δH+δsp\delta_H+\delta_{\mathrm{sp}}, proving the tensor-type bound without assuming their independence. □

a) Selecting a statistical error budget: For any target λ>0\lambda>0, sufficient conditions for δν≤2−λ\delta_\nu\le2^{-\lambda} in all three modes are

Ks≥2N3+N(λ+1)ln⁡22,K_s\ge\frac{2N}{3}+\sqrt{\frac{N(\lambda+1)\ln2}{2}},
xs−1−ln⁡xs≥ln⁡N+(λ+1)ln⁡2.(37)x_s-1-\ln x_s\ge\ln N+(\lambda+1)\ln2. \tag*{(37)}

They make each of δH\delta_H and δsp\delta_{\mathrm{sp}} at most 2−(λ+1)2^{-(\lambda+1)}. If a lifetime exposes at most Fmax⁡≥1F_{\max}\ge1 allowed fresh family/type pairs, replacing λ\lambda on the right-hand sides by λ+⌈log⁡2Fmax⁡⌉\lambda+\lceil\log_2F_{\max}\rceil makes their total cap term at most 2−λ2^{-\lambda}. Here λ\lambda controls statistical profile leakage, and the Ring-LWE advantage remains a separate term.

Ternary Spectral Tail

We bound the secret at negacyclic roots, then transfer that bound to the coefficient norm of its negacyclic square. For j≥1j\ge1, the coefficient inequality 2⋅3j−1j!≤(2j)!2\cdot3^{j-1}j!\le(2j)! holds at j=1j=1 and is preserved inductively. Comparison of even power-series coefficients yields (1+2cosh⁡z)/3≤exp⁡(z2/3)(1+2\cosh z)/3\le\exp(z^2/3).

Write s(X)=∑i=0N−1siXis(X)=\sum_{i=0}^{N-1}s_iX^i and let Hs=∥s∥1H_s=\lVert s\rVert_1 count its nonzero coefficients. Use support threshold KsK_s, spectral threshold UsU_s and norm cap Js=⌈NKsUs2⌉J_s=\left\lceil\sqrt{NK_sU_s^2}\right\rceil for s2s^2, as in Appendix B. For ωN=−1\omega^N=-1 and NN even, ∑iω2i=0\sum_i\omega^{2i}=0. Thus the real and imaginary weight vectors are orthogonal with squared norms N/2N/2. For Z=(Re⁡s(ω),Im⁡s(ω))Z=(\operatorname{Re}s(\omega),\operatorname{Im}s(\omega)) and h∈R2h\in\mathbb{R}^2, independence of sis_i gives

Eexp⁡(⟨h,Z⟩)≤exp⁡(N∥h∥22/6).\mathbb{E}\exp(\langle h,Z\rangle)\le\exp(N\lVert h\rVert_2^2/6).

For a standard two-dimensional Gaussian gg and 0<θ<3/(2N)0<\theta<3/(2N), Tonelli and the Gaussian moment identity give

EZeθ∥Z∥22=EgEZe2θ⟨g,Z⟩≤EgeθN∥g∥22/3=(1−2Nθ/3)−1.\begin{aligned} \mathbb{E}_Z e^{\theta\lVert Z\rVert_2^2} =\mathbb{E}_g\mathbb{E}_Z e^{\sqrt{2\theta}\langle g,Z\rangle} \\ &\le\mathbb{E}_g e^{\theta N\lVert g\rVert_2^2/3} =(1-2N\theta/3)^{-1}. \end{aligned}

With xs=3Us2/(2N)>1x_s=3U_s^2/(2N)>1 and θ=(1−1/xs)/(2N/3)\theta=(1-1/x_s)/(2N/3), Markov yields xse1−xsx_se^{1-x_s} per root. A union bound over the NN roots gives (36). Discrete Parseval gives ∥s2∥22≤max⁡ω∣s(ω)∣∥s∥2\lVert s^2\rVert_2^2\le\max_\omega|s(\omega)|\lVert s\rVert_2, using the exact integer negacyclic square. Together with Cauchy–Schwarz, on Hs≤KsH_s\le K_s and max⁡ω∣s(ω)∣≤Us\max_\omega|s(\omega)|\le U_s, this yields

∥s2∥1≤N∥s2∥2≤Nmax⁡ω∣s(ω)∣∥s∥2≤NKsUs2≤Js.\begin{aligned} \lVert s^2\rVert_1\le\sqrt{N}\lVert s^2\rVert_2\le\sqrt{N}\max_\omega|s(\omega)|\lVert s\rVert_2 \\ &\le\sqrt{NK_sU_s^2}\le J_s. \end{aligned}

This proves Lemma B.1’s norm implication without treating square coefficients as independent.

Numerical Certificate for the Experimental Thresholds

For N=16384N = 16384, Ks=11820K_s = 11820, and Us=1100U_s = 1100, the coefficient-norm exponent satisfies 2(Ks−2N/3)2/N>141(347/500)2(K_s - 2N/3)^{2/N} > 141(347/500). Also xs−1>158(347/500)x_s - 1 > 158(347/500), Nxs<(15/16)221Nx_s < (15/16)2^{21}, and ln⁡2<347/500\ln2 < 347/500. The spectral tail is consequently below (15/16)2−137(15/16)2^{-137}, while δH<2−141=(1/16)2−137\delta_H < 2^{-141} = (1/16)2^{-137}. Equation (35) then gives δ0<2−141\delta_0 < 2^{-141}, δ1<2−140\delta_1 < 2^{-140} and δ2<2−137\delta_2 < 2^{-137}. These rational comparisons instantiate the general theorem and are not hypotheses of its proof.

Appendix D: Terminal Conversion: Interpretation and Illustration

The terminal error budget combines scaled source phase and key-amplified rounding. For a terminal with multipliers ww, write its coefficientwise rounding errors as ϵi=rp(Ci)−(p/qc)Ci\epsilon_i = r_p(C_i) - (p/q_c)C_i.

Negacyclic multiplication satisfies

∥ϵiwi∥∞≤∥ϵi∥∞∥wi∥1≤(t/2)∥wi∥1.\lVert\epsilon_i w_i \rVert_\infty\le\lVert\epsilon_i \rVert_\infty\lVert w_i \rVert_1 \le(t/2) \lVert w_i \rVert_1.

Summing over components gives the rounding contribution tΛ/2t\Lambda/2. The converted phase therefore has bound pB/qc+tΛ/2pB/q_c + t\Lambda/2, rounded upward conservatively in Equation (24). For mixed and tensor terminals, respectively, Λ=1+∥sg∥1+∥sf∥1\Lambda= 1 + \lVert s_g \rVert_1 + \lVert s_f \rVert_1 and Λ=1+∥sg∥1+∥sg2∥1\Lambda= 1 + \lVert s_g \rVert_1 + \lVert s_g^2 \rVert_1. The square is the integer negacyclic product. For ternary ss, ∥s∥1\lVert s \rVert_1 counts nonzero coefficients.

Ignoring the ceilings only to interpret the tradeoff, the strict guard is equivalent to p>tΛ/(1−2B/qc)p > t\Lambda/(1 - 2B/q_c). Smaller admitted key norms permit smaller response moduli. Actual profile selection must also satisfy the ceilings and p≡qc(modt)p \equiv q_c \pmod{t}. The original keys, encrypted index, and source modulus qcq_c remain unchanged.

For an arithmetic illustration, take qc=1009q_c = 1009, t=17t = 17, and B=100B = 100. These values are neither proposed security parameters nor benchmark data. Both p=57p = 57 and p=91p = 91 have the same residue as qcq_c modulo tt:

ppΛ\Lambda⌈pB/qc⌉\lceil pB/q_c \rceil⌈tΛ/2⌉\lceil t\Lambda/2 \rceilB′B'Guard
5726172323<28.523 < 28.5
5736263232≮28.532 \not< 28.5
91310263636<45.536 < 45.5

Table 2.

Thus the smaller modulus is certified at Λ=2\Lambda= 2, while Λ=3\Lambda= 3 requires a larger wire profile for this bound. Failure of the sufficient guard does not demonstrate an incorrect plaintext. A certified fallback instead retains exactness, using seven coefficient bits at p=91p = 91 rather than six at p=57p = 57.

The same values also illustrate residue-preserving rounding. For c=100c = 100 and p=57p = 57, the scaled target is (p/qc)c≈5.65(p/q_c)c \approx5.65. Eligible integers are congruent to 15 modulo 17, and the nearest is rp(c)=−2r_p(c) = -2. Its error is about 7.65<17/27.65 < 17/2. The stored value is 55 modulo 57, whose residue modulo 17 differs from that of cc. Lemma 6.1 preserves the plaintext through the complete phase and its carries, rather than through individual stored residues.

Appendix E: Supported Blocked Expansion Graph

We unfold expansion blocks, track injected errors, and verify second-component independence. The smaller-modulus join does not require a new generic expansion compiler. The implemented block graph is obtained by unfolding adjacent levels of the sequential trace and extraction circuit. A block spanning b∈{1,2}b \in\{1,2\} levels has one independent new recipient svs_v. Its output maps on f∈RQf \in R_Q are

Fh(f)=∑uwh,uσu(f),∑u∥wh,u∥1≤2b.F_h(f) = \sum_u w_{h,u}\sigma_u(f), \qquad\sum_u \lVert w_{h,u} \rVert_1 \le2^b.

where hh indexes outputs, uu indexes automorphisms, wh,uw_{h,u} is a signed sum of monomials and σu\sigma_u is a public negacyclic automorphism. Unfolding transforms earlier shifts under later automorphisms, preserving the original output order. The concrete compiler checks the displayed coefficient mass on every assembled map.

For each required σu\sigma_u, switch directly from the block’s input recipient svs_v to, with target σu(s)\sigma_u(s). Hoisting means reusing one decomposition C1=∑j<kQβjQdj mod QC_1 = \sum_{j<k_Q} \beta_j^Q d_j \bmod Q across branches, with canonical coefficientwise digits djd_j. Apply σu\sigma_u to these digits. They reconstruct σu(C1)\sigma_u(C_1) modulo QQ, and their coefficient magnitudes need not match βQ−1\beta_Q - 1. They need not be the canonical digits of the transformed polynomial. No decomposition is distributed over a sum. A switched pair has phase σu(Φs(C))+ϵu\sigma_u(\Phi_s(C)) + \epsilon_u with ∥ϵu∥∞≤SQ\lVert\epsilon_u \rVert_\infty\le S_Q. Public assembly gives

Φsv(C^h)=Fh(Φs(C))+∑uwh,uϵu(modQ).\Phi_{s_v}(\widehat{C}_h) = F_h(\Phi_s(C)) + \sum_u w_{h,u}\epsilon_u \pmod{Q}.

Here C^h\widehat{C}_h is the assembled output. If VV bounds previously injected switching errors, its next bound V′V' satisfies V′≤2b(V+SQ)V' \le2^b(V + S_Q). For blocks of width one or two, this is at most the sequential recurrence 2bV+2(2b−1)SQ2^bV + 2(2^b - 1)S_Q. Beginning at zero injected switch error gives total propagated error at most 2(N−1)SQ2(N - 1)S_Q.

This tracks only the injected errors. It does not claim that incomplete sum-only algebraic traces, sparse restored phases or zero-first leaves have a fresh phase bound. The complete unfolded coefficient operator equals the sequential operator: it cancels uncontrolled projected coordinates and multiplies the selected coordinate by NN. The selected honest query coefficient has magnitude at most F0F_0, giving the complete bound EQ=NF0+2(N−1)SQE_Q = NF_0 + 2(N - 1)S_Q used in Theorem 7.2.

Second-component computation decomposes only the input second component and combines transformed digits with hint second components. Public assembly does not read first components. Induction across blocks thus establishes Equation (29). First-component linearity and the complete extraction operator establish the retained affine identity. Composite hint targets involve an earlier recipient only. Every independently sampled column and zero parent are counted in the actual recipient’s sample budget, including fresh direct-PP gallery and final-hint samples. Changing the block graph changes these budgets and its enrollment. It is not an unaccounted reuse of the sequential sample interface.

a) Exact quotient residuals: For an integer coefficient cc at Q=PaQ=Pa with odd a≡1(modt)a\equiv1\pmod{t}, the rounding map has the equivalent integer quotient form

u=center⁡a((c mod a)t−1 mod a),u=\operatorname{center}_{a}\left((c\bmod a)t^{-1}\bmod a\right),
rQ→P(c)=(c−tu)/a.r_{Q\to P}(c)=(c-tu)/a.

Here center⁡a\operatorname{center}_{a} selects the unique representative in [−(a−1)/2,(a−1)/2][-(a-1)/2,(a-1)/2], and t−1t^{-1} is taken modulo aa. The numerator is divisible by aa. The result is congruent to cc modulo tt, since a≡1(modt)a\equiv1\pmod{t}, and its residual is −tu/a-tu/a with magnitude at most t/2t/2. Thus ρi\rho_i, S2S_2 and MM in Lemma 7.1 are public integer computations on the actual second component. Per-reservation moments may tighten an enrolled certificate, but the measured instance uses a uniform worst-residual bound over the whole honest reservoir. It does not assume uniform residuals or independent convolution coefficients, nor infer a concrete Ring-LWE hardness level from δJ\delta_J.

b) Experimental complete bound: The measured construction profile uses N=16384N=16384, d=512d=512, t=1031t=1031, η=21\eta=21, H=16H=16, C=10C=10 and ℓJ=111\ell_J=111, with

P=1152921504606748673,P=1152921504606748673,
a=72057593002196993,Q=Pa.a=72057593002196993,\qquad Q=Pa.

The uniform residual bound ρi≤516\rho_i\le516 gives Z∗=822828Z_* = 822828 and δJ<2−128\delta_J<2^{-128}. Source radix 2302^{30} and final radix 2202^{20} give complete-leaf bound EJ=1516649E_J=1516649 and joined-pair bound BJ=277700936789622784<P/2B_J=277700936789622784<P/2. Final radix 2302^{30} fails the bound and is excluded. These are statistical correctness allocations, not computational security estimates. The 24-bit terminal modulus selected by the measured P60 profile is p=16767941p=16767941. Its public-residual certificate is evaluated on the actual complete pair.

Appendix F: Public Terminal Residual Certificates

An alternative certificate addresses the terminal rounding loss directly, without changing the complete source-phase bound. It uses the actual public ciphertext coefficients, rather than a tighter estimate of earlier hint errors. The ingredients are residue-preserving modulus switching and an elementary bound on sums of at most KK residual entries. The proposed extension concerns their typed composition with historical evaluation and current one-use release. High-rate constructions based on linear decryption and conversion to additive encryption already address response compression [19], [20]. This extension preserves the existing recipient graph and does not claim an optimal communication rate or a new scheme-conversion primitive.

For a complete pair c=(c0,c1)c=(c_0,c_1), use canonical coefficient lifts and write its bounded phase and integer carry as

c0+c1s=v+qch,h∈R,∥v∥∞≤B<qc/2.c_0+c_1s=v+q_ch,\qquad h\in R,\qquad\lVert v\rVert_\infty\le B<q_c/2.

Let ss be an integer ternary polynomial with at most K∈{0,…,N}K\in\{0,\ldots,N\} nonzero coefficients. For a registered odd 1<p<qc1<p<q_c satisfying p≡qc(modt)p\equiv q_c\pmod{t}, let x=(x0,x1)x=(x_0,x_1) with xi=rp(ci)x_i=r_p(c_i) the nearest unreduced residue-preserving integer lift of (23). Define integer-scaled rounding residuals and their magnitude bounds coefficientwise

ri=qcxi−pci,ρi=∣ri/qc∣.r_i=q_cx_i-pc_i,\qquad\rho_i=\lvert r_i/q_c\rvert.

For a nonnegative vector aa, TopSum⁡K(a)\operatorname{TopSum}_K(a) sums its KK largest entries, with TopSum⁡0(a)=0\operatorname{TopSum}_0(a)=0. It is distinct from the search ranking operator Top⁡3\operatorname{Top}_3. Two public converted-phase bounds are

Ep∗=⌈pB+∥r0∥∞+TopSum⁡K(∣r1∣)qc⌉,E_p^*=\left\lceil\frac{pB+\lVert r_0\rVert_\infty+\operatorname{TopSum}_K(\lvert r_1\rvert)}{q_c}\right\rceil,
Ep=⌈pBqc⌉+∥ρ0∥∞+TopSum⁡K(ρ1).E_p=\left\lceil\frac{pB}{q_c}\right\rceil+\lVert\rho_0\rVert_\infty+\operatorname{TopSum}_K(\rho_1).

Proposition F.1 (Public residual certificate). Ep∗≤Ep≤Ep∗+K+1E_p^*\le E_p\le E_p^*+K+1. If 2Ep<p2E_p<p, the pair x mod px\bmod p has centered phase bounded by EpE_p and the same plaintext as cc.

Proof. The exact integer-ring identity is

x0+x1s−ph=(pv+r0+r1s)/qc.x_0+x_1s-ph=(pv+r_0+r_1s)/q_c.

Each coefficient of r1sr_1s is a signed sum of at most KK distinct entries of r1r_1: negacyclic shifts permute their absolute values. Its magnitude is therefore at most TopSum⁡K(∣r1∣)\operatorname{TopSum}_K(\lvert r_1\rvert). Replacing the residual magnitudes divided by qcq_c by their ceilings adds less than K+1K+1. The scaled source ceiling adds less than one. Comparing the resulting integer ceilings gives the displayed slack. The strict guard gives unique centering. Since xi≡ci(modt)x_i\equiv c_i\pmod{t} and p≡qc(modt)p\equiv q_c\pmod{t}, subtraction of the same integral carry hh preserves the plaintext residue.

With K=NK=N, this certificate holds for every ternary recipient and requires no private support predicate. Moreover, ρi≤⌊t/2⌋\rho_i\le\lfloor t/2\rfloor, so a histogram with 1+⌊t/2⌋1+\lfloor t/2\rfloor bins computes it in O(N+t)O(N+t) time. A registered fallback satisfying

2(⌈pBqc⌉+(K+1)⌈t/2⌉)<p2\left(\left\lceil\frac{pB}{q_c}\right\rceil+(K+1)\left\lceil t/2\right\rceil\right)<p

makes selection a total public function on canonical ciphertext inputs, including uniformized hybrid inputs. Correct decoding additionally requires the stated phase and support bounds. For several output groups, select one registered wire profile that passes every group and sign its policy, group bounds, exact body extent and unchanged historical issue prefix as a whole.

Appendix G: Completion Across Truthful Edits

The baseline admission algorithm retires an original when its issue head is older than the current owner head. We analyze an optional variant in which truthful edits commute with an in-flight immutable-base computation. Exact private repair and current-digest validation have established predecessors in verifiable databases and incremental computation [6], [7], [16]. The question here is whether repair can preserve an already issued projected original without relaxing its historical binding or one-use completion rule.

Let original oo bind query qoq_o, immutable computation KoK_o, generation GoG_o, and historical issue head HoH_o. Its signed prefix remains unchanged. At a serialized release head HeH_e, require the following:

  1. The complete result matches the exact signed original and its immutable base, terminal type, wire profile, and current generation.

  2. The owner spends oo before whole-result private completion. No competing cache answer has released it, and no retired original is restored.

  3. The private query and complete truthful history from D0D_0 to DeD_e remain in exclusive owner custody.

  4. Correction, stable ranking, and release execute under the same release/edit lock at HeH_e.

Generation equality and unchanged assets remain mandatory. Only issue-head equality is replaced by live exact correction authority. Reconstruction, history loss, and a changed base still revoke pending completion.

Proposition G.1 (Edit-commuting completion): Under the arithmetic, source, execution, codec, and owner-state assumptions of Theorem 4.4, the optional transition above releases the exact current-search result at its release head. It invokes private completion at most once per original, including across repeated coordinates and reversions.

Proof. An admitted result is the prescribed encrypted evaluation for the base database, independently of its issue head. Exact whole-result decoding gives v0(qo)v_0(q_o). Applying the base-to-current correction (15) to the complete truthful history UeU_e gives v0(qo)+Δe(qo)=ve(qo)v_0(q_o) + \Delta_e(q_o) = v_e(q_o) by Lemma 4.1. The lock fixes the same ee for repair and release, and ranking with ties broken by row index yields the exact current top three. Consumption precedes private arithmetic. Edits never recreate a spent object, while reconstruction and failure retain monotone retirement. Induction on transitions proves at-most-once completion. □

a) Privacy interface: The edit-only refinement introduces no new encrypted parent, recipient target, or terminal type. Admission still authenticates the historical issue prefix before private arithmetic. Under causally leakage-compatible schedules for the changed transition system, idealization of private completion supplies the exact current ideal answer at release, and the descending recipient hybrids are unchanged. The existing finite loss bound consequently uses the actual fresh sample and profile-exposure budgets. This statement retains the execution, nonrollback, and logical observation premises of the main theorem. When used, the head’s optional heh_e component remains a fresh opaque label, not a hash of the edits. A public hash chain of raw private edits would permit enumeration of low-entropy edits and does not instantiate this interface.

For the split join, apply the same refinement only with the source sampling assumptions and terminal hypotheses of Theorem 7.2. The simultaneous δJ\delta_J event already covers the declared family and is charged once across the trace, rather than anew for an edit or a repeated public evaluation.

Appendix H: Earlier Representation and Lifecycle Evidence

Earlier measurements used two different constructions. Configuration A used same-key switching and therefore needs an auxiliary assumption for its hint columns. Its timings do not instantiate the independent-recipient theorem. A qualified held workload observed post-preparation costs of 12.467 s for an immutable encrypted base with client-side edit correction, 23.667 s for server-side updates under authenticated execution and 35.127 s for the mutable server construction with additional randomized tensor checks. These costs cover the complete subsequent workload, not a single query. These architecture observations include different transport and protocol placement and do not isolate one mechanism. Permitted cache-only service cost 263 ms cold and 55.0 ms prepared.

An earlier independent-recipient pair-service study used 32,768 rows, eleven queries, edits and paced links at 64 MiB/s for setup and 512 KiB/s online. One calibration and three qualified held cohorts checked 198 top-three outputs, including 60 current native completions. Capped terminals saved 8 KiB per reply and improved fresh-query medians by 12.93–18.16 ms for one authenticated full-index response and 5.99–13.41 ms for retained objects framed as an ordered group aggregate. Both require complete authenticated coverage before private completion. Cold-cost ordering was inconsistent and plaintext caching had the lowest full offline cost. These are wire-profile results, not timings for the smaller-modulus join.

A separate six-configuration study uses blocked expansion without a private key-cap test and a public residual codec. It compares completion of an in-flight query across edits, retirement and reissuance after an edit, and permitted plaintext caching. With a controlled post-issue edit and shared 1.25 MB/s downlink (decimal units), three qualified held cohorts give median first answers of 519.962 ms for completion across edits and 1055.238 ms for retirement and reissuance. Each completes privately once, but reissuance requires two public evaluations rather than one. The paired first-answer ratio is 1.973, but end-to-end workloads take 32.451 and 32.171 s, so no end-to-end improvement is established. In the unpaced no-edit condition, cache answers supersede every HE result, which is retired without private completion. This lifecycle study uses a different construction profile from the main P60 comparison. Their timings are not composed.

References

  1. [1]A. Viand, C. Knabenhans, and A. Hithnawi, “Verifiable Fully Homomorphic Encryption,” arXiv:2301.07041v2, 2023. [Online]. Available: https://arxiv.org/abs/2301.07041v2
  2. [2]R. A. Mahdavi, A. Diao, and F. Kerschbaum, “ZipPIR: High-throughput Single-server PIR without Client-side Storage,” arXiv:2603.09190v1, 2026. [Online]. Available: https://arxiv.org/abs/2603.09190v1
  3. [3]Y. Dai, B. Xiang, L. Qin, Y. Deng, and J. Zhang, “FlashPIR: low-latency FHE-based single-server PIR with low client overhead,” Cybersecurity, vol. 9, no. 171, 2026. [Online]. Available: https://link.springer.com/article/10.1186/s42400-026-00601-7DOI
  4. [4]J. Drean, F. Jepsen, G. E. Suh, S. Devadas, A. Jaleel, and G. Saileshwar, “Teaching an Old Dog New Tricks: Verifiable FHE Using Commodity Hardware,” Proceedings on Privacy Enhancing Technologies, vol. 2025, no. 3, 2025. [Online]. Available: https://petsymposium.org/pets/2025/pets-2025-0099.pdfarxiv.org/abs/2412.03550
  5. [5]C. Knabenshans, A. Viani, A. Merino-Gallardo, and A. Hitnawi, “vFHE: Verifiable Fully Homomorphic Encryption,” in Proceedings of the 12th Workshop on Encrypted Computing and Applied Homomorphic Cryptography, 2024. [Online]. Available: https://cknabs.github.io/assets/pdf/vfhe.pdf
  6. [6]S. Benabbas, R. Gennaro, and Y. Vahlis, “Verifiable Delegation of Computation over Large Datasets,” Cryptology ePrint Archive, Paper 2011/132, 2011. [Online]. Available: https://eprint.iacr.org/2011/132
  7. [7]Y. Zhang, J. Katz, and C. Papamanthou, “IntegriDB: Verifiable SQL for Outsourced Databases,” in Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, 2015. [Online]. Available: https://integridb.github.io/IntegriDB.pdfDOI
  8. [8]Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(Leveled) Fully Homomorphic Encryption without Bootstrapping,” in Proceedings of the 44th Annual ACM Symposium on Theory of Computing, 2012, pp. 309–326. [Online]. Available: https://people.csail.mit.edu/vinodv/6892-Fall2013/BGV.pdf
  9. [9]B. Biasoli, C. Marcolla, N. Murru, and M. Urani, “Accurate BGV Parameters Selection: Accounting for Secret and Public Key Dependencies in Average-Case Analysis,” arXiv:2504.18597v3, 2026. [Online]. Available: https://arxiv.org/abs/2504.18597v3
  10. [10]M. Gao and H. Zheng, “A Critique on Average-Case Noise Analysis in RLWE-Based Homomorphic Encryption,” Cryptology ePrint Archive, Paper 2025/1036, 2025. [Online]. Available: https://eprint.iacr.org/2025/1036DOI
  11. [11]J. J. Engelsma, A. K. Jain, and V. N. Boddeti, “HERS: Homomorphically Encrypted Representation Search,” arXiv:2003.12197v3, 2022. [Online]. Available: https://arxiv.org/abs/2003.12197v3
  12. [12]Y. Bae, M. Kim, J. Lee, S. Kim, J. Kim, Y. Choi, and N. Mireshghallah, “PPMI: Privacy-Preserving LLM Interaction with Socratic Chain-of-Thought Reasoning and Homomorphically Encrypted Vector Databases,” arXiv:2506.17336v3, 2025. [Online]. Available: https://arxiv.org/abs/2506.17336v3
  13. [13]Y. Litchev and L. Ouyang, “Batched Paillier-Based Hamming-Distance Computation over Binary Embeddings,” arXiv:2609.21364v1, 2026. [Online]. Available: https://arxiv.org/abs/2609.21364v1
  14. [14]F. Tramer and D. Boneh, “Slalom: Fast, Verifiable and Private Execution of Neural Networks in Trusted Hardware,” arXiv:1806.03287v2, 2019. [Online]. Available: https://arxiv.org/abs/1806.03287v2
  15. [15]R. Xin, T. Wang, X. Wu, W. Meng, S. Zhang, and S. Yu, “BioZKFHE: Scalable Encrypted Biometric Identification via Verifiable Homomorphic Similarity Evaluation,” arXiv:2607.22065v1, 2026. [Online]. Available: https://arxiv.org/abs/2607.22065v1
  16. [16]S. Srinivasan, A. Chepurnov, C. Papamanthou, A. Tomescu, and Y. Zhang, “Hyperproofs: Aggregating and Maintaining Proofs in Vector Commitments,” in 31st USENIX Security Symposium. USENIX Association, 2022, pp. 3001–3018. [Online]. Available: https://www.usenix.org/conference/usenixsecurity22/presentation/srinivasan
  17. [17]L. Martinco and M. Kohlweiss, “AGATE: Augmented Global Attested Trusted Execution in the Universal Composability Framework,” in 2025 IEEE 38th Computer Security Foundations Symposium (CSF), 2025. [Online]. Available: https://www.research.ed.ac.uk/en/publications/agate-augmented-global-attested-trusted-execution-in-the-universa/
  18. [18]T. Gollamudi, A. Gollamudi, and J. Gancher, “ILAC: Correctness via Type Checking for Fully Homomorphic Encryption,” arXiv:2509.11559v1, 2025. [Online]. Available: https://arxiv.org/abs/2509.11559v1
  19. [19]Z. Brakerski, N. Döttling, S. Garg, and G. Malavolta, “Leveraging linear decryption: Rate-1 fully-homomorphic encryption and time-lock puzzles,” Cryptology ePrint Archive, Paper 2019/720, 2019. [Online]. Available: https://eprint.iacr.org/2019/720DOI
  20. [20]R. A. Mahdavi, A. Diao, and F. Kerschbaum, “HE is all you need: Smaller FHE responses via additive HE,” arXiv:2303.09043v2, 2024. [Online]. Available: https://arxiv.org/html/2303.09043v2

Paper details

vlnc:W_ymh4hg69
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents