Sequential squaring with precomputation.tex 9.93 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

% \def \lncs {}



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

%Local macros
% \DeclareLanguages{}


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


Krzysztof Pietrzak's avatar
Krzysztof Pietrzak committed
\title{Verifiable Delay Functions in Fixed Groups of Unknown Order}%Sequential Squaring with Precomputation}
kklein's avatar
kklein committed
48 49 50 51 52 53 54 55 56
%  IST Austria\\ \email{\{ckamath,karen.klein,pietrzak,\}} 


Krzysztof Pietrzak's avatar
Krzysztof Pietrzak committed
57 58 59 60 61 62 63 64 65 66 67
A verifiable delay function (VDF) on input a challenge $x$ and time parameter $T$ outputs a value $y$ together with a proof $\pi$. The value $y$ can be computed in $T$ sequential steps, but not much faster, even with high parallelism. $\pi$ is an efficiently verifiable proof that certifies that $y$ is correct. 

VDFs were only recently introduced, but have already found many applications, most prominently in blockchain protocols. Currently, the only practical constructions of VDFs compute a value $y=x^{2^T}$ by squaring $x$ sequentially $T$ times in a group of unknown order.

Two such groups have been suggested, RSA groups $Z_N^*$ (where the group operation is multiplication modulo a product $N=p\cdot q$ of two large primes $p,q$) and class groups of an imaginary quadratic field. 

The RSA group has the advantage 

