VDF.tex 11.3 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 152 153
%\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}}


%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 $T$ doesn't make this task easier.

\begin{lemma}
For any algorithm $\mathcal{A}(N,T)$ that does some precomputation of (parallel) time $T$ and when receiving an input $x\in QR_N$ computes $y=x^{2^T}$ within time $\tau<T$, there exists an algorithm $\mathcal{B}$ which on input $(N,x',2T)$ outputs $y'=(x')^{2^{2T}}$ within time less than $2T$.
\end{lemma}
\begin{proof}

\end{proof}

{\color{cyan}OLD:
However, in the following we will assume that each algorithm is allowed to run some precomputation of time $T$ on input $(N,T)$ before receiving an instance $x\in QR_N$.
}

\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. Note, that we allow the simulator to do some precomputation of time $T$.

{\color{cyan}OLD:
\begin{definition}
Let $\lambda$ be a security parameter and $T$ a time parameter. 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. Then $\Pi$ is \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 $\poly(\log T)$ with probability $1$.
\item \textbf{Soundness: }For any instance $(x,y)$ and any deterministic prover $\hat {\mathcal{P}}$ that runs in time $\poly(\log T)$ and succeeds with probability $p>\negl(\lambda)$, one can extract $y$ from $\hat{P}(x,y)$ in time $1/p\cdot\poly(\log T)$ with probability $1-\negl(\lambda)$.
\item \textbf{Computational zero-knowledge: }There exists a simulator $\mathcal{S}$ who runs some precomputation of time $T$ and after receipt of $x$ outputs a transcript $\mathcal{S}(x)$ in time $\poly(\log T)$ such that no algorithm running in time $\poly(\lambda)$ can distinguish between $\mathcal{V}$'s view on the protocol $\Pi(x,y)$ (including $\mathcal{V}$'s random coins) and $\mathcal{S}(x)$.
\end{itemize}
\end{definition}

\begin{remark}
One could also consider a slightly different definition where, instead of allowing all algorithms to do some precomputation of time $T$, they get some additional information. In the construction below this additional information would be $\{(x')^{2^{T/2^i}}\}_{i\in [0,\lceil\log T\rceil]}$ for some uniformly random $x'\out QR_N$, which can be randomized by each party to get arbitrarily many instances $\{(x'')^{2^{T/2^i}}\}_{i\in [0,\lceil\log T\rceil]}$ for uniformly distributed $x''\out QR_N$.
\end{remark}
}

{\color{blue}NEW SUGGESTION:
\begin{definition}\label{zk}
Let $\lambda$ be a security parameter, $\epsilon\in(0,1)$, and $T$ a time parameter. Let $\Pi$ be a two-party protocol between a prover $\mathcal{P}$ and a verifier $\mathcal{V}$, $x$ an instance to the protocol and $(y,\nu)$ some secret information of the prover. Then $\Pi$ is \emph{$(T,\epsilon)$-computational zero-knowledge} (with respect to $y$) if the following properties hold:
\begin{itemize}
\item \textbf{Correctness: }For honest parties $\mathcal{P}$ and $\mathcal{V}$, the protocol accepts within time $T^\epsilon$ with probability $1$.
\item \textbf{Soundness: }For any instance $(x,y,\nu)$ and any deterministic prover $\hat {\mathcal{P}}$ that runs in time $T^\epsilon$ and succeeds with probability $p>\negl(\lambda)$, one can extract $y$ from $\hat{P}(x,y,\nu)$ in time $1/p\cdot T^\epsilon$ with probability $1-\negl(\lambda)$.
\item \textbf{Computational zero-knowledge: }There exists a simulator $\mathcal{S}$ who runs in time $T^\epsilon$ and outputs a transcript $\mathcal{S}(x)$ such that no algorithm running in time $T^\epsilon$ can distinguish between $\mathcal{V}$'s view on the protocol $\Pi(x,y,\nu)$ (including $\mathcal{V}$'s random coins) and $\mathcal{S}(x)$.
\end{itemize}
\end{definition}

\begin{remark}
Note, that the additional input $(y,\nu)$ to the prover comprises some additional information $\nu$ that helps the prover to proof correctness of his secret knowledge $y$. In the construction below, this additional information $\nu$ would consist of the $\sqrt{T}$ values stored during computation of $y$ that allow to compute $\pi=\{\mu'_i\}_{i\in[\lceil\log T\rceil-2]}$ within time $T^\epsilon$ with $\epsilon =1/2$.
\end{remark}
}

Consider the following extension of the protocol from [P18] to prove the knowledge of the solution $y=x^{2^T}$ to a puzzle $(N,x,T)$ without revealing $y$ to the verifier, where we assume that the prover stored $\sqrt{T}$ powers of $x$, denoted by $\nu=\{\nu_i\}_{i\in\sqrt{T}}$, which allow him to compute an accepting proof $\{\mu'_i\}_{i\in[\lceil\log T\rceil-2]}$ for $(N,x,T,y)$ within time $\sqrt{T}$. Let $\mathcal{R}=[0,2^\lambda]$.

\paragraph*{Zero-Knowledge protocol}
\begin{itemize}
\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 [P18] on $(N,x^*,T)$ to compute a proof $\pi^*=\{(\mu_i^*)'\}_{i\in[\lceil\log T\rceil-2]}$ for $(x^*,y^*)$.
\item $\mathcal{V}$ checks correctness of the proof $(N,x^*,T,y^*,\pi^*)$ as in [P18].
\end{itemize}

\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,1/2)$-computational zero-knowledge.
\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}$.\\
{\color{cyan}OLD:
To proof zero-knowledge, define a simulator $\mathcal{S}$ as follows: First, during the precomputation phase, on input $(N,T)$, $\mathcal{S}$ chooses $\bar{x}\out QR_N$ uniformly at random and computes $\bar{\nu_i}=\bar{x}^{2^{T/2^i-1}}$ for $i\in[\lceil\log T\rceil-2]$ as well as $\bar{y}=\bar{x}^{2^T}$. 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}

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