Multiparty Computation

Cryptography Cheat Sheet

Within this page, we summarize some key results and definitions within a few areas of mathematics and computer science that are related to results within this site. In general, lengthy explanations and summary are avoided in favor of equations, identities, or definitions.

Modular Arithmetic

We begin by stressing the difference between the mod function, and modular equivalence. The mod (or remainder) function is defined as \(x\bmod y = r\quad 0\leq r\lt y\) where \(\exists k\in\mathbb Z\) such that \(ky+r=x.\) Generally, \(x,y,r\in\mathbb Z\), though all can meaningfully be extended to \(\mathbb R\). Modular equivalence between two values \(a,b\) with respect to some quotient \(c\) is expressed as \(a\equiv b\pmod c,\) which is equivalent to the statement \(a\bmod c\quad=\quad b\bmod c.\)

Notice the the former is a function, whereas the latter is a statement of equivalence within a particular relation; the former has a 'solution', the latter is simply a property of \(a,b\). In particular, we stress that \(a\equiv b\pmod c\) does NOT imply \(a=b\bmod c\), though the reverse is true.

Now, for some major definitions, algorithms, and theorems. \(a,b,c,n,x,y\in\mathbb Z;\;p,q,\in\mathbb P\) (the set of all primes)

Equation	Name	Description
$$a\,|\,b$$	"\(a\) divides \(b\)"	$$\exists k\in\mathbb Z,\,kb=a$$
$$a\equiv b\pmod c\;\\\Leftrightarrow\;c\,|\,(a-b)$$	Equivalence of Congruency and Divisibility	If two numbers are equivalent modulo a third number, that third number divides their difference. This is plain from the definition of congruence and basic algebra.
$$\gcd(a,b)=k\\\text{where }(x|a\wedge x|b)\Leftrightarrow x|k$$	Greatest Common Divisor	The gcd of two numbers is the greatest number that divides both of them. Two numbers such that \(\gcd(a,b)=1\) are called coprime.
$$\operatorname{lcm}(a,b)=k\\\text{where }(a|x\wedge b|x)\Leftrightarrow k|x$$	Lowest Common Multiple	The lcm of two numbers is the smallest number which can be divided by both of them. Two numbers such that \(\operatorname{lcm}(a,b)=a\cdot b\) are also coprime, by the next equation.
$$a\cdot b=\operatorname{lcm}(a,b)\cdot\gcd(a,b)$$	Product of LCM and GCD	Intuitively, the lcm and gcd of two numbers are produced from the sets of their prime factors: the intersection of their prime factors is the gcd, and the union of their prime factors is the lcm. As such, the gcd and the lcm together produce both numbers in their entirety.
$$\exists x,y\text{ such that}\\xa+yb=\gcd(a,b)$$	Bézout's Identity	There is no solution to such a linear Diophantine equation (on the integers) when the right side is not a multiple of the gcd. We can find the solutions \(x,y\) to such an equation for given \(a,b\) using the Extended Euclidean Algorithm (which runs in worst case \(\operatorname O(\log\min(a,b))\) time).
$$\mathbb Z_n=\{x\bmod n\;|\;x\in\mathbb Z\}$$	The Integers modulo \(n\)	We denote by \(\mathbb Z_n\) the integers between 0 and \(n-1\). The same set not including 0 is often denoted \(\mathbb Z_n^*\). If \(n\) is a prime or a prime power, then this set is a finite field.
$$\operatorname\phi(n)=\\\left|\left\{k\;|\;k\in\mathbb Z_n^*,\,\gcd(k,n)=1\right\}\right|$$	Definition of the Totient Function	The function \(\operatorname\phi(n)\) calculates the number of positive integers less than \(n\) which are coprime to \(n\).
$$\phi(p)=p-1$$	Totient of a Prime	All numbers below a prime are coprime to it.
$$\phi(a\cdot b)=\phi(a)\cdot\phi(b)$$	Multiplicativity of the Totient	The totient function is multiplicative; this is a property often used as a trapdoor since determining the totient of a Blum integer is thought to be hard.
$$a^{(p-1)}\equiv 1\pmod p$$	Fermat's Little Theorem	For any number \(a\), \(a^p\) is equivalent to 1 \(\bmod p\). This is generalized in the next theorem.
$$\gcd(a,n)=1\Rightarrow\\a^{\operatorname\phi(n)}\equiv 1\pmod n$$	Euler's Theorem	A generalization of Fermat's Little Theorem which applies to any coprime \(a,n\). A foundational part of RSA.

Big-Oh Notation and Runtime

The Five Runtime Functions

Statement	Informal Statement	Comparison to Inequality	Formal Definition
$$f(n)\in\operatorname o(g(n))$$	\(f\) is dominated by \(g\)	$$f\lt g$$	$$\forall\,k>0,\exists\,n_0\;|\;\\\forall n\gt n_0,\,f(n)\leq k\cdot g(n)$$
$$f(n)\in\operatorname O(g(n))$$	\(f\) is bounded above by \(g\)	$$f\leq g$$	$$\exists\,k>0,\exists\,n_0\;|\;\\\forall n\gt n_0,\,f(n)\leq k\cdot g(n)$$
$$f(n)\in\operatorname \Theta(g(n))$$	\(f\) is bounded above and below by \(g\)	$$f\approx g$$	$$\exists\,k_1,k_2>0,\exists\,n_0\;|\;\\\forall n\gt n_0,\,k_1\cdot g(n)\leq f(n)\leq k_2\cdot g(n)$$
$$f(n)\in\operatorname \Omega(g(n))$$	\(f\) is bounded below by \(g\)	$$f\geq g$$	$$\exists\,k>0,\exists\,n_0\;|\;\\\forall n\gt n_0,\,f(n)\geq k\cdot g(n)$$
$$f(n)\in\operatorname \omega(g(n))$$	\(f\) dominates \(g\)	$$f\gt g$$	$$\forall\,k>0,\exists\,n_0\;|\;\\\forall n\gt n_0,\,f(n)\geq k\cdot g(n)$$

