Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm looking for the cryptographic equivalent of a Drivers license where the issuer can be verified, the issuer doesn't need to know who you showed the drivers license to, but also allows per-transaction privacy.

I would use the standard PKI system, but there is a hard coded certificate serial number in each cert, removing privacy. Issuing multiple certs per user adds management complexity I'm trying to avoid. I'd like to leverage mathematical properties of ECC (and related) to solve this problem. This question is inspired by the ability to add/multiply keys and makes me wonder what can be done if each key is used to independently sign a value.

Mentally assume that the private keys for this trust are securely stored on hardware (SIM, SmartCard etc) and the possession of the private key is sufficient validation.

For example, suppose Alice has a store that sells unicorn sweaters. Bob wants to purchase this sweater, but wants to do so anonymously. Alice demands that Bob be 18 years or older and have a verified address.

Bob doesn't want anyone to know he likes unicorn sweaters unless under the most dire situations (or where Charlie demands information from Alice that the transaction occurred)

Bob has a pre-existing identity verification setup established with Charlie. Alice trusts Charlie and will accept Charlie's voucher of Bobs age and residence.

Bob has the following goals:

  • He doesn't want Charlie to know he is shopping at Alice's shop
  • He doesn't want Alice to know more than she needs to, or be able to derive his shopping habits through a common identifier

If Bob were to give Alice his digital driver's license equivalent, she would have more information than she needs (Driver ID, full birthday, address, etc). All Alice needs is the boolean isOlder than 18, his address and have that assertion verified by Charlie.

Layman implementation approaches

One idea I thought of is for Charlie to issue many signed tokens, each certifying a different set of information about Bob, and place them on a smart card. Each token has an ID that means something to Charlie but is random to Alice. Assuming that the pieces could be recomposed and validated, Bob could cherry-pick what he wants to tell Alice, recombine it and send it to her.

This approach seems cumbersome and may grow exponentially large based on the number of permutations based on how it's implemented. There are also privacy issues since if the token (with a tokenID) is reused with another vendor, Bob's shopping habits could be derived. Finally it may allow for MITM attacks for anyone who wishes to re-use or forward Charlie's signed assertions to bad actors.

The next approach would be to have Charlie issue N copies of the previous set of tokens. Each copy would contain an anonymous identifier per N copy. If Bob wishes to do N+1 transactions, one of the tokens would have to be reused, lowering his anonymity. The complexity and size requirements also increase exponentially.

I started exploring possibilities using derive from adding or multiplying ECC keys together, and if those set of private keys used independently or in combination could be used to sign a claim, verify a claim, or to verify a different keypair signed the claim.

I then started thinking about homomorphic encryption and my head exploded.

Question

Once Bob & Charlie have an established trust, is there any way Bob can safely perform the ALL of the following actions offline, (in combination with SmartCard hardware)

  • Charlie makes an assertion (or claim) about Bob, and Charlie's claim can be verified that it was indeed signed by Charlie

  • Bob to conditionally forward an assertion Charlie made about Bob (Age > 21 | Address | Name | etc.) to Alice

  • Bob to alter the assertion so that the contents of the assertion is still readable by Alice

  • Alice can read the altered assertion, verify that it was certified by Charlie, but can't deduce any information about Bob, even with the cooperation of Eve (a random 3rd party)

  • If Charlie needs to, Charlie can extrapolate the identity of Bob, by simply viewing the assertion made to Alice, and the knowledge Charlie has about Bob

So in a sense I'm looking for an offline SAML/Claims based transaction, where Authentication of Bob's identity occurs with the cryptographic material in the Smartcard. (It's a bearer object, that isn't easily copied)

Are there any cryptographic solutions that would help solve this problem?

share|improve this question
    
I've deleted my own answer while I try to figure out what security properties a non-interactive zero-knowledge system would need here, and I'm not sure how much detail I should go into once I've figured that out. $\:$ (For example, do you know what simulation-soundness and extraction-zero-knowledge are for NIZK?) $\:$ Is Bob allowed to publish a public key before Charlie makes the assertion about Bob? $\:$ If no, then you won't be able to distinguish between Bob actually having made an assertion to Alice and Charlie having done so while pretending to be Bob. $\;\;$ –  Ricky Demer Mar 12 '13 at 23:19
    
@RickyDemer If Bob did publish something, Alice shouldn't know it, or shouldn't be able to use it for anything useful, lest Bob's purchases get correlated (Sweaters, and amazon purchases). There should be something that prevents forwarding Bob's credentials. One idea is Alice should send a challenge to Bob, (so the exchange is bound to the current session) and Bob sends Charlie's verification (of Bob's relative age and address) to Alice. –  makerofthings7 Mar 12 '13 at 23:35
    
