📚

Preliminaries

In this page we give preliminary information including definitions of the notions that are mostly used in the papers through our database.

Zero-knowledge

Zero-knowledge proof is a protocol in which a party (the prover) proves a statement to another party (the verifier) without revealing anything about what makes the statement true.

Properties of zero-knowledge proofs

Zero-knowledge proofs must have the following properties.

zk-SNARKs

zk-SNARK stands for,

They are efficient instantiations of NIZKs, which have a wide application spectrum from verifiable computations to the privacy-preserving transfer of funds.

Given a field F\mathbb{F}, and an F\mathbb{F}-arithmetic circuit C:Fn×Fh→FlC : \mathbb{F}^n × \mathbb{F}^h \rightarrow \mathbb{F}^l we denote a corresponding language by associated binary relation by RC={(x,a)∈Fn×Fh→Fl:C(x,a)=0l}\mathcal{R}_C = \{(x, a) \in \mathbb{F}^n × \mathbb{F}^h \rightarrow \mathbb{F}^l : C(x, a) = 0^l \} and a language LC={x∈Fn:∃a∈Fh,C(x,a)=0l}\mathcal{L}_C = \{x \in \mathbb{F}^n : \exists a \in \mathbb{F}^h , C(x, a) = 0^l \} .

A zk-SNARK for F\mathbb{F} is a triple of Probabilistic Polynomial Time (PPT) algorithms (Setup,Prove,Verify)(Setup, Prove, Verify) as follows:

  • Setup(1λ,R)→crsR(1^λ , R) \rightarrow crs_R : On input security parameter λ\lambda and a relation RR, outputs a Common Reference String crsRcrs_R .
  • Prove(crsR,x,w)→π(crs_R , x, w) \rightarrow \pi : On input crsRcrs_R  and a statement-witness pair (x,w)∈RC(x, w) \in \mathcal{R}_C, outputs a proof Ï€\pi for the statement x∈LCx \in \mathcal{L}_C.
  • Verify(crsR,x,Ï€)→{0,1}(crs_R , x, \pi) → \{0, 1\} : On input crsRcrs_R , statement xx and proof Ï€\pi, outputs a bit to indicate if the proof is valid or not.

Signature scheme

Signature schemes are cryptographic protocols that are used to verify the authenticity of a message. Signature schemes use public-key cryptography, i.e. signers have private and public key pairs which are used for signature generation and verification, respectively.

Signature schemes are one of the main parts of verifiable credentials in the W3C’s definition. A verifiable credential may be seen as the signature of an issuer on a set of holder-specific data (id, attributes, etc.).

Below we give a formal definition of a signature scheme.

Definition (Signature scheme)

A signature scheme is a protocol specified by four algorithms PG, KG, Sig, Ver\textsf{PG, KG, Sig, Ver} which can be defined as follows:

Properties of signature schemes

The security of a signature scheme is mainly contained in the unforgeability property which means that for any PPT adversary, it is unfeasible to generate a valid signature on any previously unsigned message, with a non-negligible probability of acceptance. The unforgeability property of a signature scheme depends on the underlying security assumption, for example, the Discrete Logarithm assumption, the Decisional Diffie-Hellman assumption, the RSA assumption, etc.

There exist many types of signature schemes, such as multi-signatures, threshold signatures, ring signatures, group signatures, blind signatures, etc., according to the functionalities that are needed.

Different types of signature schemes may have different properties. For example, consider an anonymous credential scheme. For issuing an anonymous credential, an issuer shouldn’t learn the attributes of the user. Therefore he uses a blind signature scheme in which the signer signs a commitment to the user’s private data. As required in this example a blind signature scheme should have two properties. The first one is blindness which means a signer shouldn’t learn any information about the message he signs. The second one is one-more-unforgeability: a special form of unforgeability in which any user engaging with a signer ℓ\ell times shouldn't be able to generate more than ℓ\ell signatures on previously unsigned messages.

Cryptographic accumulators

