Note that I am asking specifically for Partial Homomorphic Encryption (PHE) schemes and not Somewhat Homomorphic Encryption (SHE) schemes. I believe there are several SHE schemes that are symmetric but I am not familiar with any PHE schemes that are symmetric.
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ Well, you could just share the private keys for an asymmetric scheme and don't bother with the public ones... $\endgroup$– SEJPMCommented Aug 18, 2019 at 17:48
-
1$\begingroup$ From Wikipedia, for the persons that are wondering: " Partially homomorphic encryption encompasses schemes that support the evaluation of circuits consisting of only one type of gate, e.g., addition or multiplication. Somewhat homomorphic encryption schemes can evaluate two types of gates, but only for a subset of circuits." However, that makes me wonder, as partially homomorphic seems a subset of somewhat homomorphic. So I presume that there is another specific property - such as performance - that you are after? $\endgroup$– Maarten Bodewes ♦Commented Aug 18, 2019 at 18:22
-
$\begingroup$ Oh, hmm, doesn't need to be a subset of course, if the particular circuits do not allow for one gate to present in all situations... $\endgroup$– Maarten Bodewes ♦Commented Aug 18, 2019 at 18:25
-
1$\begingroup$ Recall any encryption scheme can be made fully homomorphic by allowing for non-compact ciphertexts. While this doesn't answer the question, the circuits you can write with respect to a single (commutative) operation have quite small representations (essentially integers), and moreover the only time you couldn't "decrypt, eval, and re-encrypt" to manage ciphertext size is the case when a single server (who doesn't know the key) is being sent many ciphertexts from many different people (who all do). That all being said, I know of nothing that meets your specification. $\endgroup$– Mark Schultz-Wu ♦Commented Aug 21, 2019 at 7:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
It depends on what you mean by "symmetric". As mentioned in the comments, you could use an asymmetric scheme and let $\mathsf{k} = (\mathsf{sk},\mathsf{pk})$. This seems unsatisfying though.
If you want symmetric to exclude this definition, a natural way to restate your question is "Are there any partially homomorphic encryption schemes in Minicrypt", in the sense that you can build them from solely the existence of a one-way function. I'm unsure of the answer in this situation, but there's some evidence against it being true.
For motivation, an easy way to construct a somewhat homomorphic encryption scheme is from $\mathsf{LWE}$. This states that: $$(A, As + e)\approx_c (A, u)$$ for $A$ and $e$ distributed correctly. Standard LWE encryption schemes then use $As+e$ as a "blind", and then apply the one-time pad. This design pattern of "Use a pseudo-random function to construct a "blind", then use the one-time pad" is fairly common. What gives LWE its homomorphic property is that the pseudo-random function $(A, As+e)$ is somewhat homomorphic.
So, a naturally way to try to answer your question would be starting with some one-way function / pseudo-random function that is partially homomorphic. A recent result showed that taking various minicrypt primitives and adding an additional partial homomorphic property is sufficient for many Cryptomania primitives (and therefore already takes you out of Minicrypt). This of course doesn't answer your question in the negative, but it does rule out a natural class of approaches to designing such a scheme while staying within Minicrypt.
