Talk:Homomorphic encryption

Plain English?

I came to this page while searching for an explanation of "fully homomorphic encryption." While the explanation on this page may be rigorous, it is not understandable to someone untrained in the mathematics. Is it possible to include a brief explanation of the proof and the results for the non-specialist?

Cyberpageman (talk) 13:54, 11 June 2010 (UTC)

Try http://www.mail-archive.com/cryptography@metzdowd.com/msg10571.html for a very high-level description, and then http://cacm.acm.org/magazines/2010/3/76272-computing-arbitrary-functions-of-encrypted-data/fulltext for a still reasonably high-level description, but with much more detail.

Le Grande Pamplemousse (talk) 18:54, 16 June 2010 (UTC)

Paillier

For the Paillier cryptosystem, shouldn't E(x1 + x2 mod n) be E(x1 + x2 mod m)?

That's right. I just fixed it. --Beamishboy 20:43, 11 May 2007 (UTC)

Intentional

If we're going to define Homomorphic encryption as an intentional property (as opposed to malleability, which may not be), we need to provide citations that show the designers of each of the listed cryptosystems intended it. That seems unlikely, for some of them (e.g. RSA). Superm401 - Talk 19:16, 26 November 2007 (UTC)

We should not define it as an intentional property, but it is a property that may be intentional. The point is good though: should the introduction not read "Intentionally homomorphic encryption schemes are malleable by design." ? Quondum (talk) 15:15, 13 July 2011 (UTC)

New Results?

http://www.net-security.org/secworld.php?id=7690

Secure data transmission

The intro of the article says:

Homomorphic encryption schemes are malleable by design and are thus unsuited for secure data transmission.

This seems wrong to me. Doesn't it confuse encryption with signing?

--Craig Stuntz (talk) 14:58, 18 March 2010 (UTC)

'secure' is a tricky word to use in crypto, without specifying which kind of threat a scheme protects against. Is it secure in the sense that you

know the sender, and the integrity of the message, or secure in the sense that an eavesdropper cannot read the content ? --Eivind Kjørstad (talk) 13:30, 9 August 2011 (UTC)

Bad explanation?

Does the first sentence "Homomorphic encryption is a form of encryption where a specific algebraic operation is performed on the plaintext and another (possibly different) algebraic operation is performed on the ciphertext" manage to say what it means? Shouldn't it say something like "In homomorphic encryption, there are algebraic operations X and Y such that X followed by encryption is the same as encryption followed by Y" ? —Preceding unsigned comment added by 128.240.229.3 (talk) 17:35, 6 January 2011 (UTC)

The first statement is definitely lacking in this case. The sentence should rather read something like "Homomorphic encryption is a form of encryption that maps some algebraic structure on the set of plaintexts to an equivalent structure on the set of ciphertexts – i.e., in which the encryption operation is a homomorphism". Quondum (talk) 16:14, 13 July 2011 (UTC)

Voting systems, collision-resistant hash functions, and private information retrieval

From the article:

The homomorphic property of various cryptosystems can be used to create secure voting systems,[1] collision-resistant hash functions, and private information retrieval schemes.

I think it would be good to explain exactly how each of these three examples would come about because of a fully homomorphic encryption scheme. 81.178.246.255 (talk) 19:35, 17 May 2011 (UTC)

Unfounded claims, work in progress, and advertisement?

In addition to the lack of plain English already cited, this article suffers from a number of other problems that make it inconsistent with Wikipedia principles:

1) Homomorphic encryption is very much a "work in progress", an area under active research. Parts of this article read like breathless news reports, albeit news reports on a very slow-moving story.

2) While there are references, other claims are made without support or citation, such as "enable widespread use of cloud computing" and "an efficient and fully homomorphic cryptosystem would have great practical implications" (hard to say why this would, when it is difficult to understand the subject; seems like an authority saying "trust me, this is so").

3) There is no specific "weakness" or "critique" section - everyone is presented as good news (or pretty good news or mostly likely to be pretty good news).

4) The page links to other articles of similar opacity, articles that may exist just to promote homomorphic encryption.

