0
$\begingroup$

I'm not even sure of the appropriate terminology to use to describe my problem so bear with me if the explanation is not exactly formal.

Imagine I have a simple digital calculator, with a screen and some buttons. I bring this calculator into a room full of people. I ask them each one by one to take the calculator and accumulate their age on the calculator, such that after everyone is done the calculator screen reads the combined age of everyone in the room.

The trick is that there is a lot of people in the room, and some of them are liars. I need to solve two problems relating to this:

  1. I need to know if some user(s) has lied about their age
  2. I need to know if some user(s) double counts their age

It's enough for me to recognise and throw away a bad result, not necessarily know who messed with the result.

We can assume that the calculator is rather large (ex. has a 256-digit display), but not arbitrarily large. This means that I can punch in a number that contains some identity information as well as my age, but I don't have enough digits to just have everyone's signature side by side.

Assume I've been given a value to verify.

$\endgroup$
2
  • $\begingroup$ I've added one obvious requirement. But I'm also missing how you would identify the persons. If you have just a room full of people without further identification then they may switch around ages together. You could possibly sort them using their length, then you could create a signature consisting of two numbers of their age in order. This should work up to 128 persons and for ages 0..99 - no calculation necessary. Hopefully none of them will be in wheel chairs :) $\endgroup$
    – Maarten Bodewes
    Commented Mar 24, 2016 at 11:03
  • $\begingroup$ Oh, and obviously this will only work at about the same time that you measure people. People grow, shrink, lose body parts etc. $\endgroup$
    – Maarten Bodewes
    Commented Mar 24, 2016 at 11:10

1 Answer 1

2
$\begingroup$

There is a lot to this question, and I believe some concepts of multiparty computation can be useful in relation with this problem. There's one catch: lying is a very abstract concept, even with a simple and well defined concept as age.

So, for the sake of the argument, let's define some conditions:

  • Each participant introduces a valid age value (i.e. within a given range -maybe 0-99, as Maarten proposed).
  • Each participant provides only one input to the protocol.
  • The counting entity is reliable.

For certain encryption algorithms (e.g. Lifted ElGamal) it is possible to prove that an encrypted value falls within a range without disclosing the value. Then, each participant $p$ has to generate a set $(p, E(a_p), proof_{a_p})$. When the counting entity has all the sets, it can verify each value of $p$ is unique. Since Lifted ElGamal is also additively homomorphic, the sum of all the ages can be computed without decrypting the values.

DISCLAIMER 1: if the counting entity cannot be trusted, the scheme gets harder, but the general spirit of the communication is similar.

DISCLAIMER 2: this is strongly based on protocols for voting. The verification of identity, adding and the decryption processes can be performed by different entities within the counting authority to keep a higher level of privacy around the encrypted values.


As Maarten suggested, here are some links to the relevant content:

  • Homomorphic encryption : a property of cryptosystems that enable some operations on the ciphertexts without decrypting the values.
  • Sigma protocols : a generic approach to Zero Knowledge Honest Verifier Proofs (ZKHVP).
  • Zero Knowledge : a long lecture on zero knowledge techniques. Set Membership is covered around the slide 144.
  • Estonian voting process : an example of a critical application based on the principle of division of responsibility within the counting (voting) authority).
$\endgroup$
4
  • 1
    $\begingroup$ I presume that this is what the asker is after, but I can think of different schemes that fit into the broadly asked question. Some links would be useful. $\endgroup$
    – Maarten Bodewes
    Commented Mar 24, 2016 at 12:39
  • $\begingroup$ I updated the answer with some links. Hopefully the most relevant topics were covered. $\endgroup$ Commented Mar 24, 2016 at 13:10
  • $\begingroup$ Lovely. Cannot vote up twice though. $\endgroup$
    – Maarten Bodewes
    Commented Mar 24, 2016 at 13:11
  • $\begingroup$ Thanks for the answer, suggesting homomorphic crpyto was good, in fact I am trying to solve this problem in the context of homomorphic crypto (EC-ElGamal to be exact). Furthermore I have an additional question, what if the sets cannot be separated? Meaning I am only presented with the final state of the calculator display, and I don't see any intermediate ones. I would no longer be able to validate any one age or verify the identity of a specific user. $\endgroup$
    – tolstikh
    Commented Mar 24, 2016 at 14:46

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.