NEW.tex 12.2 KB
Newer Older
kklein's avatar
kklein committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151
%\documentclass[]{llncs}
\documentclass[a4paper,12pt]{article}

% \def \lncs {}

%\input{Macros.tex}

%\usepackage{rotating}
\usepackage{amssymb,amsmath,wasysym,dsfont,bm,relsize,amsbsy}
\usepackage{amsthm}
\usepackage{color}

% Controlling the margin
% \usepackage[margin=1.25in]{geometry}
% \linespread{0.9}
\bibliographystyle{alpha}
\pagestyle{plain}

%Local macros
%\DeclareAlgorithms{in,out,level,ind,sibling}
% \DeclareLanguages{}

  \newtheorem{theorem}{Theorem}
  \newtheorem{definition}{Definition}
  \newtheorem{lemma}{Lemma}
  \newtheorem{Xlemma}{Lemma}[theorem]
  \newtheorem{corollary}{Corollary}
  \newtheorem{observation}{Observation}
  \newtheorem{claim}{Claim}[theorem]
  \newtheorem{conjecture}{Conjecture}
  \newtheorem{fact}{Fact}
  \newtheorem{remark}{Remark}

%Notes
\newcommand{\kknote}[1]{\textcolor{red}{KK: #1}}


\newcommand{\out}{\leftarrow}
\newcommand{\bin}{\{0,1\}}
\newcommand{\negl}{\operatorname{negl}}
\newcommand{\poly}{\operatorname{poly}}
\newcommand{\tpre}{T_{\operatorname{pre}}}
\newcommand{\state}{\mathsf{state}}


%opening
\title{On Simple Verifiable Delay Functions}
%\author{
%}
%\institute{
%  IST Austria\\ \email{\{habusalah,ckamath,karen.klein,pietrzak,michael.walter\}@ist.ac.at} 
%}

\begin{document}
\maketitle

\subsection*{Precomputation}
The security of the protocol from [P18] relies on the assumption that the fastest algorithm which given $x\in QR_N$ uniformly at random can compute $y=x^{2^T}$ requires $T$ sequential squarings. The following Lemma shows that any precomputation of (parallel) time $\tpre$ doesn't make this task easier.

\begin{lemma}
For any algorithm $\mathcal{A}$ that initially receives as input $(N,T)$ and does some precomputation of (parallel) time $\tpre=\poly(\lambda)$, then receives a uniformly random challenge $x\in QR_N$ and computes $y=x^{2^T}$ within time less than $T$, there exists an algorithm $\mathcal{B}$ which on input $(N,x',T')$ with $T'>\tpre$ outputs $y'=(x')^{2^{T'}}$ within time less than $T'$.
\end{lemma}
\begin{proof}
Let $\mathcal{A}=(\mathcal{A}_0,\mathcal{A}_1)$ be such an algorithm.
We construct an algorithm $\mathcal{B}$ that on input $(N,x',T')$ runs in time less than $T'$ and outputs $y'=(x')^{2^{T'}}$ as follows: On receipt of $(N,x',T')$, $\cal B$ runs $\mathcal{A}_0(N,T)$ with $T:=T'-\tpre$ and simultaneously computes $x:=(x')^{2^{\tpre}}$. This takes time $\tpre$; let $\state$ be the output of $\mathcal{A}_0$. Next, $\cal B$ invokes $\mathcal{A}_1$ on input $(N,x,T,\state)$. Note that $x$ is indeed uniformly random in $QR_N$ since the function $.^{2^{T'}}:QR_N\to QR_N$, $x\mapsto x^{2^{T'}}$ is 1-to-1 for this choice of modulus $N$ (see [BBS86, Lemma 1]). Thus, by assumption, $\mathcal{A}_1(N,x,T,\state)$ runs in time $\tau<T$ and outputs $y=x^{2^T}$. Since $y=(x')^{2^{T'}}$, this gives a solution to $\cal B$'s challenge. Neglecting the cost of computing $T=T'-\tpre$, $\cal B$ runs in parallel time $\tpre+\tau<\tpre+T=T'$, which proves the claim.
\end{proof}


