GKS Fully Homomorphic Encryption: Security Analysis

1 Introduction

• GKS is presented as a private-key scheme with unlimited multiplicative depth without bootstrapping, native encrypted search, and bit-exact decryption.Its single-ciphertext IND-EAV result is conditional on the publicly observable rank.Source: §1 · pp. 3–4

1.1 Contributions

• The paper presents the first detailed ePrint security analysis of GKS, including formal games, retraction counting, preliminary cryptanalysis, and comparative analysis.Its contribution list also covers attack strategies, zero-pattern and collision-harvest mitigations, and formal hardness assumptions.Source: §1 · p. 4, §1.1 · p. 4
• The introduction states that GKS is not intended for an exposed encryption-oracle model and does not claim IND-CPA security under such an oracle.The scheme’s single-ciphertext IND-EAV claim is conditional on rank; unconditional advantage zero is not claimed.Source: §1.1 · p. 4
• The contribution list distinguishes the 10,305-bit conservative key-generation description count from a cryptographic security level or residual uncertainty after ideal recovery.The retraction-ambiguity result also does not establish KPA indistinguishability for non-ring plaintexts.Source: §1.1 · p. 4

1.2 Paper Organization

• The paper organization lists sections on construction, security, deployment, post-ideal-recovery hardness, comparative analysis, quantum resistance, empirical validation, and future work.It also lists proof and statistical-test appendices.Source: §1.2 · p. 5

1.3 Summary Table

• The summary table is identified as organizing security by attack class.The supplied caption does not report any attack-class outcomes.Source: Table 1 · p. 5

2.1 Algebraic Defense Structure

• Before ideal recovery, GKS uses a secret permutation and embedding to obscure plaintext-slot labels and the placement of the plaintext ring in the ciphertext ring.After ideal recovery in the commutative Zp instantiation, quotient canonicalization becomes the primary attack path.Source: §2.1 · pp. 5–6

2.2 The Ring Sn

• The plaintext ring Sn has dimension 2^n over Zp; at n = 7, its dimension is 128 and its size is p^128.Source: §2.2 · p. 6

2.3 Orthogonal Idempotent Basis

• The 2^n orthogonal idempotents form a basis, and multiplication in that basis is componentwise over Zp.Source: §2.3 · p. 6

2.5 Key Generation

• Key generation selects an ideal, permutes the full orthogonal-idempotent basis, applies a nested-support triangular transformation, and selects an embedding.The resulting transformed basis is the public ring presentation, while the private key contains the ideal generators, permutation, transformation, and embedding.Source: §2.5 · pp. 6–7

2.6 Encryption and Decryption

• Encryption adds a uniformly sampled ideal element to the embedded plaintext, and decryption substitutes ideal generators before applying the inverse embedding.The paper states that decryption is exact and that addition and multiplication are homomorphic modulo the ideal.Source: §2.6 · p. 7

2.7 The Four Components of Retraction Ambiguity

• The key-description count combines permutation, triangular-transform, ideal-generator, and embedding choices, but the unrestricted triangular-family count is only nominal for the nested-support family.After the public presentation is fixed, the ideal-generator component contributes no residual bits; the permutation and embedding remain, alongside any triangular-transform freedom consistent with the observed multiplication table.Source: §2.7 · pp. 7–8
• The description count is not a proven computational lower bound or a sufficient security guarantee after ideal recovery.In the commutative Zp instantiation, quotient canonicalization may reveal the embedding and labeling with less work than brute-force search over the residual space.Source: §2.7 · p. 8

3.1.2 Zero-Knowledge of Ideal (ZKI)

• A single ciphertext does not identify the ideal in the SIMD case, but differences can yield ideal elements, making ZKI computational and motivating ideal rotation and bijective encoding.Across multiple ciphertexts, recovery is bounded by the supply of same-value differences under one ideal; operational mitigations are essential when E(0) elements may accumulate.Source: §3.1.2 · p. 9, §3.1.7 · p. 12

3.1.3 Retraction Indistinguishability under Decryption (RI-D)

• GKS lacks the approximate decryption, correlated noise, and bootstrapping exploited by the Li–Micciancio attack, but this rules out only that attack class, not all CPAD attacks.RI-D remains an assumption because a complete CPAD analysis is open; in the private-key model, submitting valid ciphertexts to the decryption oracle requires prior knowledge of I.Source: §3.1.3 · pp. 9–10

3.1.4 Triangular Basis Indistinguishability (TBI)

• TBI hides which 128 of 1024 primitive components form the plaintext ring, although the authors cannot rule out algorithms that bypass TBI without first recovering I.The multiplication table is consistent with every nested-support triangular transform; once I is known, TBI’s protection becomes inert at the quotient level.Source: §3.1.4 · pp. 10–11

