Re: Cryptographic privacy protection in TCPA
Nomen Nescio wrote: It looks like Camenisch Lysyanskaya are patenting their credential system. This is from the online patent applications database: http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO2Sect2=HITOFFp=1u=/ne tahtml/PTO/search-bool.htmlr=1f=Gl=50co1=ANDd=PG01s1=camenischOS=came nischRS=camenisch Jan Camenisch works for IBM, it's no surprise that the scheme is being patented. The scheme is not very efficient compared to Brands', but I would guess implementable if you don't mind doing allot of computation. It is based on zero-knowledge proofs. The basic idea of using zero-knowledge proofs to create an unlikable anonymous credentials system is actually pretty intuitive and simple, and people have taught about it before Camenisch Lysyanskay have. You can probably think about it yourself and come up with a similar scheme (not necessarily provably secure however) The novelty in my point of view is simply the choice of the setting in which they work in (group of quadratic residues modulo a composite), so that their scheme can apparently be proven secure under the strong RSA assumptions and the decisional DH assumption. Camenischs work on group signatures and Proving in zero-knowledge that a number n is the product of two safe primes seem to have lead to the result. --Anton
Re: Cryptographic privacy protection in TCPA
It looks like Camenisch Lysyanskaya are patenting their credential system. This is from the online patent applications database: http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO2Sect2=HITOFFp=1u=/netahtml/PTO/search-bool.htmlr=1f=Gl=50co1=ANDd=PG01s1=camenischOS=camenischRS=camenisch Non-transferable anonymous credential system with optional anonymity revocation Abstract The present invention relates to a method and system for securely proving ownership of pseudonymous or anonymous electronic credentials. A credential system is described consisting of users and organizations. An organization knows a user only by a pseudonym. The pseudonyms of the same user, established for use with different organizations, cannot be linked. An organization can issue a credential to a pseudonym, and the corresponding user can prove possession of this credential to another organization that knows him under another pseudonym. During the prove of possession of the credential nothing besides the fact that he owns such a credential is revealed. A refinement of the credential system provides credentials for unlimited use, so called multiple-show credentials, and credentials for one-time use, so called one-show credentials. Some of the claims seem a little broad, like this first one: 1. A method for establishing a pseudonym system by having a certificate authority accepting a user as a new participant in said pseudonym system, the method comprising the steps of: receiving a first public key provided by said user; verifying that said user is allowed to join the system; computing a credential by signing the first public key using a secret key owned by said certificate authority; publishing said first public key and said credential. Wouldn't this general description cover most proposed credential systems in the past, such as those by Chaum or Brands? Does anyone know how to contact the PTO regarding proposed patents, perhaps to point out prior art?
Re: Cryptographic privacy protection in TCPA
On Mon, 2 Sep 2002, Nomen Nescio wrote: It looks like Camenisch Lysyanskaya are patenting their credential system. This is from the online patent applications database: http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO2Sect2=HITOFFp=1u=/netahtml/PTO/search-bool.htmlr=1f=Gl=50co1=ANDd=PG01s1=camenischOS=camenischRS=camenisch Does anyone know how to contact the PTO regarding proposed patents, perhaps to point out prior art? It's best not to contact the PTO or the patent holder with prior art. Gregory Aharonian has written some interesting material on this in his Patent News newsletter. If you contact the patent holder or the PTO with the prior art, it will likely be listed in the patent, or future patents if the application has already been granted. In the case of an existing patents, presenting prior art to the PTO can result it the prior art being given a previously reviewed status. Prior art with a previously reviewed status, or prior art listed on the patent are both much less effective in a defense case against an infringement claim. Therefor alerting the patent holder or the PTO to prior art would actually make the patent stronger and less likely to be invalidated. Basically, the patent system is so corrupt, the best thing to do is to avoid participating it in. Just like the US democratic system. - VAB
Re: Cryptographic privacy protection in TCPA
Carl Ellison suggested an alternate way that TCPA could work to allow for revoking virtualized TPMs without the privacy problems associated with the present systems, and the technical problems of the elaborate cryptographic methods. Consider first the simplest possible method, which is just to put a single signature key in each TPM and allow the TPM to use that to sign its messages on the net. This is reliable and allows TPM keys to be revoked, but it obviously offers no privacy. Every usage of a TPM key can be correlated as coming from a single system. TCPA fixed this by adding a trusted third party, the Identity CA who would be the only one to see the TPM key. But Carl offers a different solution. Instead of burning only one key into the TPM, burn several. Maybe even a hundred. And let these keys be shared with other TPMs. Each TPM has many keys, and each key has copies in many TPMs. Now let the TPMs use their various keys to identify themselves in transactions on the net. Because each key belongs to many different TPMs, and the set of TPMs varies for each key, this protects privacy. Any given usage of a key can be narrowed down only to a large set of TPMs that possess that key. If a key is misused, i.e. scraped out of the TPM and used to create a virtualized, rule-breaking software TPM, it can be revoked. This means that all the TPMs that share that one key lose the use of that key. But it doesn't matter much, because they each have many more they can use. Since it is expected that only a small percentage of TPMs will ever need their keys revoked, most TPMs should always have plenty of keys to use. One problem is that a virtualized TPM which loses one of its keys will still have others that it can use. Eventually those keys will also be recognized as being mis-used and be revoked as well. But it may take quite a while before all the keys on its list are exhausted. To fix this, Carl suggests that the TPM manufacturer keep a list of all the public keys that are in each TPM. Then when a particular TPM has some substantial fraction of its keys revoked, that would be a sign that the TPM itself had been virtualized and all the rest of the keys could be immediately revoked. The precise threshold for this would depend on the details of the system, the number of keys per TPM, the number of TPMs that share a key, the percentage of revoked keys, etc. But it should not be necessary to allow each TPM to go through its entire repertoire of keys, one at a time, before a virtualized TPM can be removed from the system. Carl indicated that he suggested this alternative early in the TCPA planning process, but it was not accepted. It does seem that while the system has advantages, in some ways it shares the problems of the alternatives. It provides privacy, but not complete privacy, not as much as the cryptographic schemes. And it provides security to the TPM issuers, but not complete security, not as much as the Privacy CA method. In this way it can be seen as a compromise. Often, compromise solutions are perceived more in terms of their disadvantages than their benefits.
Re: Cryptographic privacy protection in TCPA
With Brands digital credentials (or Chaums credentials) another approach is to make the endorsement key pair and certificate the anonymous credential. That way you can use the endorsement key and certificate directly rather than having to obtain (blinded) identity certificates from a privacy CA and trust the privacy CA not to issue identity certificates without seeing a corresponding endorsement credential. However the idea with the identity certificates is that you can use them once only and keep fetching new ones to get unlinkable anonymity, or you can re-use them a bit to get pseudonymity where you might use a different psuedonym for a different service where you are anyway otherwise linkable to a given service. With Brands credentials the smart card setting allows you to have more compact and computationally cheap control of the credential from within a smart card which you could apply to the TPM/SCP. So you can fit more (unnamed) pseudonym credentials on the TPM to start with. You could perhaps more simply rely on Brands credential lending discouraging feature (ability to encode arbitrary values in the credential private key) to prevent break once virtualize anywhere. For discarding pseudonyms and when you want to use lots of pseudonyms (one-use unlinkable) you need to refresh the certificates you could use the refresh protocol which allows you to exchange a credential for a new one without trusting the privacy CA for your privacy. Unfortunately I think you again are forced to trust the privacy CA not to create fresh virtualized credentials. Perhaps there would be someway to have the privacy CA be a different CA to the endorsement CA and for the privacy CA to only be able to refresh existing credentials issued by the endorsement CA, but not to create fresh ones. Or perhaps some restriction could be placed on what the privacy CA could do of the form if the privacy CA issued new certificates it would reveal it's private key. Also relevant is An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation, Jan Camenisch and Anna Lysyanskaya, Eurocrypt 01 http://eprint.iacr.org/2001/019/ These credentials allow the user to do unlinkable multi-show without involving a CA. They are somewhat less efficient than Chaum or Brands credentials though. But for this application does this removes the need to trusting a CA, or even have a CA: the endorsement key and credential can be inserted by the manufacturer, can be used indefinitely many times, and are not linkable. A secondary requirement is for some kind of revocation in the case of misuse. As you point out unlinkable anonymity tends to complicate revocation. I think Camenisch's optional anonymity revocation has similar properties in allowing a designated entity to link credentials. Another less TTP-based approach to unlinkable but revocable credentials is Stubblebine's, Syverson and Goldschlag, Unlinkable Serial Transactions, ACM Trans on Info Systems, 1999: http://www.stubblebine.com/99tissec-ust.pdf (It's quite simple you just have to present and relinquish a previous pseudonym credential to get a new credential; if the credential is due to be revoked you will not get a fresh credential.) I think I would define away the problem of local breaks. I mean the end-user does own their own hardware, and if they do break it you can't detect it anyway. If it's anything like playstation mod-chips some proportion of the population would in fact would do this. May be 1-5% or whatever. I think it makes sense to just live with this, and of course not make it illegal. Credentials which are shared are easier to revoke -- knowledge of the private keys typically will render most schemes linkable and revocable. This leaves only online lending which is anyway harder to prevent. Adam On Fri, Aug 16, 2002 at 03:56:09PM -0700, AARG!Anonymous wrote: Here are some more thoughts on how cryptography could be used to enhance user privacy in a system like TCPA. Even if the TCPA group is not receptive to these proposals, it would be useful to have an understanding of the security issues. And the same issues arise in many other kinds of systems which use certificates with some degree of anonymity, so the discussion is relevant even beyond TCPA.
Re: Cryptographic privacy protection in TCPA
Dr. Mike wrote, patiently, persistently and truthfully: On Fri, 16 Aug 2002, AARG! Anonymous wrote: Here are some more thoughts on how cryptography could be used to enhance user privacy in a system like TCPA. Even if the TCPA group is not receptive to these proposals, it would be useful to have an understanding of the security issues. And the same issues arise in many other kinds of systems which use certificates with some degree of anonymity, so the discussion is relevant even beyond TCPA. OK, I'm going to discuss it from a philosophical perspective. i.e. I'm just having fun with this. Fine, but let me put this into perspective. First, although the discussion is in terms of a centralized issuer, the same issues arise if there are multiple issuers, even in a web-of-trust situation. So don't get fixated on the fact that my analysis assumed a single issuer - that was just for simplicity in what was already a very long message. The abstract problem to be solved is this: given that there is some property which is being asserted via cryptographic certificates (credentials), we want to be able to show possession of that property in an anonymous way. In TCPA the property is being a valid TPM. Another example would be a credit rating agency who can give out a good credit risk credential. You want to be able to show it anonymously in some cases. Yet another case would be a state drivers license agency which gives out an over age 21 credential, again where you want to be able to show it anonymously. This is actually one of the oldest problems which proponents of cryptographic anonymity attempted to address, going back to David Chaum's seminal work. TCPA could represent the first wide-scale example of cryptographic credentials being shown anonymously. That in itself ought to be of interest to cypherpunks. Unfortunately TCPA is not going for full cryptographic protection of anonymity, but relying on Trusted Third Parties in the form of Privacy CAs. My analysis suggests that although there are a number of solutions in the cryptographic literature, none of them are ideal in this case. Unless we can come up with a really strong solution that satisfies all the security properties, it is going to be hard to make a case that the use of TTPs is a mistake. I don't like the idea that users *must* have a certificate. Why can't each person develop their own personal levels of trust and associate it with their own public key? Using multiple channels, people can prove their key is their word. If any company wants to associate a certificate with a customer, that can have lots of meanings to lots of other people. I don't see the usefullness of a permanent certificate. Human interaction over electronic media has to deal with monkeys, because that's what humans are :-) A certificate is a standardized and unforgeable statement that some person or key has a particular property, that's all. The kind of system you are talking about, of personal knowledge and trust, can't really be generalized to an international economy. Actually, in this system the Privacy CA is not really protecting anyone's privacy, because it doesn't see any identities. There is no need for multiple Privacy CAs and it would make more sense to merge the Privacy CA and the original CA that issues the permanent certs. That way there would be only one agency with the power to forge keys, which would improve accountability and auditability. I really, REALLY, *REALLY*, don't like the idea of one entity having the ability to create or destroy any persons ability to use their computer at whim. You are suggesting that one person (or small group) has the power to create (or not) and revoke (or not!) any and all TPM's! I don't know how to describe my astoundment at the lack of comprehension of history. Whoever makes a statement about a property should have the power to revoke it. I am astounded that you think this is a radical notion. If one or a few entities become widely trusted to make and revoke statements that people care about, it is because they have earned that trust. If the NY Times says something is true, people tend to believe it. If Intel says that such-and-such a key is in a valid TPM, people may choose to believe this based on Intel's reputation. If Intel later determines that the key has been published on the net and so can no longer be presumed to be a TPM key, it revokes its statement. This does not mean that Intel would destroy any person's ability to use their computer on a whim. First, having the TPM cert revoked would not destroy your ability to use your computer; at worst you could no longer persuade other people of your trustworthiness. And second, Intel would not make these kind of decision on a whim, any more than the NY Times would publish libelous articles on a whim; doing so would risk destroying the company's reputation, one of its most valuable assets. I can't
Re: Cryptographic privacy protection in TCPA
On Fri, 16 Aug 2002, AARG! Anonymous wrote: Here are some more thoughts on how cryptography could be used to enhance user privacy in a system like TCPA. Even if the TCPA group is not receptive to these proposals, it would be useful to have an understanding of the security issues. And the same issues arise in many other kinds of systems which use certificates with some degree of anonymity, so the discussion is relevant even beyond TCPA. OK, I'm going to discuss it from a philosophical perspective. i.e. I'm just having fun with this. The basic requirement is that users have a certificate on a long-term key which proves they are part of the system, but they don't want to show that cert or that key for most of their interactions, due to privacy concerns. They want to have their identity protected, while still being able to prove that they do have the appropriate cert. In the case of TCPA the key is locked into the TPM chip, the endorsement key; and the cert is called the endorsement certificate, expected to be issued by the chip manufacturer. Let us call the originating cert issuer the CA in this document, and the long-term cert the permanent certificate. I don't like the idea that users *must* have a certificate. Why can't each person develop their own personal levels of trust and associate it with their own public key? Using multiple channels, people can prove their key is their word. If any company wants to associate a certificate with a customer, that can have lots of meanings to lots of other people. I don't see the usefullness of a permanent certificate. Human interaction over electronic media has to deal with monkeys, because that's what humans are :-) A secondary requirement is for some kind of revocation in the case of misuse. For TCPA this would mean cracking the TPM and extracting its key. I can see two situations where this might lead to revocation. The first is a global crack, where the extracted TPM key is published on the net, so that everyone can falsely claim to be part of the TCPA system. That's a pretty obvious case where the key must be revoked for the system to have any integrity at all. The second case is a local crack, where a user has extracted his TPM key but keeps it secret, using it to cheat the TCPA protocols. This would be much harder to detect, and perhaps equally significantly, much harder to prove. Nevertheless, some way of responding to this situation is a desirable security feature. Ouch, that doesn't sound too robust. The TCPA solution is to use one or more Privacy CAs. You supply your permanent cert and a new short-term identity key; the Privacy CA validates the cert and then signs your key, giving you a new cert on the identity key. For routine use on the net, you show your identity cert and use your identity key; your permanent key and cert are never shown except to the Privacy CA. This means that the Privacy CA has the power to revoke your anonymity; and worse, he (or more precisely, his key) has the power to create bogus identities. On the plus side, the Privacy CA can check a revocation list and not issue a new identity cert of the permanent key has been revoked. And if someone has done a local crack and the evidence is strong enough, the Privacy CA can revoke his anonymity and allow his permanent key to be revoked. The CA has a bit too much power if you ask me. Those are some really good reasons not to like the idea of a permanent certificate ruled by one (nasty?) person. [...] Actually, in this system the Privacy CA is not really protecting anyone's privacy, because it doesn't see any identities. There is no need for multiple Privacy CAs and it would make more sense to merge the Privacy CA and the original CA that issues the permanent certs. That way there would be only one agency with the power to forge keys, which would improve accountability and auditability. I really, REALLY, *REALLY*, don't like the idea of one entity having the ability to create or destroy any persons ability to use their computer at whim. You are suggesting that one person (or small group) has the power to create (or not) and revoke (or not!) any and all TPM's! I don't know how to describe my astoundment at the lack of comprehension of history. [...] It's not entirely clear how this technology could best be exploited to solve the problems. One possibility, for example, would be to encode information about the permanent key in the restrictive blinding. This would allow users to use their identity keys freely; but upon request they could prove things about their associated permanent keys. They could, for example, reveal the permanent key value associated with their identity key, and do so unforgeably. Or they could prove that their permanent key is not on a given list of revoked keys. Similar logical operations are possible including partial revelation of the permanent key information. There's no
Cryptographic privacy protection in TCPA
Here are some more thoughts on how cryptography could be used to enhance user privacy in a system like TCPA. Even if the TCPA group is not receptive to these proposals, it would be useful to have an understanding of the security issues. And the same issues arise in many other kinds of systems which use certificates with some degree of anonymity, so the discussion is relevant even beyond TCPA. The basic requirement is that users have a certificate on a long-term key which proves they are part of the system, but they don't want to show that cert or that key for most of their interactions, due to privacy concerns. They want to have their identity protected, while still being able to prove that they do have the appropriate cert. In the case of TCPA the key is locked into the TPM chip, the endorsement key; and the cert is called the endorsement certificate, expected to be issued by the chip manufacturer. Let us call the originating cert issuer the CA in this document, and the long-term cert the permanent certificate. A secondary requirement is for some kind of revocation in the case of misuse. For TCPA this would mean cracking the TPM and extracting its key. I can see two situations where this might lead to revocation. The first is a global crack, where the extracted TPM key is published on the net, so that everyone can falsely claim to be part of the TCPA system. That's a pretty obvious case where the key must be revoked for the system to have any integrity at all. The second case is a local crack, where a user has extracted his TPM key but keeps it secret, using it to cheat the TCPA protocols. This would be much harder to detect, and perhaps equally significantly, much harder to prove. Nevertheless, some way of responding to this situation is a desirable security feature. The TCPA solution is to use one or more Privacy CAs. You supply your permanent cert and a new short-term identity key; the Privacy CA validates the cert and then signs your key, giving you a new cert on the identity key. For routine use on the net, you show your identity cert and use your identity key; your permanent key and cert are never shown except to the Privacy CA. This means that the Privacy CA has the power to revoke your anonymity; and worse, he (or more precisely, his key) has the power to create bogus identities. On the plus side, the Privacy CA can check a revocation list and not issue a new identity cert of the permanent key has been revoked. And if someone has done a local crack and the evidence is strong enough, the Privacy CA can revoke his anonymity and allow his permanent key to be revoked. Let us now consider some cryptographic alternatives. The first is to use Chaum blinding for the Privacy CA interaction. As before, the user supplies his permanent cert to prove that he is a legitimate part of the system, but instead of providing an identity key to be certified, he supplies it in blinded form. The Privacy CA signs this blinded key, the user strips the blinding, and he is left with a cert from the Privacy CA on his identity key. He uses this as in the previous example, showing his privacy cert and using his privacy key. In this system, the Privacy CA no longer has the power to revoke your anonymity, because he only saw a blinded version of your identity key. However, the Privacy CA retains the power to create bogus identities, so the security risk is still there. If there has been a global crack, and a permanent key has been revoked, the Privacy CA can check the revocation list and prevent that user from acquiring new identities, so revocation works for global cracks. However, for local cracks, where there is suspicious behavior, there is no way to track down the permanent key associated with the cheater. All his interactions are done with an identity key which is unlinkable. So there is no way to respond to local cracks and revoke the keys. Actually, in this system the Privacy CA is not really protecting anyone's privacy, because it doesn't see any identities. There is no need for multiple Privacy CAs and it would make more sense to merge the Privacy CA and the original CA that issues the permanent certs. That way there would be only one agency with the power to forge keys, which would improve accountability and auditability. One problem with revocation in both of these systems, especially the one with Chaum blinding, is that existing identity certs (from before the fraud was detected) may still be usable. It is probably necessary to have identity certs be valid for only a limited time so that users with revoked keys are not able to continue to use their old identity certs. Brands credentials provide a more flexible and powerful approach than Chaum blinding which can potentially provide improvements. The basic setup is the same: users would go to a Privacy CA and show their permanent cert, getting a new cert on an identity key which they would use on the net. The difference is that