
\section{Preliminaries}\label{sec:prelim}
Operators $||$ and $|x|{=\log x}$ denote the concatenation and the bit length of variable $x$, respectively and  $ \log $ denotes $ \log_2 $.


 


\begin{definition}\label{def:Generic} \normalfont 
	
	A  signature scheme consists of three algorithms $  \ensuremath {\mathsf{SGN}}{\xspace} = ({\ensuremath {\mathsf{Kg}}{\xspace},\ensuremath {\mathsf{Sig}}{\xspace},\ensuremath {\mathsf{Ver}}{\xspace}}) $ defined as follows.
	
	\begin{itemize}\normalfont
		\item[--] $ (\ensuremath {\mathit{sk}}{\xspace}, \ensuremath {\mathit{PK}}{\xspace}) \leftarrow \ensuremath {\mathsf{SGN.Kg}}{\xspace}(1^\kappa) $: Given the security parameter $ \kappa $, it outputs the private and public key pair $ (\ensuremath {\mathit{sk}}{\xspace},\ensuremath {\mathit{PK}}{\xspace}) $.
		
		\item[--] $ \sigma \leftarrow \ensuremath {\mathsf{SGN.Sig}}{\xspace}(m,\ensuremath {\mathit{sk}}{\xspace}) $:
		Given the message   $ m $ and the signer's private key  $\ensuremath {\mathit{sk}}{\xspace}$, it outputs the signature $ \sigma $.
		\item[--] $ b \leftarrow \ensuremath {\mathsf{SGN.Ver}}{\xspace}(m, \sigma, \ensuremath {\mathit{PK}}{\xspace}) $: Given a message-signature pair   ($m,\sigma $), and public key  $\ensuremath {\mathit{PK}}{\xspace}$, outputs $b \ensuremath {\leftarrow}{\xspace} \{0,1\}$
	
	\end{itemize}
\end{definition}
In ordinary digital signatures, if the private key of the signer is compromised, all the signatures that are generated by the signer (past and future) become forgeable.  In forward secure signatures, the previously computed signatures remain unforgeable even if the current private key of the signer is compromised. 
 
 \subsection{Malkin, Micciancio and Miner (MMM) Scheme}
 \ensuremath {\mathsf{MMM}}{\xspace}~\cite{MaMiMi02} is a series of constructions to transform standard digital signatures $\ensuremath {\mathsf{SGN}}{\xspace}$ to forward secure   signature.  \ensuremath {\mathsf{MMM}}{\xspace}~is composed of the sum (referred to as $\bigoplus$) and product (referred to as $\bigotimes$) composition algorithms. In the sum composition, given a digital signature $\ensuremath {\mathsf{SGN}}{\xspace}$ with $t$ forward-secure signing capability, the sum composition can generate $2t$ signatures in total. For instance, given a standard one-time signature, by iteratively applying sum composition  $\log t$ times, one can obtain a forward-secure signature with $t$ signing capability.  In the product composition, given a digital signature $\ensuremath {\mathsf{SGN}}{\xspace}$ with $t$ forward-secure signing capability, the product composition can generate $t^{2}$ signatures in total. 



The main  \ensuremath {\mathsf{MMM}}{\xspace}~construction has an upper tree and multiple lower trees, which are created with the iterative execution of sum composition and are linked with the upper tree with the product composition. Lower trees are generated on the go with increasing levels of height.   This minimizes the key generation/update cost and makes the overhead of \ensuremath {\mathsf{MMM}}{\xspace}~depend on "messages signed so far" but not the total number of time periods available. Thus, the lower trees are created as needed on the go. \ensuremath {\mathsf{MMM}}{\xspace}~increases the levels in each iteration to sign more messages with a slight increase in cost (generation of a higher tree). Overall, in \ensuremath {\mathsf{MMM}}{\xspace}, the costs are either logarithmic or constant with respect to $t<T$ (i.e., $t$ is the total number of messages signed so far, and $T$ is the maximum number of signatures) and the size of the $\ensuremath {\mathit{PK}}{\xspace}$ is a small-constant. We refer curious reader to \cite{MaMiMi02} for the details.

