Subject: [Cfrg] ZKP for proving ownership of a credential

From: Manu Sporny <[email-masked]>
Date: Tue, 02 Jun 2015 22:18:03 -0400

Hi all,

I'm currently involved in some work in a Community Group at W3C called
the Credentials CG as well as the Web Payments Interest Group at W3C. An
executive summary of what the Credentials CG is trying to do is here:

https://docs.google.com/document/d/1Nq543-Am1hQUIZ2hhzAFl8KexvIEBwDDc_f3Ikz1opQ/edit

We have a subset of credentials, like proof of citizenship ("this person
is a citizen of the United Kingdom") and proof of age ("this person is
above the age of 21"), that we believe could be asserted without leaking
information that could be used by colluding websites* to identify the
individual with the credential. We're trying to avoid having a single
identifier associated w/ these credentials that can be used to track
individuals between sites.

Clearly, at some point it's impossible to protect the privacy of the
individual or organization because information like a government issued
ID or name is shared in the credential. However, those are not the use
cases we're focused on with this particular question.

We have a hunch that perhaps some form of Zero Knowledge Proof could be
used with the credential, such that:

1. The issuer of the credential (a government) could issue a
   credential to a recipient (a citizen). The credential would
   contain an assertion (this person is a citizen of the United
   Kingdom). The credential would also contain a credential-specific
   ZKP algorithm and some public ZKP initialization vectors of some
   kind.
2. The recipient (the citizen) would separate out the /private/
   credential-specific ZKP algorithm and store it. The recipient
   would also store the /public/ credential with ZKP initialization
   vectors.
3. A verifier (3rd party website, like the BBC) would then request
   a credential proving UK citizenship. The recipient and verifier
   would then go through a number of ZKP iterations until the
   verifier was satisfied.

The end result is that the recipient has proven their citizenship while
the verifier has ensured that it checked this particular property of an
individual before delivering a service to them.

Unfortunately, we don't have any experts in ZKPs in the group and need
to have a chat with someone that is an expert. Preferably, someone that
knows if it is possible to construct a ZKP that could be used in this way.

If there is a more promising cryptographic approach than using a ZKP,
we'd love to hear about that as well. Any ideas?

-- manu

* The one big caveat to this is that a simple ask of an email address,
  browser fingerprinting, supercookies, defeats this mechanism.
  However, I believe our mandate in the future is going to be
  "don't make privacy worse on the Web".

-- 
Manu Sporny (skype: msporny, twitter: manusporny, G+: +Manu Sporny)
Founder/CEO - Digital Bazaar, Inc.
blog: Web Payments: The Architect, the Sage, and the Moral Voice
https://manu.sporny.org/2015/payments-collaboration/

---

From: Paul Lambert <[email-masked]>
Date: Wed, 3 Jun 2015 02:33:43 +0000

On 6/2/15, 7:18 PM, "Manu Sporny" <[email-masked]> wrote:

>   a credential proving UK citizenship.
Unless the credential is different each time it is provided to a third
party the recipient is trackable.

This problem has been Œsolved' to some degree by P1609.2 for automotive
applications.  

Paul

>The recipient and verifier
>_______________________________________________
>Cfrg mailing list
>[email-masked]
>http://www.irtf.org/mailman/listinfo/cfrg

---

From: Manu Sporny <[email-masked]>
Date: Wed, 03 Jun 2015 00:06:31 -0400

On 06/02/2015 10:33 PM, Paul Lambert wrote:
> Unless the credential is different each time it is provided to a 
> third party the recipient is trackable.

Understood.

> This problem has been Œsolved' to some degree by P1609.2 for 
> automotive applications.

Can you define "to some degree"? Any chance that you (or someone else)
has a pointer to the methods used in that IEEE spec wrt. protecting
privacy? I can shell out the $212 for the paper, but I'd like to know a
bit more about the content before I do. I did read the preview of the
paper, but couldn't get a handle on what sort of crypto they had settled
on to solve the problem.

-- manu

---

From: William Whyte <[email-masked]>
Date: Wed, 3 Jun 2015 05:10:12 -0400

HI Manu,

I'm editor of 1609.2, which is an IEEE standard specifying communications
security services in the Connected Vehicle setting.

There are two aspects to this, one of which is addressed inside 1609.2,
one of which is addressed by system choices.

On the proof of attributes: 1609.2 certs are inherently attribute certs
rather than identity certs, and a 1609.2 cert can be used to make a
statement about the holder's permissions using an identifier known as the
Provider Service ID (PSID) in the US or the ITS-AID in Europe. There isn't
currently a PSID for stating age or citizenship, but one could be
reserved. This would allow the holder to make an authenticated statement
about their properties without giving away their identity. (There may be
similar straightforward ways to use X.509, of course, I'm more familiar
with 1609.2).

On Paul's other point, "Unless the credential is different each time it is
provided to a third party the recipient is trackable": I wouldn't say that
1609.2 on its own solves this problem. The solution that is being proposed
in the Connected Vehicle space is for devices to have multiple certs
simultaneously valid for a period of (say) a week, which is a system spec
decision built on top of 1609.2. The current plan is that for applications
that require unlinkability, such as broadcast V2V safety messages, there
will be a minimum of 20 certs available to a device for any one-week
period. It's possible that devices with a higher physical security level
will be allowed to have more certs at a time.

There isn't any large-scale 1609.2 cert issuing infrastructure at the
moment, but when there is the expectation is that it will be designed to
accommodate issuing large numbers of throwaway certs. Cert holders have
"enrolment" certs, which are just used for cert requests, and
"authorization" certs, which are used for application activities; there
are systems in place to provide assurance that neither the RA (which sees
the enrolment cert) nor the CA (which issues the authorization certs) can
tell which authorization certs belong to the same set and therefore to the
same device. (This depends on there being a reasonable volume of cert
requests so the RA can "shuffle" together cert requests from different end
entities).

There's a description of those mechanisms in William Whyte, André
Weimerskirch, Virendra Kumar, and Thorsten Hehn, “A Security Credential
Management System for V2V Communications”, 2013 IEEE Vehicular Networking
Conference (VNC 2013), December 16-18, 2013, Boston, USA, which you can
get a copy of at
http://www.cvt-project.ir/Admin/Files/eventAttachments/A%20Security%20Cree
ntial%20Management%20System%20for%20V2V%20Communications%20-%20VNC%20Confe
rence%202013_514.pdf. Those mechanisms are being incorporated in the
current working draft of 1609.2, not yet complete. Copies of the draft are
available to participating working group members, and you can start
participating by subscribing to the list by mailing [email-masked] with
body "subscribe stds-p1609".

This is an engineering solution to the problem, with choices driven by the
need to keep certificate and signature sizes as small as possible and to
enable revocation if absolutely necessary while preserving privacy for
unrevoked devices (including the revoked device before its revocation).
There are other approaches that have better privacy properties but don't
meet our constraints: for example, Chaum and Brand's anonymous
credentials, or mechanisms based on group signatures. If you don't have
our constraints, one of those approaches might fit your needs better.

Hope this is useful -- especially the last paragraph :-)