3.1.5 Retraction Indistinguishability (RI)

• RI formalizes indistinguishability between retractions generated with the same ideal but independent remaining key components; its stronger oracle formulation is unavailable to adversaries in the private-key model.The key-component counts are algebraically independent, but quotient canonicalization makes many permutation and triangular descriptions redundant.Source: §3.1.5 · p. 11, §3.1.6 · p. 11

3.1.7 Limitations and Open Problems

• A public prefix-sum under fixed triangular basis can expose plaintext-bearing coordinates for non-uniform plaintexts, so the fixed-T single-layer configuration is unsuitable for low-entropy data pending measurements.The paper recommends double encryption with ideal rotation and, where possible, random-T; random triangular basis, non-commutative instantiation, or genuinely uniform plaintexts close the stated algebraic channel.Source: §3.1.7 · pp. 11–12
• After ideal recovery, quotient canonicalization removes much of the permutation and triangular ambiguity, leaving an O(p) embedding search in the commutative Zp case and no residual barrier for ring-structured plaintexts.At p ≈ 2^30, the embedding search is about 30 bits; canonicalization has not yet been run at production parameters. In the ZN instantiation, the residual post-recovery security is that of the factoring instance.Source: §3.1.7 · p. 12

3.3 Identified Attack Vectors

• The current Gröbner-basis attack is impractical at n = 7, triangular-transform recovery remains information-theoretically ambiguous, and no known embedding reduces GKS to a lattice problem.Gröbner computation is feasible at research parameters n = 3; the meet-in-the-middle attack requires enumerating 263,242 partial keys in each half.Source: §3.3.1 · p. 13, §3.3.2 · p. 14, §3.3.3 · p. 14

3.3.7 Attack 7: Post-ideal canonicalization / direct-readout attack

• For ring-structured plaintexts, post-ideal canonicalization can read plaintexts directly when p ≈ 2^30; E(0) also yields an ideal element because every ring homomorphism maps zero to zero.The direct-readout attack requires ideal recovery and applies only to ring-structured plaintexts; double encryption is recommended for ring data, while ZCG and double encryption prevent zero from entering plaintext or intermediate space.Source: §3.3.7 · pp. 14–15

3.3.9 Attack 9: Rank Order Attacks

• A single pair’s public rank can distinguish same-plaintext from different-plaintext ciphertexts, enabling equality testing and, after enough collisions, recovery of I or the composed kernel K.Differences across repeated plaintext values combine; a corpus of N ciphertexts with D distinct plaintexts yields N − D independent same-value differences. ZCG is designed to remove collisions but is not yet fully implemented.Source: §3.3.9 · p. 16

3.4.1 IND-EAV Security Game

• Single-ciphertext IND-EAV security is conditional on the open balance lemma; with full-slot bijective encoding, one ciphertext alone cannot identify its ideal by consistency testing.The public rank invariant reveals plaintext weight, and applying it to ciphertext differences creates an equality test, so the single-ciphertext argument does not extend to multi-ciphertext access.Source: §3.4.1 · p. 17

3.4.3 Theorem 2

• Theorem 3.2 gives a combinatorial lower bound of 210,305 valid key descriptions, but this count alone does not establish computational security.It counts KeyGen descriptions before ideal recovery, not residual ambiguity after I is known; effective post-recovery security depends on the open Retraction Recovery Problem.Source: §3.4.3 · p. 18

3.4.4 KPA Non-ring Plaintexts

• For non-ring plaintexts, valid retractions can map a nonzero ciphertext to any candidate nonzero plaintext; for ring-structured plaintexts, effective security is O(p), requiring p ≈ 2^128 for 128-bit security.The description count is not itself a security level, and the rarity of accidental ideal elements does not prevent their public recognition.Source: §3.4.4 · p. 18

3.4.5 IND-CPA Security: Limitation and Context

• IND-CPA is not instantiated in the private-key deployment because outsiders lack an encryption oracle, but exposing one would enable ideal-element accumulation; IND-CCA2 is impossible for every FHE scheme.The absence of an encryption oracle is a deployment property, not algebraic immunity.Source: §3.4.5 · p. 19

3.4.6 Formal KPA-Zero Security Game; 3.4.7 Definition

• At n = 7, an adversary with at least 896 encryptions of zero can reconstruct I and distinguish a zero challenge with advantage 1/2; I-recovery alone does not reveal nonzero plaintexts.Zero-pattern leakage is one residual channel; in the commutative Zp instantiation, recovering I enables decryption through quotient canonicalization.Source: §3.4.6 · p. 19, §3.4.7 · p. 20

