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.
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.
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
Exact Current Search
Let be the initial database of binary vectors of dimension , with ordered distinct row identifiers . A query is . A truthful authorized edit satisfies and . Its application produces . Repeated coordinates and reversions are allowed. Let be the ordered edit log and its endpoint identifier. For a fixed base and a single nonrollback history, the counter identifies the prefix. The optional metadata 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 , define
sorts rows lexicographically by 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- are separate functionalities.
Encrypted evaluation uses the sign map . For , the sign-correlation identity is
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 , 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 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 ’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 ): 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 -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 . Response compression uses (Section VI). The split join adds an intermediate modulus (Section VII), giving at unchanged ring dimension.
An Independent Recipient Graph
Let be the padded query length, the smallest power of two at least . Choose an odd plaintext modulus . Since , every sign correlation in has a unique centered representative modulo , allowing exact recovery from its plaintext residue.
Let be the ring dimension with , and the projection stride. For any integer modulus , define
The source ciphertext modulus is odd, with . We use coefficient , Euclidean and maximum norms, denoted , and . Products are negacyclic, with . We use the leveled BGV scheme [8]. Each secret has independent uniform coefficients in . For an integer , each error coefficient has centered binomial distribution 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
Here has centered plaintext coefficients modulo , is the error polynomial, is secret, and is an independent uniform public mask in . The phase cancels the mask. An integer lift represents this residue with integer coefficients, not necessarily centered, and must be bounded before decoding.
Sample independent secrets and, when needed, a final , with . In this sequential graph, 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 , publish identity and automorphism hints addressed to . For an integer gadget radix and , a column with target is
where and are fresh mask and error draws, or and . Final hints use the same sampling rule with recipient and target or , as required by the terminal type below. Each role also publishes one independent parent with as its public-key record. It counts as an exposed sample, although queries and gallery entries use secret-key encryption.
For , use coefficientwise base- digits of representatives in . With hints addressed to , define
Its phase under is modulo . 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 , projection extracts coefficients at stride . The embedding reverses this placement, inserting zeros elsewhere. Let be the canonical inverse of modulo , which compensates for the expansion factor , and encode the query as
with coefficients centered modulo . A fresh public seed yields uniform . The owner prepares the private mask and issues the masked first-component row:
Only is sent. The secret still has coefficients. The transmitted row has the same distribution as the selected first-component coefficients of a fresh ciphertext in the full -dimensional ring. The private noise row has independent coefficients. The owner holds the query-independent preparation until a single issuance.
For , define from using sum-only algebraic trace levels, then two-way expansion levels. Level switches identity and automorphic branches to the same new recipient, and adds them. Two-way levels also subtract them, shifting the difference by . Lower outputs precede upper outputs. Its output ciphertext pairs, called leaves, under encode query signs as constants for .
Lemma 3.1 (Projection and retained affine identity): In error-free phase algebra, leaf is times the selected input phase coefficient at . Unselected coefficients cancel. With fixed hints and , the complete component identity is
Proof. On support at multiples of , multiplies coefficient by . The sum selects and doubles even positions, while the shifted difference selects and doubles odd positions. Induction eliminates coordinates outside multiples of , then isolates in source order, with total multiplier . 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 proves (9) exactly in . ☐
Here has a zero input first component, rather than zero plaintext. It depends only on the seed and fixed switching hints.
Partition the database into groups of at most rows. Within each group, encrypt feature column under , with local row indices and zero padding. We suppress the group index and use for its local rows. Decoded groups are concatenated in original row order. Write its encrypted pair as . Multiplying each column by its query-sign leaf and summing places row ’s sign correlation at coefficient , for conversion to distance by (3). Use for unlinearized pair multiplication. Let be the server’s query-independent prepared tensor, a three-component product ciphertext. The arriving first-component coefficient row supplies the late correction
The complete tensor uses decryption multipliers . 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
Pair switches both linear and quadratic tensor terms to . Mixed switches only the quadratic term and retains the linear term under . 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 decoder cannot decode the mixed terminal. For each type, the phase is modulo the ciphertext modulus, where are the terminal components.
Define the fresh phase bound , single-switch error bound , complete expanded-leaf bound , and terminal phase bound by
for pair, mixed, tensor indices respectively.
Lemma 3.2 (Complete source-phase bound). Each complete authorized terminal has an integer phase lift such that and
on actual rows, with zero plaintext on padding. If , centered source decryption recovers those plaintexts exactly.
Proof. Canonical digits satisfy , so each switching error is bounded by , using . Automorphisms and monomial shifts are signed permutations and preserve the coefficient infinity norm. Each output combines two switching errors. Their propagated total after levels is . Lemma 3.1 eliminates unselected input coordinates before applying the fresh bound to the selected ones, giving . No fresh bound is assigned to the sparse restored phase or the zero-first preparation alone. Gallery phases have bound . Their negacyclic products with complete leaves have aggregate bound . The typed final switches add zero, one, or two errors . Every error is divisible by in its integer lift. Since , the plaintext is the sign correlation. The bound below makes this lift the unique centered phase. Only then is reduction modulo applied. Centering that residue gives the integer correlation in Equation (3), since . □
Protocol and Correctness
Computation, Authority, and State
binds the encrypted base, independent key graph, ordered identifiers, layout, terminal type, permitted wire profiles, their selection rule and prescribed program. authorizes current answers. names the enrolled worker and its receipt/channel keys, not the physical server. Correct computation under authorizes no release at an obsolete head or generation. An original is an issued query message.
The authority and capability state is
Here is the truthful edit log, the durable lifetime ledger charging one slot per preparation attempt, exclusively held unused preparations, pending originals, and consumed or retired originals. Sans-serif symbols denote identifiers, calligraphic symbols state collections. Pending entries bind queries to issue-time metadata:
The fresh nonce names the issued instance, with subscripts denoting issue-time values. 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 , and completion permissions, halting use without refunds. Durable failure closes before dependent work.
Algorithms 1–2 implement serialized owner transitions. authenticates the owner, checks , regenerates from , and registers per-group seed-only state from (Section III or § 7), with permitted quadratic switching. Its authenticated acknowledgment binds these four arguments. Plaintext queries, and remain private. decrypts all groups of the admitted payload with multipliers (11) and the enrolled codec. It checks zero padding and returns base distances via (3), without correction, ranking or release.
Algorithm 1. Private preparation and unique issue
Input: open owner state and enrolled executor .
Prepare: durably charge a fresh slot in . Draw fresh and compute by (8). Request from .
On an authenticated acknowledgment matching the preparation binding, store in . Failure closes the owner without refund.
Issue : require a ready slot , take its tuple and delete that entry before validating and forming .
Choose , form , durably mark issued, and store in .
Send the owner-signed .
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 , the selected wire profile and the complete payload under . Subsets cannot authorize Finish.
Ordered Local Correction
Keeping the encrypted base at , correct row ’s distance by
Algorithm 2. Authenticated completion and current release
Input: state , nonce identifying original , and response . All steps run under the owner’s release/edit lock, with current head .
Reject and stop unless has an issued, unconsumed entry in . Read and check the complete public frame, signature and binding.
If public admission fails, retire durably, remove entry from , and stop without private completion.
Durably mark consumed in and remove entry from before any private arithmetic.
If , , or a cache answer has superseded , stop without Finish or release.
Create and spend an internal one-use permission before . Partial calls cannot be retried.
Compute using (15). Release . Private failure closes the owner without release or refund.
Lemma 4.1 (Telescoping correction): For every truthful ordered history, .
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 scan cost per fresh query, but exactness requires no sparsity assumption. The owner advances 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 , , , while advancing and revoking old pending originals. Only held unused preparations transfer. They remain unready until the new executor acknowledges . 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 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 , let count originals issued from slot and count whole-result private completion attempts for original . The predicate requires all of the following:
and . The charged-slot set and consumed or retired originals grow monotonically.
Each completion follows durable consumption and whole-result admission under the exact binding . Its issue head and generation equal the current and at the serialized completion transition.
Every release agrees with the authorized projection of at its serialized release head .
An edit preserves and all prior charges and consumption marks. Reconstruction additionally preserves , 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 for queries and . Equation (8) then gives . 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 for every allowed terminal type . 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 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 by Equation (3). Lemma 4.1 therefore makes Algorithm 2’s corrected vector exact at . 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
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 -compatible adaptive policies. In world , the source and owner use policy . The host sees only the declared public view and outputs a bit. Its public-view distinguishing advantage is
Both policies use exact private ideal outputs for subsequent decisions and remain independent of secret-key state and hidden encryption randomness.
For recipient , let bound the decisional Ring-LWE advantage between at most ordinary samples
where are independent uniform elements of , has the specified ternary distribution, and has independent coefficients. includes the reduction’s complete simulation time. The invertible map gives the exact scaled-error distribution used in Equation (4). After scaling, the sample coordinates supply the mask and zero-message first component. Adding 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 . Let be the bit length of fresh seeds and random protocol names, count all fresh parent seeds, and count adversarial XOF input queries. Let count the remaining fresh random names. Coupling to ideal interfaces with distinct identifiers gives
Failed and unused reservations count. Identical republishing does not. For a strict fair-bit polynomial-time reduction, cap each rejection stage at candidates. With samples and fresh role-secret draws,
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 for every allowed terminal type and pointwise exact terminal decoding, together with the authentication and binding games above. Then
Before such failure, substituting exact for authorized 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 .
Source bounds and exact decoding give . 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 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 for every allowed terminal type and pointwise exact terminal decoding. Under Section II’s execution premises and the games above,
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 keep recipients real and replace parent and hint first components addressed to by independent uniform elements of . For the adjacent reduction at , draw all other secrets independently and obtain ’s samples from its ordinary Ring-LWE oracle, followed by the invertible map. Every still-real target incoming to depends only on known lower secrets, so the reduction adds it to the oracle’s masked component. All outgoing hints involving the unknown 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 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 . Retained preparations use only 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 .
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 , fresh gallery parents , and query-preparation reservations , the sequential per-recipient sample budgets are
Tensor has no final role. With gallery groups, one encryption per feature and group gives at initial setup. Across generations reusing the graph and admitting at most fresh reservations per generation, use 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 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 makes . The seed/name length 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 to wire modulus , retaining and using bits per coefficient. Let bound the complete integer phase, including scores and noise. The baseline uses from Equation (12). § 7 uses with its own complete-phase bound. Let be the decryption multiplier vector from Equation (11). Its aggregate coefficient norm , summed over terminal components, measures rounding-error amplification.
Choose an odd wire modulus with . For a canonical coefficient , select the nearest integer to in , rounding halfway ties upward:
This BGV terminal modulus switching [8] preserves . Eligible integers are spaced apart, giving . The wire stores .
Lemma 6.1 (Whole-phase terminal correctness): Suppose an authorized source terminal has centered phase lift with . If
then the reduced terminal has the same plaintext at every coefficient.
Proof. Let be the integer canonical component lifts. Then
with carry polynomial . Set coefficientwise and
The rounding errors have coefficient bound , so . The canonical wire phase is congruent to modulo . Equation (24) makes its unique centered lift. Since each rounded lift preserves its residue modulo and , . Individual wire components need not preserve that residue. The argument applies to the complete phase including its carries. □
The guard prevents wraparound modulo . Appendix D illustrates both terms of and distinguishes rounded lifts from stored residues.
At setup, privately compare with the public type-specific cap (Appendix B). Select the smaller wire profile if it passes, otherwise the worst-case fallback. Bind the type and profile in 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 , form the residual bounds coefficientwise. Let sum the largest entries, where is the registered support cap. At a ternary recipient with , the sufficient guard is
Negacyclic shifts use at most 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 . Malformed frames are rejected publicly. Totality also holds on uniformized hybrid inputs, without asserting their plaintext correctness.
Profile Exposure and Privacy
For pair terminals, . Choose a public threshold . Since is , Hoeffding bounds the fallback probability by
Appendix B gives the corresponding mixed/tensor 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 index the allowed fresh family/type pairs, with terminal-type index for pair . Bound lifetime profile exposure by
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
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 . 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 . 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
For causally -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 precedes a retained ciphertext–ciphertext join at . Ordinary BGV modulus switching [8], [9] can incur rounding loss that prevents a useful smaller . 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 with integer ratio odd, , and . Thus . Write and for a complete source leaf. Denote by the unreduced integer rounding map of Equation (23), extended to integer inputs. It preserves residues modulo , has residual magnitude at most , and satisfies for integers . Lemma 3.1 gives
where is the canonical residue and is inserted at coefficient zero. Define on canonical lifts, coefficientwise,
Here is the retained seed-only pair, is the late rounded scalar, and is the completed query leaf. This enrolled circuit generally differs from rounding as a whole, since rounding is not additive. The incomplete 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 under the same integer secret polynomial , with fresh randomness, giving . Final hints also use modulus , with targets , and recipient . The seed-only database join is . Its completed value obeys the exact identity
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 . 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 . Worker reconstruction reuses it under a new . The owner’s internal lifecycle controller fixes positive integer limits on catalog draws and on query-preparation reservations per catalog, including failed, unused and retired draws. The source fixes the expansion graph and join profile, then samples with independent uniform ternary coefficients, independently of its pre-draw history. Here indexes the graph’s gallery recipient, equal to in the sequential graph. Let 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 , its leaf’s second component is
Here is the deterministic public recurrence, and the mask family is independent of . 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 . Final-recipient admission does not filter . A graph or join-modulus change requires a fresh charged catalog and . 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 permitted reservation seeds per catalog, sampled independently of . 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 per world enters . 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- sample requires a distinct source- oracle call.
Lemma 7.1 (Simultaneous rounding under adaptive selection): For reservation and feature leaf , suppress in the residual notation and let , , and . Thus bounds the largest residual and bounds their squared weight sum. For tail parameter , bound convolution magnitudes by
Under the source sampling assumptions above, every coefficient of the error polynomial for every honestly reserved feature leaf is bounded by its corresponding , except with probability at most
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 is a signed sum of independent mean-zero ternary variables with fixed weights . Its variance is at most and each summand has magnitude at most . Bernstein’s two-sided bound is
For 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 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 , choosing gives . 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 be the source and final gadget radices. The selected query coefficient has phase bound from Equation (8). Put and for one source switch. A two-level block maps an incoming switching-error bound to , no larger than the sequential . It preserves the extraction operator, so complete source leaves admit in either graph. Appendix E gives the maps. Let be an enrolled upper bound on every in the finite family, including as-yet undrawn reservations, not merely an observed maximum. and give a uniform choice. The final-switch error bound is . Define the complete split-leaf and joined-pair bounds by
The leaf bound adds scaled source phase, two first-component rounding errors and the secret-weighted residual. Joining gallery columns and switching two tensor components gives .
The final wire modulus is , distinct from the join modulus. Section VI applies with and complete bound : for example, 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 , registering with
ensures totality by the residual guard of Section VI, even on canonical hybrid inputs. It does not assert that hybrid phases obey . 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 be a valid complete source-leaf phase bound and an enrolled uniform upper bound on Equation (30) over all allowed reservations. For in Equation (32), assume , enrolled terminal conversion exact for phases bounded by , 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 . Its adaptive privacy bound gains at most . All sample and exposure budgets are recomputed for the actual enrolled graph and charged lifetime, using ordinary Ring-LWE games at .
Proof. For integer component lifts, the complete source identity is with carry and . Scale it by . The split phase differs by the two first-component residuals of magnitude at most and , giving outside the lemma’s event. Subtracting and using preserves its plaintext. Gallery phases have bound . Their join and two final switches give . 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 . 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 sample by the invertible map gives the required scaled-error distribution. Reducing a fresh such sample modulo gives exactly a fresh direct sample under the same integer secret. Uniform samples remain uniform with equal numbers of preimages. Every direct sample uses a separate oracle call, distinct from exposed samples. Earlier-recipient target shifts commute with reduction, so the mixed-modulus graph introduces no key cycle. The two-world inequality adds 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: , , 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, , error parameter , source radix , and final radix . Its public residual selector chooses among prescribed 23-, 24-, and 25-bit representations. The honest family declares catalogs and 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].
| Profile | Prep. (s) | Public (ms) | Private (ms) | Paid (s) |
| Q120 fixed24 | 3.514 | 217.625 | 25.079 | 12.159 |
| P64 fixed24 | 7.205 | 213.312 | 25.145 | 14.228 |
| P60 residual | 4.635 | 116.155 | 39.635 | 9.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 , the declared reservoir gives statistical correctness bound . 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 , a coefficient has
Indeed is a centered -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 is invertible modulo , multiplication of both ordinary sample components by is a bijection on . It maps to 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 and . A width- candidate word, with , contributes its low bits. Values at least are rejected. For a prescribed accepted coefficient , sample a geometric rejection count with , then independent rejected low-bit values uniform in . 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 specified rejects and one specified acceptance is
Including high bits gives exactly the original uniform-word probability. Repeat for all 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 . 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- samples, the same construction uses in place of .
The domain includes the fixed tag, public role identity, and fresh seed. Over fresh invocations and 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 is odd, , and each accepted coefficient needs fewer than two candidates in expectation. Capping every rejection stage at costs at most per stage. The conservative 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 two-bit candidates per coefficient, using the first candidate below three and aborting if none exists. For each its subprobability is
This is exactly uniform ternary coupled to an independent exhaustion event. The union bound over fresh role-secret draws is . For the concrete choice , 16 draws, and , it is . 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 for and for , with . Define and set
The support and spectral failure budgets are
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
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, is , so Hoeffding gives . This proves pair and, by a union bound, mixed. The Gaussian exponential argument in Appendix C gives
On and the spectral event’s complement, by the norm implication proved in Appendix C. The two bad events have union probability at most , proving the tensor-type bound without assuming their independence. □
a) Selecting a statistical error budget: For any target , sufficient conditions for in all three modes are
They make each of and at most . If a lifetime exposes at most allowed fresh family/type pairs, replacing on the right-hand sides by makes their total cap term at most . Here 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 , the coefficient inequality holds at and is preserved inductively. Comparison of even power-series coefficients yields .
Write and let count its nonzero coefficients. Use support threshold , spectral threshold and norm cap for , as in Appendix B. For and even, . Thus the real and imaginary weight vectors are orthogonal with squared norms . For and , independence of gives
For a standard two-dimensional Gaussian and , Tonelli and the Gaussian moment identity give
With and , Markov yields per root. A union bound over the roots gives (36). Discrete Parseval gives , using the exact integer negacyclic square. Together with Cauchy–Schwarz, on and , this yields
This proves Lemma B.1’s norm implication without treating square coefficients as independent.
Numerical Certificate for the Experimental Thresholds
For , , and , the coefficient-norm exponent satisfies . Also , , and . The spectral tail is consequently below , while . Equation (35) then gives , and . 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 , write its coefficientwise rounding errors as .
Negacyclic multiplication satisfies
Summing over components gives the rounding contribution . The converted phase therefore has bound , rounded upward conservatively in Equation (24). For mixed and tensor terminals, respectively, and . The square is the integer negacyclic product. For ternary , counts nonzero coefficients.
Ignoring the ceilings only to interpret the tradeoff, the strict guard is equivalent to . Smaller admitted key norms permit smaller response moduli. Actual profile selection must also satisfy the ceilings and . The original keys, encrypted index, and source modulus remain unchanged.
For an arithmetic illustration, take , , and . These values are neither proposed security parameters nor benchmark data. Both and have the same residue as modulo :
| Guard | |||||
| 57 | 2 | 6 | 17 | 23 | |
| 57 | 3 | 6 | 26 | 32 | |
| 91 | 3 | 10 | 26 | 36 |
Table 2.
Thus the smaller modulus is certified at , while 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 rather than six at .
The same values also illustrate residue-preserving rounding. For and , the scaled target is . Eligible integers are congruent to 15 modulo 17, and the nearest is . Its error is about . The stored value is 55 modulo 57, whose residue modulo 17 differs from that of . 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 levels has one independent new recipient . Its output maps on are
where indexes outputs, indexes automorphisms, is a signed sum of monomials and 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 , switch directly from the block’s input recipient to, with target . Hoisting means reusing one decomposition across branches, with canonical coefficientwise digits . Apply to these digits. They reconstruct modulo , and their coefficient magnitudes need not match . They need not be the canonical digits of the transformed polynomial. No decomposition is distributed over a sum. A switched pair has phase with . Public assembly gives
Here is the assembled output. If bounds previously injected switching errors, its next bound satisfies . For blocks of width one or two, this is at most the sequential recurrence . Beginning at zero injected switch error gives total propagated error at most .
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 . The selected honest query coefficient has magnitude at most , giving the complete bound 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- 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 at with odd , the rounding map has the equivalent integer quotient form
Here selects the unique representative in , and is taken modulo . The numerator is divisible by . The result is congruent to modulo , since , and its residual is with magnitude at most . Thus , and 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 .
b) Experimental complete bound: The measured construction profile uses , , , , , and , with
The uniform residual bound gives and . Source radix and final radix give complete-leaf bound and joined-pair bound . Final radix 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 . 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 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 , use canonical coefficient lifts and write its bounded phase and integer carry as
Let be an integer ternary polynomial with at most nonzero coefficients. For a registered odd satisfying , let with the nearest unreduced residue-preserving integer lift of (23). Define integer-scaled rounding residuals and their magnitude bounds coefficientwise
For a nonnegative vector , sums its largest entries, with . It is distinct from the search ranking operator . Two public converted-phase bounds are
Proposition F.1 (Public residual certificate). . If , the pair has centered phase bounded by and the same plaintext as .
Proof. The exact integer-ring identity is
Each coefficient of is a signed sum of at most distinct entries of : negacyclic shifts permute their absolute values. Its magnitude is therefore at most . Replacing the residual magnitudes divided by by their ceilings adds less than . The scaled source ceiling adds less than one. Comparing the resulting integer ceilings gives the displayed slack. The strict guard gives unique centering. Since and , subtraction of the same integral carry preserves the plaintext residue.
With , this certificate holds for every ternary recipient and requires no private support predicate. Moreover, , so a histogram with bins computes it in time. A registered fallback satisfying
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 bind query , immutable computation , generation , and historical issue head . Its signed prefix remains unchanged. At a serialized release head , require the following:
The complete result matches the exact signed original and its immutable base, terminal type, wire profile, and current generation.
The owner spends before whole-result private completion. No competing cache answer has released it, and no retired original is restored.
The private query and complete truthful history from to remain in exclusive owner custody.
Correction, stable ranking, and release execute under the same release/edit lock at .
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 . Applying the base-to-current correction (15) to the complete truthful history gives by Lemma 4.1. The lock fixes the same 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 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 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]A. Viand, C. Knabenhans, and A. Hithnawi, “Verifiable Fully Homomorphic Encryption,” arXiv:2301.07041v2, 2023. [Online]. Available: https://arxiv.org/abs/2301.07041v2
- [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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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