How much depth should you go into? I admit I'm not that well versed in all the mathematics (and symbols) of cryptography but I will study whatever you share until I understand it completely/100%. I'll study the 101 terminology wherever it's offered. –  makerofthings7 Mar 12 '13 at 23:39
    
I think much of this is addressed by MSFT's UProve technology, but I haven't heard anything new about it in 2 years –  makerofthings7 Mar 13 '13 at 1:37

3 Answers 3

What you are describing is an anonymous credential system. There are two different ways to go about making these and two actual systems that use those techniques: Microsoft's U-prove and IBM's Idemix.

If you're interested in smart card usage, you'd probably prefer U-prove as it tends to work better with smart cards. It's described by its original developer, Stefan Brands, in this book.

The other system, which I am more familiar with, is a system by Jan Camenisch and Anna Lysyanskaya first described here, though there have been serious improvements since then. Effectively the way it works is Bob gets Charlie to sign something like "Bob (Age > 21 | Address | Name | etc.)." Bob can then prove to Alice that Charlie signed a message saying his Age >21 without revealing the actual signature or the rest of the message. Bob does this with a zero knowledge proof that proves he has a singature by Bob on a message without revealing anything other than that the message says he's over 21.

Various extensions of this basic idea allow for both global revocation ( which is what you describe where Charlie can extract an identity from the transaction) or local where Alice can merely blacklist whoever it was who presented an id.

Very recent work even allows Charlie to issue credentials to Bob that Bob can then make limited (or unlimited) delegates to others.

share|improve this answer
    
Does either system allow for Bob to anonymously assert Age > 21 so that each assertion can't be correlated among different relying parties? –  makerofthings7 Mar 14 '13 at 4:32
1  
Both do if Charlie is willing to sign "age >21" for bob. If Charlie just signs Bob's actual age, then I know Idemix can handle proofs that age > 21. I do not know if U-prove can do so efficiently, but I suspect it can. –  imichaelmiers Mar 14 '13 at 4:34
    
I'm fascinated by this subject matter.. if you have links to delegation or revocation that would be tremendously helpful. –  makerofthings7 Mar 14 '13 at 4:40
    
@imichaelmiers: $\;\;$ What he's describing is a (mostly) non-interactive, mostly-anonymous $\hspace{1 in}$ (explicitly not to Charlie) credential system. $\:$ I'm pretty sure a zero knowledge argument would $\hspace{0.7 in}$ be enough, since an unbounded Bob could just forge Charlie's signature. $\:$ (Is your idea $\hspace{1 in}$ that Charlie's signature key pair could also be Fail-Stop?) $\;\;\;\;$ –  Ricky Demer Mar 14 '13 at 5:45
1  
@makerofthings7 Try the first couple of papers from the link below. I've read the first three and they are somewhat useful. scholar.google.com/… –  imichaelmiers Mar 14 '13 at 19:17

This sounds like OAuth or SAML. Consider the login process for this site. Stackexchange wants to verify your identity, but you don't want to give them your password. So Stackexchange relies on Google or Yahoo or OpenID to verify identity.

You can also use SAML. Basically, the identity provider verifies all information, signs the assertion (> 18, address) and you provide that assertion to the service provider (Alice/Unicorn Shop). Alice verifies the assertion and accepts it.

share|improve this answer
    
And in the case of this site, Google or Yahoo or the OpenID provider know that I just requested access to this site. But what if I don't want them to know which sites I sign into? That is the scenario presented here. –  mlibby Jan 2 at 19:09
    
You can use a custom or modified SAML, or SAML 1.0. The identity provider authenticates you and signs an assertion with its private key. You may then present that assertion to any service that trusts the identity provider. If the service trusts the identity provider (Google/Yahoo), then it can verify the assertion with the identity provider's public key to know you were correct authenticated. The identity provider needn't know to whom you present its assertion, but normally it is auto-submitted to the service for ease. –  Chloe Jan 3 at 0:38

