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.
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
e and N are known to the verifier,
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
Grace provides him with a proof value
Alice asks Paul to prove that
x is larger than a bound
- Alice gives Paul
- Paul applies
x-y public operations to degrade
Px into a proof for
- Paul gives
Py to Alice
- Alice applies
y public operations to degrade
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.