3.4.8 Concrete Bound on Carl’s I-Recovery Path

• Carl’s expected ideal-element harvest per session is pcoll · N(N − 1)/2; session-fresh ideals reset accumulated samples at each rotation, so recovery needs dim I linearly independent ideal elements within one session.If N − D is below dim I (896 at n = 7), Carl cannot span I by collision subtraction, even with a membership oracle. A Chernoff bound is heuristic; only the Markov form is rigorous.Source: §3.4.8 · pp. 20–21

3.4.9 Ideal Recovery via Equivalent-Ciphertext Differencing; 3.3.8 Attack 8: Non-Zero KPA

• Observable, confirmed differences of equal encryptions can yield enough ideal elements to recover I by linear algebra, while self-subtraction alone yields no useful sample.Manufactured zero differences can be genuine ideal elements, so defenses rely on preventing observation of individual differences, controlling subtraction, and outer masking through double encryption; non-exposure of intermediates alone is insufficient.Source: §3.3.8 · p. 15, §3.4.9 · p. 21

3.4.9 Ideal Recovery via Equivalent-Ciphertext Differencing

• The remaining pairwise-rank equality test is not removed by defenses that withhold equalities from search; limiting repeated values under one ideal is its binding control.Source: §3.4.9 · p. 21

3.5.1 Mitigation 1: Ideal Rotation

• Fresh ideals sampled independently for each query session or rotation interval make samples collected under an old ideal uninformative about the new ideal [19, §8.1, Remark 4].Source: §3.5.1 · p. 21

3.5.2 Mitigation 2: Bijective Encoding

• Bijective encoding maps plaintext 0 to a nonzero ring element, prevents input-zero KPA pairs, and preserves valid encryption under the stated encoding.It does not prevent collision-subtraction of independent encryptions of the same encoded value; ideal rotation and multiplicity bounds limit useful differences under one ideal, and both encoding and rotation are needed to eliminate zero-pattern leakage entirely.Source: §3.5.2 · p. 22

3.5.3 Mitigation 3: SIMD Security Amplification

• SIMD packing makes pure-ideal harvesting exponentially rarer: at n = 5 and H = 15 bits, full-vector collision probability is 2^-480, yielding roughly 2^-433 expected pure samples in ten million records.Tests found no Hamming-distance oracle from intermediate ranks, but corrected probes show rank can reveal difference weight; under double encryption, that measurement does not map to useful constraints on original low-entropy slots, and ideal rotation limits observed pairs.Source: §3.5.3 · p. 22

3.5.4 Mitigation 4: Channel Compartmentalization — Independent Ideals for Search & Compute

• Independent search and compute ideals prevent search-side leakage from compromising compute ciphertexts, because the search interface supplies labeled equalities while the compute interface supplies none.The channels have separate ciphertext domains, and recovery of one ideal yields no information about the other.Source: §3.5.4 · p. 23

3.5.5 Mitigation 5: Double Encryption

• Double encryption raises the rank-harvest target from dim I to dim K and removes a clean outer-ideal harvest, while distinct inner ciphertexts of the same plaintext produce differences in K.The outer rank test distinguishes identical inner ciphertexts (dim Iout), distinct encryptions of the same plaintext (dim K), and otherwise full rank; attacker-controlled equal inner operands still expose Iout, so outer-ideal rotation is needed to close that channel.Source: §3.5.5 · p. 23

3.5.6 Mitigation 6: ZN Instantiation and Non-Commutative Rings

• ZN instantiation and non-commutative-ring mitigations address post-ideal-recovery canonicalizations and are covered by GKS patents.Source: §3.5.6 · p. 24

3.5.7 Mitigation 7: ZCG: Collision Elimination

• ZCG applies collision controls at both original-plaintext and intermediate layers under double encryption, removing the collision prerequisite for rank-order and differencing attacks.The described controls include short-term ideals for headers or labels, row-wise SIMD packing, epoch-unique nonces, duplicate-value adjustment, and client-side duplicate checks with re-encoding.Source: §3.5.7 · p. 24

4.1 Compiled API Mode

• The compiled API omits rank evaluation, while subtraction rate limits and key expiry are advisory controls.The library is distributed as an integrity-protected compiled library.Source: §4.1 · p. 25

4.2 Client Custody Architecture

• In client custody, ciphertext remains in the data-owner-controlled environment, where evaluator requests run under clock, counter, timer, and type monitoring.The data owner retains the ciphertext and controls the compute environment.Source: §4.2 · p. 25

4.3 Client Sovereign Architecture

