Age verification

Verifikation af alder

When you verify your age in current solutions, you are oversharing. That means you reveal more information about yourself than is needed. The other part doesnt need to know your social security number, or all the contents of your drivers license. They dont even need to know your day of birth. They just need to know that your age is not below some threshold. Yes or no. It is a binary question.

Når du verificerer din alder i nuværende løsninger, overdeler du. Det vil sige du afgiver flere informationer om dig selv end nødvendigt. Den anden part behøver ikke kende dit CPR nummer, eller alt hvad der står i dit kørekort. De behøver ikke engang at kende din fødselsdato. De har kun brug for at vide at din alder ikke er under en eller anden tærskelværdi. Ja eller nej. Det er et binært spørgsmål.

You might think that you could instead authorize them to ask the authorities their yes or no question. But this creates another problem. That way the authorities would know about your age verifications. This is not needed. It also creates incentives for unethical authorities, to set up rules for age requirements and other requirements, to increase monitoring of citizens, while on paper not being a surveillance state.

Det kan være du tænker at du kan klare det ved at bemyndige dem til at stille autoriteterne deres ja-nej-spørgsmål. Men det skaber et andet problem. På den måde ville autoriteterne kende til dine aldersverifikationer. Det er unødvendigt. Det skaber osse incitamenter for uetiske autoriteter, til at opsætte regler om alderskrav og andre krav, for at øge overvågningen af borgerne, mens der på papiret ikke er nogen overvågningsstat.

But there is a technical solution, that allows you to verify your age, revealing only that one bit of information that the other part needs to know, in a way where no other parties will know about the verification. The solution is to use a so-called Zero Knowledge Proof (ZKP).

Men der er en teknisk løsning, som gør at man kan verificere sin alder, og kun afgive den ene bit information som den anden part behøver, på en måde hvor ingen andre parter vil kende til verifikationen. Løsningen er at bruge et såkaldt zero knowledge bevis (ZKP på engelsk).

Such a gizmo normally works by starting up some heavy machinery - like constructing a circuit, turning it into polynomials, and so on. But in this case that is not necessary, because there is a simple and elegant solution. It uses hash-chains.

Sådan et virker normalt ved at starte noget tungt maskineri op - såsom at konstruere et kredsløb, lave det om til polynomier, og så videre. Men i dette tilfælde er det ikke nødvendigt, for der er en simpel og elegant løsning. Den bruger hash-kæder.

The solution uses only a few basic cryptographic building blocks.

Løsningen bruger kun nogle få basale kryptografiske byggesten.

Thats all! I told you its going to be simple...

Det er alt! Jeg sagde jo det vil blive simpelt...

Alice and Bob example

Alice og Bob eksempel

Let me start with a contrived example. There are three players:

Lad mig starte med et opdigtet eksempel. Der er tre spillere:

A: The age authority Alice. She is the mother of Bob.
B: The boy Bob. He is 7 years old.
C: The Cycling Center at the holiday resort where Bob and his family are staying. They lend out bicycles, tricycles and electrical bikes.

A: Aldersautoriteten Alice. Hun er Bobs mor.
B: Drengen Bob. Han er 7 år gammel.
C: Cykeludlånet ved det feriecenter hvor Bob og hans familie er. De udlåner tohjulede cykler, tricykler og el-cykler.

To lend a bicycle it requires you to be at least 5 years old. Otherwise you get a tricycle.

For at låne en tohjulet cykel skal man være mindst 5 år gammel. Ellers får man en tricykel.

So how can Bob prove he is at least 5, without revealing his actual age of 7, and without bothering Alice about it?

Så hvordan kan Bob bevise han er mindst 5, uden at røbe sin faktiske alder på 7, og uden at Alice skal bøvle med det?

Alice selects a random number r, and then uses the public known hash function H, to iterate it 7 times on r. This gives her the commitment: c = H⁷r

Alice vælger et tilfældigt tal r, og bruger så den offentligt kendte hash funktion H, til at iterere 7 gange på r. Det giver hende denne commitment: c = H⁷r

