Vectors, w.r.t. commitment schemes, are simply arrays or ordered multi-sets, (sets with possible repetition of elements), unlike the regular definition of elements of linear spaces. For example, $[2, 3, 1, 2, 5]$ will be a vector in this context (left to right order). Between sets and vectors, we could have also considered commitments to multi-sets without a specified order, but this is fairly uncommon in the literature. Vector commitments are similar to set commitments, but values of the elements are encoded into the digest (and opening proofs) along with their particular order in the vector. This means that the digest (and opening proofs) must be specific to not only to each element value but also to their particular positioning, and in other words, not be invariant to permutations of the input vector. This requirement is a consequence of the idea of positional binding, which we take as a central principle in vector commitments, in addition to zero-knowledge partial openings as was the case in set commitments. In some of the literature, $\mathrm{O}(1)$ opening proof size is stated as a requirement for a commitment scheme to be considered a vector commitment, which we do not agree with. We will ignore this characterization. The figure above shows different types of vector commitments discussed in the literature. We will first focus on commitments based on cryptographic hash functions (CRHFs), both a simple scheme and then Merkle trees, which build upon the simple scheme to improve performance. After that we will discuss Verkle trees that replace CRHFs in a Merkle tree with something more efficient (usually based on pairings, such as polynomial commitments) to increase the arity of the tree and improve performance even further (pairing-based vector commitment are reductions of polynomial commitments and will be discussed in the next chapter in more depth).

In this chapter, we discuss set commitments, which are the first in the hierarchy with a partial opening mechanism. The mathematical object to be committed to, which will consitute our message $m$, is a set $m = {m_1, m_2,...,m_n}$ of variable size $n \leq n_\text{max}$. Being a set, its elements are unique, i.e. $i\neq j \implies m_i\neq m_j$ and indexing of the elements is arbitrary. In practice, commitments to sets are usually simulated by vector commitments. However, there is an important commitment primitive called an accumulator that is invariant to the arbitrary indexing of the set's elements (order/permutation invariance). Accumulators are not vector commitments, as they do not commit to a particular positioning of the elements. We will discuss accumulators through a specific example. <span style="color: #0; font-family: Times New Roman; font-size: 1.1em;">Accumulators with groups of known order -- DL </span> Let us assume that the elements of the sets to be committed to belong to the set $\mathbb{S}$. In other words, the sets to be committed to are elements of the power set of $\mathbb{S}$, $m \in 2^\mathbb{S}$.

In our view, the simplest family that is at the base of the hierarchy of commitment schemes consists of commitments to messages with no parts, which we call simple-element commitments. Paradoxically, all messages have some parts to them, perhaps outside of a single bit of information, i.e. a message that contains a single $0$ or a $1$. Therefore, it is not the nature of the messages being committed to that is of importance, but the treatment of the messages by the commitment scheme that makes them "single-element commitments" in our catagorization. In more practical terms, a single-element commitment scheme does not allow a partial opening of the message and treats it as a single indivisible entity. When any part of a message is opened, it is forced by the scheme to be revealed in its entirety. Next, we discuss a few different schemes in more detail by describing the four algorithms associated with commitments as discussed in the previous chapter. <span style="color: #0; font-family: Times New Roman; font-size: 1.1em;">CRHF-based commitments </span> Cryptographic hash functions (CRHFs) are primitives that approximate a random oracle, a theoretical black box that responds to every unique query with a truly random response chosen uniformly from its output domain.

