8
$\begingroup$

Smart and Vercauteren proposed a homomorphic encryption scheme (PKC 2010) following Gentry's principles. ​ Though their scheme can achieve fully homomorphism theoretically, they admitted that "for practical values of n our scheme cannot be made fully homomorphic" (p. 16).

However, perhaps the only (see update 1 below) public fully (not somewhat) homomorphic encryption implementation libScarab, is claimed to be using the SV scheme. ​ The authors of that library also have a paper "POSTER: An Implementation of the Fully Homomorphic Smart-Vercauteren Crypto-System" (CCS'11) about their implementation.

There are several parameters chosen differently in the latter paper from the original paper, maybe for achieving full homomorphism. But they did not explain the security of their choices, and I cannot figure out it by myself.

So my question is, can libScarab be viewed as a serious secure FHE implementation?

Update 1 (18 Nov 2015)

I've found there are two other public fully homomorphic encryption (including bootstrapping) libraries (HELib and FHEW) released by illustrious cryptologists Shai Halevi / Victor Shoup and Leo Ducas / Daniele Micciancio. Both are slower than libScarab, but I think they supply more security.

| improve this question | |
$\endgroup$
7
$\begingroup$

The SV scheme made some significant simplifications that turned out to hurt security. Specifically, it's known how to break the scheme in subexponential time (roughly $2^{n^{2/3}}$) in the dimension $n$ of the lattice defined by the public key. Moreover, it's known that the scheme can be broken in polynomial time by a quantum computer. In short, the reason is that the SV scheme has an ad-hoc method of key generation, which tends to produce "weak" ideals that can be attacked more efficiently than arbitrary ideals. See this paper for further details.

| improve this answer | |
$\endgroup$
  • $\begingroup$ In SV, $N$ defined as $N = 2^n$. So the attack is $2^{N^{2/3}}$ or $2^{n^{2/3}}$ $\endgroup$ – kelalaka May 9 '16 at 11:42
0
$\begingroup$

If we refer to the original SV paper we'll find that they compute the security level (although it is assumed to be based on Gentry original work, and without taking their changes into consideration) so for certain values of parameters we can figure out the security level. However, what is really weird is the work that implemented their model, they changed the parameters in a way that, in my opinion, degrades the security into very weak model ($2^{25}$) bit security. Also, I tried to change the parameters myself from the source file and I was surprised how this doesn't affect the keygen time and encryption time (the time should increase as the security parameters increase), but it gives wrong output values.

| improve this answer | |
$\endgroup$
  • $\begingroup$ What was the parameters? $\endgroup$ – kelalaka May 1 '16 at 20:31
  • $\begingroup$ If you look to the header files you'll find the following values: N 8 MU 4 LOG_NU 384 S1 8 S2 5 . These parameters give 34 RSA bit security, which is very weak and can't be used. $\endgroup$ – Never too late May 3 '16 at 8:15
  • $\begingroup$ This is the default values. There the parameters are, AFAIK, B_{2,N} not B_{2,\infty}. $\endgroup$ – kelalaka May 3 '16 at 8:19
  • $\begingroup$ Can you clarify please ? Yes these are the default values, I am trying to change them to reach certain security level $\endgroup$ – Never too late May 3 '16 at 8:23
  • $\begingroup$ It seems, impractical. I was trying to do so, but gave up. In the original article, the depth is so small for the recrypt for practical implementation, they reach "This corresponds to N ≥ 136422400 or thus n 27". $\endgroup$ – kelalaka May 3 '16 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.