A cryptographic accumulator is a short binding commitment to a set of values. The cryptographic accumulators can be categorized into two classes, i.e. symmetric and asymmetric accumulators.

Security properties

Optional properties

Optional properties that a cryptographic accumulator may have can be found in the below table.

Source: https://arxiv.org/pdf/2103.04330.pdf

The first set of properties depends on the set size. An accumulator can be additive, subtractive, static, or dynamic according to addition or deletion support it has.

The second set depends on the membership proof. An accumulator can be positive, negative or universal according to the proof type it supports, i.e. membership, non-membership, or both. Note that all these three types can be achieved in zero-knowledge fashion.

The third set depends on the accumulator manager. An accumulator can be trusted or not trusted (or strong) according to the the need for a trusted or not trusted manager.

Finally the fourth set depends on the communication type. An accumulator can be synchronous or asynchronous according to the synchrony assumption it has.

Commitment schemes

A commitment scheme is a cryptographic building block widely used in cryptographic protocols. It enables a user (in a protocol) to choose a value and commit to it in a way that it can no longer be altered. The user doesn’t have to reveal the value that he committed to. However, he can choose to do so if needed.

Definition (Commitment scheme)

A commitment scheme is specified by three algorithms, i.e. KeyGen\textsf{KeyGen}, Com\textsf{Com}, and Ver\textsf{Ver} which can be defined as follows:

Properties of commitment schemes

The security of a commitment scheme is defined over two main properties, i.e. hiding and binding properties.

Hiding property means that after a prover commits to a value, a verifier cannot learn anything about the value unless the prover reveals it.

Binding property means that after a prover commits to a value, he cannot change the value included in the commitment. In other words, when a prover reveals the value by opening a commitment, the verifier knows that the revealed information is the value that was committed to originally.

These properties are usually achieved by using the underlying assumptions such as the RSA assumption, the CDH assumption, etc.

Threshold Public-Key Encryption (TPKE)

Threshold Public-Key Encryption (TPKE) is an extension of public-key encryption where a single party holds the secret decryption key. In TPKE, a number of parties hold partial secret decryption keys (usually generated by distributed key generation protocols), and a sufficient number (threshold) of users can jointly decrypt a ciphertext.

A TPKE scheme can be defined by four algorithms, i.e. TKeyGen, Enc, TDec\textsf{TKeyGen, Enc, TDec} and Combine\textsf{Combine} that can be defined as follows:

Bilinear Pairings

Let G1G_1, G2G_2, and GtG_t be cyclic groups of the same order pp. A bilinear pairing e:G1×G2→Gt\textsf{e}:G_1 \times G_2 \rightarrow G_t is a function that maps a pair of elements from groups G1G_1 and G2G_2 to another group, and satisfies the following properties:

Types of pairings

There exist three basic types of bilinear pairings [12]

  1. Type-1: G1=G2G_1 = G_2
  1. Type-2: G1≠G2G_1 \neq G_2 but there exists an efficient homomorphism ϕ:G2→G1\phi : G_2 \rightarrow G_1 , while no efficient one exists in the other direction.
  1. Type-3: G1≠G2G_1 \neq G_2 and no efficiently computable homomorphism exists between G1G_1 and G2G_2, in either direction.

Type-1 pairings (also called symmetric pairings) are insecure since DDH is easy in G1G_1. Type-2 pairings have intermediate efficiency due to the homomorphism from G2G_2 to G1G_1. Type-3 pairings are more efficient than other types. They support the XDH assumption which implies the difficulty of the Computational co-Diffie-Hellman (co-CDH) problem in G1G_1 and G2G_2, and the difficulty of the Decisional Diffie-Hellman (DDH) problem in G1G_1.

Cryptographic Hash Function

A cryptographic hash function maps input strings of an arbitrary length to output strings of fixed length. The hash function is a many-to-one function as the number of inputs is larger than the outputs.

A cryptographic hash function H\textsf{H} has the following properties:

Decentralized Identity

Definitions related to Decentralized Identity can be found in Decentralized identity, the ultimate guide.

