Re: Brands' private credentials
Adam Back wrote: On Mon, May 10, 2004 at 02:42:04AM +, Jason Holt wrote: 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. There is code for this in openssl (not sure if its the same technique, its described as a ring signature). One of the more amusing aspects is it was posted anonymously and signed by a group of likely-looking candidates. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff
Re: more hiddencredentials comments (Re: Brands' private credentials)
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
Re: Brands' private credentials
On Mon, May 10, 2004 at 02:42:04AM +, 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
Re: Brands' private credentials
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
On Mon, 10 May 2004, Adam Back wrote:
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?
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. So the server would have to find two R's that both satisfy
the MAC but produce different ciphertexts in order to learn anything from the
response.
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. They might be lying about the doctor part, and really
sending against patient OR nonexistant, in which case your response reveals
that you're a patient. That's why we recommend that your response (if any)
include the policy for the creds you used in decryption. So if Alice is
responding to a message she decrypted with her patient cred, which she only
(implicitly) discloses to Medicare, and the response itself is only for AIDS
clinics, she should encrypt against Medicare AND AIDS_clinic.
(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)
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
That's very slick. I'll check it out.
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.
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.
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. :)
-J
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.2.3 (GNU/Linux)
iD8DBQFAn9/HnwLgjivV2NERAkBUAJwLhH7lZBtd/boI6Edn3JWA+eStDQCdEFZi
GI4rzGoiscp0Ze/+iKweu08=
=eX/X
-END PGP SIGNATURE-
more hiddencredentials comments (Re: Brands' private credentials)
On Mon, May 10, 2004 at 08:02:12PM +, 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
Re: more hiddencredentials comments (Re: Brands' private credentials)
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On Mon, 10 May 2004, Adam Back wrote: 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? I don't quite get what you're suggesting. Could you give a more concrete example? 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. 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. -J -BEGIN PGP SIGNATURE- Version: GnuPG v1.2.3 (GNU/Linux) iD8DBQFAoAQfnwLgjivV2NERAtVcAKC8vQ6wxHeZ5Z3L4zcWPvZL7WKRqACgvB6y 8GxvXfFyewCuAA0FSAjdKoY= =ukVn -END PGP SIGNATURE-
Re: Brands' private credentials
[copied to cpunks as cryptography seems to have a multi-week lag these days]. OK, now having read: http://isrl.cs.byu.edu/HiddenCredentials.html http://isrl.cs.byu.edu/pubs/wpes03.pdf and seeing that it is a completely different proposal essentially being an application of IBE, and extension of the idea that one has multiple identities encoding attributes. (The usual attribute this approach is used for is time-period of receipt .. eg month of receipt so the sender knows which key to encrypt with). On Wed, Apr 28, 2004 at 07:54:50PM +, Jason Holt wrote: properties to Brands', and even does some things that his doesn't. so here is one major problem with using IBE: everyone in the system has to trust the IBE server! I feel a little presumptuous mentioning it in the context of the other systems, which have a much more esteemed set of authors and are much more developed, but I'm also pretty confident in its simplicity. One claim is that the system should hide sensitive attributes from disclosure during a showing protocol. So the example given an AIDs patient could authenticate to an AIDS db server without revealing to an outside observer whether he is an AIDs patient or an authorised doctor. However can't one achieve the same thing with encryption: eg an SSL connection and conventional authentication? 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. Further more there seems to be no blinding at issue time. So to obtain a credential you would have to identify yourself to the CA / IBE identity server, show paper credentials, typically involving True Name credentials, and come away with a private key. So it is proposed in the paper the credential would be issued with a pseudonym. However the CA can maintain a mapping between True Name and pseudonym. However whenever you show the credential the event is traceable back to you by collision with the CA. Note that most anonymous credential systems are encumbered by patents. I would not say your Hidden Credential system _is_ an anonymous credential system. There is no blinding in the system period. All is gated via a trust-me CA that in this case happens to be an IBE server, so providing the communication pattern advantages of an IBE system. What it enables is essentially an offline server assisted oblivious encryption where you can send someone a message they can only decrypt if they happen to have an attribute. You could call this a credential system kind of where the showing protcool is the verifier sends you a challenge, and the shower decrypts the challenge and sends the result back. In particular I don't see any way to implement an anonymous epayment system using Hidden Credentials. As I understand it is simply not possible as the system has no inherent cryptographic anonymity? Adam
Re: Brands' private credentials
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On Sun, 9 May 2004, Adam Back wrote: and seeing that it is a completely different proposal essentially being an application of IBE, and extension of the idea that one has multiple identities encoding attributes. (The usual attribute this approach is used for is time-period of receipt .. eg month of receipt so the sender knows which key to encrypt with). Right, good summary. One claim is that the system should hide sensitive attributes from disclosure during a showing protocol. So the example given an AIDs patient could authenticate to an AIDS db server without revealing to an outside observer whether he is an AIDs patient or an authorised doctor. 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, likewise for every possible combination of things somebody might ask you for, but that's not very practical. Presumably this is why the other systems also allow proof of expressions without revealing all the attributes you used to do so. 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: now the server has to reveal attributes to a complete stranger. For sensitive systems, it's easy to get circular dependencies where neither side wants to go first. Hidden credentials let you enforce the policy in the ciphertext: if you can read this, let's talk. if not, I didn't want to talk to you anyway (and you won't learn why). (Incidentally, two other similar systems came out at about the same time as mine, both geared less toward extreme policy/credential paranoia and more toward resolving such circular dependencies: OSBE (Li, Du, Boneh) and Secret Handshakes (Balfanz et al)). Further more there seems to be no blinding at issue time. So to obtain a credential you would have to identify yourself to the CA / IBE identity server, show paper credentials, typically involving True Name credentials, and come away with a private key. So it is proposed in the paper the credential would be issued with a pseudonym. However the CA can maintain a mapping between True Name and pseudonym. However whenever you show the credential the event is traceable back to you by collision with the CA. Right, that is a big consideration with my system; CAs can be nosy. Of course, any CA will want you to show paper credentials or some other real-world proof that they should give you a credential. But you're right that the Chaum/Brands/LC family do have a big advantage in limiting the risks of big-brother CAs once they've issued it to you. I would not say your Hidden Credential system _is_ an anonymous credential system. There is no blinding in the system period. All is gated via a trust-me CA that in this case happens to be an IBE server, so providing the communication pattern advantages of an IBE system. If your definition requires anonymity wrt the CA, then you're right. My system lets folks: * authenticate based on attributes rather than identity * access resources without the server even knowing whether they fulfill the policy * hide policies from people who don't fulfill them 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 have to write a survey paper for my Ph.D. requirements, and I've been thinking I should write a big feature table as part of it. In particular I don't see any way to implement an anonymous epayment system using Hidden Credentials. As I understand it is simply not I've never really considered it as a payment system. It's geared more toward systems which use extremely sensitive resources, and their corresponding sensitive policies and credentials. -J -BEGIN PGP SIGNATURE- Version: GnuPG v1.2.3 (GNU/Linux) iD8DBQFAnuwCnwLgjivV2NERAs/lAKC2B9R0EQJY+fgh46QpjkdmsdjbMwCgziHw VRCNzAhIdnIImHMyu7Lpvwk= =wpJ0 -END PGP SIGNATURE-