Alice gives (r,c) to Bob.

Alice giver (r,c) til Bob.

If he likes to, Bob can check H⁷r ≟ c to be sure it is okay.

Hvis han ønsker det, kan Bob tjekke H⁷r ≟ c for at være sikker på det er i orden.

Bob then calculates the proof: p = H²r

Bob udregner så beviset: p = H²r

Bob uses 7 - 5 = 2 iterations, because this leaves the minimum chain that the Cycling Center needs to know.

Bob bruger 7 - 5 = 2 iterationer, fordi det levner den mindste kæde som Cykeludlånet har brug for at kende.

He then gives the center (p,c).

Han giver så udlånet (p,c).

The Cycling Center checks if H⁵p ≟ c

Cykeludlånet tjekker om H⁵p ≟ c

Note that because the hash function is one-way, the center cannot guess what came before p, not to mention what r is. They learn nothing else about Bobs age, than it is 5 or more. They also dont need to get hold of Alice and ask her if Bob is old enough.

Læg mærke til at da hash funktionen er en-vejs, kan udlånet ikke gætte hvad der kom før p, for slet ikke at tale om hvad r er. De finder ikke ud af andet om Bobs alder, end at den er 5 eller mere. De har heller ikke brug for at få fat i Alice for at spørge hende om Bob er gammel nok.

The center is satisfied with the proof, so they lend Bob a stylish blue bicycle with an electric two-tone horn.

Udlånet godtager beviset, så de låner Bob en flot blå cykel med et elektrisk to-tonet horn.

That is it! Very elegant, right?

Det var det hele! Meget elegant, ikke sandt?

But we need a couple of modifications before we are there.

Men vi har brug for et par ændringer før vi er helt i mål.

Bob could fake it

Bob kunne forfalske

Bob is fervently longing for one of the electrical bikes. But the required age is 15 years.

Bob ønsker sig inderligt en af el-cyklerne. Men alderskravet er 15 år.

He cannot make proofs for more than 7 years with the r and c he has from Alice. Unless he cheats.

Han kan ikke lave beviser for mere end 7 år med det r og c han har fra Alice. Medmindre han snyder.

Bob could iterate H some more times on the c he got, and then give this fake commitment to the center. He even could do the whole process with selecting an r and calculating c himself, just with 15 iterations of H.

Bob kunne iterere H nogle flere gange på det c han har, og så give denne forfalskede commitment til udlånet. Han kunne endda køre gennem hele processen ved selv at vælge et r og udregne c, bare med 15 iterationer af H.

One way to avoid that, is that the center starts requiring that commitments have a valid signature by authorities they trust. So Alice should sign the commitment before she gives it to Bob.

En måde at undgå det på, er at udlånet begynder at kræve at commitments er skrevet under af autoriteter som de stoler på. Så Alice skal skrive commitmenten under inden hun giver den til Bob.

Diana could abet

Diana kunne medvirke

Bobs older sister, Diana, is 15 years old. She also received a commitment from Alice.

Bobs storesøster, Diana, er 15 år gammel. Hun fik osse en commitment af Alice.

Diana is not that interested in the Cycling Center, so she could give her r and her c to Bob.

Diana er ikke så interesseret i Cykeludlånet, så hun kunne give sit r og sit c til Bob.

One way the center could avoid that, is to require, that commitments contain an image of the owners signature, and combine that with a process where you have to sign your proof when you give it to the center.

En måde udlånet kunne undgå det på, er at kræve, at commitments indeholder et billede af ejerens underskrift, og kombinere det med en procedure hvor man skal underskrive sit bevis når man afleverer det til udlånet.

When Alice made the commitments to Bob and Diana, she should have put images of their signatures in each of them respectively. If Bob tried to use Dianas commitment, the center would see that his signature didnt match.

Da Alice lavede commitments til Bob og Diana, skulle hun have lagt billeder af deres underskrifter i hver af dem respektivt. Hvis Bob forsøgte at bruge Dianas commitment, kunne udlånet se at underskriften ikke passede.

Fitting the parts together

Det hele samlet

