Slashdot Mirror
Protecting Online Identity Through Cryptography
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."
Unfortunately it is all too easy to accomplish identify theft via some very uncomplicated and low-tech methods. People still click on links in emails and type their financial information into fake websites or answer questions over the phone to the nice IRS man who wants to send me a tax rebate. However, I do applaud any effort to protect folks identities.
http://www.busyweather.com/
Millionaire's Problem: Alice and Bob want to find out who has more money without disclosing the amount of their fortunes to each other, or even to a mutually trusted third party. By applying special functions to their information that disguised it, Yao proved that each could know who was richer without either revealing their true holdings.
No wonder Millionaires are so stupid... if this is what they consider a "Problem"...
i certainly hope that was an attempt at humor
If you mod me down, I will become more powerful than you can imagine....
Forget about security on any large (sort of large) anything. Look at this site...you are immediately penalized for being anonymous.
What a load of shit.
We live in an age where anonymity is almost totally gone. We can hope, now, only for privacy. And the best way to do that is by vigorous demand for encryption methods and other tools that prevent a company or entity from asking a thousand and one personal questions just to pad their database.
Comment removed based on user account deletion
Tools like these COULD do more do help consumers. [fixed it for you]
:-)
Really, do you think Amazon or Google or somesmallretailer.com will settle for asking the minimum amount of information necessary to complete a transaction?
They already ask for more info than they need, presumably for 'security' purposes [ie, so someone isn't using your credit card to buy a bunch of Dells for orphans in Russia], but they just happen to keep using that data for marketing purposes. And now that they are already collecting all this information, they have a vested interest to keep getting this information, because they know it's valuable, both within their own company and to sell to other companies.
Today, businesses, together with Visa/Amex/Mastercard could set up a system so you, Joe Consumer, would just need to authenticate yourself to V/A/M, and the V/A/M web site would generate a one-time code that can be used for a purchase up to X dollars, and you just paste it into, say MacMall's web site, say with your email address, MacMall validates the number with V/A/M for the purchase amount, and then sends you an email with the download link/registration code for some software you just purchased. Do you realistically think MacMall would go for a system like this?
It would take one of two things to get a system like this going:
1) Consumers, en mass, would need to demand the online shops they shop at use systems like this instead of the ones they already have. And stop shopping online until the online stores actually implement these new systems. Likelyhood of this happening: 0.00001% There just isn't enough people that are passionate enough about their privacy, relative to the people who shop online just to avoid the lineups at the big box store.
2) Some hacker steals the identity of every member of congress and senator in the US, from some online store they all use, screws their credit and blatantly taunts all of them about doing it. Then then does it again to another online store they all use after they fix their identities and get the first store to fix it's security, and taunts them again. And then taunts all of them again. They then legislate the Online Privacy Act of 2050. Likely of this happening: 1%. Basically, someone who wants improved privacy online would need to do this to get them to do it. Of course, this is a high-risk proposition for that person
Sleep your way to a whiter smile...date a dentist!
For people who want background or just enjoy math, Brands's book is Rethinking Public Key Infrastructure.
We also have electronic cash which uses zero-knowledge 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.
Why would any business want to use it? The bar that scans your drivers license gets some valuable information in the process. The porn site that asks for your credit card information to verify your age gets a credit card that they can use or sell. The bank that you ask for a loan gets all sorts of information, all of which it can sell or use to market itself. The current situation is bad for the customer, but the customer isn't the one who decides what verification system is used. None of this will change until large numbers of people refuse to do business with companies that demand more information than they need. And that's never going to happen.
This is not the first use of multi-party computation. MPC is probably the most advanced cryptographic tool theoretical crypto has produced in the last 35 years. (The strongest flavour being Universally Composable MPC). Also, though the intuitive concept of secure MPC was introduced by Yao the later results of Goldreich, Micali and Wigderson in their 1986 paper How to Play Any Mental Game is the one upon which modern MPC is based and the result which is usually cited in cryptographic literature. (My guess is the wired article author got the bit about Yao from wikipedia.) It is in this paper that the security requirements of such a protocol are first formally described using what is now called the ideal/real paradigm. Essentially a secure protocol computing some joint functionality of all players inputs should be as secure as if there where a totally honest trusted third party who would gather their input, compute the function and privately hand the outputs back to all players. (This paradigm is probably at least as important a contribution to modern crypto as the actual MPC protocol they presented in the paper.)
The problem with MPC protocols is that since they are so very general and powerful they tend to also be horribly inefficient (though polynomially bounded (i.e. in P). Never the less the constant are often horrible and could require on the order of n^2 rounds of communication. Another hurdle in their wider adoption in the field of security is that they represent a significantly more complicated concept then say encryption or a hash function and so tend to be a difficult sell to non-cryptographers.
However at least one company, Cryptomathics of Aarhus, Denmark are working on an implementation of MPC. The main client being the danish government which wants to use the product to setup an online market through which local farmers can to sell there goods. The idea being that by using an MPC protocol to do this rather then some central (government run) server no body needs to trust anyone else, not even the government; just their own implementation of the software on their computers. As long as that is correct and uncorrputed they are guarenteed all the security they could hope for.
Of course there is always the argument that you might well be better off trusting the government to host the entire show then your own computer, but on the other hand even IF the government runs some online auction server, you still need to connect to that remote system from your own computer. So a secure server is still not going to help you protect yourself from local corruptions. At least now that is the ONLY thing left to worry about.
A practical application of this is at http://www.cypherpunks.ca/otr/ (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).
"Ten years from now, they could do it in a few seconds." -- The Racketeer of the Hellfire Club, 1993, Phrack 42
To the asshole who tagged the article `terroristsdream': terrorism is not an excuse to erode our right to privacy. Fuck off.
Simply put, this will not take off until businesses and corporations that warehouse our personal data are held financially liable for any losses that occur related to that data. Right now there is way too much positive financial incentive to hold onto as much consumer data as a company can, and almost no incentive not to. This situation will have to be reversed before companies will invest in a technology such as this.
'The tyrant will always find pretext for his tyranny.' - Aesop's Fables
When you pay with a credit card outside they make you verify the billing zip code. That's it. It's enough information to verify that you are either the primary card holder or know the person well enough to know their zip code. It's not cryptography in any sense but it does implement the concept of least necessary information rather well. They could ask for a lot more... your SSN or DOB for instance... but for the purposes of buying gas a zip code is just the right amount of info.
A fool throws a stone into a well and a thousand sages can not remove it.
- Real name: first and last
- Credit card numbers
- Bank account numbers
- Social Security Number
- And for good measure, your mother's maiden name
Please, show us how you don't want privacy or anonymity. Or did you mean you want it only for yourself?You seem very confused. If you don't trust people, you should love this technology. It will allow you to deal with those untrustworthy people without you having to give them your private information.
I can not explain to you how a comparison is done without leaking information (that is pretty involved), but I can understand the much simpler operation of addition.
:-) In this computation no information was leaked at any point, and yet the three parties were able to correctly calculate the sum.
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. This code is part of a larger project for MPC called VIFF, see http://viff.dk/