Another interesting composition in  \cite{MaMiMi02} is the iterated product composition.  In this construction, a new forward secure scheme is achieved by applying the sum composition once and then iterate the product composition to this two-time signature to get $ 2^{2^{\log\log t}} $ and get $ t $  time signature scheme.  







 








\section{Performance Analysis} \label{sec:PerformanceAnalysis}
In this section, we compare the performance of  different instantiations of \ensuremath {\mathsf{FROG}}{\xspace}~with  its counterparts. We also discuss the performance of some of the selected alternative constructions described in Section \ref{sec:contrib}. As mentioned, we also instantiated forward secure schemes using the iterated product composition technique presented in \cite{MaMiMi02}. For the sake of clarity we denote instantions with this technique as \ensuremath {\mathsf{FROG}^*}{\xspace}. 









\subsection{Analytical Performance}
We denote the signature, public key, and private key sizes of the base signature scheme as $|\sigma|$, $|pk|$ and $|sk|$, respectively. We denote the size of hash output as $|H|$.   $\ensuremath {\mathsf{FROG}}{\xspace}_{\sigma}$, $\ensuremath {\mathsf{FROG}}{\xspace}_{sk}, \ensuremath {\mathsf{FROG}}{\xspace}_{pk}$ denote the signature, public key, and private key sizes of \ensuremath {\mathsf{FROG}}{\xspace}.  $H$ denotes a hash operation (also a PRF call for the simplicity). \ensuremath {\mathsf{FROG.Sig}}{\xspace}~includes the amortized update cost for a given composition.  Following the guidelines given by NIST\footnote{https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/faqs}, we set $ t=2^{64} $.  We present the analytical performance of our instantiations (\ensuremath {\mathsf{FROG}}{\xspace}~and \ensuremath {\mathsf{FROG}^*}{\xspace}) in Table \ref{tab:analytical}.  As depicted, \ensuremath {\mathsf{FROG}^*}{\xspace}~provides compact signature and private key sizes with the cost of  an increased computational overhead.




















\subsection{Experimental Performance Evaluation and Comparisons} \label{subsec:PerformanceEval}
We now elaborate the detail of our performance analysis and comparison with XMSS-MT. We use the similar instantiations of XMSS-MT in  \cite{XMSS:LMS:Compare:Panos:2017:IACR}. We note that as also highlighted in  \cite{XMSS:LMS:Compare:Panos:2017:IACR}, the HSS-LMS is slightly more computationally efficient than XMSS-MT, but we currently focus on XMSS-MT standard due to  its ease of test.  We compare \ensuremath {\mathsf{FROG}}{\xspace}~and \ensuremath {\mathsf{FROG}^*}{\xspace}~and its counterpart in terms of (i) private key, signature and public key sizes, and (ii) key generation, signature generation,  and  signature verification.  We run our experiments on an i7 Kaby Lake equipped with a  2.9 GHz Quad-Core Intel Core and 8 GB RAM. 

We instantiated both  \ensuremath {\mathsf{FROG}}{\xspace}~and \ensuremath {\mathsf{FROG}^*}{\xspace} with three signature schemes: (i) Dilithium \cite{dilithium}: For this scheme we used the recommended parameters set  (see Table 2 in  \cite{dilithium}) which provides 138-bits of security with signature size and public key size  of 2701  and 1472 bytes, respectively. We used this scheme as it is one of the prominent lattice-based signature schemes for NIST post-quantum standardization process. We use the reference implementation and the AVX2 implementation  (increases parallelism and throughput in floating point SIMD calculations). (ii) BLISS \cite{BLISS}: For this scheme we used BLISS-II parameters set (see Table 1 in \cite{BLISS}) which provides 128-bits of security. We note that we have selected BLISS due to its smaller signature size. The signature and public key sizes in our selected variants are $ 625 $ and 875 bytes, respectively. BLISS using Gaussian Sampling to produce a one-time masking term in the signature generation and therefore, obtains a better signature size as compared to Dilithium \cite{dilithium}, with a cost of signature generation performance. Additionally we note that the Gaussian Sampling  technique is susceptible to side-channel attacks. We stress that each BLISS private/public key pair is used only once (minimal side-channel attack risk). We used the reference implementation for BLISS.  (iii) WOTS$ ^+  $ \cite{WOTSP}: We used  a variant with 128-bits of security with $ w=4 $ and $ m=n=256 $.  We instantiated it with both  SHA256   and SHAKE256.  


