6
$\begingroup$

As it is discussed here that the highest security any homomorphic encryption scheme is at most IND-CCA1, Is there any known fully homomorphic encryption scheme that achieves this security level? Out of many schemes mentioned here (or otherwise) which of them are IND-CCA1 secure ? (not necessarily practical though)

$\endgroup$
  • 2
    $\begingroup$ I am only aware of this paper studying the CCA1 security of very early FHE schemes: eprint.iacr.org/2010/560. $\endgroup$ – DrLecter Oct 31 '15 at 10:43
  • $\begingroup$ I thought this other stackexchange question mention some good articles too crypto.stackexchange.com/questions/627/… (sorry I would like to put this as a comment not as an answer to your question but I don't have enough reputation) $\endgroup$ – lcestari Nov 1 '15 at 23:43
  • $\begingroup$ If you mean "strongest" in terms of security, any FHE scheme based on standard lattice assumptions (NOT ideal lattice assumptions) and reducible to a known hard problem on lattices is probably the strongest. $\endgroup$ – pg1989 Nov 2 '15 at 1:12
  • $\begingroup$ What level of strength ? CCA-1 ? or less ? $\endgroup$ – sashank Nov 2 '15 at 3:11
  • $\begingroup$ @DrLecter I learnt offline from NP Smart that, the scheme in the paper you mentioned is prone to Soliloquy attack and that it is no longer considered stronger , i could not get any reference to it though beyond this web.eecs.umich.edu/~cpeikert/soliloquy.html $\endgroup$ – sashank Nov 2 '15 at 3:13
1
$\begingroup$

A recent paper: https://arxiv.org/abs/1804.06862 claims to be fully homomorphic with IND-CCA1. However it is a symmetric encryption scheme and I'm not sure if IND-CCA1 is an appropriate measure in this setting.

Besides this, I think security is based on the hardness of solving overdetermined systems of quadratic equation over $\mathbb{Z}_{(p\cdot q)^2)}$ rings, which then might not be Quantum-hard. If I'm not mistaken, there are sixteen quadratic equations and if we can factor $(p\cdot q)^2$ then these equations can be efficiently solved.

Otherwise the scheme is pretty efficient, in terms of key-length, decryption and encryption time, I think. It is noise free and based on ring-automorphisms for matrices with elements from the quaternion-ring over some $\mathbb{Z}_{(p\cdot q)^2)}$ ring.

However as the paper appeared only recently, an in-deep analysis, besides the argumentation auf the authors, is not yet availablabe as far as I know.

$\endgroup$
  • $\begingroup$ I glanced through the paper, and I don't see the quadratics. Unless I'm missing something, the encryption process would appear to be a linear function of the plaintext and the random data, where the plaintext and the random data are linearly independent. If this is correct, then it should be easy enough to break by asking for the known plaintext of the same plaintext repeatedly, and then look for the common subspace (which you can do even if you don't know the factorization of $pq$) $\endgroup$ – poncho May 25 '18 at 21:37
  • $\begingroup$ The paper proves that recovering the 'key' is a hard problem; they don't address recovering the plaintext (which, if my surmise is correct, is easy) $\endgroup$ – poncho May 25 '18 at 21:48
  • 2
    $\begingroup$ Verified; if you look at equation 1 on page 6, the plaintext $m$ is just $\sum x_{i,j} c_{i,j}$, for 16 secret values $x_{i,j}$ ($x_{i,j}$ are quadratic functions of the 'real' key, we will choose to ignore that, and just deal with the $x_{i,j}$ values); if you obtain 16 known ciphertexts, you can just solve the 16 linear equations to recover $x_{i,j}$, and that allows you to decrypt everything. So, to address the OP's question, this would appear not to be the most FHE solution out there... $\endgroup$ – poncho May 25 '18 at 22:10
  • $\begingroup$ Equation 1 on page 6 is not linear, since all elements are from quaternions over a ring. Hence their product $\cdot$ is not commutative! They are of the form $\ldots \overline{a}_{d,e}\cdot c_{f,g}\cdot a_{h,i} * \ldots $ and you can not simply rewrite this into $\ldots \overline{a}_{d,e}\cdot a_{h,i}\cdot c_{f,g}$. Thats is, what I mean with quadratic. Linear equations whould be trivial, of course. Hover, although the quaternionic prodoct is not commutative, in case of Quaternions over $\mathbb{R}$ or $\mathbb{C}$ the product is just antisymmetric, which would make the equations indeed... $\endgroup$ – Mark Neuhaus May 25 '18 at 22:43
  • 1
    $\begingroup$ But on the other side, you might still enrole each quaternion into a four dimensional vector (actually its not a vector but a module element) with some multiplication and then you can eventuelly rewrite into a linear system using commuativity in $\mathbb{Z}_{(qp)^2}$. Would be great to see in detail where this leads to! You might get $64$-equation instead, but if they are linear, its still easy to solve using Ring-Gauss $\endgroup$ – Mark Neuhaus May 25 '18 at 23:02

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.