Self Sovereign Identity
cryptography level: intermediate
Nowadays we stand on the edge of the digital revolution. Blockchain gives a new life for a P2P technology. There is nothing new here, just an excellent mixing of the existing robust technics, such as P2P, key-value storage, cryptography and others. Blockchain opens doors for completely new markets as well as transforms the well-established ones.
Self Sovereign Identity is the next area to be changed. The identity idea, problem and solution are very well covered by Sovrin in their WP. In my posts I’m going to take you through the generalized mathematical schemes under the hood. Actually scientists have done a kind of cryptography researches and I’m going to summarize their works to demonstrate how it efficiently uses in the modern digital world.
Innovative Identity systems should satisfy 3 basic criteria: DPKI, Anonymous Credentials and Credentials Revocation.
The effectiveness and efficiency of any commercial interaction depends strongly on the level of trust that exists between the involved parties. Trust determines if parties are willing to depend on each other, even if negative consequences are possible, and without it, commercial transactions will be inefficient because of doubts about payments, ability to deliver a service, etc.
The goal of DPKI is to ensure that no single third-party can compromise the integrity and security of the system as a whole. Trust is decentralized through the use of technologies that make it possible for geographically and politically disparate entities to reach consensus on the state of a shared database. DPKI focuses primarily on decentralized key-value datastores, called blockchains, but it is perfectly capable of supporting other technologies that provide similar or superior security properties.
I would recommend you to start reading about DPKI from here. There you can find the methods engaged to address PKI problems. Web-Of-Trust propagated great specification as Blockchain scales and evolves DPKI ideas.
Authentication of users is vital to most of the electronic systems we use today. It is usually achieved by giving the user a token, or credential, that the user must present to prove that she has permission to access a service. An important challenge that such systems face is how to revoke a user’s privileges in case she/he misbehaves or their credential gets compromised.
The revocation methods are important for any identity system. The platform has to ensure that user or authority may be revoked at any time. If it happened, other participants should be notified immediately and revoked subject’s attributes will not be acceptable anymore.
Anonymous Credential systems allow users to selectively prove statements about their identity attributes while keeping the corresponding data hidden.
Anonymous credentials is a technique that guarantees that user’s private information is never revealed. The user proofs that specific attributes fulfills Verifier’s requirements (age > X, nationality, etc) without revealing any additional information about their identity. Next generation identity systems should satisfy the follow criteria: the user has to be anonymous when obtaining credentials, the user has to be protected from identity theft and the user’s secret key SK should never be leaked to any other party.
Traditionally, such systems are based on digital signature. Digital signature schemes are a fundamental cryptographic application. They give the electronic equivalent of the paper-based idea of having a document signed. A digital signature scheme consists of (1) a key generation algorithm that generates a public key PK and a secret key SK; (2) a signing algorithm that takes as inputs a message m and a secret key SK and generates a signature σ; and (3) a verification algorithm that tests whether some string σ is a signature on message m under the public key PK. Signature scheme exists if and only if one-way functions exist.
To satisfy criteria above, the protocol should operate on a committed message and the user should obtain signature on it.
Camenisch & Lysyanskaya Digital Signature
Traditionally the digital signature operates on a fix length hash of the incoming message, thus we can get hash of messages and calculate the final result. One of its most interesting features is probably the ability of CL-signature to be randomized: given a valid CL-signature σ = (a, b, c) on a message m, anyone can generate another valid signature on the same message by selecting a random scalar t and computing:
σ’ =(pow(a, t), pow(b, t), pow(c,t)).
Camenisch & Lysyanskaya Digital Signature allows to prove knowledge of a signature and to obtain signature on a secret message based on proofs of knowledge. Thus, when a user wants to convince a verifier that she/he has obtained a credential from an issuer and selectively reveal some of the messages of the credential, she/he employs a zero-knowledge proof stating that she/he “knows” a signature by the issuing organization and messages that the signature is valid.
Another efficiency of CL-signatures is that it can be used to sign r-message vectors (m-1, …, m-r) at once. The subject’s attributes (age, social number, etc.) can be represented as a single vector to sign.
CL-signature has the same simple three steps — Generation, Sign, and Verify — with one minor change, they need to know the number of messages that will be handled.
> Key generation (group details are consciously omitted).
CL has RSA nature and uses Key based on safe prime numbers p and q. Camenisch & Lysyanskaya signature encrypts arbitrary number of attributes and provides efficient scheme to verify them partly.
For user who encrypts L attributes, the signature looks as follow:
IN — RSA Module: n, n=pq
IN — Randoms: Z, S, R0, …, R(L-1)
OUT — Public key: (n, R0, …, R(L-1), Z, S)
OUT — Secret Key: (p)
To compare with RSA signature there are multiple values encrypted here. The signature use special random S to blind the data for signature issuer.
IN — User’s L attributes: (m1, …, mL)
OUT — Random Prime: e
OUT — Random number: v
The signature consists of (e, A, v). However, if A public it destroys privacy doing linkable transactions. To prevent security leak, the derived signature (e, A’, v’) can be generated for each transaction accordingly to randomizable properties .
IN — User’s L attributes: (m1, …, mL)
IN — Public Key: (n, R0, …, R(L-1), S, Z)
IN — Signature: (e, A, v)
Obviously to verify the signature the Verifier should obtain the user’s attributes. To hide real attribute and implement full model, 2 more steps should be introduced: committed scheme & ZKP.
Committed scheme is a basic cryptography method to hide information until sometime in the future. Details can be found here.
> Pedersen commitment
Commitment is just a special message from the sender to the receiver. De-commitment is a group of values to verify validity of commitment. Let’s take a look an exampe:
IN — Message: m
IN — RSA module: n, n=pq
IN — Random number: g, h
IN — Random number: r
OUT — Public Key: (n, g, h)
OUT — Commitment: com = (g^m) * (h^r)
OUT — De-commitment: (m, r)
To check the committed value the Verifier calculates:
> Zero-knowledger proof
The idea of ZKP is that the Prover convinces the Verifier about the secret without revealing it. Protocol consists of an interaction session with the follow properties:
the verifier learns nothing about the prover's secret
- proof of knowledge (soundness)
the prover can persuade the verifier only if she/he knows the secret
if the prover knows the secret she/he can always convince the verifier
One of the simplest tp demonstrate is the proof of knowledge of a discrete logarithm. In order to prove knowledge of:
the prover interacts with the verifier as follows:
- The Prover commits himself to randomness r: com=g^r.
- The Verifier replies with a challenge c chosen at random: c
- The Prover sends the third and last message (the response): s = r+cx
- The Verifier accepts, if g^s =com * (y^c), where y = g^x
> Putting Things Together
To address criteria for anonymous credetential the cryptgraphic techniques should be mixed together.
There are 3 entities: Verifier, Signer, Prover.
- The Issuer signs the Prover’s attributes with Camenisch & Lysyanskay signature: (e, A, v).
- The Verifier asks if the Prover meets specific request: “age above then X years” or nationality “either US or FR or ..” etc.
- The Prover derives signature, generated ZKP of having signature over attributes from particular issuer and ZKP to reply on the incoming request.
Anonymous credentials provides :
- Knowledge of the signature over the set of attributes
- Knowledge of attributes without revealing their respective values
- An attribute’s value lies within a numeric range
- An attribute’s value is not equal to another value
- An attribute’s value is or is not a member of a set
Have fun and enjoy cryptography.
- J. Camenisch and A. Lysyanskaya, “A signature scheme with efficient protocols,” in SCN, ser. Lecture Notes in Computer Science, vol. 2576. Springer, 2002, pp. 268–289.
- Camenisch, J. and Groß, T., 2008, October. Efficient attributes for anonymous credentials. In Proceedings of the 15th ACM conference on Computer and communications security (pp. 345–356). ACM.
- “Specification of the identity mixer cryptographic library version 2.3.0,” 2009, http://domino.research.ibm.com/library/cyberdig.nsf/ papers/EEB54FF3B91C1D648525759B004FBBB1/$File/rz3730 revised.pdf.
- D. Khovratovich, “Anonymous credential,” 2016, https://github.com/hyperledger/indy-anoncreds/blob/master/docs/anoncred-usecase0.pdf.
- D. Khovratovich and J. Law, “Sovrin: digital identities in the blockchain era,” https://sovrin.org/wp-content/uploads/AnonCred-RWC.pdf.
- F. Boudot. Efficient proofs that a committed number lies in an interval. In B. Pre- neel, editor, Advances in Cryptology — EUROCRYPT 2000, volume 1807 of Lec- ture Notes in Computer Science, pages 431–444. Springer Verlag, 2000.
- Camenisch J, Lysyanskaya A. Signature schemes and anonymous credentials from bilinear maps. InAnnual International Cryptology Conference 2004 Aug 15 (pp. 56–72). Springer, Berlin, Heidelberg.