As depicted in Table \ref{tab:Laptop}, we compared our instantiations with six different instantiations of   XMSS-MT-SHA256    with different parameters sizes, since, based on our initial benchmark, XMSS-MT with  SHA256 showed significantly better performance than the one instantiated with SHAKE256.  We adopted the implementation from \cite{XMSSGit}. For XMSS-MT we considered $ t =2^{20}, 2^{40}, 2^{60} $. For $ t =2^{20} $, we considered  the number of subtrees to be $ 2 $ and $ 4 $.  For $ t =2^{40} $, we considered  the number of subtrees to be $ 2 $.  For $ t =2^{60} $, we considered  the number of subtrees to be $ 3 $ $ 6 $, and $ 12$. 
 
 
Following NIST's recommendation,  both \ensuremath {\mathsf{FROG}}{\xspace}~and \ensuremath {\mathsf{FROG}^*}{\xspace}~allow for up to $ t= 2^{64} $ signature generation. \ensuremath {\mathsf{FROG}}{\xspace}~performs significantly better than all of XMSS-MT variants for key generation, signature generation and signature verification. However, as a trade-off, it has larger private key sizes and slightly larger signature sizes. However, since private key is only stored on the signer's machine, and does not affect communication overhead. Our \ensuremath {\mathsf{FROG}^*}{\xspace}~variants provides better signature and private key sizes, with the cost of added performance overhead on all other algorithms. however, it is still shown to be more efficient than all other XMSS-MT variants. 
 
 \section*{Acknowledgment}
The work of Attila A. Yavuz is supported by the NSF CAREER Award CNS-1917627 and an unrestricted gift via Cisco Research Award.
 












\section{The Proposed Scheme FROG}  \label{sec:contrib}
We   instantiate  the generic constructions given in \cite{MaMiMi02} with the existing efficient lattice-based  \cite{dilithium,BLISS} and hash-based \cite{WOTSP}  post-quantum signatures to create a    series new post-quantum forward-secure signature we call \ensuremath {\mathsf{FROG}}{\xspace}~({\em Forward-secuRe pOst-quantum siGnature}) . 


\subsection{Design Rationale} 
In our design, we aim to achieve high computation efficiency while keeping  sub-linear signature/key sizes, all with signing capabilities scalable to the security parameter (e.g.,  $t = 2^{\kappa}$).  However, following NIST guidelines, we set $ t=2^{64} $ for \ensuremath {\mathsf{FROG}}{\xspace}. 

(i) The sub-linear key sizes in forward-secure schemes are generally achieved by a tree structure. For instance, in XMSS-MT, given a pre-determined (fixed) $t=2^{h}$  ($ h  $ is the height of the tree) number of messages to be signed, $d$ XMSS  sub-trees are computed during key generation, each of height $l$, such that $h=l\cdot d$. A Merkle-tree is constructed on top these sub-trees to compute the final public key that can verify the generated signatures, which include the authentication path from leaves to the root. Note that the tree structure in XMSS-MT is rigid and $t$ is pre-determined. The signature sizes, signature generation and especially key generation overhead grow substantially for larger $t$ values, and if it reaches $t$, the system must be re-initialized.  HSS-LMS~also follows a similar strategy.
In our design, we depart from HHBS approaches, but instead rely on \ensuremath {\mathsf{MMM}}{\xspace}~\cite{MaMiMi02} that generates hierarchical trees {\em as needed and on-the-fly}. In particular, we   harness the sum composition  iteratively and in conjunction with product composition to obtain practical performance results. However, as mentioned before,  \ensuremath {\mathsf{MMM}}{\xspace}~generic framework might lead to  inefficient forward-secure schemes if the underlying primitive and composition methods are not selected carefully. 

(ii) We observe that {\em on-the-fly} tree construction requires generating a  fresh private/public key pair per update, and therefore, the key generation overhead must be minimized.  That is, the signing overhead of on-the-fly constructions depend on the key generation  of the underlying signature primitive as much  its signing overhead. We identified that Dilithium~\cite{dilithium} and BLISS~\cite{BLISS} offer efficient key generation and signing, making them appropriate choices for the iterated sum and product compositions. For the sake of providing a more leveled comparison with HHBS schemes, we also instantiated schemes based on a relatively recent one-time hash-based signature in \cite{WOTSP}. In iterated sum and product compositions, we create a new private/key pair for each item to be used, and then another two pairs for the future tree elements in an amortized manner.  

