1\documentclass{article}
  2\usepackage[utf8]{inputenc}
  3\usepackage{amsfonts}
  4\usepackage{amsthm} % theorems structure
  5\usepackage{enumerate}
  6\usepackage{hyperref} % links
  7\usepackage{tikz} % diagrams
  8\usepackage{pgf-umlsd} % diagrams
  9\usepackage{amsmath} % arrows
 10
 11\theoremstyle{definition}
 12\newtheorem{example}{Example}[section]
 13
 14\title{Sigma protocol and OR proofs - notes}
 15\author{arnaucube}
 16\date{March 2022}
 17
 18\begin{document}
 19
 20\maketitle
 21
 22\begin{abstract}
 23	This document contains the notes taken during the \emph{Cryptography Seminars} given by \href{https://github.com/rbkhmrcr}{Rebekah Mercer}.
 24\end{abstract}
 25
 26\tableofcontents
 27
 28\section{Sigma protocol}
 29
 30\subsection{The protocol}
 31Let $q$ be a prime, $q$ a prime divisor in $p-1$, and $g$ and element of order $q$ in $\mathbb{Z}_p^a$. Then we have $G = \langle g \rangle$.
 32\\
 33We assume that computationally for a given $A$ it's hard to find $a \in \mathbb{F}$ such that $A = g^a$.
 34\\
 35Alice wants to prove that knows the \emph{witness} $w \in \mathbb{F}$, such that the \emph{statement} $X = g^w$, without revealing $w$.
 36
 37\begin{enumerate}[1.]
 38	\item Alice generates a random $a \xleftarrow{r} \mathbb{F}$, and computes $A=g^a$. And sends $A$ to Bob.
 39	\item Bob generates a challenge $c \xleftarrow{r} \mathbb{F}$, and sends it to Alice.
 40	\item Alice computes $z=a + c \cdot w$, and sends it to Bob.
 41	\item Bob verifies it by checking that $g^z == X^c \cdot A$.
 42\end{enumerate}
 43
 44We can unfold Bob's verification and see that:
 45$$g^z == X^c \cdot A$$
 46$$g^{a+cw} == g^{wc} g^a$$
 47$$g^{a+cw} == g^{wc+a}$$
 48
 49\begin{center}
 50\begin{sequencediagram}
 51    \newinst[1]{a}{Alice}
 52    \newinst[3]{b}{Bob}
 53    \mess[0]{a}{$A$}{b}
 54    \mess[2]{b}{$c$}{a}
 55    \mess[2]{a}{$z$}{b}
 56    \mess[0]{b}{$ok$}{a}
 57\end{sequencediagram}
 58\end{center}
 59
 60Properties:
 61\begin{enumerate}[i.]
 62	\item \emph{correctness/completness}: if Alice know the witness for the statement, then they can create a valid proof.
 63	\item \emph{soundness}: if someone does not have knowledge of the witness, can not form a valid proof (verifier will always reject).
 64	\item \emph{zero knowledge}: nobody gains knowledge of anything new with the proof. prior knowledge + proof = prior knowledge
 65\end{enumerate}
 66
 67\subsection{Non interactive protocol}
 68With the \emph{Fiat-Shamir Heuristic}, we model a hash function as a random oracle, thus we can replace Bob's role by a hash function in order to obtain the challenge $c \in \mathbb{F}$.
 69\\
 70So, we replace the step 2 from the described protocol by $c = H(X || A)$ (where $H$ is a known hash function).
 71
 72\subsection{What could go wrong (Simulator)}
 73If the verifier (Bob) sends $c \in \mathbb{F}$, prior to the prover committed to $A$, the prover could create a proof about a public key which they don't know $w$.
 74\begin{enumerate}[1.]
 75	\item Bob sends $c \xleftarrow{r} \mathbb{F}$ to Alice
 76	\item Alice generates $z \xleftarrow{r} \mathbb{F}$
 77	\item Alice then computes $A = g^z X^{-c}$, and sends $z, A$ to Bob
 78	\item Bob would check that $g^z == X^c A$ and it would pass the verification, as $g^z== X^c \cdot A \Rightarrow g^z==X^c \cdot g^z X^{-c} \Rightarrow g^z == g^z$.
 79\end{enumerate}
 80
 81As we've seen, it's really important the order of the steps, so Alice must commit to $A$ before knowing $c$.\\
 82This 'fake' proof generation is often called the \emph{simulator} and used for further constructions.
 83
 84\section{OR proof}
 85
 86\emph{OR proofs} allows the prover to prove that they know the witness $w$ of one of the two known \emph{public keys} $X_0, X_1 \in \mathbb{F}$, without revealing which one. It uses the construction seen in the \emph{sigma protocols} together with the idea of the \emph{simulator}.
 87
 88A similar construction is used for $n$ statements in the \emph{ring signatures} scheme (used for example in \emph{Monero}). In our case, we will work with $n=2$.
 89
 90\subsection{The protocol}
 91\subsubsection{Simulator}
 92We can assume that the simulator is a box that for given the inputs $(g, X)$, it will output $(A_s, c_s, z_s)$, such that verification succeeds ($g^{z_s}==X^{c_s} \cdot A_s$).
 93
 94\begin{center}
 95\begin{tikzpicture}
 96\node [draw,
 97    minimum width=2cm,
 98    minimum height=1.2cm,
 99    right=1cm
100    ]  (simulator) {simulator};
101\draw[-stealth] ++(-1,0) -- (simulator.west)
102    node[midway,above]{$g, X$};
103\draw[-stealth] (simulator.east) -- ++(+2,0)
104    node[midway,above]{$A_s, c_s, z_s$};
105\end{tikzpicture}
106\end{center}
107
108Internally, the simulator computes
109$$z_s \xleftarrow{r} \mathbb{F},~c_s \xleftarrow{r} \mathbb{F},~A_s = g^{z_s} \cdot X^{c_s}$$
110
111\subsection{Flow}
112For two known \emph{public keys} $X_0, X_1 \in G$, Alice knows $w_b \in \mathbb{F}$, for $b \in \{0, 1\}$, such that $g^{w_b} = X_0$ or $g^{w_b} = X_1$. As we don't know if Alice controls $0$ or $1$, from now on, we will use $b$ and $1-b$.
113\\
114So, Alice knows $w_b \in \mathbb{F}$ such that $X_b = g^{w_b}$, and does not know $w_{1-b}$ for $X_{1-b}=g^{w_{1-b}}$.
115
116\begin{enumerate}
117    \item First of all, as in the \emph{Sigma protocol}, Alice generates a random \emph{commitment} $a_b \xleftarrow{r} \mathbb{F}$, and computes $A_b = g^{a_b}$.
118    \item Then, Alice will run the \emph{simulator} for $1-b$.
119	\begin{list}{}
120	    \item Sets a random $c_{1-b} \xleftarrow{r} \mathbb{F}$, and runs the simulator with inputs\\$(c_{1-b}, X_{1-b})$, and outputs $(A_{1-b}, c_{1-b}, z_{1-b})$.
121	    \item Remember that internally the \emph{simulator} will set random\\
122		$z_{1-b}, c_{1-b} \xleftarrow{r} \mathbb{F}$, and compute an $A_{1-b}$ such that\\
123		$A_{1-b} = g^{z_{1-b}} \cdot X_{1-b}^{c_{1-b}}$.
124	\end{list}
125	\item Now, Alice sends $A_b, A_{1-b}$ to Bob
126	\item And Bob sends back the \emph{challenge} $s \xleftarrow{r} \mathbb{F}$.
127	\item Alice then splits the challenge $s$ into $c_b, c_{1-b}$, by $s = c_{1-b} \oplus c_b$. So Alice can compute $c_b = s \oplus c_{1-b}$.
128	\item Then Alice computes $z_b = a_b \cdot w_b + c_b$. And sends to Bob $(c_b, c_{1-b}, z_b, z_{1-b})$.
129	\item Bob can perform the verification by checking that:
130	\begin{enumerate}[i.]
131	    \item $s == c_b \oplus c_{1-b}$
132	    \item $g_{z_{1-b}} == A_{1-b} \cdot X_{1-b}^{-c_{1-b}}$
133	    \item $g_{z_b} == A_b \cdot X_b^{-c_b}$
134	\end{enumerate}
135\end{enumerate}
136
137
138
139\begin{center}
140\begin{sequencediagram}
141    \newinst[1]{a}{Alice}
142    \newinst[3]{b}{Bob}
143    \mess[1]{a}{$A_b, A_{1-b}$}{b}
144    \mess[1]{b}{$s$}{a}
145    \mess[1]{a}{$c_b, c_{1-b}, z_b, z_{1-b}$}{b}
146\end{sequencediagram}
147\end{center}
148
149\section{Resources}
150\begin{enumerate}
151    \item \href{https://cs.au.dk/~ivan/Sigma.pdf}{https://cs.au.dk/~ivan/Sigma.pdf}
152    \item \emph{Cryptography Made Simple}, Nigel Smart. Section 21.3.
153\end{enumerate}
154
155\end{document}