6
$\begingroup$

Came across this startup claiming practical FHE and then their blog post going into some additional details on it.

It was my understanding that practical FHE is still years/decades off. They said back in September 2015 that they would publish the details of their FHE cipher which they call “KFHE”, but it appears that the details still have not been released (as of June 2016). They have released the source code for their KFHE implementation, however. From it, it appears they are using multivariate quadratic FHE.

What is multivariate quadratic FHE and what is unique about this FHE compared to previous attempts? How does this hardness assumption compare to others that have been previously used in building FHE?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ @CatNap, I've edited your question to make it more concrete and reopened the question. I hope I haven't altered your original intent too terribly much. If so, feel free to edit. $\endgroup$
    – mikeazo
    Commented Jun 2, 2016 at 1:12
  • 1
    $\begingroup$ I don't see anybody with a crypto backgroud in the list of actual employees of the company. I see a CEO and software engineers. This in itself is a bad sign. They list JC Faugère and L Perret which are serious reference but in now do they say if their involvment went beyond answering yes to the question "Can I use your name ?". Another bad sign Since they admit that the primitive has been broken we need to trust them that their unpublished countermeasures. Really really bad sign. I can't tell if there is something to it but from all of the above. It doesn't look good. $\endgroup$
    – Alexandre Yamajako
    Commented Jun 2, 2016 at 4:28
  • $\begingroup$ @AlexandreYamajako, I must have missed where they admit that their primitive has been broken. Where is that? $\endgroup$
    – mikeazo
    Commented Jun 2, 2016 at 11:17
  • $\begingroup$ This is what I get from this paragraph "Much of the work in this space has been pioneered by both Faugère and Perret — with whom we’ve been working in order to build a primitive that’s hardened against the classes of cryptanalytical attacks they’ve published." Actually, the only two peer reviewed papers they cite are cryptanalysis papers from Faugère & Perret $\endgroup$
    – Alexandre Yamajako
    Commented Jun 3, 2016 at 1:47
  • 2
    $\begingroup$ That is emphatically not what that paragraph says. One can question the wisdom of using an MQ hardness assumption, but to say their specific assumption has been broken is incorrect. $\endgroup$
    – pg1989
    Commented Jun 3, 2016 at 17:30

1 Answer 1

Reset to default
8
$\begingroup$

I've spoken to the CEO a couple times. They've contracted some prominent French cryptographers to vet their cryptosystem, but no security analysis or whitepaper has been released.

Their KFHE scheme is different than previous schemes because it uses a different hardness assumption that leads to better performance and smaller keys. Previous FHE schemes used hardness assumptions based on ideal lattices, but their scheme uses a different assumption based on the hardness of solving a system of quadratic equations in many variables. Whether their construction truly is a practical general-purpose FHE scheme is not clear, since perf numbers for general circuits are not available (as far as I know).

Schemes based on solving systems of multivariate quadratic equations have some nice properties, including the aforementioned performance benefits as well as conjectured resistance to quantum attacks, but have proven extremely difficult to get right. Many schemes based on these assumptions have been severely broken. However, there exist cryptosystems from this family that are widely believed to be secure.

The homomorphic properties of their scheme are used to build a kind of multi-user searchable encryption in their main product, Kodex. A user allows other users to search on their documents by homomorphically sharing document search keys. I don't know all the details, but my guess is this specific 'share' operation can be done efficiently because they avoid evaluating a circuit and just do stuff directly.

As with all shiny new things in cryptography, caution is called for. Editorializing a bit, I see little reason to believe this is snake oil. [Indeed, if they were only looking for a rubber stamp from Faugere and Perret it seems like something would have been made public already.] However, perfectly honest and forthright people have built many, many broken cryptosystems, so I recommend taking any claims with a moderately-sized grain of salt until given reason to do otherwise.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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