5
$\begingroup$

I'm new to the list, a layman in cryptography, but a competent programmer. Seeking your help for a practical algorithm that I can implement please.

Problem

Let a prover P hold an identity document D, e.g. a passport, that contains a date of birth field dob.

A verifier V wants to check that:

  1. that I hold the document
  2. that D.dob is >= <some date>

All without P exposing D or V trusting P.

thanks and regards d.

$\endgroup$
  • 1
    $\begingroup$ That's not possible without further assumptions. A practical and simple version would be to use the eID functions, which are used by some countries. This is basically just using a trusted third party (the card issuer), which performs the check. If you just consider a paper passport, this is pretty much impossible without revealing the ID, because there is nothing to check. $\endgroup$ – tylo May 31 '17 at 7:53
  • 2
    $\begingroup$ You could take look at the TR 03110 documents specified by the German BSI. One problem is that this is not that suitable as an introduction to cryptography (but neither is this subject, I suppose). I guess the term you are looking for is attribute-based pseudonymous authentication. Or terms really :P $\endgroup$ – Maarten Bodewes May 31 '17 at 8:27
  • $\begingroup$ Is V permitted to know enough information to forge a D with any particular age? (This would imply that V is not allowed to know P's actual date of birth, but is permitted to know how P would answer if P was any arbitrary age) $\endgroup$ – Cort Ammon Jun 1 '17 at 19:35
  • $\begingroup$ Re tylo's comment: I think the prover will need to be an identity authority and issuer of said identity document. $\endgroup$ – dazraf Jun 2 '17 at 20:32
  • $\begingroup$ I must say, I am very grateful for all your thoughtful answers. As a newcomer to the field, it's wonderful to receive such help. Thank you. $\endgroup$ – dazraf Jun 2 '17 at 20:39
5
$\begingroup$

Here's a solution using RSA as the primitive. There's probably a variant based on elliptic curves. Though maybe not. RSA is great for this kind of stuff.

The protocol

Grace the government worker gives the prover Paul an identity document. One of the document fields is an age threshold proof value. This is a standard RSA signature over some public fields of Bob's identity document (EG:name, picture etc.) that Paul would use to prove he is Paul.

Instead of using the standard RSA signature algorithm to generate the signature, Grace uses a multiple of the private exponent when doing the operation. This is equivalent to applying the private operation multiple times.

age_proof=sig^(d*age) mod N

To verify this signature we have to apply the public operation age times to get back the original signature value.

sig=age_proof^(e*age) mod N

Note that sig, e and N are known to the verifier, age and age_proof are not known.

Suppose Paul is 35. If Alice wants paul to prove he is at least 20 years old, Paul first performs 15 public RSA operations on his proof of age value. He passes this value to Alice who performs an additional 20 exponentiations and gets back the original signature.

This can be seen as a chain of signatures. Grace, by repeatedly applying the private operation to Bob's signature value creates a chain of signature values which can be traversed in the forwards direction to get to the signature value.

What the system provides

Paul has an integer x Grace provides him with a proof value Px

Alice asks Paul to prove that x is larger than a bound y

  • Alice gives Paul y
  • Paul applies x-y public operations to degrade Px into a proof for Py
  • Paul gives Py to Alice
  • Alice applies y public operations to degrade Py into P0 which is a signature of some data about the thing that was signed (EG: Who owns the proof.)

Proof of age range

A more practical proof of age system would use two numbers. The numbers would be measured in days or hours and be the difference between the owner's data of birth and a date far in the past (say 1900AD) and a date far in the future (2200AD)

The first number, referenced to a date in the past proves youngness. The larger this number the more recent the date of birth.

The second number, referenced to a date in the future proves oldness. The larger this number the farther in the past the date of birth is and the older someone is.

This avoids the need to reissue or update cards as the card holder ages. The proof of youngness can be useful for businesses that want to implement youth discounts.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for an elegant algorithm and description. Very much appreciated. $\endgroup$ – dazraf Jun 2 '17 at 20:29
2
$\begingroup$

I recently found another solution, similar to @richard-thiessen, above, using hash chains. The basic idea comes from a paper by angel and walfish.

The prover would ask a trusted 3rd party to sign a document containing a) some necessary metadata that the verifier would want to see (maybe the name and the date the document was created) b) C = Hash^age(S)

The third party would then send this document to the prover, along with S

S is some random integer, and C is the end of the hash chain. If the prover is 60 years old (according to the document), 60 hashes must be calculated. b) his age in years, along with a timestamp for when the document was produced

When the verifier wants to challenge the prover's age, the verifier sends an integer q to the prover.

The prover then sends 2 hash chains to the verifier a) C (along with the metadata from the bank, signed by the bank) b) C' = Hash^(age-q)(S)

Similarly to the RSA solution above, the verifier then "finishes" the hash chain by performing q more hashes. Since finding the right pre-image of a hash is "hard", we know the prover couldn't guess C'. And since the verifier trusts the trusted source and verifies its signature, we know C is also correct.

This is simplified from the paper, but just a little bit.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you ads for a practical solution and the very useful reference. I'm reading the paper. $\endgroup$ – dazraf Jun 2 '17 at 21:04
1
$\begingroup$

One would prove "more or equal" statement about integers with a proof of knowledge protocol of a non-negative witness. This could be done with (1) Lagrange theorem stating existence of representation as a sum of four squares, and (2) protocols for integers (basically, committing with a group of a hidden order).

Solution based on Lagrange theorem was introduced by Helger Lipmaa, "On Diophantine Complexity and Statistical Zero-Knowledge Arguments". Proofs with integers were introduced by Camenisch and Stadler.

For implementation, take a look at Idemix design tech report.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you Vadym for very useful references. I'm reading them now :-) $\endgroup$ – dazraf Jun 2 '17 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.