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."

Millionaire's Problem

[Vectronic]

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"...

Re:Identity theft is still aided by it's own victi

[davester666]

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 :-)

MPC and it's uses

[0ptix]

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 [purdue.edu] 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 [cryptomathic.com] 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.

Gas stations already do this....

[foniksonik]

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.