(iii) New public keys must be relayed to the verifier for each update, and therefore both the signature and public key sizes must be minimized. We selected BLISS \cite{BLISS}  due to its parameters sizes which offers a more compact size than the existing post-quantum signature alternatives.  Our approach also shed a light of how existing NIST post-quantum signature candidates perform under some generic forward-secure transformations. Our observation indicates that only the candidates whose total signature plus public key size is relatively small might yield efficient results. In this regard, the lattice-based candidates such as Dilithium~\cite{ducas2018crystals} and Falcon~\cite{fouque2018falcon} seem only alternatives. We will later discuss our future plan to devise a one-time lattice based signature similar to \cite{DBLP:journals/joc/LyubashevskyM18} and with the optimizations proposed in \cite{dilithium} and the potential performance gains from such construction. 

 \subsection{The Description of  Main Instantiation}
\ensuremath {\mathsf{FROG}}{\xspace}~is constructed by performing an iterative sum and product composition of \ensuremath {\mathsf{SGN}}{\xspace}. Let  $\bigoplus$ and $\bigotimes$ denote the application of sum and product composition defined in Section \ref{sec:prelim} only once. We denote composing two instantiations of \ensuremath {\mathsf{SGN}}{\xspace}~with the sum composition as $\ensuremath {\mathsf{SGN}}{\xspace} \bigoplus \ensuremath {\mathsf{SGN}}{\xspace}$. Similarly,  $\ensuremath {\mathsf{SGN}}{\xspace} \bigotimes \ensuremath {\mathsf{SGN}}{\xspace}$ denotes two instantiations of a signature scheme with the sum composition. $\ensuremath {\mathsf{SGN}}{\xspace}^{\bigoplus}_{K}$ means an iterative composition of \ensuremath {\mathsf{SGN}}{\xspace} ~with itself $K$ times. Recall that $1\leq t \leq 2^{\kappa}-1$ denotes the total number of signatures signed {\em so far}.  For example, in XMSS-MT, $1\leq t \leq K << 2^{\kappa}-1$, whereas in \ensuremath {\mathsf{FROG}}{\xspace}~$t$ can approach to $2^{\kappa}$.  We can express the \ensuremath {\mathsf{FROG}}{\xspace}~as follows:

\begin{equation*}
\ensuremath {\mathsf{SGN}}{\xspace}_{\log t}^{\bigoplus} \bigotimes \{ \ensuremath {\mathsf{SGN}}{\xspace}_{i}^{\bigoplus} \}_{i=0}^{t}
\end{equation*}

\ensuremath {\mathsf{MMM}}{\xspace}~has an {\em } upper-tree and multiple lower-trees, which are constructed on-the-fly as needed:

 (i) We first create a forward-secure signature scheme with $\log t$ signing capability by iterating $\ensuremath {\mathsf{SGN}}{\xspace}_{\log t}^{\bigoplus}$ via sum composition. These private/public key pairs are the leaves of {\em the upper-tree}, and are used to certify the public keys of the signatures that will be used to verify the data items in the lower-trees. (ii) There will be multiple lower-trees that will be created as new data items to be signed arrive. Each lower-tree $1\leq i \leq t$ will be a new forward-secure iterative sum composition $ \ensuremath {\mathsf{\SGNONLY}}{\xspace}_{i}^{\bigoplus}$ that can sign $2^{i}$ data items. (iii) The leaves of upper-tree and the lower-tree are connected with a product composition. That is, once the leaves (i.e., key pairs) of $ \ensuremath {\mathsf{\SGNONLY}}{\xspace}_{i-1}^{\bigoplus}$ are depleted, we create a new lower-tree $ \ensuremath {\mathsf{\SGNONLY}}{\xspace}_{i}^{\bigoplus} $ and compose it with the corresponding leave of the upper-tree by calling the product composition. (iii) We adopt the amortized update strategy to ensure that transition from one lower-tree to the next one does not incur heavy key generation overhead.  In each update operation for  $ \ensuremath {\mathsf{\SGNONLY}}{\xspace}_{i}^{\bigoplus} $, we also generate two key pairs (the leaves) for the next tree $i+1$. Hence, once the key pairs for $i$'th lower-tree are depleted, the keys for new tree will be ready, and heavy (bulk) key generation is not needed. This approach enables a uniform update efficiency and is essential to handle large lower-tree sizes. However, it requires storing initial keys for the next lower-tree, and therefore  increases the private key size. This overhead only grows with $t$  as $O(\kappa \cdot \log t^{2})$, and therefore is space-efficient. For small-number of messages to be signed, one can omit amortization and perform batch update only for new lower-trees to be generated. 

