On Mon, May 10, 2004 at 02:42:04AM +0000, Jason Holt wrote:

...

However can't one achieve the same thing with encryption: eg an SSL connection and conventional authentication?

How would you use SSL to prove fulfillment without revealing how? You could get the CA to issue you a "patient or doctor" SSL cert,

Well SSL was just to convince you that you were talking to the right server ("you have reached the AIDs db server"). After that I was presuming you use a signature to convince the server that you are authorised. Your comment however was that this would necessarily leak to the server whether you were a doctor or an AIDs patient. However from what I understood from your paper so does your scheme, from section 5.1: P = (P1 or P2) is encoded HC_E(R,p) = {HC_E(R,P1),HC_E(R,P2)} With Hidden Credentials, the messages are in the other direction: the server would send something encrypted for your pseudonym with P1 = AIDs patient, and P2 = Doctor attributes. However the server could mark the encrypted values by encoding different challenge response values in each of them, right? (Think you would need something like Bert Jaap-Koops Binding cryptography where you can verify externally to encryption that the contained encrypted value is the same to prevent that; or some other proof that they are the same.) Another approach to hiding membership is one of the techniques proposed for non-transferable signatures, where you use construct: RSA-sig_A(x),RSA-sig_B(y) and verification is x xor y = hash(message). Where the sender is proving he is one of A and B without revealing which one. (One of the values is an existential forgery, where you choose a z value first, raise it to the power e, and claim z is a signature on x= z^e mod n; then you use private key for B (or A) to compute the real signature on the xor of that and the hash of the message). You can extend it to moer than two potential signers if desired.

...

Outside of this, the usual approach to this is to authenticate the server first, then authenticate the client so the client's privacy is preserved.

If you can trust the server to do so. Firstly, hidden credentials limit what the server learns, so you don't *have* to trust the server as much. But secondly, they also solve the problem which shifts to the server when it goes first:

OK so the fact that the server is the AIDs db server is itself secret. Probably better example is dissident's server or something where there is some incentive to keep the identity of the server secret. So you want bi-directional anonymity. It's true that the usual protocols can not provide both at once; SSL provides neither, the anonymous IP v2 protocol I designed at ZKS had client anonymity (don't reveal pseudonym until authenticate server, and yet want to authenticate channel with pseudonym). This type of bi-directional anonymity pretty much is going to need something like the attribute based encryption model you're using. However it would be nice/interesting if one could do that end-2-end secure without needing to trust a CA server.

My system lets folks:

* access resources without the server even knowing whether they fulfill the policy

this one is a feature auth based systems aren't likely to be able to fullfil, you can say this because the server doesn't know if you're able to decrypt or not

So it's definitely in the realm of other privacy systems. We could define a new term just to exclude my system from the others, but at this point I don't think naming confusion is any worse for my system; they all have lots of different nonorthogonal features.

I think it would be fair to call it anonymity system, just that the trust model includes a trusted server. There are lots of things possible with a trusted server, even with symmetric crypto (KDCs). Adam

On Mon, May 10, 2004 at 08:02:12PM +0000, Jason Holt wrote:

Adam Back wrote:

...

[...] However the server could mark the encrypted values by encoding different challenge response values in each of them, right?

Yep, that'd be a problem in that case. In the most recent (unpublished) paper, I addressed that by using R as the key for a ciphertext+MAC on the actual message.

OK that sounds like it should work. Another approach that occurs is you could just take the plaintext, and encrypt it for the other attributes (which you don't have)? It's usually not too challenging to make stuff deterministic and retain security. Eg. any nonces, randomizing values can be taken from PRMG seeded with seed also sent in the msg. Particularly that is much less constraining on the crypto system than what Bert-Jaap Koops had to do to get binding crypto to work with elgamal variant.

In either case, though, you can't just trust that the server encrypted against "patient OR doctor" unless you have both creds and can verify that they each recover the secret.

The above approach should fix that also right?

(And you're right, the AIDS example is not very compelling. The slides give a better one about FBI agents, but I'm still looking for other examples of super-sensitive transactions where HCs would fit)

dissident computing I think Ross Anderson calls it. People trying to operate pseudonymously and perhaps hiding the function of their servers in a cover service.

Hugo Krawczyk gave a great talk at Crypto about the going-first problem in IPSec, which is where I got the phrase. He has a nice compromise in letting the user pick who goes first, but for some situations I think hidden credentials really would hit the spot.

Unless it's signifcantly less efficient, I'd say use it all the time.

...

I think it would be fair to call it anonymity system, just that the trust model includes a trusted server. There are lots of things possible with a trusted server, even with symmetric crypto (KDCs).

Yeah, although I think most of them would require an on-line trusted server. But that just makes all sorts of things way too easy to be interesting. :)

Yes. But you could explore public key based without IBE. You may have to use IBE as a sub-protocol, but I think ideally want to avoid the IBE server being able to decrypt stuff. Sacrificing the IBE communication pattern wouldn't seem like a big deal. Hmm well IBE is has a useful side-effect in pseudonymity systems because it also has the side-effect of saving the privacy problems in first obtaining the other parties key. Other way to counteract that is to always include the psuedonym public key with the pseudonym name (which works for mailto: style URLs or whatever that are electronically distributed, but not for offline distributed). Btw one other positive side-effect of IBE is the server can't impersonate by issuing another certificate in a pseudonyms name because there is definitionally only one certificate. I was thinking particularly if you super-encrypt with the psuedonym's (standard CA) public key as well as the IBE public key you get the best of both feature sets. btw#2 You could probably come up with a way to prevent a standard (non IBE) CA from issuing multiple certs. eg. if he does that and someone puts two certs together they learn CA private key, ala Brands credential kind of offline double spending protection. Kind of a cryptographically enforced version of the policy enforced uniqueness of serial numbers in X.509 certs. And we change the policy to one cert per pseudonym (kind of sudden death if you lose the private key, but hey just don't do that; we'd have no other way to authenticate you to get a new cert in the same psuedonyms name anyway, so you may just as well backup your pseudonym private key). Adam

Gap may be I'm misunderstanding something about the HC approach. We have: P = (P1 or P2) is encoded HC_E(R,p) = {HC_E(R,P1),HC_E(R,P2)} so one problem is marking, the server sends you different R values: {HC_E(R,P1),HC_E(R',P2)} so you described one way to fix that by using symmetric crypto (where it is difficult to get a message to decrypt 2 different ways with different keys and get other than line noise out of the 2nd key). But next problem you mentioned, server could simply lie and send you {HC_E(R,P1),R2} for random value R2 now if you reply he knows you have property P1. So I was suggesting that after you decrypt HC_E(R,P1) you encrypt it again to check if R2 == HC_E(R,P2) which you should be able to do if you know P2, you have R (because you just decrypted it), and if you tweak the crypto system so that there is no non-deterministic aspect such as OAEP, randomization factors etc.

...

Unless it's signifcantly less efficient, I'd say use it all the time.

Well, I wouldn't complain. :) (Although pairings are quite slow, on the order of hundreds of milliseconds.) Hilarie Orman presented it at an IETF meeting to what was reportedly a lukewarm response, and they also raised the patent issue. Dan Boneh is sensitive to the issue of patented crypto, and was quite considerate when I asked about it, but www.voltage.com still has the same vague statement in their FAQ about how they're not going to be evil with the patent, so it's still up in the air whether IBE will be useful in IETF standards.

If one were not explicitly interested in the IBE communication pattern, and to avoid the patents in IETF protocol problems, I would think one could do something without IBE. eg. you mentioned earlier the problem of issuing one cert per attribute permutation. Instead how about you issue one cert per attribute to psuedonym plus attribute. In the case where you are not due the attribute, you just don't learn the corresponding private key. One problem with this is you have to avoid the server learning the private key for the one you don't. Now it might be possible eg. with Elgamal / DH to make an efficient non-interactive ZKP that convinces you that the server chose the private key fairly (and so does not know any corresponding private key). But another way to side-step the issue is to have the CA issue you two certs per attribute. You choose the private key for one it chooses the private key for the other. Data is encrypted with both keys. In the case of you not being due the attribute the CA does not give you the private key it generated. You could probably use some of the key gen stuff from multi-party signatures (where multiple parties are involved and each holds a private key fragment), however they tend to be inefficient I think so above is probably simple and efficient enough. Adam