Commitment schemes are fundamental components of many cryptography protocols. A commitment scheme allows a committer to compute and publish a value $d=C(m)$, called a commitment or a digest, which binds him/her to a message $m$ (binding) without revealing it to the public (hiding/zero-knowledge). Later, she may open the commitment by revealing to the public a candidate $m^$ that she claims to correspond (fully or partially) to the hidden message $m$ associated with the digest $d$. A public verifier can then check that the candidate $m^$ is indeed consistent with the commitment $d$ obtained from the hidden message $m$, hitherto unknow to the verifier. As mentioned, commitment schemes can be catagorized based on the type of data or information containing mathematical objects they operate on, which corresponds to the type/structure of the message $m$. The message can have many parts and have the structure of sets, vectors, functions and so on. In the notation we will use, $i(m)$ will indicate the $i$th element of the committed message $m$, when $m$ is a set (arbitrary order) or a vector (natural order). In the case of a commitment to a function $m$ however, $i(m)$ will indicate $m(i)$, the evaluation of $m$ at $i$, which requires $i$ to be an element of its domain. In the case of commitments to messages with multiple parts, a partial opening is relevant. In such cases, partial opening for a specific part of the message $i(m)$ involves revealing both a candidate $m_i^$ and an opening proof $\pi_i$ that is needed to show the consistency of $m_i^$ with the overall commitment $d$ for the entire message.

In this note, we take a look at a recent survey paper on Threshold Signature Schemes (TSSs) in the context of ECDSA (a signature scheme we discussed earlier in this note) and talk about a particular way of sharing a secret value $s$ among different parties that relies on Lagrange polynomials called Shamir Secret Sharing (we will refer to it as SSS). Since we discussed polynomial representation/decomposition based on Lagrange as part of our series on polynomial commitments, SSS is easy to discuss as it uses much of the same foundation. For a more general discussion, we highly recommend the original survey. Much of our discussion will be simplified in comparison. <span style="color: #0; font-family: Times New Roman; font-size: 1.1em;">Secret Sharing Schemes </span> A $(t, n)$-secret sharing scheme splits a (secret) value/mathematical object $s$ into $n$ different shares to be distributed to multiple parties, such that $t + 1 \leq n$ distinct shares are necessary and sufficient to reconstruct $s$. This would mean that there is a certain amount of redundency of information in each of the shares (at least as much as $n/(t+1)$) such that accumulation of $t+1$ of them is enough to learn all the necessary information to determine $s$ (which we refer to as $n$ as if there was no redundency). Further, this redundency of information must be distributed to different shares such that any $(t+1)$ of them would be sufficient for reconstructing $s$.

In this series of notes, we will discuss fully homomorphic encryption (FHE) schemes, beginning with the first such scheme introduced by Craig Gentry in his thesis work that builds upon ideal lattices. Along with this introductory work, we will discuss a more intuitive and easier to understand approach based on integer encryption. Taken together, it is possible to understand FHEs without understanding ideal lattices, which we will discuss separately. In the chapters that follow, we will discuss some of the more recent advances in FHEs, such as FHEs over a torus, as well as some of the methods that speed up the bootstrapping step, typically the most expensive step computationally. <span style="color: #0; font-family: Times New Roman; font-size: 1.1em;">Chapters (private) </span> Principles of Fully Homomorphic Encryption [target=_blank] <span style="color: #0; font-family: Times New Roman; font-size: 1.1em;">Components of FHEs </span>Somewhat Homomorphic Encryption Schemes (SWHEs) [target=_blank] Integer SWHE of [DGHV09] [target=_blank]