The protocol in real world terms, looks like this overall:

Protokollen overført til den virkelige verden, ser samlet set sådan ud:

The number r should be selected randomly from the image of H. It will therefore, in other words, look like the output from H.

Tallet r skal vælges tilfældigt fra billedmængen af H. Det vil derfor, med andre ord, se ud som outputtet fra H.

When B sends the proof to C, he also proves that he has the privB key.

Når B sender beviset til C, beviser han samtidig at han har privB nøglen.

The protocol can be different from the one shown here, but the core of it, with a hash-chain that is being shortened, is the same in all versions.

Protokollen kan se anderledes ud end den som er vist her, men kernen af den, med en hash-kæde som bliver forkortet, er den samme i alle udgaver.

The earlist version I have found was published back in 1995 by Pedersen in "Electronic Payments of Small Amounts". But because it is so simple, it is not unlikely that there are earlier versions.

Den tidligste udgave jeg har kunnet finde blev publiceret tilbage i 1995 af Pedersen i "Electronic Payments of Small Amounts". Men da den er så simpel, er det ikke usandsynligt at der findes tidligere udgaver.

The technical term for the protocol is range proof.

Den tekniske betegnelse for protokollen er range bevis (range proof på engelsk).

Issues

Problemer

The first issue is that you can only prove that k is greater than or equal to some threshold. It could be nice if you were able to prove less than or equal relations as well. If you have a hard upper bound, this is possible. But you often times dont, and then only greater than or equal proofs are possible.

Det første problem er at man kun kan bevise at k er større end eller lig med en tærskelværdi. Det ville være rart hvis man osse kunne bevise mindre end eller lig med relationer. Hvis man har en hård øvre grænse, er det muligt. Men det har man sjældent, og så er større end eller lig med beviser det eneste der kan lade sig gøre.

The second issue is scalability. Issuing and checking takes time linear in the value of k or the threshold. This is prohibitively expensive for many applications. Like proofs around the balance of a bank account. You could of course count thousands, and then it might become practicable. But there is a limit to the granularity you can reasonably get with this protocol.

Det andet problem er skalérbarhed. Det tager tid lineært i k eller tærskelværdien, at udstede og at tjekke. Det er for meget i mange tilfælde. Såsom beviser for indeståendet på en bankkonto. Man kunne selvfølgelig tælle i tusinder, og så kan det alligevel være det går an. Men der er en grænse for granulariteten som man i praksis kan opnå med denne protokol.

Variations

Variationer

There are digital signature schemes that only relies on hash functions. So it should be possible to make the protocol in a way that doesnt make use of public key cryptography.

Der findes digitale signatur metoder som kun bruger hash funktioner. Så det skulle være muligt at lave protokollen på en måde der ikke bruger public key kryptografi.

For some use cases, the granularity you need, is different in the low and the high end. There are many ways to accomodate this. One is to use logarithms.

I nogle brugsscenarier, vil den granularitet man har brug for, være forskellig i den lave og den høje ende. Der er mange måder at imødekomme det på. En er at bruge logaritmer.

Some people have worked on combining multiple hash-chains having different step sizes. This fixes the problem with scalability. But at the same time it compromises the privacy, as some information about k is given off.

Nogle har arbejdet på at kombinere flere hash-kæder med forskellige skridtstørrelser. Det løser skaleringsproblemet. Men det går samtidig ud over privacy, da noget information om k bliver afgivet.

The future

Fremtiden

Hash-chains and protocols, like the one described here, are part of the large SSI agglomeration of technologies, that is being built these years. There is a lot of active research in this area, so we could be lucky that someone comes up with an improved version. But the protocol as it is, is still perfectly usable in a number of use cases - and it is delightfully simple.

Hash-kæder og protokoller, i stil med den beskrevet her, er en del af den store gruppe af SSI teknologier, som bliver opbygget i disse år. Der forskes ret aktivt indenfor feltet, så vi kunne være heldige at en eller anden finder en forbedret udgave. Men protokollen som den er, er helt fin i en række brugsscenarier - og den er dejligt simpel.