\subsection*{Unique PoSW}
One can slightly change the protocol from [P18] to obtain a \emph{unique} verifiable delay function, i.e., a protocol where not only the statement $y$ is unique but also the corresponding proof $\pi=\{\mu'_i\}_{i\in[\lceil\log T\rceil-2]}$. To this aim, note that for our choice of modulus $N=pq$ with $p\equiv q\equiv 3\mod 4$ the squaring function $.^2:\mathbb{Z}_N^*\to QR_N$, $x\mapsto x^2$ is 4-to-1, and its restriction to quadratic residues is 1-to-1 (see [BBS86, Lemma 1]). However, there is no efficient algorithm known for deciding quadratic residuosity. Fortunately, the Jacobi symbol can be used to sort out two of the four square roots of a given quadratic residue $x$, namely those with Jacobi symbol $-1$. For the two roots $x_1,x_2$ with $(\frac{x_1}{N})=(\frac{x_2}{N})=1$, it holds: $x_2=N-x_1$. Thus, we suggest the following modifications to the halving protocol from [P18]:

\begin{itemize}
\item Let $\mu_{i}'$ be the unique element in $\{x_i^{2^{T_i/2-1}}, N-x^{2^{T_i/2-1}}\}\cap[0,\lfloor N/2\rfloor]$.
\item If $\mu_i'\notin\mathbb{Z}_N^*\cap [0,\lfloor N/2\rfloor]$ or the Jacobi symbol\footnote{Note, computing the Jacobi symbol (almost) does not increase the computational cost: It's basically Euclid's algorithm for computing the greatest common divisor and this needs to be done anyway to check the first condition (see, e.g., [lecture notes https://people.csail.mit.edu/vinodv/6892-Fall2013/Angluin.pdf, Theorem 33]).} $(\frac{\mu_i'}{N})\neq 1$, then $\mathcal{V}$ rejects.
\end{itemize}

\begin{lemma}
The modified protocol is unique.
\end{lemma}
\begin{proof}

\end{proof}


\subsection*{Zero-knowledge PoSW}
In many applications, it might be useful to proof that one computed $y=x^{2^T}$ without actually reveiling $y$ and the corresponding proof $\pi=\{\mu'_i\}_{i\in[\lceil\log T\rceil-2]}$. In the following we define a notion of computational zero-knowledge proof of knowledge that captures this idea in our context. In the following, we show that the simple and efficient verifiable delay function from [W18] can be extended to proof the knowledge of statement $x^{2^T}$ in zero-knowledge.
\kknote{Unfortunately, this does not seem to be the case for the construction from [P18]: While we can construct a simulator who outputs accepting proofs in time $\poly(\log T)$, these proofs can be distinguished from correct ones in approximately the same time.}

\begin{definition}
Let $\lambda$ be a security parameter, $T$ a time parameter, and $f,g:\mathbb{N}\to\mathbb{R}$ two sublinear functions. Let $\Pi$ be a two-party protocol between a prover $\mathcal{P}$ and a verifier $\mathcal{V}$, and $(x,y)$ an instance to the protocol, where $x$ is the common input and $y$ the secret the prover wants to prove knowledge of. Then $\Pi$ is $(T,f(T))$-\emph{computational zero-knowledge} (for time parameter $T$) if the following properties hold:
\begin{itemize}
\item \textbf{Correctness: }For honest parties $\mathcal{P}$ and $\mathcal{V}$, the protocol accepts within time $f(T)$ with probability $1$.
\item \textbf{Soundness: }For any instance $(x,y)$ and any deterministic prover $\hat {\mathcal{P}}$ that runs in time $f(T)$ and succeeds with probability $p>\negl(\lambda)$, one can extract $y$ from $\hat{P}(x,y)$ in time $1/p\cdot f(T)$ with probability $1-\negl(\lambda)$.
\item \textbf{Computational zero-knowledge: }There exists a simulator $\mathcal{S}$ who after receipt of $x$ outputs a transcript $\mathcal{S}(x)$ in time $f(T)$ such that no algorithm running in time $f(T)$ can distinguish between $\mathcal{V}$'s view on the protocol $\Pi(x,y)$ (including $\mathcal{V}$'s random coins) and $\mathcal{S}(x)$ \kknote{with probability $>\negl(\lambda)$}.
\end{itemize}
\end{definition}

