\documentclass[a4paper]{article}
\usepackage[hmargin=2cm,vmargin=2cm]{geometry}


\pagestyle{plain}

\usepackage{amssymb,amsthm,amsmath,amsfonts,longtable, comment,array, ifpdf, hyperref,url}
\usepackage{graphicx}

\title{Revocation with type-3 pairings}
\author{Dmitry Khovratovich}
\date{5 May 2017, version 0.3}

\begin{document}

\maketitle


\section{Setup}

This section describes how the Prover obtains  a non-revocation claim from the Issuer.


\subsection{Common parameters for all Issuers}



Issuer and Prover mutually trust each other in submitting values of the right format
during credential's issuance. This trust can be eliminated at the cost of some extra steps.


Common parameters:
\begin{itemize}
    \item Groups $\mathbb{G}_1,\mathbb{G}_2,\mathbb{G}_T$ of
    prime order $q$;
    \item Type-3 pairing operation $e:\, \mathbb{G}_1\times\mathbb{G}_2\rightarrow\mathbb{G}_T$.
    \item Generators: $g$ for $\mathbb{G}_1$, $g'$ for
    $\mathbb{G}_2$.
\end{itemize}

Typically the triplet $(\mathbb{G}_1,\mathbb{G}_2,\mathbb{G}_T)$ is selected together with a pairing function as only a few combinations admit a suitable pairing. Existing implementations provide just a few possible pairing functions and thus triplets, thus making the group details in fact oblivious to the user. For the sake of curiosity we note that $\mathbb{G}_1,\mathbb{G}_2$ are different groups of elliptic curve points, whereas $\mathbb{G}_T$ is not a curve point group.

\subsection{Issuer revocation setup}\label{sec:iss-revoc-setup}

Issuer makes the following steps:
\begin{enumerate}
    \item Generate random $h,h_0,h_1,h_2,\widetilde{h}\in \mathbb{G}_1$;
    \item Generate random $u,\widehat{h}\in \mathbb{G}_2$;
    \item Generate random $sk,x \pmod{q}$.
    \item Compute 
\begin{align*}
    pk&\leftarrow g^{sk}; & y&\leftarrow \widehat{h}^x.
\end{align*}. 
\item The issuer revocation public key is
$pk^R = (h,h_0,h_1,h_2,\widetilde{h},\widehat{h},u,pk,y)$ and the secret key is $(x,sk)$.
\end{enumerate}