\subsection{Alternative Instantiations}
(i) As aforementioned, one can use different signature schemes (either one-time or polynomially bounded)  to be used in the construction. However, careful consideration needs to be taken in order to ensure that the resulting forward-secure scheme will be efficient.   For instance, one can imagine the use of W-OTS variants~\cite{OTS:WOTS,OTS:WOTSPlus:2013}  to offer different performance trade-offs. In W-OTS, the length of hash-chain $w$ poses a trade-off between the signature/public key sizes and computational overhead. We have investigated different $w$ values and signature/public key sizes for W-OTS instantiated with \ensuremath {\mathsf{MMM}}{\xspace}. In order to have comparable signature sizes with \ensuremath {\mathsf{FROG}}{\xspace}, $w$ value must be relatively large (e.g. $  > $400), and this makes the key generation and signing of W-OTS rather expensive~for $\kappa=100-110$. It might be possible that W-OTS variants offer desirable trade-offs for different $\kappa$ and some applications might prefer a hash-based signature as a base scheme as opposed to a lattice-based constructs. Hence, we capture the possibility of any future OTS that has smaller signature and/or  public key sizes that may rely on a different building blocks.



(ii-iii) We consider hybrid approaches, wherein the upper tree is replaced by a (H)HBS and the lower-tree is generated with iterative constructions as described in the main scheme. This may lead an efficient constructions as (H)HBS (e.g., LMS~\cite{LMS:RFC}) is efficient for small-fixed number messages to be signed, and the upper-tree harbors $\kappa$ key pairs at most. Another alternative is to compute a hash-chain for any selected signature, and place $\kappa$ public keys as a part of the master public key. This approach makes the master public key large, but in return, it makes \ensuremath {\mathsf{MMM}}{\xspace}~signature size much smaller as the hash chain elements replace the leaves of upper-tree, and only the signature is transmitted but not the public keys. 

