Archives for posts with tag: Brakerski

Fully homomorphic encryption has evolved from Craig Gentry’s original work based on worst case problems in ideal lattices and problems based on sparse subset sums, to newer schemes such as the BGV Ring Learning With Errors (LWE) scheme (based on lattice SVP) – This is a scheme where the plaintext space is taken to consist of integer  subrings \mathcal{O}_{\mathbb{Q}(\zeta_m)} = \mathbb{A}_p  : = \mathbb{Z}[X]/\langle \Phi_m(X),p \rangle \cong \mathbb{Z}_p(\zeta_m) of  cyclotomic number fields \mathbb{Q}(\zeta_m)/\mathbb{Q}. Of the lattice based schemes, other than the Ring LWE based BGV scheme, (named after Brakerski, Gentry and Vaikuntanathan) there is also the “LATV” scheme of Lopez-Alt, Tromer and Vaikuntanathan, based on the NTRU problem, and Brakerski’s “Scale Invariant” scheme. Notably, the BGV scheme introduces the novel modulus switching technique that, while ensuring the correctness of the scheme, allows the evaluator to scale down the magnitude of the noise in the ciphertexts without knowing the secret key. But here, we pause and take note of the original noise management technique in Gentry’s original work, which is commonly known as the bootstrapping theorem – it states that efficient fully homomorphic encryption can be constructed from a somewhat homomorphic scheme that “compactly” evaluates its decryption circuit.

To expand on this notion, consider a ‘somewhat’ homomorphic scheme \varepsilon with plaintext space P = {0,1}, a ciphertext \Psi_1 that encrypts a message \pi under a public key pk_1, and a secret key sk_1 associated with pk_1. The key sk_1 is then encrypted under a second public key pk_2. Denote the encryption of the jth bit of sk_1 under pk_2 as \bar{sk_1}_j.  Define a ‘re-encryption’ procedure for the ciphertext \Psi_1 as the following –

Recrypt_\varepsilon(pk_2,D_\varepsilon, \langle \bar{sk_1}_j \rangle, \Psi_1) :

1) \bar{\Psi_1}_j \gets Encrypt_\varepsilon(pk_2, \Psi_1j)

2) \Psi_2 \gets Evaluate_\varepsilon(pk_2, D_\varepsilon, \langle \langle \bar{sk_1}_j \rangle, \langle \bar{\Psi_1}_j \rangle \rangle)

Where D_\varepsilon denotes the scheme’s decryption circuit. The algorithm takes the bits of the ciphered message \Psi_1 (which is an encryption of the message \pi under pk_1), and encrypts them under the ‘outer’ encryption key pk_2 to yield the ciphertext bits \bar{\Psi_1}_j.  The decryption circuit is then homomorphically evaluated with the ciphered decryption secret \bar{sk_1} (the secret key sk_1 encrypted under pk_2) and the ‘doubly’ encrypted message ciphertext \bar{\Psi_1}. This latter step removes the ‘inner’ encryption of the message \pi under the key pk_1, thereby yielding the ciphertext \Psi_2 which is just the encryption of \pi under pk_2. The bootstrapping theorem states that such an algorithm can be used as an effective noise reduction mechanism to create a fully homomorphic encryption scheme from a somewhat homomorphic one so long as the decryption circuit is “compact” and does not increase noise components to a level that results in ciphertext “wraparound” in the underlying ring. Another way to say this is that the scheme cannot work if the magnitude of ciphertext noise results in reductions modulo q during decryption, where q is a parameter that characterizes the ciphertext space. Interestingly, the decryption circuit associated with Gentry’s original somewhat homomorphic scheme was not sufficiently compact for bootstrapping fully homomorphic encryption. The curcuit was therefore “squashed” along with an approach where the party encrypting data  initiates the homomorphic decryption process.

In the context of privacy preserving outsourced computation, the Recrypt procedure described would typically be evaluated by an untrusted counterparty. Therefore, it cannot compromise the security of secret keys (This is the case since \bar{sk_1} used by the decryption circuit is the encryption of a secret key rather than the secret key itself) [Todo: discuss circular security and security of key dependent messages].

Lets take a step back and consider some essential aspects of the problem and of Gentry’s original scheme  – Fully homomorphic encryption (FHE) schemes allow for the computation of arbitrary functions on encrypted data viz. you can do anything on the data that can be efficiently expressed as a circuit. FHE schemes have eluded cryptographers for at least 3 decades. In 2009 Craig Gentry published an initial scheme based on the ideal coset problem instantiated over ideal lattices, that is lattices corresponding to ideals in polynomial rings of form \mathbb{A} = \mathbb{Z}[X] / \Phi_m(X) , consisting of residues of integer polynomials modulo the m'th cyclotomic polynomial $latex \Phi_m(X) $ of degree m.