Verifiable credentials

A Verifiable Credential (VC) is a credential with cryptographic proof that an issuer indeed issued the credential for a user and agrees with the user’s claims included in it. Definitions related to Verifiable Credentials can be found in W3C’s Verifiable Credentials Data Model v1.1.

Sybil resistance

A Sybil attack is a kind of attack against a network in which the attacker gains disproportionately large influence on the network by creating multiple identities and submitting them to the system. For example, consider a threshold signature scheme used in a distributed network. If the number of identities that the attacker holds is more than the threshold, then it can produce valid signatures on any message on behalf of the entire network.

It is crucial for a distributed system to have a sufficient level of Sybil resistance. For example, a Sybil resistance mechanism could rely on

References

  1. Decentralized Anonymous Credentials, https://eprint.iacr.org/2013/622.pdf.
  1. ZEBRA: Anonymous Credentials with Practical On-chain Verification and Applications to KYC in DeFi, https://eprint.iacr.org/2022/1286.
  1. Efficient Sparse Merkle Trees Caching Strategies and Secure (Non-)Membership Proofs, https://eprint.iacr.org/2016/683.
  1. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design, https://ieeexplore.ieee.org/document/4568209.
  1. An Efficient Threshold Public Key Cryptosystem Secure Against Adaptive Chosen Ciphertext Attack, https://link.springer.com/content/pdf/10.1007/3-540-48910-X_7.pdf
  1. Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme, https://link.springer.com/content/pdf/10.1007/3-540-36288-6_3.pdf
  1. Security of Blind Signatures Revisited, https://link.springer.com/content/pdf/10.1007/s00145-015-9225-1.pdf.
  1. Commitment Schemes and Zero-Knowledge Protocols, https://www.researchgate.net/publication/221621428_Commitment_Schemes_and_Zero-Knowledge_Protocols
  1. Verifiable Credentials Data Model v1.1, https://www.w3.org/TR/vc-data-model/
  1. Decentralized Identifiers (DIDs) v1.0, https://www.w3.org/TR/did-core/
  1. https://en.wikipedia.org/wiki/Sybil_attack.
  1. Pairings for Cryptographers, https://eprint.iacr.org/2006/165.
  1. An Introduction to Pairing-Based Cryptography, https://www.math.uwaterloo.ca/~ajmeneze/publications/pairings.pdf.
  1. Discrete Logarithm Problem, https://en.wikipedia.org/wiki/Discrete_logarithm
  1. Decisional Diffie-Hellman Assumption, https://en.wikipedia.org/wiki/Decisional_Diffie–Hellman_assumption
  1. RSA Problem, https://en.wikipedia.org/wiki/RSA_problem
  1. Efficient Revocation of Anonymous Group Membership Certificates and Anonymous Credentials, https://eprint.iacr.org/2001/113.pdf.
  1. Universal Accumulators with Efficient Nonmembership Proofs, https://www.cs.purdue.edu/homes/ninghui/papers/accumulator_acns07.pdf
  1. An Overview of Cryptographic Accumulators, https://arxiv.org/pdf/2103.04330.pdf
  1. Bloom, B. H. (1970a). Space/time trade-offs in hash coding with allowable errors. Comm. of the ACM, 13(7):422–426. https://dl.acm.org/doi/10.1145/362686.362692
  1. Baldimtsi, F., Camenisch, J., Dubovitskaya, M., Lysyanskaya, A., Reyzin, L., Samelin, K., and Yakoubov, S. (2017). Accumulators with applications to anonymity-preserving revocation. In 2017 IEEE European Symp. on Security & Privacy (EuroS&P), pages 301–315. IEEE, https://www.researchgate.net/publication/318125384_Accumulators_with_Applications_to_Anonymity-Preserving_Revocation
  1. XDH assumption, https://en.wikipedia.org/wiki/XDH_assumption
  1. Computational Diffie–Hellman assumption, https://en.wikipedia.org/wiki/Computational_Diffie–Hellman_assumption