This is the third of a series of posts on the prospects for using
privacy-enhancing technologies in the NSTIC Identity Ecosystem.
In the first two posts we’ve looked at two, or rather three,
privacy-enhancing authentication technologies: U-Prove, Idemix, and
the Idemix Java card. The credentials provided by these technologies
have some or all of the privacy features called for by NSTIC, but they
have various practical drawbacks, the most serious of which is that
they are not revocable by the credential issuer.
Given these drawbacks, it is natural to ask the question: are
privacy-friendly credentials really necessary for NSTIC? My answer
is: they are not needed in many important use cases, and they are
useful but not indispensable in other important cases; but they are
essential in cases that are key to the success of NSTIC.
Use Cases Where Privacy-Enhancing Technologies Are Not Needed
The most common use case of Web authentication is the case where a
user registers anonymously with a Web site and later logs in as a
returning user. Traditionally, the user registers a username and a
password with the site and later uses them as credentials to log in.
Today, third-party login is becoming popular as a way of mitigating
the proliferation or reuse of passwords: the user logs in with
username and password to a third-party identity provider, and is then
redirected to the Web site, which plays the role of relying party.
But there is a way of avoiding passwords altogether: the Web site can
issue a cryptographic credential to the user upon registration, which
the user can submit back to the Web site upon login. In that case
there is no third party involvement and no privacy issues. The
cryptographic credential can therefore be an ordinary PKI certificate.
No privacy-enhancing technologies are needed.
The PKI certificate binds the newly created user account to the
public key component of a key pair that the browser generates on the
Other cases where privacy-enhancing technologies are not needed are
those where a credential demonstrates that the user possesses an
attribute whose value uniquely identifies the user, and the relying
party needs to know the value of that attribute. (One example of such
an attribute is an email address.) Privacy-enhancing technologies are
not useful in such cases because a uniquely-identifying attribute
communicated to relying parties can be used to track the user no
matter what type of credential is used to communicate the attribute.
Use Cases Where Privacy-Enhancing Technologies Are Useful but not Essential
Privacy-enhancing technologies are useful but not essential when the
attributes certified by a credential do not uniquely identify the
user, and the user has a choice of credential issuers. They are
useful in such cases because they prevent the issuer from tracking the
user’s activities by sharing data with the relying parties. They are
not essential, however, because the user may be able to choose a
credential issuer that she trusts. (Most privacy-enhancing
technologies also prevent relying parties from collectively tracking
the user by sharing their login information, without involvement of
the credential issuer, but the risk of this happening may be more
Examples of non-identifying attributes are demographic attributes
(city of residence, gender, age group), shopping interests, hobby
interests, etc.; such attributes are usually self-asserted, but they
can be supplied by an identity provider, chosen by the user, as a
matter of convenience, so that the user does not have to reenter them
and maintain them uptodate at each relying party. Examples of sites
that may ask for such attributes are dating sites, shopping deal
sites, hobbyist sites, etc.
Of course, a credential that contains non-identifying attributes will
not by itself allow a user to log in to a site. But it can be used in
addition to a PKI certificate issued by the site itself to recognize
Use Cases Where Privacy-Enhancing Technologies Are Necessary
Privacy-enhancing technologies are necessary when the relying party
does not require uniquely identifying information, and there is only
one credential issuer. That one credential issuer could be the
government. Non-uniquely-identifying information provided by
government-issued credentials could include assertions that the user
is old enough to buy wine, or is a resident of a particular state, or
is licensed to practice some profession in some state, or is a US
citizen, or has the right to work in the US.
I find it difficult to find examples where people would have a
reasonable fear of being tracked through their use of
government-issued credentials. But the right to privacy is a human
right that is held dear in the United States, and has been found to be
implicitly protected by the US constitution. Government-issued
credentials will only be acceptable if they incorporate all available
privacy protections. That makes the use of privacy-enhancing
technologies essential to the success of NSTIC.
Wanted: Efficiently-Revocable Privacy-Friendly Credentials
So: privacy-friendly credentials are necessary; but, in my opinion,
the drawbacks of existing privacy-enhancing technologies make them
impractical. Therefore we need new privacy-enhancing technologies.
Those new technologies should have issue-show and multi-show
unlinkability; they should provide partial information disclosure,
including proofs of inequality relations involving numeric attributes;
and they should be efficiently revocable.
Fortunately, that’s not too much to ask. U-Prove and Idemix have been
pioneering technologies, but they are now dated. U-Prove is based on
research carried out in the mid-nineties, and the core cryptographic
scheme later used in Idemix was described in a paper written in 2001.
A lot of research has been done in cryptography since then, and
several new cryptographic schemes have been proposed that could be
used to provide privacy-friendly credentials.
I don’t think a scheme meeting all the requirements, including
efficient revocation, has been designed yet. (I would love to be
corrected if I’m wrong!) But possible ingredients for such a system
have been proposed, including methods for proving non-revocation in time
proportional to the square root of the number of revoked credentials
or even in practically constant time
Stefan Brands has told me that the cryptosystem described in  is considered part of the U-Prove technology, and that the revocation technique of  could be integrated into the existing U-Prove implementation to provide issuer-driven revocation. If that were done and the resulting system proved to be suitably efficient, the only ingredient missing from that system would be multi-show unlinkability.
Once a scheme with all the ingredients has been designed and
mathematically verified, it still needs to be implemented.
Cryptographic implementations are few and far between, but that does
not mean that they are difficult. Recently, for example, three
different systems of privacy-friendly credentials were implemented
just for the purpose of comparing their performance
Next and Last: Usability and Deployment
To conclude the series, in the next post I’ll try to respond to a
comment made by Anthony Nadalin on the
Commons mailing list:
“if it’s not useable or deployable who cares?”.
Stefan Brands, Liesje Demuynck and Bart De Decker.
A practical system for globally revoking the unlinkable pseudonyms of unknown users.
In Proceedings of the 12th Australasian Conference on Information Security and Privacy, ACISP’07.
Preconference technical report available at http://www.cs.kuleuven.be/publicaties/rapporten/cw/CW472.pdf.
T. Nakanishi, H. Fujii, Y. Hira and N. Funabiki.
Revocable Group Signature Schemes with Constant Costs for Signing and Verifying.
In IEICE Transactions,
J. Lapon, M. Kohlweiss, B. De Decker and V. Naessens.
Performance Analysis of Accumulator-Based Revocation Mechanisms.
In Proceedings of the 25th International Conference on Information Security (SEC 2010).