• Client sovereignty keeps all decryption authority with the data owner and separates compute, search, and enforcement through three independent ideals.Source: §4.3 · p. 25

4.4 Epoch Key Architecture

• The epoch-key architecture uses ephemeral per-epoch keys that expire at epoch boundaries, gating evaluation capabilities.Source: §4.4 · p. 26

• After ideal recovery, commutative Zp leaves an O(p) embedding search (about 30 bits at p ≈230), while ring-structured plaintexts are readable directly from canonical decomposition.The table counts retraction ambiguity in bits for fixed ideals.Source: §5 · p. 26, Table 5 · p. 26
• The ZN composite-modulus variant ties quotient canonicalization to integer factorization, giving approximately 112 bits of classical hardness at 2048-bit N.Source: §5 · p. 26
• The non-commutative matrix-ring variant introduces a non-trivial radical and eliminates direct commutative semisimple decomposition.Source: §5 · p. 26

6.1 CKKS IND-CPAD Vulnerability

• Li–Micciancio showed CKKS broken under IND-CPAD, while GKS exact arithmetic structurally closes the decryption-error channel.Source: §6.1 · p. 27

6.2 Comparison with RLWE: Different Tradeoffs

• RLWE benefits from 15+ years of lattice cryptanalysis, while GKS offers unlimited depth, exact decryption, and native search based on assumptions independent of RLWE.Source: §6.2 · p. 27

6.3.2 Where GKS differs structurally

• GKS samples independent ideal elements for ciphertexts, hides quotient structure behind operations modulo I, and in the ZN variant requires factoring N for canonicalization.Source: §6.3.2 · p. 27

6.3.3 What this section does not establish

• The section rules out specific historical linear-algebraic and orbit attacks by structural exclusion, but does not establish a standalone security proof.Source: §6.3.3 · p. 27

6.4 GKS Performance Metrics Summary

• 2.4 µs/slot encryption, 2 ns/slot addition, 31 ns/slot multiplication, 2.3 µs/slot decryption, and 16× expansion were reported.Measurements were on commodity hardware without a GPU, using double encryption, SIMD, and rings 6/7/8.Source: §6.4 · p. 28

• In the single-ciphertext model, quantum resistance follows from Theorem 3.1.Source: §7 · p. 28
• Shor's algorithm is inapplicable because GKS does not reduce to abelian hidden subgroup problems, and lattice algorithms are inapplicable because GKS is non-lattice.Source: §7 · p. 28
• Grover's algorithm provides a quadratic speedup for post-I exhaustive search, reducing the cost to O(√p).Source: §7 · p. 28

• Table 8 presents empirical validation of GKS-FHE on medical data.Source: Table 8 · p. 28

9.1 GKS Performance Metrics

• GPU benchmarks are planned as future work.Source: §9.1 · p. 29

9.2 GKS Key Management & Use Cases

• Companion papers address operating and search keys, ML-KEM transport, and key delegation.Source: §9.2 · p. 29

9.3 Future Research

• Open problems include small-parameter verification of Theorem 3.2, public cryptanalytic challenges, third-party audits, and formal reductions for Retraction Recovery.Source: §9.3 · p. 29

10 Conclusion

• GKS is described as noise-free, with security centered on preventing I-recovery through ZKI, mitigated by ZCG, while providing exact decryption and native search without bootstrapping.Source: §10 · p. 29

A.1 Single-ciphertext ensembles and the balance condition

• Security must be evaluated over the mixture of ciphertext ensembles sampled by KeyGen, because fixed-I ciphertexts occupy disjoint cosets.Source: §A.1 · p. 32
• Public multiplication-by-c rank distinguishes cosets whose representatives have different weights outside the ideal.Source: §A.1 · p. 32
• With all slots in use, SIMD encoding bijectively maps slot vectors onto Sn, so every ciphertext has exactly one decrypting slot vector for each candidate key.Source: §A.1 · p. 32

A.2 Theorem 1 — IND-EAV Security in the Ciphertext-Only Model

• Ciphertext ensembles are identical if and only if the plaintexts have equal Hamming weight.Source: §A.2 · p. 32
• Unequal-weight plaintexts are distinguishable by public rank with ∆=1, so the stated IND-EAV result is conditional on conditioning on rank.Source: §A.2 · p. 32
• Across 300 independent KeyGen draws, equal-weight plaintexts produced no distinguisher above the sampling noise floor.Source: §A.2 · p. 32
• Finite sampling cannot establish negligible statistical distance for equal-weight plaintexts, leaving this an algebraic open question.Source: §A.2 · p. 32

A.3 Theorem 2 — Retraction Ambiguity Bound

