Fully homomorphic encryption from GSW and decision LWE #
Gentry's generic bootstrapping constructions are instantiated with GSW at the logarithmic-depth
parameter family. The base scheme is DepthParameters.scheme, its decryption circuits are the
actual raw-input decryptors, and its bootstrappability, correctness, widths and native runtime
are proved without computational assumptions. Bootstrappability is for Gentry's gate set
Γ = {identity, NAND}: the schemes evaluate De Morgan circuits by compiling each De Morgan level
into two NAND levels.
The security premise is decision LWE for exactly this family: secret dimension λ + 1,
centered-binomial noise of width λ + 1, and the quasi-polynomial modulus 2 ^ (16384 * t ^ 2)
with t = 1 + ⌈log₂ (λ + 2)⌉.
- Leveled FHE. One uniformly generated polynomial-size decryption circuit family, one natively
computable decryption algorithm and fixed polynomial widths are chosen first. Then every
polynomially bounded depth family is covered by an actual scheme with that decryption algorithm,
assuming only decision LWE [Gentry2009, Definition 3 and Theorem 3]. Security is proved both
asymptotically (
exists_leveled_of_decisionLWE) and with a concrete-security reduction matching Gentry's Theorem 4 up to a constant factor (advantage_leveled_eqandadvantage_leveled_le, [Gentry2009, Section 2, Theorem 4, p. 171], with asymptoticIsPPTrather than a multiplicative runtime bound relative to the adversary). Native certificates are uniform for each depth family; key generation reads only the unary security parameter. - Fully homomorphic encryption. The one-key self-loop construction evaluates every circuit,
assuming decision LWE for this family and the separate one-key circular-security assumption
Encryption.CircularSecurefor the base scheme [Gentry2009, Section 2, the self-loop construction]. This is a one-key specialization of the KDM security Gentry assumes there. Circular security is not derived from LWE.
Neither theorem asserts lattice hardness, a worst-case reduction, or circuit privacy.
Main results #
Cslib.Crypto.Homomorphic.GSW.DepthParameters.computableInPolyTime_secretWidth: the base GSW secret width is computable in polynomial time in unary.Cslib.Crypto.Homomorphic.GSW.DepthParameters.isPPT_leveledAdversary: the unified base reduction for the leveled GSW scheme is native strict PPT.Cslib.Crypto.Homomorphic.GSW.DepthParameters.advantage_leveled_eq: exact concrete-security reduction loss of the leveled GSW scheme to the base GSW scheme.Cslib.Crypto.Homomorphic.GSW.DepthParameters.advantage_scheme_le: concrete-security bound for the base GSW scheme in terms of decision-LWE advantage andhidingError.Cslib.Crypto.Homomorphic.GSW.DepthParameters.advantage_leveled_le: concrete-security bound for the leveled GSW scheme in terms of decision-LWE advantage andhidingError.Cslib.Crypto.Homomorphic.GSW.DepthParameters.exists_leveled_decrypt_circuits: uniformly generated polynomial-size decryption circuits for the leveled GSW scheme across all budgets.Cslib.Crypto.Homomorphic.GSW.DepthParameters.exists_leveled_of_decisionLWE: leveled FHE.Cslib.Crypto.Homomorphic.GSW.DepthParameters.fullyHomomorphic_of_decisionLWE_of_circularSecure: FHE under the additional circular-security assumption.
References #
The base GSW secret width dimension k * width k is computable in polynomial time in unary.
For any polynomial-time unary budget family, the unified base reduction leveledAdversary
for the leveled GSW scheme is native strict PPT.
Exact concrete-security reduction loss of the leveled GSW scheme to the base GSW scheme ([Gen09], Section 2, Theorem 4, p. 171, up to a constant factor in the loss; the running-time clause is not formalized).
One uniform reduction bounds the base GSW scheme's chosen-message advantage by twice its
decision-LWE advantage plus hidingError.
Concrete-security bound for the leveled GSW scheme in terms of the decision-LWE distinguisher
advantage and hidingError ([Gen09], Section 2, Theorem 4, p. 171, up to a constant factor
in the loss; the running-time clause is not formalized).
The leveled GSW scheme's complete tagged decryption algorithm has a uniformly generated family
of polynomial-size circuits on the derived widths
(3 * secretWidth k + 1) + (ciphertextWidth k + 1), shared across all depth budgets and requiring
no computational assumption.
Leveled FHE from GSW under decision LWE for this family, with quasi-polynomial modulus.
One uniformly generated polynomial-size circuit family computes the common decryption algorithm
Leveled.decrypt decryptionCircuits, which is natively computable, and the key and ciphertext
widths are fixed polynomials; all of these are chosen before the depth. Every polynomially
bounded depth family is then covered by an actual scheme with an efficiently computable budget
and exactly that decryption algorithm: it is correct for every circuit of the requested depth,
has the fixed widths, native algorithms and IND-CPA security. No circular-security assumption is
used.
Fully homomorphic encryption from GSW: under decision LWE for this family, with quasi-polynomial modulus, and the explicit one-key circular-security assumption for the base scheme, the self-loop construction correctly evaluates every finite circuit. Its widths are those of GSW, its decryption circuits have polynomial size, its four algorithms are native, and it is IND-CPA.