%\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{Sequential Squaring with Precomputation}
%\author{
%}
%\institute{
% IST Austria\\ \email{\{ckamath,karen.klein,pietrzak,michael.walter\}@ist.ac.at}
%}
\begin{document}
\maketitle
\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