The Issuer fixes the number $L$ of credentials per accumulator. For each accumulator:
\begin{enumerate}
\item Generate random $\gamma\pmod{q}$.  
\item Compute $g_1,g_2,\ldots,g_L,g_{L+2},\ldots,g_{2L}$ where
$g_i = g^{\gamma^i}$. 
\item Compute $g_1',g_2',\ldots,g_L',g_{L+2}',\ldots,g_{2L}'$ where
$g_i' = g'^{\gamma^i}$. 
\item Compute $z = (e(g,g'))^{\gamma^{L+1}}$.
\item Set $V \leftarrow\emptyset$, $\mathrm{acc}\leftarrow 1$.
\end{enumerate}  The accumulator public key is $(z)$ and secret key is $(\gamma)$.


\section{Issuance of non-revocation claim}

Prover starts:
\begin{enumerate}
    \item Loads Issuer's revocation key $pk^R$ and generates random $s'\bmod{q}$.
     \item Computes $U \leftarrow h_2^{s'}$
taking $h_2$ from $pk^R$.
\item Sends $U$ to the Issuer.
\end{enumerate}
We assume that the attribute $m_2$ is used to enumerate provers by Issuer (details are irrelevant for revocation). Then Issuer proceeds:
\begin{enumerate}
    \item Generates random numbers $s'',c\bmod{q}$.
    \item Takes $m_2$ from the primary 
    claim he is preparing for the Prover.
    \item Selects the accumulator index $A_i$ and the user index $i$ for the Prover so that $i$ has not been assigned yet for $A_i$.
    \item Computes 
\begin{align}
\sigma &\leftarrow \left( h_0 h_1^{m_2}\cdot U\cdot  g_i\cdot  h_2^{s''}\right)^{\frac{1}{x+c}};&
w &\leftarrow \prod_{j\in V}g_{L+1-j+i}';\\
\sigma_i &\leftarrow g'^{1/(sk+\gamma^i)};&
u_i &\leftarrow u^{\gamma^i};\\
\mathrm{acc}&\leftarrow \mathrm{acc}\cdot g'_{L+1-i};&
V&\leftarrow V\cup\{i\};\\
\mathrm{wit}_i&\leftarrow\{\sigma_i,u_i,g_i,w,V\}.
\end{align}
\item Sends $(A_i,\sigma,c,s'',\mathrm{wit}_i,g_i,g_i',i)$.
\item  Publishes updated $V, \mathrm{acc}$.
\end{enumerate}
Prover finishes:
\begin{enumerate}
    \item Computes $s \leftarrow s'+s''$.
    \item Stores \emph{non-revocation claim} $C_{NR}\leftarrow(A_i,\sigma,c,s,\mathrm{wit}_i,g_i,g_i',i)$.
    \item [TEST] Tests
\begin{align}
\frac{e(g_i,acc_V)}{e(g,w)} &\overset{\text{?}}{=} z;\\
e(pk\cdot g_i, \sigma_i) &\overset{\text{?}}{=} e(g,g');\\
e(\sigma,y\cdot \widehat{h}^c)& \overset{\text{?}}{=} e(h_0 \cdot h_1^{m_2}h_2^{s}g_i,\widehat{h}).
\end{align} 
\end{enumerate}
    
    \section{Revocation}

Issuer revokes user with $m_2$ value that corresponds to accumulator $\mathrm{acc}$, index $i$, and valid index set $V$:
\begin{enumerate}
\item Sets $V\leftarrow V\setminus\{i\}$;
\item Computes $\mathrm{acc} \leftarrow \mathrm{acc}/g'_{L+1-i}$.
\item Publishes $V,\mathrm{acc}$.
\end{enumerate}
    
\section{Presentation of non-revocation proof}
This phase is a part of the entire presentation protocol, which instructs the prover to maintain sets $\mathcal{C}$ and
$\mathcal{T}$, which are filled by all primary claims and their non-revocation complements
used in the presentation.

\subsection{Preparation}
Verifier starts:
\begin{enumerate}
\item Loads Issuer's public revocation key $p = (h,h_1,h_2,\widetilde{h},\widehat{h},u,pk,y)$.
\end{enumerate}
Prover continues:
\begin{enumerate}
\item Loads Issuer's public revocation key $p = (h,h_1,h_2,\widetilde{h},\widehat{h},u,pk,y)$.
\item Loads the non-revocation claim $C_{NR}\leftarrow(A_i,\sigma,c,s,\mathrm{wit}_i,g_i,g_i',i)$;
\item Obtains recent $V,\mathrm{acc}$ (from Verifier, Sovrin link, or elsewhere).
\item Updates $C_{NR}$:
\begin{align*}
w&\leftarrow w\cdot \frac{\prod_{j\in V\setminus V_{old}}g'_{L+1-j+i}}{\prod_{j\in V_{old}\setminus V}g'_{L+1-j+i}};\\
V_{old}&\leftarrow V.
\end{align*}
Here $ V_{old}$ is taken from $\mathrm{wit}_i$ and updated there.

\item Selects random $\rho,\rho',r,r',r'',r''',o,o'\bmod{q}$;
\item Computes
\begin{align}
E &\leftarrow h^{\rho} \widetilde{h}^o &
D & \leftarrow g^r\widetilde{h}^{o'};\\
A &\leftarrow \sigma \widetilde{h}^{\rho}&
\mathcal{G} &\leftarrow g_i\widetilde{h}^r;\\
\mathcal{W} &\leftarrow w\widehat{h}^{r'} &
\mathcal{S}&\leftarrow \sigma_i \widehat{h}^{r''}\\
\mathcal{U}&\leftarrow u_i \widehat{h}^{r'''}
\end{align}
and adds these values to $\mathcal{C}$.

\item Computes 
\begin{align}
m&\leftarrow \rho \cdot c; & t&\leftarrow o\cdot c;\\
m'&\leftarrow r\cdot r''; & t'&\leftarrow o'\cdot r'';
\end{align}
\item Generates random $\widetilde{\rho},\widetilde{o},\widetilde{o'},\widetilde{c},
\widetilde{m},\widetilde{m'},\widetilde{t},\widetilde{t'},
\widetilde{m_2},\widetilde{s},
\widetilde{r},\widetilde{r'},\widetilde{r''},\widetilde{r'''},
\bmod{q}$.

\item Computes 
\begin{align}
\overline{T_1}&\leftarrow h^{\widetilde{\rho}} \widetilde{h}^{\widetilde{o}} &
\overline{T_2}&\leftarrow E^{\widetilde{c}}h^{-\widetilde{m}}\widetilde{h}^{-\widetilde{t}}
\end{align}
\begin{equation}
\overline{T_3}\leftarrow e(A,\widehat{h})^{\widetilde{c}}\cdot e(\widetilde{h},\widehat{h})^{\widetilde{r}}\cdot
e(\widetilde{h},y)^{-\widetilde{\rho}}\cdot
e(\widetilde{h},\widehat{h})^{-\widetilde{m}}\cdot
e(h_1,\widehat{h})^{-\widetilde{m_2}}\cdot e(h_2,\widehat{h})^{-\widetilde{s}}\\
\end{equation}
\begin{align}
\overline{T_4}&\leftarrow e(\widetilde{h},\mathrm{acc})^{\widetilde{r}}\cdot
e(1/g,\widehat{h})^{\widetilde{r'}}&
\overline{T_5}&\leftarrow g^{\widetilde{r}}\widetilde{h}^{\widetilde{o'}}\\
\overline{T_6}&\leftarrow D^{\widetilde{r''}}g^{-\widetilde{m'}}
\widetilde{h}^{-\widetilde{t'}}&
\overline{T_7}&\leftarrow e(pk\cdot \mathcal{G},\widehat{h})^{\widetilde{r''}}\cdot 
e(\widetilde{h},\widehat{h})^{-\widetilde{m'}}\cdot
e(\widetilde{h},\mathcal{S})^{\widetilde{r}}\\
\overline{T_8}&\leftarrow e(\widetilde{h},u)^{\widetilde{r}}
\cdot e(1/g,\widehat{h})^{\widetilde{r'''}}
\end{align}
and add these values to $\mathcal{T}$.
\item [TEST] Tests that for
\begin{align*}
\widetilde{\rho}&=\rho &\widetilde{o}&=o &\widetilde{o'}&=o'
&\widetilde{c}&=c\\
\widetilde{m}&=m&\widetilde{m'}&=m'&\widetilde{t}&=t&\widetilde{t'}&=t'\\
\widetilde{m_2}&=m_2&\widetilde{s}&=s
&\widetilde{r}&=r&\widetilde{r'}&=r'\\\widetilde{r''}&=r''&\widetilde{r'''}&=r'''
\end{align*}
the following holds:
\begin{align}
E&\overset{\text{?}}{=} h^{\widetilde{\rho}} \widetilde{h}^{\widetilde{o}} &
1&\overset{\text{?}}{=} E^{\widetilde{c}}h^{-\widetilde{m}}\widetilde{h}^{-\widetilde{t}}
\end{align}
\begin{equation}
\frac{e(h_0\mathcal{G},\widehat{h})}{e(A,y)} \overset{\text{?}}{=} e(A,\widehat{h})^{\widetilde{c}}\cdot e(\widetilde{h},\widehat{h})^{\widetilde{r}}\cdot
e(\widetilde{h},y)^{-\widetilde{\rho}}\cdot
e(\widetilde{h},\widehat{h})^{-\widetilde{m}}\cdot
e(h_1,\widehat{h})^{-\widetilde{m_2}}\cdot e(h_2,\widehat{h})^{-\widetilde{s}}\\
\end{equation}
\begin{align}
\frac{e(\mathcal{G},\mathrm{acc})}{e(g,\mathcal{W})z}&\overset{\text{?}}{=} e(\widetilde{h},\mathrm{acc})^{\widetilde{r}}\cdot
e(1/g,\widehat{h})^{\widetilde{r'}}&
D&\overset{\text{?}}{=} g^{\widetilde{r}}\widetilde{h}^{\widetilde{o'}}\\
1&\overset{\text{?}}{=} D^{\widetilde{r''}}g^{-\widetilde{m'}}
\widetilde{h}^{-\widetilde{t'}}&
\frac{e(pk\cdot\mathcal{G},\mathcal{S})}{e(g,g')}&\overset{\text{?}}{=} e(pk\cdot \mathcal{G},\widehat{h})^{\widetilde{r''}}\cdot 
e(\widetilde{h},\widehat{h})^{-\widetilde{m'}}\cdot
e(\widetilde{h},\mathcal{S})^{\widetilde{r}}\\
\frac{e(\mathcal{G},u)}{e(g,\mathcal{U})}&\overset{\text{?}}{=} e(\widetilde{h},u)^{\widetilde{r}}
\cdot e(1/g,\widehat{h})^{\widetilde{r'''}}
\end{align}
\end{enumerate}
After all claims are processed, Prover generates $c_H$:
$$
c_H \leftarrow H(\mathcal{T},\mathcal{C},n_1).
$$

\subsection{Last preparation steps}
Prover finalizes:
\begin{enumerate}
\item Computes
\begin{align*}
\widehat{\rho} &\leftarrow \widetilde{\rho} - c_H\rho\bmod{q} &
\widehat{o} &\leftarrow \widetilde{o} - c_H\cdot o\bmod{q}\\
\widehat{c} &\leftarrow \widetilde{c} - c_H\cdot c\bmod{q} &
\widehat{o'} &\leftarrow \widetilde{o'} - c_H\cdot o'\bmod{q}\\
\widehat{m} &\leftarrow \widetilde{m} - c_H m\bmod{q} &
\widehat{m'} &\leftarrow \widetilde{m'} - c_H m'\bmod{q}\\
\widehat{t} &\leftarrow \widetilde{t} - c_H t\bmod{q} &
\widehat{t'} &\leftarrow \widetilde{t'} - c_H t'\bmod{q}\\
\widehat{m_2} &\leftarrow \widetilde{m_2} - c_H m_2\bmod{q} &
\widehat{s} &\leftarrow \widetilde{s} - c_H s\bmod{q}\\
\widehat{r} &\leftarrow \widetilde{r} - c_H r\bmod{q} &
\widehat{r'} &\leftarrow \widetilde{r'} - c_H r'\bmod{q}\\
\widehat{r''} &\leftarrow \widetilde{r''} - c_H r''\bmod{q} &
\widehat{r'''} &\leftarrow \widetilde{r'''} - c_H r'''\bmod{q}.
\end{align*}
and add them to $\mathcal{X}$.
\end{enumerate}

After all claims are processed this way, 
 Prover sends $(c_H,\mathcal{X},\{Pr_C\},\{Pr_p\},\mathcal{C})$  to the Verifier.
 \subsection{Verification of non-revocation proof}
 
 Verifier computes
\begin{align}
\widehat{T_1}&\leftarrow E^{c_H}\cdot h^{\widehat{\rho}} \cdot \widetilde{h}^{\widehat{o}} &
\widehat{T_2}&\leftarrow E^{\widehat{c}}\cdot h^{-\widehat{m}}\cdot\widetilde{h}^{-\widehat{t}}
\end{align}
\begin{equation}
\widehat{T_3}\leftarrow\left(\frac{e(h_0\mathcal{G},\widehat{h})}{e(A,y)} \right)^{c_H} \cdot e(A,\widehat{h})^{\widehat{c}}\cdot e(\widetilde{h},\widehat{h})^{\widehat{r}}\cdot
e(\widetilde{h},y)^{-\widehat{\rho}}\cdot
e(\widetilde{h},\widehat{h})^{-\widehat{m}}\cdot
e(h_1,\widehat{h})^{-\widehat{m_2}}\cdot e(h_2,\widehat{h})^{-\widehat{s}}\\
\end{equation}
\begin{align}
\widehat{T_4}&\leftarrow\left(\frac{e(\mathcal{G},\mathrm{acc})}{e(g,\mathcal{W})z}\right)^{c_H} \cdot e(\widetilde{h},\mathrm{acc})^{\widehat{r}}\cdot
e(1/g,\widehat{h})^{\widehat{r'}}
&
\widehat{T_5}&\leftarrow D^{c_H}\cdot g^{\widehat{r}}\widetilde{h}^{\widehat{o'}}\\
\widehat{T_6}&\leftarrow  D^{\widehat{r''}}\cdot g^{-\widehat{m'}}
\widetilde{h}^{-\widehat{t'}}&
\widehat{T_7}&\leftarrow
\left(\frac{e(pk\cdot\mathcal{G},\mathcal{S})}{e(g,g')}\right)^{c_H}\cdot e(pk\cdot \mathcal{G},\widehat{h})^{\widehat{r''}}\cdot 
e(\widetilde{h},\widehat{h})^{-\widehat{m'}}\cdot
e(\widetilde{h},\mathcal{S})^{\widehat{r}}\\
\widehat{T_8}&\leftarrow \left(\frac{e(\mathcal{G},u)}{e(g,\mathcal{U})}\right)^{c_H}\cdot e(\widetilde{h},u)^{\widehat{r}}
\cdot e(1/g,\widehat{h})^{\widehat{r'''}}
\end{align}
and adds these values to $\widehat{T}$.

\subsection{Final hashing}\label{sec:finalhash}
After all claims are processed this way:
\begin{enumerate}
\item Verifier computes 
$$
\widehat{c_H}\leftarrow H(\widehat{\mathcal{T}},\mathcal{C},n_1).
$$
\item If $c_H=\widehat{c_H}$ output VERIFIED else FAIL.
\end{enumerate}


\section{Differences from the original}

This section lists the changes to the type-1 pairing-based revocation scheme:
\begin{enumerate}
    \item A new group $\mathbb{G}_2$ is introduced with generator $g'$.
    \item A new variable $\widehat{h}$ is introduced.
    \item Variable $u$ now belongs to $\mathbb{G}_2$.
    \item Variable $y$ is now computed from 
    $\widehat{h}$.
    \item New variables $g_1',\ldots, g_{2L}$ are introduced in $\mathbb{G}_2$.
    \item $v_R$ is replaced by $s$.
    \item $w, \mathrm{acc}, \sigma_i$ are computed using $g'$, not $g$.
    \item $\mathcal{W}, \mathcal{S}, \mathcal{U}$ are 
    computed using $\widehat{h}$.
    \item The second argument of the pairing function is never $h$ or $\widetilde{h}$,
    both cases are now using $\widehat{h}$.
\end{enumerate}

    \end{document}