Sequential squaring with precomputation.tex 9.93 KB
 kklein committed Jul 15, 2019 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 %\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  Krzysztof Pietrzak committed Jul 22, 2019 47 \title{Verifiable Delay Functions in Fixed Groups of Unknown Order}%Sequential Squaring with Precomputation}  kklein committed Jul 15, 2019 48 49 50 51 52 53 54 55 56 %\author{ %} %\institute{ % IST Austria\\ \email{\{ckamath,karen.klein,pietrzak,michael.walter\}@ist.ac.at} %} \begin{document} \maketitle  Krzysztof Pietrzak committed Jul 22, 2019 57 58 59 60 61 62 63 64 65 66 67 \begin{abstract} 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 \end{abstract}  kklein committed Jul 15, 2019 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 \section{Introduction} 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 (ethereum.org) and Chia (chia.net). 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. \section{Preliminaries} \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\tpre$ outputs $y'=(x')^{2^{T'}}$ within time less than $T'$ (with the same probability $\epsilon$). \end{lemma} \begin{proof} 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