Consider the following extension of the protocol from [W18] to prove the knowledge of the solution $y=x^{2^T}$ to a puzzle $(N,x,T)$ without revealing $y$ to the verifier. Let $\mathcal{R}=[0,2^\lambda]$.

\paragraph*{Zero-Knowledge protocol based on [P18].}
\begin{enumerate}
\item Setup: $\mathcal{P,V}$ receive an instance $(N,x,T)$, $\mathcal{P}$ additionally gets $y=x^{2^T}$ and $\nu=\{\nu_i\}_{i\in[\sqrt{T}]}$.
\item The verifier $\mathcal{V}$ chooses $h\out\mathcal{R}$ uniformly at random, computes a commitment $c=H(h)$ (where $H$ is a collision resistant hash function) and sends it to $\mathcal{P}$.
\item The prover $\mathcal{P}$ chooses $\alpha\out\mathcal{R}$ uniformly at random and sends $x^\alpha$ to the verifier $\mathcal{V}$.
\item $\mathcal{V}$ computes $x^*=x^\alpha x^h$, and sends $h$ to $\mathcal{P}$.
\item  $\mathcal{P}$ checks whether $c=H(h)$; if not it aborts. Otherwise, $\mathcal{P}$ computes $y^*=y^{\alpha+h}=(x^*)^{2^T}$ and $\nu_i^*=(\nu_i)^{\alpha+h}$ for $i\in[\sqrt{T}]$. 
\item $\mathcal{P}$ and $\mathcal{V}$ run the PoSW protocol [W18] on $(N,x^*,T)$ to compute a proof $\pi^*$ for $(x^*,y^*)$.
\item $\mathcal{V}$ checks correctness of the proof $(N,x^*,T,y^*,\pi^*)$ as in [W18].
\end{enumerate}

