Sistemas de credenciales anónimos

Gestión de identidad mediante pruebas de conocimiento cero y su rendimiento en sistemas embebidos

Juan Marín Noguera
Junio de 2023

Tutor: Jorge Bernal Bernabé
Codirector: Jesús García Rodríguez

Problems of traditional authentication

OAuth

OLYMPUS

request policypolicytokenpolicytokenrequestcred.

OLYMPUS for IoT

  • A pub that wants to restrict access to minors.
  • A hotel that wants to grant access to common infrastructure to clients only.
  • Anonymous voting by means of pseudonyms.*

...without having to identify users.

* Vote counting would need to be checked by other means.

What are zero knowledge proofs?

  • PPT interactive system: pair of communicating Turing machines equipped with random number generators that run in polynomial time.
    • These are prover and verifier.
  • Polynomial property: relation $\rho$ where checking if a pair $(I,S)$ belongs is in $\mathcal{P}$ w. r. t. $I$.
    • $I$ is the witness, known by the prover.
    • $S$ is the instance, known by both.

What are zero knowledge proofs?

PPT interactive systems satisfying:

  • Completeness. If both parties are honest, the verifier almost surely accepts.
  • Soundness. A cheating prover almost surely can't convince the verifier that it knows a witness.
  • Zero knowledge. Every verifier admits a PPT that takes an instance and produces a transcript $\mathcal{P}$-indistinguishable from one of an actual interaction with the prover.

Sigma protocols

commitmentchallengeresponseChoose randomr in Gt <- f(r)Choose randominteger ccs <- r + cI¿f(s) = t + cS?
  • We can make the protocol non-interactive by setting $c$ to a hash of the relevant parameters, including $t$.
  • The prover just sends $(t,s)$ or $(c,s)$, the Schnorr signature.

Extended PS-MS Schnorr signatures

  • Credential: $$\footnotesize \begin{matrix} (\text{id}, &\text{birth}, &\text{area}, &\dots)\\ (\text{12345678F}, &\text{1972-05-01}, &\text{Madrid}, &\dots) \end{matrix} $$
  • Attributes partitioned into Revealed, Hidden, and with extra Proofs.
  • Pedersen commitments: $(v,o)\rightsquigarrow X^vY^o$.
    • $(v,o,data)\rightsquigarrow(X^vY^o,f(v,data))$.

Inspection

$$(id,r)\rightsquigarrow(g^r,g^{id}h^r)$$
  • Allow a trusted inspector to deanonymize the user.
    • e.g. a judge, to investigate cases of hate speech.
  • Elgamal encryption.
    • $g$ is the group generator.
    • $h$ is $g^z$, for some random $z$ only known to the judge.

Pseudonym

$$id\rightsquigarrow\text{scope}^{id}$$
  • Identify the user for a given scope.
  • Unlinkable to other scopes.
  • Scope values should be chosen transparently.

Revocation

$$\footnotesize (rh,r,revtok)\rightsquigarrow\\ (X_*^{rh}Y_*^r,\text{NIZK.Prove}[revtok,revk,((r,\emptyset),\mathtt{REVEAL})]) $$
  • Prove that the credential has not been revoked.
    • Option 1. Have an epoch attribute in the credential and issue a new credential every time the epoch changes.
    • Option 2. Have a revocation authority that signs and publishes pairs $(rh,epoch)$ with a revocation handle and an epoch, have a revocation handle in the credential and link both.

Architecture

MIRACL Core
pfecCwrapper
dp-ABC implementation

Workflow

The code


	      struct dpabcProofVtbl {
	           const struct dpabcSerialVtbl *pre;
	           const struct dpabcSerialVtbl *img;
	           const struct dpabcSerialVtbl *param;
	      
	           void *(*morph)(const Zp *val, const void *data, const void *param);
	           void (*maddpre)(void *dest, const Zp *factor, const void *addend);
	           void (*maddimg)(void *dest, const Zp *factor, const void *addend);
	           bool (*eqimg)(const void *im1, const void *im2);
	           void *(*cloneimg)(const void *img);
	           int (*fromitem)(
	                const void *itdata, void **pre, void **randpre, void **param);
	           void (*freeitem)(void *itdata);
	           bool (*checkparm)(
	                const void *itdata, const void *param, const void *inst);
	           bool (*checkval)(const void *itdata, const Zp *val);
	      };
	    

	      struct dpabcSerialVtbl {
	           void (*write)(char *out, const void *obj);
	           void *(*read)(const char *in);
	           size_t (*size)(void);
	           void (*free)(void *obj);
	      };
	    

	      int sscanrec(const char *bytes, const char *fmt, ...);
	      int sprintrec(char *out, const char *fmt, ...);
	      int ssizrec(const char *fmt, ...);

	      // Later
	      sprintrec(res, "c1zz****",
	           p->type, p->commped, p->respval, p->resprand,
	           tbl->img, p->inst, tbl->img, p->comm,
	           tbl->pre, p->resp, tbl->param, p->param);
	    

Test devices

Raspberry Pi 4 model B. 1.8 GHz Cortex-A72 CPU, ARMv8 ISA (64 bits), 1 GB RAM.
Raspberry Pi 2 model B. 900 MHz Cortex-A7 CPU, ARM v7 ISA (32 bits), 1 GB RAM.
ESP32-C3. 160 MHz scalar CPU, RISC-V RV32IMC ISA (32 bits), 400 kB SRAM.

Performance

Raspberry Pi 4

Performance

Raspberry Pi 2

Performance

ESP32-C3

Inspection proofs

Pseudonym proofs

Revocation proofs

Conclusions

  • Review of cryptographic techniques.
  • Design and implementation of an extensible ZK-proof library.
  • Benchmarking of ZK proofs in embedded systems.
  • Still a long way to go.
    • Range proofs.
    • Multiattribute proofs.
    • Semantics of tuples.

Questions?