Runtime Sequence

The following is a sequence from the lowest to highest runtimes. \(k\) is an arbitrary constant greater than 1. Notice the notation used:

$$\operatorname O(1)\subset\operatorname O(\log n)\subset\operatorname O(n^{1/k})\subset\operatorname O(n)\subset\operatorname O(n\log n)\subset\operatorname O(n^k)\subset\operatorname O(k^n)\subset\operatorname O(n!)$$

Experiments

Much of cryptography uses a particular notation for probability that can take some getting used to: experiment notation. A single event is written in the form \(x\leftarrow\mathcal X\), where \(x\) is a variable being sampled from some distribution \(\mathcal X\). We define the probability distribution of a set \(S\) to be the uniform distribution \(\mathcal S\) over that set. We define the probability distribution of some function applied to a variable, as in \(F(x,y)\), to be a probability distribution over the outputs of that function given those inputs. We now define the probability of some predicate p after a series of \(n\) events (in its most general form) as follows: $$\operatorname{Pr}\left[x_1\leftarrow\mathcal X_1;\;x_2\leftarrow\mathcal X_2;\;\dots;\;x_n\leftarrow\mathcal X_n\;:\;\operatorname p(x_1,\dots,x_n)\right].$$

So, as an example, let's use experiment notation to define the ciphertext indistinguishability of an encryption protocol, then go through it step by step. We define three protocols that make up the encryption scheme: $$\begin{align} \mathcal G: &1^k\;\mapsto\;(\{0,1\}^k,\{0,1\}^k)\\ &\mathcal G(1^k)=(p_k,s_k)\\ \mathcal E: &\{0,1\}^k,\{0,1\}^k\;\mapsto\;\{0,1\}^k\\ &\mathcal E(p_k,m) = c\\ \mathcal D: &\{0,1\}^k,\{0,1\}^k\;\mapsto\;\{0,1\}^k\\ &\mathcal D(s_k,c) = m.\end{align}$$ To define correctness (very quickly and loosely; see the page on primitives for a more official definition), we state that, for any pair \(p_k,s_k\) created by \(\mathcal G(1^k),\;\mathcal D\left(s_k,\mathcal E\left(p_k,x\right)\right)=x\) for all \(x\in\{0,1\}^k\). We now define a particular type of security using experiment notation. We call such an encryption scheme ciphertext indistinguishable under chosen plaintext attack if, for all probabilistic polynomial-time algorithms \(\mathcal A\) and for negligible function \(\operatorname\mu\): $$\operatorname{Pr}\left[(p_k,s_k)\leftarrow\mathcal G(1^k);\; (m_0,m_1,\text{state})\leftarrow\mathcal A(p_k);\; b\leftarrow\{0,1\};\; b'\leftarrow\mathcal A\left(\text{state},\mathcal E(p_k,m_b)\right)\;:\; b=b'\right]\quad\leq\quad\frac12+\operatorname\mu(k).$$

We now present the same experiment (or "game") as an annotated list of the different pieces, with some explanations for choices made in the writing of the expression:

1. \((p_k,s_k)\leftarrow\mathcal G(1^k)\): We (the challenger) use the key generation algorithm to create a key pair.
2. \((m_0,m_1,\text{state})\leftarrow\mathcal A(p_k)\): We allow the adversary (algorithm) to generate two messages, \(m_0\) and \(m_1\), and some variable representing the state of the algorithm after its initial run. We provide the algorithm with the public key, which means it is able to try as many (polynomially many) encryptions as it wishes before deciding on specific messages. We do not need to provide the public key again, as the algorithm (without loss of generality) will include it in its state.
3. \(b\leftarrow\{0,1\}\): We uniformly at random choose some bit \(b\).
4. \(b'\leftarrow\mathcal A\left(\text{state},\mathcal E(p_k,m_b)\right)\): We let the adversary (algorithm) continue by providing it with its state variable, as well as the encryption of \(m_b\) under the public key. We allow it to make a guess (\(b'\)) for which message \(m_{b'}\) was encrypted.
5. \(b=b'\): We calculated the probability that, having done all this, the adversary correctly guessed which message we encrypted.
6. \(\leq\frac12+\operatorname\mu(k)\): Firstly, we note that we cannot expect the probability to be less than \(\frac12\); guessing at random should produce a probability of \(\frac12\), so we know it will be at least better than that. It is for this exact purpose that negligible functions are so often used in cryptography: to allow us to define a notion of being barely better (or worse) than some bound. As a thought experiment to demonstrate the need for this extra 'wiggle room', we imagine an adversary which calculates \(k\) encryptions for \(m_0,m_1\), meaning it will definitely be correct if the encryption we give it happens to be equal to any of those calculated encryptions. This is better than guessing, but only negligibly (\(\frac{k}{2^{-k}}\)) so.