In this short note, we discuss subgroups, cosets and prove Lagrange's theorem. These algebraic concepts come up in various places in cryptography research and can be important to internalize. We start with some simple facts. Given a group $(G, \cdot)$, a subgroup $(H, \cdot) \leq (G, \cdot)$ has the same composition rules as the original group, has the same identity element $e$, and composition of two of its elements remains within the subgroup (closed under composition). Composition is associative and the inverse elements are part of the subgroup as well. In other words, $(H, \cdot)$ has all the properties of a group in itself. $G$ itself and ${e}$ are both subgroups of $G$, although $G$ is not a proper subgroup. Lagrange's theorem is about the orders (or cardinalities) of the subgroups of a group. Given a group $(G, \cdot)$ of order $|G|$, its subgroups cannot simply have any arbitrary order. Langrange's theorem states that the order of any subgroup $(H, \cdot)$ of $(G, \cdot)$ must have an order $|H|$, that divides $|G|$, i.e. $\exists k\in \mathbb{N}$ such that $|G|=k|H|$. This is due to the idea of cosets, (non-intersecting) partitionings of a group, associated with any one of its given subgroups. We will show that each coset in a partition associated with a subgroup has the same cardinality. Therefore, the cardinality of a coset in a partition must divide the order of the group. Further, the subgroup itself is one of the cosets of the partition associated with itself and therefore has an order that divides the order of the group as well. The notation used for a left coset of $H$ is $g H$. It is the set $gH = {h\in H | g \cdot h}$ where $g$ can be any element of $G$. If $g = e$, the identity element, then $gH = H$ and this is the only coset in the partition associated with $H$ that is a subgroup. The rest of the cosets are not groups themselves since they do not intersect with $H$ and therefore do not contain the identity element $e$, which is a requirement for being a group.

In this series of notes, we explore zkSNARKs in the context of PLONK and Halo2, two modern proof systems that find applications in the real world. PLONK and Halo2 bear similarities and differences from each other, which provides us with the background to understand various elements of zkSNARKs and the computational and space complexities of these proof systems. Along the way, we will discuss prevailing principles of PLONK and Halo2, such as, transforming computations into efficient arithmetic circuits, Lagrange interpolation of polynomials, accumulators, permutation arguments, lookup arguments, commitment schemes and elliptic curves, some directly in this series and some by referring to other notes where we discuss these topics in more depth. We will begin by briefly introducing zkSNARKs, the theoretical principles that they embody, their uses as succinct knowledge arguments as well as their information theoretic hiding (zero-knowledge) properties. Afterwards, we will give an introduction to PLONK and its more recent variant Halo2. In each chapter that follows, we will introduce and give a clear definition for a different element of these proof systems. In the final chapter, we will discuss how to bring together all the elements to construct a succinct zero-knowledge proof.

This note aims to detail our thoughts on a particular short post from researchers at Aztec, the team behind the original PLONK zk-SNARKs. Due to the original post's short form, some of the details are not altogether clear to us. It requires some leaps of logic or creativity in certain parts. Therefore, the explainations in this note might be a bit misleading in parts and should be taken with a grain of salt.Nevertheless, we will take the burden of possibility of being mistaken and write out what we understood from the original post. Further, the methods in these notes (or methods similar to them) are implemented in the following repository, https://github.com/privacy-scaling-explorations/halo2wrong, to create efficient circuits for ECDSA verification algorithm which uses large fields. <span style="color: #0; font-family: Times New Roman; font-size: 1.1em;">Motivation </span> In some circuits such as DSA, we are frequently interested in representing modulo arithmetic over a large prime field, equations of the sort $a\cdot b = r \text{ mod } p$ where $p$ is a large prime. Typically, a witness $(a,b,r,q,p)$ is produced and the integer constraint $a\cdot b = q\cdot p + r$ is included as part of the polynomial commitment. Using non-native arithmetic discussed in this note, we can replace these types of constraints with (multiple) constraints over smaller numbers. Therefore, our goal in this note is to emulate certain expensive constraints in a different way. <span style="color: #0; font-family: Times New Roman; font-size: 1.1em;">Setup </span>

Digital signatures are crpytographic schemes that provide message authentication (the receiver can verify the origin of the message), integrity (the receiver can verify that the message has not been modified since it was signed) and non-repudiation (the sender cannot falsely claim that they have not signed the message). In this short note, we discuss arithmetic circuit constraints that ensures that a witness, a set of inputs and outputs, correctly computes (or are related to each other through) the Digital Signature Algorithm (DSA) and its more advanced version that uses elliptic curves. Both algorithms are based on groups of known order and the discrete logarithm (DL) security assumptions. A signature scheme has three parts, the setup algorithm which involves private and public key generation, the signature algorithm itself, and a verification algorithm for checking if a signature is authentic. The verification algorithm is the only part of the scheme that is public and is typically the only part that is of importance for circuit constraints. For example, the verification algorithm for DSA appears in smart contracts executed in the Ethereum Virtual Machine. The veracity of the inputs and outputs of this verification algorithm can be shown by encoding a set of contraints into a circuit used to prove a larger set of computations with a ZK-SNARK. We will introduce the two algorithms, DSA and Elliptic-curve DSA in turn and briefly discuss the circuit constraints associated with each.