\begin{lemma}\label{lem:zk}
Assuming that given $x\in QR_N$ the fastest algorithm to compute $y=x^{2^T}$ requires $T$ sequential squarings and that no algorithm can distinguish $y$ from a uniform $y'\out QR_N$ in time less than $\exp(\lambda)$, the above protocol is $(T,f(T))$-computational zero-knowledge \kknote{for some $f(T)=O(\log T)$}.
\end{lemma}
\begin{proof}
The correctness property is naturally satisfied whenever $\mathcal{P,V}$ honestly follow the protocol.\\
For soundness, consider a deterministic prover $\hat{\mathcal{P}}$ and an extractor $\mathcal{E}$ who rewinds $\hat{\mathcal{P}}$ several times. From any accepting run, $\mathcal{E}$ receives $y^*=y^{h+\alpha}$ for some uniformly random $h\out\mathcal{R}$. Assume there are three accepting runs with values $h_1,h_2,h_3$ such that $\gcd(h_1-h_2,h_1-h_3)=1$. \kknote{Missing: probability that random integers are coprime.}%%%
Then there exist integers $\beta_1,\beta_2$ such that $\beta_1(h_1-h_2)+\beta_2(h_1-h_3)=1$, and these are easy to compute (using Euclid's algorithm%?
\kknote{check size of $\beta_1,\beta_2$}
). Thus, after receipt of $y_1^*=y^{h_1+\alpha}$, $y_2^*=y^{h_2+\alpha}$, $y_3^*=y^{h_3+\alpha}$ together with the values $h_1,h_2,h_3\in\mathcal{R}$, the extractor $\mathcal{E}$ can compute $y=\big(y_1^*(y_2^*)^{-1})^{\beta_1}(y_1^*(y_3^*)^{-1}\big)^{\beta_2}$.\\
To proof zero-knowledge, define a simulator $\mathcal{S}$ as follows: Upon receipt of $x\in QR_N$, $\mathcal{S}$ chooses uniform $\beta\out\mathcal{R}$, $h\out \mathcal{R}$, and computes $\tilde{x}=\bar{x}^\beta x^{-h}$ and a proof $\bar{\pi}=\{\bar{\mu}'_{i}\}_{i\in[\lceil\log T\rceil-2]}$ for $\bar{y}=(\bar{x}^\beta)^{2^T}$.\footnote{Note, rerandomizing by $\beta$ allows $\mathcal{S}$ to simulate proofs for several instances $x\in QR_N$.} The simulator outputs $\mathcal{S}(N,x,T)=(H(h),\tilde{x},h,\bar{y},\bar{\pi})$, which is indistinguishable from $(H(h),x^\alpha,h,y^*,\pi^*)$ in the honest transcript within time $\poly(\lambda,\log T)$.
\end{proof}

\begin{remark}
We can also consider a non-interactive version of the above protocol which can be proven secure in the random oracle model.
\end{remark}

\paragraph*{Zero-Knowledge protocol based on [W18].}

We can also extend the VDF from [W18] to a zero-knowledge protocol in a similar manner as above. To this aim, note that the proof $\pi=x^{\lfloor 2^T/B\rfloor}$ for a statement $(x,y=x^{2^T})$ can be computed in time $\log{T}$ when $\sqrt{T}$ space as well as $\sqrt{T}$ parallelism is available.

\begin{claim}
Using $\sqrt{T}$ stored values $\{\nu_i\}_{i\in[\sqrt{T}]}$, all being powers of $x$ obtained during the computation of $y=x^{2^T}$, one can compute a proof $\pi=x^{\lfloor 2^T/B\rfloor}$ for $(x,y)$ in time $\log{T}$ with $\sqrt{T}$ parallelism. \kknote{To be proved in detail}
\end{claim}

If we run the protocol from [W18] as a subroutine in step 6 of the above construction, we obtain a $(T,\log T)$-computational zero-knowledge proof of knowledge of $y=x^{2^T}$. Unfortunately, the improved bound $\log T$ can only be achieved when using $\sqrt{T}$ parallelism. This is in contrast to the construction based on [P18] where proofs can be computed in time $\sqrt{T}$ using $\sqrt{T}$ space but no parallelism. \kknote{Unlike for [P18], here we do not need to allow precomputation.}

\begin{lemma}
Assuming that given $x\in QR_N$ the fastest algorithm to compute $y=x^{2^T}$ requires $T$ sequential squarings and that no algorithm can distinguish $y$ from a uniform $y'\out QR_N$ in time less than $\exp(\lambda)$, the above protocol is $(T,\log T)$-computational zero-knowledge.
\end{lemma}
\begin{proof}
Clearly, correctness follows immediately and soundness similarly to the proof of Lemma \ref{lem:zk}.
To proof zero-knowledge, define a simulator $\mathcal{S}$ as follows: On input $(N,x,T)$, $\mathcal{S}$ samples $h,\alpha\out\mathcal{R}$ and computes $x^*=x^{\alpha+h}$, just as in the real protocol. Then it samples a large prime $B$ \kknote{uniformly from the domain of $H_{prime}$} and $c\out\mathcal{R}$, computes $y^*=(x^*)^{cB+r}$, where $r=2^T\mod B$, and sets $\pi^*=(x^*)^c$. Finally, $\mathcal{S}$ outputs $(H(h),x^\alpha,h,y^*,\pi^*)$.
\end{proof}

As in the case of [P18], the non-interactive version of the above zero-knowledge protocol can be proven secure in the random oracle model using the programmability of random oracles.

%%%references
%AngluinLecturenotes, BlumBlumShub86, Pietrzak18, Wesolowsi18
\end{document}