If Bob and Charlie will share a secret, then it information-theoretic privacy might
be possible, otherwise the best that can be hoped for is computational anonymity.
I haven't come up up with any way to achieve information-theoretic privacy when
Bob and Charlie share a secret, so I will only be addressing computational privacy.
I assume that Bob can generate a key pair and publish the public key before Charlie makes the assertion.
(It does not matter whether or not Alice knows Bob's public key.)



Use:

${}$1. $\:$ a computational NIZK argument system in the Common Reference String model
${}$2. $\:$ a tag-based CCA2 Public Key Encryption scheme with perfect completeness
${}$3. $\:$ a standard signature scheme and a one-time signature scheme


Charlie's public key is $\:$ honestly_generated_CRS || public_encryption_key || signature_verification_key
Charlie's private key is $\:$ decryption_key || signing_key
Bob's key pair is for signatures.

To make an assertion about Bob, Charlie sends
[assertion,sign(["Bob",Bob's_public_key,assertion])]$\:$ to Bob.
I don't get what you mean by "conditionally forward"ing the assetion.

To alter the assertion, Bob:
generates a one-time signature key pair $\:\langle vk\hspace{.01 in},\hspace{-0.01 in}sk\rangle$
signs session_info with his private key
encrypts $\:$[assertion,sign(["Bob",Bob's_public_key,assertion]),the_signature_just_generated]
with Charlie's public encryption key using $\:$vk$\:$ as the tag
argues that the ciphertext follows the above description and $\:$assertion$\:$ mathces the altered assertion
signs session_info with $\:$sk$\:$
and sends $\:$[session_info,one_time_signature,ciphertext,argument]$\:$ to Alice.

Alice can verify that that was certified by Charlie by verifying the argument. $\:$ Alice can verify
that Charlie would be willing to extrapolate Bob's identity by verifying the one-time signature.
Since the PKE scheme is tag-based CCA2 secure and the argument system is computationally
zero knowledge, the only information Alice can deduce about Bob is the length of
[assertion,sign(["Bob",Bob's_public_key,assertion]),the_signature_just_generated])$\:$.
Charlie can extrapolate the identity of Bob by decrypting the ciphertext that was sent to Alice,
although he is supposed to not do so if he doesn't get a valid corresponding one-time signature.


If the relation between $\:$assertion$\:$ and altered_assertion is of the form "there exists $w$ such that ...",
such a $w$ could not necessarily be easily found even if one existed, and Alice
wants to be sure that Bob knows such a $w$ (as opposed to merely knowing
that there is one), then the NIZK system need to be simulation-sound.
(Namely, it would need to be such that, given a simulation-CRS and access to simulated proofs
of arbitrary statements, it's still infeasible to come up with a proof of a different false statement.)

www.cs.ucl.ac.uk/staff/J.Groth/NIZKJournal.pdf constructs CRS-model NIZK proofs under (the Subgroup Decision Assumption or) the Decisional Linear Assumption, (the latter of) which hopefully holds for suitably chosen Elliptic Curves. $\:$ http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.7990
gives a general method to make any NIZK system simulation-sound,
which could be instantiated with $\:$ eprint.iacr.org/2009/486.pdf .

If Bob can generate his key pair after seeing Charlie's public key, then you might want to have Bob's
key pair be for a standard signature scheme and a Fail-Stop Signature scheme, with the prekey as an additional part of Charlie's public key. $\:$ I'm fairly confident that, under ECDL, one could find a family
of bundling homomorphisms such that the prekey test does not need any interaction. $\:$ (The reason for
using a standard signature scheme anyway would be in case Charlie learns that Bob lost his signing key.)

share|improve this answer
    
This is very helpful and is a great starting point for my independent studies (even the terms are helpful). Since the Key based approach is based on RSA primes, and I'm trying to integrate with UProve (based on the intractable discrete logarithm problem) is it possible to adapt your line of thinking into this type of mathematical foundation? I'm doing thought experiments on using UProve to display a constant to Alice1 and a different constant when speaking to Alice2... AliceN. Charlie could deduce Bobs ID across every Alice, but the consortium of Alice's couldn't do the same without Bob. –  makerofthings7 Mar 20 '13 at 3:20
    
I don't know of any way to do this from just the RSA assumption and the discrete log assumption. $\hspace{.5 in}$ You can get the second thing by having Bob use a pseudo-random function of the n in Alice_n to $\hspace{.5 in}$ generate $\:\langle vk\hspace{.01 in},\hspace{-0.01 in}sk\rangle\:$ from a standard signature scheme (instead of just a one-time signature scheme), $\hspace{.25 in}$ and use it to sign [session_info,ciphertext] (instead of just session_info). $\:$ –  Ricky Demer Mar 20 '13 at 21:46
    
When I responded to your comment, I hadn't registered "this type of mathematical foundation". $\:$ The Subgroup Decision Assumption is somewhat similar to the RSA assumption (it's far more similar to the factoring problem), and the Decisional Linear Problem is somewhat similar to the discrete logarithm problem (it's far more similar to Decisional Diffie-Hellman). $\:$ –  Ricky Demer Mar 21 '13 at 5:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.