• The key components—permutation, triangular transform, ideal generators, and embedding—are independently selectable and algebraically orthogonal.The permutation and triangular transform act on basis representations, while ideal generators fix the kernel and embeddings select idempotents.Source: §A.3 · p. 32
• At r = 10, nested-support triangular transformations contribute at least 512 bits of choices, while unrestricted unitriangular matrices contribute 523,776 nominal bits.The permutation count is 1024!, or approximately 8,769 bits; for n = 7, the ideal-generator and embedding counts are 2896 and 2^128.Source: §A.3 · pp. 32–33

A.4 Theorem 6 (Composition — Total Retraction Ambiguity)

• For n = 7 and r = 10, compatible private-key descriptions number at least 210,305 conservatively or 2533,569 nominally unrestricted.These are compatible-description counts, not a stated cryptographic security level.Source: §A.4 · p. 33

A.5 Theorem 3 — Retraction Ambiguity for Non-Ring Plaintexts

• For non-ring plaintexts, retractions map ciphertexts independently across candidate plaintexts, producing combinatorial ambiguity; labelled pairs permit affine recovery.The labelled-pair recovery case is described as out of scope for the intended architecture.Source: §A.5 · p. 33

A.6 Theorem 4 — Soundness of Bijective Encoding

• The bijective encoding is injective, excludes zero from its image, preserves addition with an offset, and preserves multiplication without correction.The encoding is defined as ϕ(m) = α(m) + e1; multiplication satisfies ϕ(a)ϕ(b) = ϕ(ab).Source: §A.6 · p. 33

A.7 Theorem 5 — IND-CCA2 Impossibility

• IND-CCA2 is impossible because a decryption-oracle query on c′ = c + Enc(0) returns the corresponding plaintext while c′ differs from c.Source: §A.7 · p. 33

B1: Key Entropy Tests

• Ideal 0 is independently recoverable at 32 bits for order 5 and 128 bits for order 7, setting the operative security floor for that key component.The paper recommends at least order 7 for the plaintext ring and order 10 for the cipher ring in single encryption.Source: B1: Key Entropy Tests · p. 34

B2: Coordinate Distance Tests

• Equal-versus-distinct ciphertext coordinate distances were statistically indistinguishable; separate KeyGen-ensemble tests sampled fresh keys and one ciphertext per plaintext per key.The distance tests covered single and double encryption, while the ensemble plaintext weight counts nonzero SIMD slots.Source: B2: Coordinate Distance Tests · p. 35, B10: KeyGen-Ensemble Measurements · p. 40

B3: Kernel Span Test

• With same-value differences harvested, public multiplication can generate the ideal; pairwise rank can identify equal pairs, so a pre-grouped set is unnecessary.The harvest condition concerns the total independent same-value differences under one ideal, not one value’s multiplicity; a nonzero collision cap is insufficient.Source: B3: Kernel Span Test · p. 35

B4: Kernel Peel Test

• Single encryption yielded a full ideal harvest, whereas double encryption yielded a larger ideal span classified as one inseparable big kernel, not two sequential breaks.Recovery of the composed kernel’s relation to the composed decryption map has not yet been analyzed; double encryption raises the harvest threshold rather than adding a post-recovery barrier.Source: B4: Kernel Peel Test · pp. 36–37

B5: Rank Difference

• A single ciphertext difference separates equal from unequal plaintexts by rank, while spanning the ideal requires about Nh ≈ dim I pairs.The equal-plaintext difference has rank dim I for single encryption or dim K for double encryption; unequal pairs have full rank.Source: B5: Rank Difference · p. 37

B6: Rank Single Ciphertext

• Single-ciphertext rank rises with plaintext support weight, exposing more than whether the plaintext is zero; under double encryption, the intermediate’s high entropy limits useful constraints on the original.Per-session ideal rotation further caps samples collected under any one ideal.Source: B6: Rank Single Ciphertext · p. 38

B7: Sampler Distance; B8: Distance-Staircase

• Sampler-distance tests were near-uniform for single encryption and occasionally biased for double encryption; distance-staircase rank rose monotonically with differing SIMD slots.The sampler probe is only a proxy for mask quality, while double-encryption distance samples do not map to useful constraints on original low-entropy slots.Source: B7: Sampler Distance · p. 38, B8: Distance-Staircase · p. 39

B9: Affine Harness Test

• The labelled affine harness recovered the decryption map after matched pairs spanned the ciphertext subspace, but matched pairs are unavailable to the private-key evaluator.Empirical recovery succeeded in 100 of 100 trials at 513 and 2,049 pairs and in none of 100 trials at up to nine fewer pairs.Source: B9: Affine Harness Test · p. 39