In this series of notes, we explore cryptographic commitment schemes, which are primitives that lie at the foundation of various cryptosystems, such as digital signatures and zero-knowledge proofs. Commitment schemes can be categorized based on the type of data or information containing mathematical objects (think data structures but possibly extended to infinities) they operate on, such as sets, vectors, functions and so on. Specifically, we are interested in building a hierarchy of commitment schemes that connect to each other through reductions, mathematical bridges that allow us to simulate a family of commitments designed for a simpler type of object (such as a set), through another family of commitments designed for a more complex type (such as a vector, which can be viewed as an ordered multi-set). We will begin by discussing the origins of commitment schemes and the oracle ideals they embody, binding and hiding. Then, we describe the common elements within all commitment schemes, four well-specified algorithms that make up a commitment, whose computational complexity along with their output sizes determine the efficiency of the scheme. In each chapter that follows, we will introduce and give a clear definition for a different family of commitments based on the catagorization above, e.g. set commitments, vector commitments, univariate polynomial commitments and so on. Further, we will introduce some of the most common or well-known commitment schemes used across many applications in the real-world for that particular family.

Univarite polynomials are functions of the form $f(x) = a_0 x^0+a_1 x^1 + a_2 x^2+ ... + a_n x^n$ with a single scalar input (univariate) $x$ and a scalar output. Coefficients $f_a = [a_0, a_1, ..., a_n]$ of a univariate polynomial $f$ of maximal degree $n$ ($a_n=0$ etc. must be considered, hence maximal qualifier) uniquely identifies it and differentiates it from other univariate polynomials of maximal degree $n$. On the other hand, this is not the only way to identify and represent a polynomial of maximal degree $n$. Knowing the evaluation of the polynomial at any $n+1$ unique points, also identifies and represents such a polynomial, i.e. given a unique set of points $\bar{x} = [x_0, x_1, x_2, ..., x_n]$, $f_\bar{x} = [(x_0, f(x_0)), (x_1, f(x_1)), (x_2, f(x_2)), ..., (x_n, f(x_n))]$ is a representation that identifies $f$ among all such polynomials as well. Mapping this representation $f_\bar{x}$ to the polynomial $f(x)$ is accomplished through Lagrange interpolation. \begin{align} f(x) &= \sum_{i=1}^{n} l_{x_i}(x)f(x_i) \hspace{0.3in} (\text{Green in the figure below.})\ l_{x_i}(x) &= \prod_{j=0, j\neq i}^{n} \frac{x-x_j}{x_i-x_j} \hspace{0.3in} (\text{Blue/animated in the figure.}) \end{align} The goal of this chapter is to discuss commitments to univariate polynomials. An obvious question that follows is, since we can represent a polynomial $f$ as the coefficient vector $f_a$ or the evaluation vector $f_\bar{x}$ of length $n+1$, can we not simply commit to these representation vectors and be done? Are vector commitment schemes equivalent to univariate polynomial commitment schemes?

EXPLORATIONS IN CRYPTOGRAPHY RESEARCH A Hierarchical View of Cryptographic Commitment Schemes Circuit Constraints for Elliptic Curve Digital Signature Algorithm (ECDSA) Aztec Emulated Field and Group Operations for Efficient Large Number Arithmetic Decrpyting Zero-Knowledge Proofs - zkSNARKs Subgroups, Cosets and Lagrange's Theorem Fully Homomorphic Encrpytion Schemes Threshold Signature Schemes Through Shamir Secret Sharing