Protecting Online Identity Through Cryptography 87
A new startup, Credentica, hopes to offer the ability for you to perform secure transactions using the smallest amount of personal information possible. Their goal is to both protect privacy and enhance security, which they hope will be a mutually inclusive process. "The technique employs secure multi-party computation, a branch of cryptography that can calculate meaningful answers about secret information by knowing only some non-revealing clues about that secret. The underlying theory was demonstrated in 1982 by Andrew Yao in the so-called Millionaire's Problem [...] U-Prove employs an ID token, a special kind of digital certificate that allows for minimal selective disclosure. The tokens can store all kinds of information, but users can disclose only the minimum amount of data required in any given transaction. They leave no unwanted data trails and permit both anonymity and pseudonymity."
Re:Millionaire's Problem (Score:3, Informative)
another counterexample [wikipedia.org]
Book pointer (Score:5, Informative)
Re:Why do we need spy tools? (Score:3, Informative)
We also have electronic cash [wikipedia.org] which uses zero-knowledge [wikipedia.org] systems to protect privacy. Note real implementations are far more sophisticated than the simple example at Wikipedia. The only information you can get from the cash is the information necessary to prove it has been paid to you.
Re:Please explain (Score:3, Informative)
A practical application of this is at http://www.cypherpunks.ca/otr/ [cypherpunks.ca] (with a plugin for a few common AIM application, most usefully for pidgin née gaim).
This one has an implementation called the "Socialist Millionaires Problem", which sounds the same, although I recall it being used only to tell if two secret values are the same on both side, thus augmenting the key exchange protocol with man-in-the-middle detection capabilities, provided the parties has shared knowledge about something (and something reasonably private).
Re:Book pointer (Score:3, Informative)
Re:Book pointer (Score:1, Informative)
Re:Please explain (Score:2, Informative)
Imagine three millionaires in a room who wants to compute the sum of their incomes. Let us say that the millionaires can agree in advance that the sum can be represented by an integer in the range 0..100. They just need some upper limit, so the number could denote billions, trillions or whatever. Each millionaire then chooses three numbers a random from the interval 0..100 with the only condition that they sum up to the millionaires own income. The sum must be calculated modulo 100, which simply means that the numbers wrap around when they reach 100. So 75 + 50 = 25 and so on.
If the three millionaires are worth M1, M2, and M3, respectively, then the first millionaire chooses numbers r11 + r12 + r13 = M1, the second chooses r21 + r22 + r23 = M2, and so on. This is a simple secret sharing which hides M1, M2, M3 perfectly. Seeing any two shares (the random numbers) reveal nothing about the target value because depending on the third share, the target could be anything.
They send their first number to the first millionaire, the second number to the second millionaire and so on. These numbers are send securely. Each millionaire now has three shares: the first millionaire has r11, r21, and r31, and likewise for the other two millionaires.
If each millionaire adds their shares, they end up with shares of the correct sum! So the first millionaire computes s1 = r11 + r21 + r31, the second computes s2 = r12 + r22 + r32, and so on. They then publish these shares and now they can all compute the correct sum S:
S = s1 + s2 + s3
= (r11 + r21 + r31) + (r12 + r22 + r32) + (r13 + r23 + r33)
= (r11 + r12 + r13) + (r21 + r22 + r23) + (r31 + r32 + r33)
= M1 + M2 + M3
Voila!
The secret sharing scheme used here is a simple one that requires the cooperation of all involved partie There also exists threshold schemes in which only a subset of the parties is needed to open a shared secret. Shamir's scheme is most famous and relies on the simple fact that you need two points on a straight line to determine it. So encode your secret s as the point (0, s) and pick a random straight line that goes through (0, s). Then hand out other points on the line to the other players. As long as each player only knows his own point, he cannot determine the y-axis intersection (the secret), but when any two players get together, then they can easily determine the secret. This scheme generalizes naturally to polynomials of higher degrees, which require more players to get together to reconstruct the secret.
If you can read Python, then you might be interested in my Python code here: http://viff.dk/api/viff.shamir-pysrc.html [viff.dk]. This code is part of a larger project for MPC called VIFF, see http://viff.dk/ [viff.dk]