Formal security analysis performed on GKS private-key FHE scheme
The claim
The GKS FHE scheme is secure under the authors' formal analysis
Published as: “GKS Fully Homomorphic Encryption: Security Analysis”
So what
The scheme offers a private-key FHE alternative with conditional ciphertext-only security, but practical deployment must address collision-harvest risks and the weak post-ideal security before it can replace lattice-based FHE in real applications.
The five-minute version
GKS private-key FHE achieves conditional single-ciphertext IND-EAV security after conditioning on the publicly observable rank, but its multi-ciphertext COA security depends on preventing same-value collisions, which are only mitigated by the not-yet-implemented Zero Collision Guarantee (ZCG). The evidence includes a proof of conditional IND-EAV and empirical checks showing no distinguisher on equal-weight ensembles, while the paper admits that post-ideal recovery security is modest and that a full ITS proof is open.
What they found 3
- Conditional IND-EAV holds after conditioning on rank (Hamming weight).
“Single-ciphertext IND-EAV holds after conditioning on the publicly observable rank (equivalently, Hamming weight). Unconditional advantage zero is not claimed.”
- Equal-weight plaintext ensembles show no distinguisher above noise floor.
“Equal-weight ensembles showed no distinguisher above the sampling noise floor (Appendix A.2).”
- Multi-ciphertext COA attacks require a same-value pair under one ideal; mitigation relies on ZCG which is not yet fully implemented.
“Residual issue: requires a same-value pair under one ideal. Mitigated if ZCG is enforced (§3.5.7); ZCG is designed, not yet fully implemented.”
What undercuts it the paper’s own results
- The paper admits that after the ideal I is recovered, the remaining security barrier is only an O(p) embedding search (~30 bits), which is weak.
- A proof that the statistical distance is negligible remains open, so the authors do not claim a completed ITS theorem.
Stated limits 3
- A proof that the statistical distance is negligible remains open, so we do not claim a completed ITS theorem.
- The map from the published f-basis to canonical coordinates is a public prefix-sum. Consequently the 2n plaintext-bearing coordinates are unmasked. For non-uniform plaintext distributions an eavesdropper can therefore recover the multiset of slot values (up to the secret permutation) from a single ciphertext.
- Until measurements of uniformity are finished we treat the fixed-T single-layer configuration as unsuitable for low-entropy plaintexts and recommend double encryption together with ideal rotation and (where possible) random-T.
What’s new here 4
- Provides the first formal security analysis of a private-key FHE scheme (GKS) rather than lattice-based public-key schemes.
- Introduces and analyzes the Zero Collision Guarantee (ZCG) mechanism to mitigate collision-harvest attacks.
- Defines and studies new hardness assumptions specific to idempotent ring structures (ZKI, TBI, RI-D, RI).
- Offers detailed combinatorial key-space counting and retraction-ambiguity bounds for the scheme.
Threat model stated by the source
Artifacts & methods 5
- GKS private-key FHE schemesystem
- Zero Collision Guarantee (ZCG)
- Bijective encoding
- Ideal rotation
- Performance measurements on commodity hardwareevaluation