4
$\begingroup$

I am looking for a way to allow parties to publicize encrypted values that can only be decrypted by one or a select few other parties, but that allow everyone to check how close they are to the mean of all such publicized values.

This of course would mean that there is some entropy that is lost; the encryption would not be perfect because certain information can be gleaned from the given values.

However, are there schemes in which this is possible? At first I thought it might be possible using Homomorphic Encryption, but as far as I now know, these seems to allow to calculate the mean as encrypted value, but not the process of comparing the other values against it.

Is there a way to do this?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Can we assume the mean is public already? That is, computing mean is not a question. Is it ok to treat approximate-mean and acceptable difference as integers, not real numbers? What action is expected from/after decryption? $\endgroup$
    – Vadym Fedyukovych
    Commented Jan 20, 2018 at 11:46
  • 1
    $\begingroup$ I am confused, it looks like all answers read that anybody could get the distance between any encrypted value and the mean. Didn't you mean that you wanted each person to learn only 1 distance from the mean? that is, their distance from the mean $\endgroup$
    – Florian Bourse
    Commented Jan 22, 2018 at 9:18

3 Answers 3

Reset to default
4
$\begingroup$

If I understand what you're looking for correctly, that would completely destroy the security.

First off, if an attacker can compute the difference between her value and the mean, it is trivial to find the actual mean. Simply encrypt the number $0$ and then compare it to the mean.

If she can compute the mean of any subset, it's pretty trivial to recover plaintexts: just compute the "mean" of a single ciphertext. Even if you somehow make it work only for subsets of a particular size or something, she can still decrypt an arbitrary ciphertext $c$ like so:

$$ d(c) = (N+1)(\mu(S\cup m)-\mu(S\cup e(0)))$$

Where $e(0)$ is the encrypted $0$, $S$ is some arbitrary subset of the ciphertexts, $N$ is the size of $S$, and $\mu$ is the mean of a subset.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ But I think the idea is that the set of values from which we calculate the mean is the set of publicized values, therefore, it is fixed and not controlled by the attacker. The attacker would not be able to calculate new means. $\endgroup$
    – Hilder Vitor Lima Pereira
    Commented Jan 21, 2018 at 10:04
  • 1
    $\begingroup$ @HilderVitorLimaPereira Even if you could devise a mathematical method that allows you to calculate the mean of only published values (which seems unlikely), you would have to update it when new values are published. And just viewing how the mean changes as each new value was published would let you figure out the plaintext. $\endgroup$
    – Chris
    Commented Jan 21, 2018 at 10:08
  • 1
    $\begingroup$ @HilderVitorLimaPereira And if nothing else, such a method would clearly require the intervention of the person holding the private key, and allow an attacker to discover the true mean of whatever subset is used. Why, then, would the holder of the private key not just publish the mean periodically? $\endgroup$
    – Chris
    Commented Jan 21, 2018 at 10:10
3
+50
$\begingroup$

I believe what you are looking for is Functional encryption This will allow you to create a key which will allow limited operation on the ciphertext, in this case the differences to the mean.

Obviously from your definition the information leakage is very large if we are looking at scalar values, knowing the set of differences of a set of numbers from their mean is almost as much information as is in the full set. If you are not using a scalar but using a vector and L2 distance for instance this becomes more meaningful.

In the Scalar case if I have $n$ numbers each with $k$ bits. Their total information is obviously $n * k$ bits. Yet revealing their differences from the mean, the remaining entropy is no more than the mean ($k$ bits as well) and the sign relative to the mean $n$ bits so we get $n+k$ instead of the $n*k$ as before, nearly everything is revealed by design. Still this should be doable with functional encryption

Improve this answer
$\endgroup$
2
$\begingroup$

There has been research into Fully Homomorphic Encryption, which can be implemented using lattice-based cryptography. Theoretically, FHE lets you run arbitrary computer programs on encrypted data, including the one you want.

It's slow, though. It would take millions of years just to evaluate relatively simple gates using this method.

https://dl.acm.org/citation.cfm?id=1834954 https://www22.in.tum.de/fileadmin/papers/essos15a.pdf

EDIT: If you want the "true" or "false" result of the computation to be visible to anyone who computes it, you can also do the following: Publish the ciphertext of "true" and "false" and create a noninteractive zero-knowledge proof that they were encrypted with the same key as all the published values. (NIZKs can be generated to prove the result of any NEXP computation, as demonstrated by the PCP Theorem and more recently by the Pinocchio compiler, which can take C programs and compile it into a binary that not only executes a program, but also prove that it was executed correctly).

Actually, you could just run the original computation yourself and generate one of these proofs. This will convince people that certain values are "close" to the mean, but it won't allow them to run the computation directly themselves.

EDIT2: You could extend that last solution a little further, and publish a commitment to the list of values of interest, a list of distances from the mean, and an NIZK that verifies that the list of distances is correct. Anyone will be able to see the list of distances and use the NIZK to verify that it is correct. This solution is actually efficient enough, using Pinocchio or IOPs, to be usable in practice.

Improve this answer
$\endgroup$
6
  • $\begingroup$ homomorphic encryption doesn't seem to solve the problem as the result of the operation is still encrypted $\endgroup$
    – Meir Maor
    Commented Jan 21, 2018 at 15:57
  • $\begingroup$ Edited it to reveal the result to everyone. $\endgroup$
    – Ian MathWiz
    Commented Jan 21, 2018 at 16:17
  • 1
    $\begingroup$ Interesting approach, but usually homomorphic encryption does not produce deterministic results exactly to avoide this type of comparisons. Should you use a deterministic homomorphic encryption you would be revealing equality relationship between encrypted values. which is leaking extra info. $\endgroup$
    – Meir Maor
    Commented Jan 21, 2018 at 16:41
  • 1
    $\begingroup$ The other approach is to forgo the homomorphic encryption and just run the computation and publish the NIZK, but as I mentioned this only allows them to verify the computation, not to directly run it themselves. $\endgroup$
    – Ian MathWiz
    Commented Jan 21, 2018 at 17:32
  • 1
    $\begingroup$ This last option seems like a reasonable solution IMHO $\endgroup$
    – Meir Maor
    Commented Jan 21, 2018 at 18:08

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.