kklein's avatar
kklein committed
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
Verifiable delay functions (VDFs) are functions whose evaluation requires a prescribed number of sequential operations (a \emph{delay}), but at the same time are \emph{verifiable} in the sense that they offer an efficient way of proving the correctness of the output: Given an input $x$, the prover does not only compute the output $y$ of the function but also provides a proof $\pi$, which allows the verifier to verify that $y$ is indeed the correct output of the function much more efficiently than evaluating the function himself.\\
The design and implementation of VDFs have become a hot topic in cryptography especially due to their application in several decentralized cryptocurrencies such as Ethereum ( and Chia ( The two most practical proposals are those by Pietrzak \cite{P18} and Wesolowski \cite{W18}. Both of them are inspired by the timelock puzzle of Rivest, Shamir and Wagner \cite{RSW96} and rely on the assumption that, given a description of a group of unknown order of size exponential in the security parameter $\lambda$ and a uniformly random group element $x$, the fastest algorithm to compute $x^{2^T}$ for some time parameter $T=\poly(\lambda)$ requires $T$ sequential squarings.\\
Unfortunately, without a trusted setup it seems to be a quite challenging task to efficiently generate groups of unknown order. Currently, there are two different approaches: The first one is to use an RSA group, where the modulus $N$ is generated as the product of two safe primes via multi-party computation. The second, on the other hand, is to use the class group of an imaginary quadratic number field, which can be uniquely defined by choosing its discriminant and also allows efficient group operations, while efficiently computing its order (i.e., the class number) has been a longstanding open problem in computational algebraic number theory. No matter which of these two option is used, it would be much more convenient to generate a group once and forever than choosing a fresh one for each application of the VDF.\\
However, if the group (and potentially also the time parameter $T$) is known ahead of time, we need to make a (seemingly) stronger assumption, namely, that even after doing some precomputation of time $\tpre=\poly(\lambda)$ computing $x^{2^T}$ for a fresh uniformly random group element $x$ still requires $T$ sequential group operations. In this work we prove that the latter assumption is actually implied by the former one and, thus, justify the choice of recent proposals to reuse the setup parameters.


\subsection{The Assumptions}
In the following we state our assumptions for arbitrary groups.

\begin{definition}[Sequential Squaring Assumption]\label{ssa}
Let $\lambda$ be a security parameter. The \emph{sequential squaring assumption} holds in a group $\cal G$ if for all time parameters $T\in\mathbb{N}$, $T=\poly(\lambda)$ and all algorithms $\cal A$ running in time $\tau<T$, the probability that $\cal A$ on input a description of the group $\cal G$ and a uniformly random element $x\in\cal G$ outputs $y=x^{2^T}$ is negligible in $\lambda$.

In particular, the sequential squaring assumption states that sequentially computing $x_i=x_{i-1}^2$ for $i=1,\dots,T$ with $x_0:=x$ is essentially the best algorithm to compute $x^{2^T}$. Clearly, this can only hold in sufficiently large (superpolynomial in the security parameter $\lambda$) groups. Furthermore, note that the assumption also cannot hold if the order of the group is known since reducing $2^T$ modulo $|\cal G|$ allows to compute $x^{2^T}$ as $x^{2^T\mod |\mathcal{G}|}$.

\begin{definition}[Strong Sequential Squaring Assumption]\label{sssa}
Let $\lambda$ be a security parameter, $\cal G$ a finite group, and $\tpre=\poly(\lambda)$ a time parameters. The \emph{strong sequential squaring asssumption} holds in $\cal G$ if for all time parameters $T\in\mathbb{N}, T=\poly(\lambda)$, and all algorithms $\mathcal{A}$, which on input $(\mathcal{G},T)$ first run some precomputation of time $\tpre$, then receive some uniformly random element $x\in\cal G$ and run for additional time $\tau<T$, the probability that $\mathcal{A}$ outputs $y=x^{2^T}$ is negligible in $\lambda$.

\subsection{RSA Groups from Strong Primes}

For Pietrzak's protocol it is necessary to consider groups of unknown order where, additionally, it is hard to find low-order elements. This is clearly satisfied whenever we consider the subgroup $QR_N$ of quadratic residues in an RSA group where the modulus $N$ is chosen as the prodoct of two distinct \emph{strong} primes, i.e., $N=pq$ with $p=2p'+1\neq q=2q'+1$ and $p,q,p',q'$ prime. While distinguishing whether a given element is a quadratic residue seems to be hard, it is easy to sample uniform elements from $QR_N$ by sampling a uniform element from $\mathbb{Z}_N$ and squaring it.\\
In the following we represent $\mathbb{Z}_N$ by $N$ and say that $\mathbb{Z}_N$ satisfies Assumption \ref{ssa} or \ref{sssa} if the assumption is satisfied for the subgroup $QR_N$.

\section{Equivalence of the Assumptions for RSA Groups}

%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.

The following Lemma will allow us to prove equivalence of Assumptions \ref{ssa} and \ref{sssa} for RSA groups whenever the modulus $N$ is the product of two strong primes.

Let $N=pq$ be the product of two distinct strong primes. For any algorithm $\mathcal{A}$ that initially receives as input $(N,T)$ %the description of a group $\cal G$ and a time parameter $T$, 
and does some precomputation of (parallel) time $\tpre$, then receives a uniformly random challenge $x\in QR_N$ %%%
and computes $y=x^{2^T}$ within time less than $T$ (with probability $\epsilon$), there exists an algorithm $\mathcal{B}$ which on input %$(\mathcal{G},x',T')$ with $x'\in\mathcal{G}$ 
$(N,x',T')$ with $x'\out QR_N$ uniformly random and $T'>\tpre$ outputs $y'=(x')^{2^{T'}}$ within time less than $T'$ (with the same probability $\epsilon$).
Let $\mathcal{A}=(\mathcal{A}_0,\mathcal{A}_1)$ be such an algorithm, where $\mathcal{A}_0$ denotes the partial algorithm which runs the precomputation and $\mathcal{A}_1$ denotes the algorithm run after $x$ is given to $\cal A$.
We construct an algorithm $\mathcal{B}$ that on input $(N,x',T')$ %$(\mathcal{G},x',T')$
runs in time less than $T'$ and outputs $y'=(x')^{2^{T'}}$ as follows: On receipt of $(N,x',T')$%$(\mathcal{G},x',T')$
, $\cal B$ runs $\mathcal{A}_0(N,T)$ %$\mathcal{A}_0(\mathcal{G},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)$. %$(\mathcal{G},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 e.g. \cite[Lemma 1]{BBS86}). %%%%
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.

Let $\lambda$ be a security parameter and $N=pq$ be the product of two distinct strong primes of bitsize $\lambda$. If the sequential squaring assumption holds for $\mathbb{Z}_N$%$\cal G$
, then also the strong sequential squaring assumption holds in $\mathbb{Z}_N$.%$\cal G$.