\begin{table*}[t!]
	\centering
	\vspace{ 2mm}
	
	
	\caption{Analytical performance of \ensuremath {\mathsf{FROG}}{\xspace}~and \ensuremath {\mathsf{FROG}^*}{\xspace}} \label{tab:analytical}

	\begin{threeparttable}
		\begin{tabular}{| c || c | }
			\hline
			
			\textbf{Operation/Parameter} & \specialcell[]{\textbf{Computation/Storage Cost}}\\ \hline \hline 
			\multicolumn{2}{|c|}{\textbf{MMM}} \\ \hline\hline 
			$ \ensuremath {\mathsf{FROG.Kg}}{\xspace}  $ 	& $ 2 \; \ensuremath {\mathsf{SGN.Kg}}{\xspace} $ \\ \hline
			$ \ensuremath {\mathsf{FROG.Sig}}{\xspace} $ 	& $   3\;  \ensuremath {\mathsf{SGN.Kg}}{\xspace}+2\;  \ensuremath {\mathsf{SGN.Sig}}{\xspace}+2H  $ \\ \hline
			$ \ensuremath {\mathsf{FROG.Ver}}{\xspace} $  	& $  2\; \ensuremath {\mathsf{SGN.Ver}}{\xspace}+(\log  \kappa + \log t )H  $ \\ \hline
			$\ensuremath {\mathsf{FROG}}{\xspace}_{\sigma}$& $ 2|\sigma|+4|pk|+( \log \kappa +\log t +1)\cdot |H|$\\ \hline 
			$\ensuremath {\mathsf{FROG}}{\xspace}_{pk}$ & $  |H|$\\ \hline 
			$\ensuremath {\mathsf{FROG}}{\xspace}_{sk}$ & $  (2+ \log \kappa)\cdot |sk|+6|pk|+4\cdot  \log \kappa \cdot |H|  + 3\log t \cdot |H| + \kappa (\log t)^{2}$\\ \hline \hline 
			\multicolumn{2}{|c|}{ \textbf{Iterated Product  Composition}} \\ \hline\hline 
			$ \ensuremath {\flatss\mathsf{.Kg}}{\xspace}  $ 	& $\log \log t (5\; \ensuremath {\mathsf{SGN.Kg}}{\xspace}+\ensuremath {\mathsf{SGN.Sig}}{\xspace}+2 \kappa \cdot H)  $ \\ \hline
			$ \ensuremath {\flatss\mathsf{.Sig}}{\xspace} $ 	& $  3 \; \ensuremath {\mathsf{SGN.Kg}}{\xspace}+2 \; \ensuremath {\mathsf{SGN.Sig}}{\xspace}+ (\kappa +1) \cdot H $ \\ \hline
			$ \ensuremath {\flatss\mathsf{.Ver}}{\xspace} $  	& $ 2 (\log \log t \cdot \ensuremath {\mathsf{SGN.Ver}}{\xspace}+H)   $ \\ \hline
			$\ensuremath {\mathsf{FROG}^*}{\xspace}_{\sigma}$& $ 2|\sigma|+4|pk|+\kappa $\\ \hline 
			$\ensuremath {\mathsf{FROG}^*}{\xspace}_{pk}$& $  |H|$\\ \hline 
			$\ensuremath {\mathsf{FROG}^*}{\xspace}_{sk}$& $ \log \log t (2 |sk| + 6|pk|+4\kappa)      +       \kappa \cdot (\log  t)^{2}+|sk|\cdot \log \kappa$\\ \hline 
			
		\end{tabular}
		\begin{tablenotes}[flushleft]\scriptsize{ 
			
				
			
				
			
			}
		\end{tablenotes}
	\end{threeparttable}


\end{table*}

(iv) All of the above techniques receive significant computational benefit from pre-computation methods with an expense of  larger memory usage. For example, in amortized update strategy, the generated keys are independent from the messages, and therefore can be pre-computed and stored to be used later. This accelerates signature generation as a small and constant number of key update operations are performed beforehand. Parallel computing (e.g., GPUs, FPGAs) can be used to accelerate the batch generation of pre-computed elements and then fed into online  computations. 

\subsection{Security Argument from Base Scheme OTS and MMM}
\ensuremath {\mathsf{FROG}}{\xspace}~is a transformation of efficient post-quantum one-time signatures into multiple-time forward-secure signatures via MMM~\cite{MaMiMi02}. Hence, the security of \ensuremath {\mathsf{FROG}}{\xspace}~directly follows from the sum and/or product composition proofs of MMM~in~\cite{MaMiMi02} provided that the base OTS schemes are secure. We instantiate \ensuremath {\mathsf{FROG}}{\xspace}~with well-proven OTSs as outlined, and therefore \ensuremath {\mathsf{FROG}}{\xspace}~schemes are as secure as MMM with its corresponding base OTS schemes.





















\section{Introduction}\label{sec:Introduction}%
Forward-security ensures that the past messages are protected even if the current secret key is exposed.  Forward-secure digital signature schemes~(e.g., \cite{FWSigBasis_Anderson97}) are key-evolving signatures that periodically update the private key and delete the previous key. This prevents an adversary who compromises the system from forging the previously computed digital signatures on past messages, since their corresponding keys were erased. Forward-secure digital signatures enhance the breach and compromise-resiliency of digital signatures. Hence, they play a critical role in many real-life applications such as secure audit logging, digital forensics, financial applications, public key certificate infrastructures, and many others. 

