In this blog post we outline the main
operations in the YASHE fully homomorphic encryption (FHE) scheme. For the exact details see the paper introducing YASHE.

López-Alt, Tromer, and
Vaikuntanathan proposed a (multi-key) FHE scheme based on the work by Stehlé and Steinfeld in which a provably secure version of NTRUEncrypt is presented with security based on standard problems in ideal lattices. The
FHE scheme from López-Alt, Tromer, and Vaikuntanathan needs to make an
additional assumption relating to the uniformity of the public key, the
so-called decisional small polynomial ratio (DSPR) assumption, to allow
homomorphic operations and remain semantically secure. Brakerski introduced an
approach to limit the noise growth during homomorphic operations via a
tensoring technique.

In this paper, Yet Another Somewhat Homomorphic Encryption (YASHE) scheme is introduced which
incorporates the best of these techniques. YASHE avoids the DSPR assumption by
using the techniques described by Brakerski and construct a new fully
homomorphic encryption scheme from the Stehlé and Steinfeld version based on
standard lattice assumptions and a circular security assumption.

Besides this theoretical advantage,
YASHE has other attractive properties

- This new scheme is scale-invariant: this means it avoids the modulus-switching technique of Brakerski, Gentry and Vaikuntanathan.
- The ciphertext consists of only a single ring element (as in this paper) as opposed to the two or more ring elements for schemes based purely on the ring learning witherrors (RLWE) assumption.

In the following I will describe
the more practical variant of YASHE (denoted YASHE’ in the paper). Note that this practical variant YASHE' does need the DSPR assumption.

In
order to show how YASHE works we need to fix some parameters. Selecting secure
parameters is a difficult task by itself for which tools have been generated
(see for instance our previous blog post).
For this post I simply assume correct and secure parameters have been chosen
(but see the paper for some example parameters). Given the security parameter
$\lambda$, fix a positive integer $d$ and modulus $q$ that determine $R={\mathbb Z}[X]/(\Phi_d(X))$, and $t$ with $1< t < q$, and distributions $\chi_{\mathrm{key}}$, $\chi_{\mathrm{err}}$ on $R$.

The function $P_{w, q}$ is a generalization of the PowersofTwo and $D_{w, q}$ is a generalization of BitDecomp from this paper. Instead of a radix-2 representation these functions use a radix-$w$ system. These function take a single ring element and output $\ell_{w,q} = \lfloor\log_w(q)\rfloor + 2$ ring elements. The choice of $w$ is important since it allows for a trade-off between efficiency and error growth.

**Key generation**. KeyGen $(d,q,t,\chi_{\mathrm{key}}, \chi_{\mathrm{err}}, w)$

- Sample $f', g \leftarrow \chi_{\mathrm{key}}$ and let $f = [tf' + 1]_q $.
- If $f$ is not invertible modulo $q$, choose a new $f'$.
- Compute the inverse $f^{-1} \in R$ of $f$ modulo $q$ and set $h = [tgf^{-1}]_q$.
- Sample $\vec{e},\vec{s}\leftarrow \chi_{\mathrm{err}}^{\ell_{w,q}}$, compute $\vec{\gamma} = [P_{w,q}(f) + \vec{e} + h \cdot \vec{s}]_q \in R^{\ell_{w,q}}$.
- Output $({\sf pk}, {\sf sk}, {\sf evk}) = (h,f,\vec{\gamma})$.

**Encryption**. Encrypt $(m, {\sf pk})$

- For a message $m+tR$, choose $[m]_t$ as its representative.
- Sample $s,e \leftarrow \chi_{\mathrm{err}}$.
- Output the ciphertext $c = [\lfloor q/t \rfloor [m]_t + e + {\sf pk}\cdot s]_q \in R.$

**Decryption**. Decrypt $(c, {\sf sk})$

- To decrypt a ciphertext $c$, compute $m = \left[\left\lfloor \frac{t}{q}\cdot[{\sf sk}\cdot c]_q \right\rceil \right]_t \in R.$

**Key switching**. KeySwitch $(\tilde{c}_{\sf Mult}, {\sf evk})$

- Output the ciphertext $[\langle D_{w,q}(\tilde{c}_{\sf Mult}) , {\sf evk} \rangle]_q$.

**Homomorphic addition**. Add $(c_1,c_2)$

Given two ciphertexts $c_1, c_2\in R$, which encrypt two messages $m_1, m_2$, their sum

*modulo*$q$, $c_{\sf Add} = [c_1 + c_2]_q$, encrypts the sum of the messages

*modulo*$t$, $[m_1 + m_2]_t$.

**Homomorphic multiplication**. Mult $(c_1,c_2, {\sf evk})$

Output the ciphertext

$$c_{{\sf Mult}} = \textrm{KeySwitch} (\tilde{c}_{\sf Mult}, {\sf evk}), \mbox{ where } \tilde{c}_{\sf Mult} = \left[\left\lfloor\frac{t}{q} \cdot c_1 \cdot c_2\right\rceil\right]_q.$$

__YASHE in practice__This practical version of YASHE has been used in order to ensure privacy of sensitive medical data. In this work it is shown how to privately conduct predictive analysis tasks on encrypted data using homomorphic encryption. As a proof of concept a working implementation of a prediction service running in the cloud, which takes as input private encrypted health data, and returns the probability for suffering cardiovascular disease in encrypted form. Since the cloud service uses homomorphic encryption, it makes this prediction while handling only encrypted data, learning nothing about the submitted confidential medical data.

In a recent paper in the framework of the HEAT project, a modular hardware architecture for somewhat homomorphic function evaluation using YASHE is presented. In another recent publication, YASHE is implemented to investigate the potential of FPGAs.

## No comments:

## Post a Comment