Cheers,

William

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Manu Sporny
Sent: Wednesday, June 03, 2015 12:07 AM
To: Paul Lambert; Crypto Forum Research Group
Subject: Re: [Cfrg] ZKP for proving ownership of a credential

Understood.

-- manu

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 3 Jun 2015 02:39:14 -0700

On Tue, Jun 2, 2015 at 7:18 PM, Manu Sporny <[email-masked]>
wrote:

> individual with the credential.

Do you have more specific requirements than that? I know those are just
some contrived examples, but if those are really your only requirements,
the simple administrative solution in my mind is to simply only issue these
types of credentials to people who meet these criteria in the first place.
If you can solve the problem that way, I think you can use a simpler scheme
than a zero knowledge proof. I say this specifically because I don't think
getting any more fine-grained than citizenship and age is important to
solve this particular problem, and if that's the case, there are simpler
privacy-preserving systems that are easier to implement and reason about.

Here's a scheme I think fits into this general problem space and doesn't
require a zero knowledge proof. I should probably mention one of the chairs
name is on the paper:

https://eprint.iacr.org/2006/080.pdf

I'm not sure this is particularly well suited to your proposed problem, but
I'm wondering if your proposed problem could be simplified in such a way
that it would fit.

-- 
Tony Arcieri

---

From: Alec Edgington <[email-masked]>
Date: Wed, 3 Jun 2015 12:12:15 +0100

It sounds as if you may be after 'direct anonymous attestation' (DAA).
There are a number of protocols for this, the earlier ones based on RSA
(rather cumbersome), and the more modern ones (a.k.a. ECDAA) based on EC
pairings. Primitives to support these protocols are being introduced in the
TPM 2.0 standard, for example (though without specifying a specific
protocol). See for example http://eprint.iacr.org/2011/658.pdf for a
discussion of the security properties (and a suggested protocol).

The general idea is that the 'issuer' has a private and a public key; each
entity generates a secret key; there is an enrolment protocol where the
issuer and entity use their keys to generate a credential; later the entity
can use its secret key and the credential to sign an (anonymous)
attestation, which can be verified by the third party using the issuer's
public key. Controlled linkability of credentials is also possible.

---

From: Paul Lambert <[email-masked]>
Date: Thu, 4 Jun 2015 00:07:42 +0000

Manu,

>Can you define "to some degree"?
The clear note from William on P1609 hopefully answered that I was
referring to the engineering solution of P1609 having many attribute
certificates issued per entity.

Paul

> Any chance that you (or someone else)

---

From: David Jacobson <[email-masked]>
Date: Wed, 03 Jun 2015 20:10:10 -0700

>> paper, but couldn't get a handle on what sort of crypto they had settled
Keep in mind that Manu's original request was cast in terms of proving 
citizenship and at last age 21.  The solutions that have been mentioned 
address the problem of proving that some key-fob-like device is assigned 
to a person who is a UK Citizen and at least 21. They do not address the 
issue of proving that the person in possession of the device is the 
person it was assigned to.  That is not all that much of a problem with 
a car.  The owner of the car will presumably protect the device quite 
well, and will only loan it to people he/she intends to have access to 
the car.  But things might be different when it comes to under-age kids 
getting into drinking establishments.

     --David

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 3 Jun 2015 21:12:36 -0700

On Wed, Jun 3, 2015 at 8:10 PM, David Jacobson <[email-masked]>
wrote:

> address the problem of proving that some key-fob-like device is assigned to
> a person who is a UK Citizen and at least 21. They do not address the issue
> of proving that the person in possession of the device is the person it was
> assigned to.  That is not all that much of a problem with a car.  The owner
> of the car will presumably protect the device quite well, and will only
> loan it to people he/she intends to have access to the car.  But things
> might be different when it comes to under-age kids getting into drinking
> establishments.
>

Confinement is the Gordian Knot of bearer credentials, be they paper or
digital.

-- 
Tony Arcieri

---

From: Vadym Fedyukovych <[email-masked]>
Date: Fri, 5 Jun 2015 20:39:41 +0300

> party the recipient is trackable.

It depends on credential type.
This holds for a blind signature (u-prove) such that
recipient produces a challenge
verifiable with equality-of-two-logarithms relation.
This does not hold for a strong RSA -based credentials scheme.

> This problem has been ?solved' to some degree by P1609.2 for automotive
> applications.  
> 
> 
> Paul
> 
>