Cryptic 1.1.1 Copyright (c) 2009-2011 Entr'ouvert Copyright (c) 2009 Ates Mikael All rights reserved. INTRODUCTION ------------ Cryptic - Cryptographic tools and protocols Cryptic is a free software library released under the GNU GPL v2 and above license. Cryptic allows the implementation of digital certificates with advanced properties. The goal is to ensure privacy for cross-organization exchanges of certified data. Cryptic is written in C language and depends on glib and openssl. Bindings for the Python and Java languages are provided. REPOSITORY ---------- * git@repos.entrouvert.org:cryptic.git LISTS ----- * Development: cryptic-devel@listes.entrouvert.com (archive) * Git commits: cryptic-commits@listes.entrouvert.com (archive) DESCRIPTION ----------- Advanced certificates helps in reducing the certified information disclosed to verifiers. The certificates have the following properties: * Selective disclosure of content. * Proofs on attributes contained in certificates. * Unlinkability between certificate issuing and showing transactions. The Cryptic library can be used to create at a low-level certificates with the properties previously enumerated. The certificate formatting, in XML or ASN1 for instance, is not handled in Cryptic. The goal is a fine-grained information disclosure for off-line certificates. Such certificates may be used multiple times without re-issuing. When a certificate is issued on demand, it is trivial to make it includes only the needed information. However, when the certificate is already issued, it is useful to have means to select which signed information is revealed. For instance, the selective disclosure allows to reveal a date of birth and not a place of birth both contained in the same certificate. A range proof allows to only reveal that the certificate prover is of age and not reveal the date of birth contained in the certificate. A certificate is said 'proved' because a secret is included in the certificate. To only show a certificate require to prove to verifier that the secret is known without revealing it. (It is similar to prove the knowledge of a private key making a signature. In a way, the public key is proved as a certificate is proved.) Certificate holder is a term usually avoided because it may refer to bearer tokens. Holder may be used if it is taken as a synomous to know the secret of the certificate hold. Furthermore, the CL-Signature implementation allows the unlinkability of a certificate issued with this certificate shown to verifiers. In other words, the certificate signature can not be used as a factor of linkability between to transactions involving a same certificate. (But many other factors may be used (time correlation, attribute contents, etc.), unlinkability is a huge paradigm.) The unlinkability may be expected when a user shows multiple times a same certificate or between the issuing and showing transactions of this certificate. The unlinkability of the user transactions is a strong property of anonymity and ion some cases a privacy-preserving principle. For instance, Cryptic can be used to implement e-cash and e-voting architectures. The library does not deal with storage and protocols, only computation. OVERVIEW -------- The library includes: libcryptic.a: Group generation Prime order group Quadratic residues group Signature schemas Camenisch-Lysyanskaya Signature (CL-Signature) Proof of Knowledge Schnorr zero-knowledge proof of knowledge protocol. Range proofs on integers INSTALLATION ------------ Please check the Makefile before compiling. Then, autogen.sh make make check make install QUICK START ----------- See tests/tests.c, bindings/python/samples.py, bindings/java/Myclass.java BITS OF DOCUMENTATION --------------------- *** Error Codes *** Error codes are listed in error.h. - Functions return a negative error code on failure and 0 either - Except verification functions that return 1 on success and <= 0 on failure - Getters return NULL if no member Take care that functions cryptic_clsig_load_certificate* verify the signatures but return 0 on success including the checking of a valid signature. *** Generic helper functions *** Many helper functions are defined in utils.h *** Maths directory *** Class: CrypticPrimeOrderGroup Allows to create a prime order group. This kind of group can be used for zero knowledge proofs of knowledge. The group has prime modulus p. p is a safe prime. p = 2pp + 1 with pp also prime. The generator of the group is g. To create a prime order group with a modulus of size 512 bits: CrypticPrimeOrderGroup *g = NULL; g = cryptic_prime_order_group_new(512); The classe has a member that is a table of generators that may be used as bases for proofs. This table is filled with the function cryptic_prime_order_group_more_bases(). For instance, cryptic_prime_order_group_more_bases(g,10); Class: CrypticQRG Allows to create a quadratic residues group. Such a group is used by the Camenisch-Lysyanskaya signature. Two safe primes p and q. p = 2pp +1 and q = 2qq +1 n = pq The QRG is the multiplicative group Z_n^* The order is pp*qq A base (a quadratic residue) is picked from the group: From a random r of size n: qr = r^2 mod n and qr != 1 and coprime(qr-1,n) Other quadratic residues are generated from the first picked. With a random of size the group order: New_qr = qr^rand mod n Functions to pick qrs: int cryptic_qrg_pick_base(CrypticQRG *qrg, BIGNUM *out_base); int cryptic_qrg_pick_k_bases(CrypticQRG *qrg, BIGNUM **out_bases, int nb_bases); Class: CrypticDecomposeInteger Decompose an integer in four squares. Used in range proofs. CrypticDecomposeInteger* decomposition = NULL; decomposition = cryptic_decompose_integer_new(numToDecompose); cryptic_print_bn("first square: ", decomposition->a); cryptic_print_bn("second square: ", decomposition->b); cryptic_print_bn("thrid square: ", decomposition->c); cryptic_print_bn("forth square: ", decomposition->d); utils files Basic functions. Up to now, only random numbers are necessary. - The random value is returned in parameter and an error code is returned: int cryptic_find_random(BIGNUM *ret, int size); int cryptic_find_random_with_range_value(BIGNUM *ret, BIGNUM *value); - Without error code: BIGNUM* cryptic_ret_random(int size); BIGNUM* cryptic_ret_random_with_range_value(BIGNUM *value); *** Protocols directory *** ** Schnorr proof of knowledge (pok_schnorr directory) ** Class: CrypticZkpkSchnorr Used to lead Zero knowledge proof of knowledge with the Schnorr protocol. Let g be the generator of a group of prime order q. Assume that you know y=g^x and as a prover you want to prove that you know x to the verifier who knows y without revealing x and the verifier learns with a negligeable probability nothing about x. You pick a random and send the commitment: t = g^r The verifier challenges you with c you prove that you know x responding: s = r - cx The verifier check that t ?= y^c . g^s Explanation: s = r -cx <=> r = s + cx <=> g^r = g^s + g^cx <=> g^r = g^s + (g^x)^c You can prove like this any discrete logarithm representation (DLREP). A dlrep looks like dlrep = g1^q1 . ... . gi^qi Then you want to prove that you know {q1,...,qi} to a verifier who knows dlrep. {g1,...,gi} are prime ordre group bases shared between the prover and the verifier. Both the prover and the verifier init their proof the same way CrypticZkpkSchnorr* shn_prover = NULL; shn_prover = cryptic_zkpk_schnorr_new(bases, nb_quantities, modulus); The prover computes the commitment with cryptic_zkpk_schnorr_round1(shn_prover); and sends the commitment to the verifier shn_prover->commitment The prover receives the challenge and compute the responses, one per quantity to prove. cryptic_zkpk_schnorr_round2(shn_prover, order, challenge, quantities); and sends the responses to the verifier shn_prover->responses The verifier verifies the proof with cryptic_zkpk_schnorr_verify_interactive_proof(shn_verifier, dlrep, commitment, challenge, responses); The order to compute the responses in not mandatory. however if not used the random must be >> cx to keep the zero knowledge. This is useful because in some cases the verifier is not assumed to know the group order with cryptic_zkpk_schnorr_round2_without_order() You have noticed that the randoms used in the commitment are generated into the function. However, in some cases you need to combine proofs to prove statements on the same quantity in two different proofs. We you lead this kind of proofs you must use the same random number in the two proofs when you to prove that the quantity is the same. You deduce that the answer will be the same for the two proofs. The first round function can then be used with randoms given in parameters. You generate them by yourself and then give them in parameters arranged as you want. cryptic_zkpk_schnorr_round1_one_random_chosen(shn, random, position); cryptic_zkpk_schnorr_round1_randoms_chosen(shn, randoms); The proof previously presented is an interactive proof relying on a challenge freshly generated by the verifier after the commitment. Using the random oracle model played by a hash function, it is feasible to realise a non-interactive proof. The details on how to compute the hash are given later because the class CrypticHashForNiProofs is dedicated for this purpose. However th hash is tipically of the form of a concatenation modulus || bases || dlrep || Commitment and then hashed. Only the verifier function differs cryptic_zkpk_schnorr_verify_noninteractive_proof(shn, dlrep, hash, responses); From the prover point of view, the prover needs to generate the hash and give it as a parameter instead of the challenge to compute the responses. *** Utils directory *** print files Function used to print bignums and display CLSIG structure parameters AUTHOR ------ Mikaël Ates