\subsection{The State of the Art and Its Limitations} \label{subsec:}
Several forward-secure digital signatures have been proposed with different performance trade-offs (e.g.,  \cite{FWSig_BellareMiner99,FWSecItkis_Reyzin_01,FWSecKozlov_Reyzin_02}). There is generally a trade-off between signature and public key sizes, update frequency and computational efficiency, and number of items that can be signed for some variants. Forward-secure signatures generally are computationally costly compared to standard signatures, and have larger signature and/or key sizes. Some of the forward-secure signatures offer extended properties such as aggregation~\cite{BAFYavuzNing09,Yavuz:2012:TISSEC:FIBAF,FssAggNew,FAS_Asymptotic,Yavuz:CORE:2020}, untrusted update~\cite{FWSecBoyenUntrusedupdate:2006,FWSigUntrustedUpt_CCS07} ,   selective verification~\cite{Logging_VerifiableExcerpt}, and group signatures~\cite{FWSEc:LatticeGrou:2019}. These features might increase the efficiency of the schemes in  one front, while incurring other cost and constraints in an another  (e.g., more compact signatures but larger public keys and/or more computational overhead). There are also generic forward-security frameworks (e.g.,~\cite{FWSigfromAnyScheme_Hugo2000,MaMiMi02}) that can transform any standard signature into a  forward-secure signature. However, these generic transformations might lead inefficient results (e.g.~\cite{FWSigfromAnyScheme_Hugo2000}), and specially tailored constructions might outperform them with careful designs (e.g.~\cite{FWSec:TightReduction:2020}) for some performance metrics. 

The vast majority of  the existing forward secure signatures rely on conventional intractability problems (e.g., factorization, discrete logarithm problem (DLP), elliptic curve (ECDLP)). However, it is well-known that the conventional signature schemes are vulnerable to the emerging quantum computers, and therefore, NIST has initiated the second round of standardizations for post-quantum    cryptography\footnote{\url{https://csrc.nist.gov/projects/post-quantum-cryptography/}}. The existing post-quantum digital signatures, compared to   their conventional counterparts, are known to be   costly in terms of communication, computation and energy consumption. Forward secure version of such constructions are expected to be  even costlier than the original schemes. 

The forward-security for post-quantum signatures have been mainly investigated for hash-based digital signatures (HBS) ~\cite{OTS_Lamport_79}. To our best knowledge, the other NIST standardization   candidates have not yet been explored extensively from the forward-security perspective. For instance, it is clear that a generic forward-secure transformation (e.g., ~\cite{FWSigfromAnyScheme_Hugo2000,MaMiMi02}) for  many of these candidates yield highly inefficient constructions due to their very large signature and/or public key sizes.  HBS (e.g., Lamporr~~\cite{OTS_Lamport_79}) are among the first signature schemes with  a post-quantum security. There are  number of efficient one-time HBS (e.g., ~\cite{OTS_r_time_HORSED_2006,HORS_BetterthanBiBa02,OTS:WOTS,OTS:WOTSPlus:2013}) but they can only sign one or a few messages per key pair. Recently, a NIST candidate (SPHINCS~\cite{SPHINCS:Bernstein:2015}) addressed this limitation   with a stateless design, albeit suffering from   large signature sizes (e.g., 41 KB).  

Forward-secure signatures are by design stateful. Hence, to our knowledge, at this point, the HBSs such as  XMSS~\cite{XMSS:Buchmann:2011} and LMS~\cite{LMS:OriginalPatent,LMS:RFC}  are the most efficient forward-secure post-quantum secure alternatives. These schemes are usually efficient only for small to moderate number of messages to be signed. However, once the total number of messages to be signed  increases, the computational overhead, and especially the cost of key generation, grows significantly. Both of these schemes rely on hierarchical variants (e.g., HSS-LMS) to handle signing capabilities over $t>2^{40}$. (we refer them as Hierarchical HBS (HHBS)).  In any cases, HHBSs generally require $t$ to be pre-defined, and their key/signature generation overhead and signature sizes grow extremely large  for a big $t  $ .  There is a need for post-quantum forward-secure signatures that are efficient, practical and can scale for large number of messages to be signed. 

\subsection{Objectives and Desirable Properties}
The goal of this work is to create  a series of  post-quantum forward-secure signatures that achieve highly efficient key and signature generation while maintaining sub-linear signature, private key and constant public key sizes. We aim that our schemes should be at least competitive or outperform existing alternatives for small/moderate $t$ values (for some performance metrics), while significantly outperform them when $ t $ grows   for the   all performance metrics.  We outline some of the desirable properties of  \ensuremath {\mathsf{FROG}}{\xspace}. 

\begin{itemize}
	
	\item ~{\em \underline{Efficient Key Generation }}: For $ t=2^{64} $, the key generation of \ensuremath {\mathsf{FROG}}{\xspace}, instantiated with  the lattice-based signature in \cite{dilithium}~is almost $ 2200\times $ faster than the most efficient key generation instance of XMSS-MT variant for key generation (with 12 layers) with the maximum of  $ 2^{60} $ signature generation capability.   This difference significantly grows for XMSS-MT variants with lower number of sub-trees  (e.g., 3 or 6). 
	
	\item ~{\em \underline{Efficient Signature Generation }}: The signature generation of \ensuremath {\mathsf{FROG}}{\xspace}~is two signature generation  plus three key generation overhead of the underlying signature scheme along with a constant number of hash calls. This cost is again independent from both the total number of messages to be signed or number of messages signed so far, making \ensuremath {\mathsf{FROG}}{\xspace}~signing magnitudes of times more efficient than XMSS-MT. For example, for $t=2^{64}$, the lattice-based instantiation of \ensuremath {\mathsf{FROG}}{\xspace}~based on \cite{dilithium} (with AVX optimization) is $  \approx 15 \times $ faster than most efficient  XMSS-MT  variant for signature generation (with 12 layers).  The hash-based instantiation of \ensuremath {\mathsf{FROG}}{\xspace}~based on \cite{WOTSP} is $  \approx 8 \times $ faster than the most efficient XMSS-MT  variant (with 12 layers). 
	
	\item ~{\em \underline{Efficient Signature Verification}}:  The signature verification of \ensuremath {\mathsf{FROG}}{\xspace} (with basic MMM instantiation)~is two signature verification  plus   a constant number of hash calls.  For example, for $t=2^{64 }$, the lattice-based instantiation of \ensuremath {\mathsf{FROG}}{\xspace}~based on \cite{dilithium} is $  \approx 17\times $ faster than most efficient  XMSS-MT  variant for verification (with 3 layers).  The hash-based instantiation of \ensuremath {\mathsf{FROG}}{\xspace}~based on \cite{WOTSP} is $  \approx 8 \times $ faster than the most efficient XMSS-MT  variant (with 3 layers). 
	
	\item ~{\em \underline{Compact Public Key}}: The public key of \ensuremath {\mathsf{FROG}}{\xspace}~is just a hash value ( half size of XMSS-MT variants), and therefore is optimal.
	
	\item ~{\em \underline{Competitive Signature Sizes}}:  The signature sizes in  some \ensuremath {\mathsf{FROG}}{\xspace}~variants (e.g., hash-based) could slightly larger than those variants in XMSS-MT with lower number of layers (e.g. $ t=2^{60} $ with three layers), however, usually such variants of XMSS-MT have a very costly key generation  and signature generation algorithms.  For example, for instantiation of \ensuremath {\mathsf{FROG}}{\xspace}~with Dilithium \cite{dilithium}, the signature size is $ 13,624 $  bytes where in XMSS-MT with $ 12 $ layers, signature size is $ 27,688 $ bytes. The signature size becomes more favorable for XMSS-MT with lower layers. We investigated another variant of \ensuremath {\mathsf{FROG}}{\xspace}, called \ensuremath {\mathsf{FROG}^*}{\xspace} (iterative product composition of MMM)~that enjoys shorter signatures and private keys but with a more expensive key generation and signature verification.  Remark that in many cases, \ensuremath {\mathsf{FROG}^*}{\xspace}~is still significantly more computationally efficient than XMSS-MT variants. 
\end{itemize}


\noindent\textbf{Limitations:} As aforementioned, our constructions (\ensuremath {\mathsf{FROG}}{\xspace}~and \ensuremath {\mathsf{FROG}^*}{\xspace}) outperform XMSS-MT variants in almost all the metrics. However, our schemes suffer from larger private key sizes. For instance, for the hash-based instantiations of \ensuremath {\mathsf{FROG}}{\xspace}, the private key size could be as large as $ 715,840 $ bytes, which is about $ 18\times$ larger than the largest private key size for the instantiated XMSS-MT variants. \ensuremath {\mathsf{FROG}^*}{\xspace}  has a smaller private sizes but with more computational overhead. However, we think that this is a very favorable trade-off since unlike public key size, the private key size does not incur any (online) communication overhead.