5) Why are there no links to cryptography portal or to the page on Homomorphism? (http://en.wikipedia.org/wiki/Homomorphism)

The article seems to read like a promo piece written by someone who understands the topic and loves the topic and wants us all to love the topic, but cannot be bothered explaining it to the rest of us, telling us how it relates to anything else, or what might be good and might be bad about it. — Preceding unsigned comment added by PeterWhittaker (talk • contribs) 14:41, 31 July 2011 (UTC)

Answering your third point: the weakness part is very technical, but someone could write things about the impossibility of obtaining a IND-CCA2 homomorphic scheme and that it is hard (nowadays) to find even IND-CCA1 schemes. Also, it is possible to write about the unusual assumptions, like the circular security one. Another drawback of homomorphic schemes is that they are very slow. But we do not know until know if it is a intrinsically property or if truly efficient homomorphic encryption schemes may happen some day. -- Lp.vitor (talk) 02:23, 15 June 2016 (UTC)

Fully homomorphic

The definition "Fully Homomorphic Encryption: We say that a homomorphic encryption scheme E is fully homomorphic if it compactly evaluates all circuits." from Gentry's thesis is supposed to distinguish a scheme of limited multiplicative depth (a somewhat homomorphic scheme) from a multiplicatively unlimited scheme rather than an algebraically homomorphic scheme, i.e. a scheme that supports addition and multiplication, from one that supports only one operation. In the current definition of "FHE" the somewhat homomorphic schemes would be already "fully homomorphic". — Preceding unsigned comment added by 91.43.122.207 (talk) 00:54, 13 December 2011 (UTC)

Anybody got any comment on this? Otherwise we should modify the article. — Preceding unsigned comment added by 93.199.37.153 (talk) 23:42, 16 December 2011 (UTC)

There may be a problem in the interpretation, an particular that calling the limited depth scheme being "somewhat homomorphic" may not be implying "not FHE", but rather "limited depth FHE", where FHE still refers to algebraic homomorphism. The concept of algebraic homomorphism is too crucial to the topic to reuse the obvious name FHE to mean something completely different. I have not read the thesis in detail and am not qualified to comment; I am merely bringing attention to this possible confusion. Quondum^talk_contr 05:03, 17 December 2011 (UTC)

A slide from a talk by Nigel Smart and Frederik Vercauteren (linked in the references section) reads "A somewhat homomorphic scheme is one which can evaluate homomorphically all arithmetic circuits from a given set C (e.g. bounded depth)." Mihalog

Category of integers?

I don't understand the following paragraph in the article.

The "homomorphic" part of a fully homomorphic encryption scheme can also be described in terms of category theory. If C is the category whose objects are integers (i.e., finite streams of data) and whose morphisms are computable functions, then (ideally) a fully homomorphic encryption scheme elevates an encryption function to a functor from C to itself.

How can the domain of a computable function be a single integer? As standardly defined it is a set of integers (or more usually of natural numbers).

Since the paragraph neither makes sense nor is sourced, I propose simply deleting it. --Vaughan Pratt (talk) 23:50, 19 October 2012 (UTC)

I agree: the statement does not seem to make sense. Obtext (talk) 06:08, 23 October 2012 (UTC)

I also agree: this does not make sense on the face of it, although I have seen a similar construction: for example, let A be a set; then the category of elements of A has as objects the elements of A and morphisms a→a' functions A→A such that f(a) = a' . In any case, the article does express a good idea--- well, to me at least--- and I'd like to clarify just what the idea is. I believe the real situation is something like this: Consider the category C with one object, the set N of natural numbers. Morphisms are computable functions, all going from N to N. What would be good for homomorphic cryptography is an endofunctor of C that is naturally isomorphic to the identity on C. The isomorphism takes a natural number to its encoding; it needs to be an isomorphism so that decoding is possible; functorality, as described in the article, makes it as homomorphic as possible. The only thing I'm curious about is naturality. If N is the functor and X is the encoding function, naturality amounts to X(f(n)) = (F(f))(X(n)), for all f:N→N, n in N. This looks useful but I'm not sure if it doesn't make it insecure somehow; I know more about category theory than cryptography. Cyrapas (talk) 00:07, 11 June 2013 (UTC)

Alternatively, they might simply be making use of the fact that the set of natural numbers is isomorphic to the set of finite sets (or sequences) of natural numbers (this is borne out by the `finite streams of data' comment). Cyrapas (talk) 00:10, 11 June 2013 (UTC)

Cyrapas's description involving the category with one object is more accurate than what's there now (though, I think it just has to be a natural injection from the identity functor to the endofunctor X, rather than a natural isomorphism: not all numbers have to be the encryption of some number). If others think it would be illuminating or helpful, we should replace the current pararaph with a version of it. Freebirth Toad (talk) 06:58, 19 February 2014 (UTC)

Nov 2012 Breakthrough

I'm not the most savvy cryptographer, but the last paragraph in this article seems very suspicious. In the citation it claims:

Cutting the long story short, ZK111 is information theoretic secure, quasi-linear O(n· logn), fully-homomorphic, public key encryption algorithm. It is one of its kind because all of the above mentioned features were never present in one single algorithm.

Are literally impossibly good. Theoretically secure public key? That alone seems provably impossible. Can anyone explain how this algorithm works? Otherwise I'll be removing it. Sylvanelite (talk) 23:53, 4 December 2012 (UTC)

Unpadded RSA equation wrong?

I wrote a simple program to verify the unpadded RSA multiplication. According to the text ε(x1)*ε(x2) = ε(x1*x2 mod m), but that doesn't seem to work. What seems to be correct is (ε(x1)*ε(x2)) % m = ε(x1*x2 % m) 178.1.54.238 (talk) 22:37, 23 March 2016 (UTC)