Specifically, in his initial somewhat homomorphic construction, Gentry employs computational assumptions around the ideal coset problem (ICP) – when instantiated over ideal lattices. this is equivalent to the so called the bounded distance decoding problem (BDDP). The second computational assumption used involves sparse subset sums – this arises out of a requirement to  ‘squash’ the decryption circuit in order to address its essential non-compactness .  At the time, lattices were chosen to further minimize complexity of the decryption circuit and facilitate the bootstrap while maximizing the scheme’s evaluative capacity – decryption in lattice based schemes is typically dominated by matrix vector multiplication (NC1 complexity). Contrast this to RSA, for instance, that requires evaluating modular exponents.

To recap, a central aspect of Gentry’s result is precisely bootstrapping, which brings us to US patent 2011/0110525 A1 granted May 12 2011 “Fully homorphic encryption method based on a bootstrappable encryption scheme, computer program and apparatus” (Asignee IBM).  Within the detailed description of the invention, the following is stated – “It is shown that if the decryption circuit of a somewhat homomorphic encryption scheme is shallow enough, in particular, if it is shallow enough to be evaluated homomorphically by the somewhat homomorphic scheme itself (a self-referential property), then this somewhat homomorphic scheme becomes “bootstrappable”, and can be used to construct a fully homomorphic scheme that can evaluate circuits of arbitrary depth.” The description within the remaining text of the patent is essentially a distillation of Gentry’s 2009 thesis. So on the face of it, it does look like bootstrapping is covered by the patent.

There is the lingering question of the applicability of this (or other) patents to the “leveled”  scheme of Brakerski, Gentry, Vaikuntanathan (BGV) published in 2011. This is a fully homomorphic scheme based on the learning with errors (LWE) or Ring-LWE (RLWE) problem/s. Rather than bootstrapping as a noise management technique, BGV starts with somewhat homomorphic encryption and uses tensor products along with a process called re-linearization and modulus switching to maintain the relative magnitude of ciphertext noise during homomorphic evaluation, but does propose bootstrapping as an optimization for evaluating deeper circuits that otherwise in the purely leveled scheme may require very large parameter choices for “aggregate” plaintext / ciphertext rings.

Concerning references and the attribution of results – the work discussed spans multiple groups and individuals including Craig Gentry, Vinod Vaikuntanathan, Shai Halevi, Zvika Brakerski, Nigel Smart, F. Vercauteren, Adriana Lopez-Alt and Eran Tromer to name a few.

Some notes on the Brakerski and Vaikuntanathan’s (BV) homomorphic encryption scheme published in 2011, two years following Gentry’s publication of a fully homomorphic encryption scheme.

BV achieves fully homomorphic properties from the standard learning with errors problem (LWE). Gentry’s original scheme was based on ideal lattices. This was partly motivated through natural homomorphisms that arise from using ideals in rings given the fact that they’re closed under addition and multiplication. BV, however, contend that the security of schemes based on ideal lattices rests on relatively untested cryptographic assumptions, in addition to which, the bootstrapping procedure in Gentry’s formulation requires “squashing” or simplifying the decryption circuit, which introduces an additional hardness assumption in the form of the sparse subset sum problem. The BV scheme, in contrast, is based on known worst case, classical hardness assumptions of standard problems on arbitrary lattices – the specific problem employed in this scheme is learning with errors (LWE), which states that given an n dimensional secret vector over an integer field, any polynomial number of “noisy”, random linear combinations of the coefficients of the vector are indistinguishable from uniformly random elements in the underlying field. Best known algorithms for LWE are almost exponential in dimension n of the secret vector.

An artifact of cipher text multiplication in BV is that the resulting polynomial expression contains terms quadratic in the secret key. Therefore a key aspect of the scheme is so called “re-linearization” which involves publishing encryptions of linear and quadratic terms in the secret key in the resulting polynomial under a new secret key. The substituted expression is then linear in the new secret key. The scheme additionally relies on creating a chain of L secret keys along with encryptions of the quadratic terms of a given key in the chain under the next key. This allows for L levels of multiplications under the scheme.

Similar to Gentry’s original blueprint, BV starts with a somewhat homomorphic  scheme based on standard LWE, and then creates a bootstrappable scheme that inherits initial scheme’s homomorphic properties and utilizes dimension modulus reduction for managing cipher text noise during successive evaluations up to the prescribed multiplicative depth. From a security standpoint, dimension modulus reduction does not significantly affect Regev’s reduction of Decision LWE (DLWE) to approximate, worst case short vector problems (SVP) on reduced dimensional lattices, thereby maintaining security of the initial scheme.

So what’s the relationship to existing patent’s for Gentry’s scheme?  Not sure. Next we will discuss aspects of the Brakerski, Gentry, Vaikuntanathan (BGV) scheme that among other things, is a “Ring-LWE” adaptation of BV that incorporates Smart Vercauteren batch operations (“cipher text packing”) by defining the message space to consist of elements in a polynomial ring.

%d bloggers like this: