Post-Quantum Adaptor Signatures and Payment Channel Networks

Abstract

Adaptor signatures, also known as scriptless scripts, have recently become an important tool in addressing the scalability and interoperability issues of blockchain applications such as cryptocurrencies. An adaptor signature extends a digital signature in a way that a complete signature reveals a secret based on a cryptographic condition. It brings about various advantages such as (i) low on-chain cost, (ii) improved fungibility of transactions, and (iii) advanced functionality beyond the limitation of the blockchain’s scripting language.

In this work, we introduce the first post-quantum adaptor signature, named ${\mathsf {LAS}}$. Our construction relies on the standard lattice assumptions, namely Module-SIS and Module-LWE. There are certain challenges specific to the lattice setting, arising mainly from the so-called knowledge gap in lattice-based proof systems, that makes the realization of an adaptor signature and its applications difficult. We show how to overcome these technical difficulties without introducing additional on-chain costs. Our evaluation demonstrates that ${\mathsf {LAS}}$ is essentially as efficient as an ordinary lattice-based signature in terms of both communication and computation. We further show how to achieve post-quantum atomic swaps and payment channel networks using ${\mathsf {LAS}}$.

1 Introduction

Blockchains are decentralized platforms run by miners, where each transaction on the blockchain can be seen as an application formed of some script(s). The scripting language of a blockchain defines potential functionalities that can be implemented on blockchain. Bitcoin, for example, consists of very few scripts, which restricts its use mainly into coin transactions. Ethereum, on the other hand, has a Turing-complete scripting language that enables users to run more advanced and complicated applications.

A user who wants to deploy and execute a transaction needs to pay a fee to the miners. The fee is determined by the storage and computational costs of running each script of the transaction. Thus, it is beneficial to handle some operations off-chain to reduce the on-chain fee paid to the miners. In this manner, Poelstra introduced the notion of scriptless scripts [25], which is later named as adaptor signatures [3, 15].

Adaptor signatures can be seen as an extension over a digital signature, where first a “pre-signature” is generated and its completion to a (full) signature reveals a secret based on a cryptographic condition. The conditions are defined over a hard relation such as the discrete log problem, and the complete signature reveals a witness matching with the statement embedded into the pre-signature. The verification of the signature is done in the same way as the original signature scheme. Thus, while the miners verify only the signature, parties involved in the signature generation can embed an additional condition.

The main advantages of adaptor signatures can be summarized as follows: (i) A significant reduction in on-chain costs, (ii) improved fungibility of transactions, and (iii) ability to incorporate complex conditions, which may otherwise be impossible to execute due to the limitation of the blockchain’s scripting language. More specifically, if the condition is published on-chain separately, then it would incur additional storage and verification costs. At the same time, since the condition is embedded inside a signature, for the outsiders and miners the signature with a condition is indistinguishable from a regular one. This fungibility property is especially useful to hide payment channel network transactions among any other transactions [21]. Moreover, adaptor signatures enhance the functionality of blockchains with a limited scripting language. Since the condition embedded within the signature is not verified by miners, it is not limited by the blockchain’s scripting language. These advantages have been utilized in payment channel networks  [3, 21], atomic swaps  [24], and discrete log contracts  [8].

None of these works, however, provide security against powerful quantum computers as they rely on discrete-log-related assumptions. As evident, e.g., from NIST’s efforts for standardization of post-quantum (i.e., quantum-resistant) algorithms [22], there is a major need for designing quantum-secure alternatives of currently deployed schemes. In fact, in the blockchain community, there are already significant efforts and considerations towards migrating to post-quantum cryptography. For example, Ethereum 2.0 Serenity upgrade [5] is planned to have an option for a post-quantum signature, Zcash developers plan to update their protocol with post-quantum alternatives when they are mature enough [31], and Hcash is building a post-quantum privacy-preserving blockchain [17].

Lattice-based cryptography, studied extensively in the last decades, is a promising candidate for post-quantum security. For example, Dilithium [9], which is based on standard lattice assumptions, is among the 2nd round signature candidates in NIST’s post-quantum standardization process. Beyond basic cryptographic schemes such as encryption and signature, lattice-based cryptography also supports advanced schemes such as zero-knowledge proofs (ZKP), which play a crucial role in blockchain applications. For example, advanced ZKPs have recently been studied in [12, 13] and there are even recent efforts in constructing blockchain-specific applications based on lattice assumptions [14, 30].

Our contributions. In this work, we introduce the first post-quantum adaptor signature, $\mathsf {LAS}$, in support of the efforts towards migration to post-quantum cryptography. Our construction relies on standard lattice assumptions, namely Module-LWE and Module-SIS, and is essentially as efficient as an ordinary lattice-based signature scheme based on the same assumptions. In particular, the signature scheme underlying $\mathsf {LAS}$ is a simplified version of Dilithium [9].

We further show how to realize post-quantum payment channel networks and atomic swaps using $\mathsf {LAS}$. Our results show that these applications can be realized in the post-quantum setting without incurring an additional on-chain cost. The on-chain cost is effectively the cost of an ordinary lattice-based signature.

The main technical difficulties in constructing lattice-based adaptor signatures, as well as atomic swaps and payment channel networks, stem from the following two related facts. First, hard-to-find pre-images of lattice-based one-way functions, and in general user’s secret keys, are required to have small coefficients in comparison to the system modulus q. In this case, a common technique used to hide user’s secrets is rejection sampling, which is applied depending on the secret. As a result, in the setting of a payment channel network where a multi-party interaction is required with each user having his/her own secret, the realization of a secure construction demands a more careful analysis.

Secondly, efficient lattice-based zero-knowledge proofs underlying the (ordinary) signature scheme we employ have an inherent knowledge (soundness) gap (see, for example, [12, 19, 20]). That is, a witness extracted from a protocol interaction satisfies an extended relation $R'$ whereas an honest user’s secret satisfies a stronger relation R such that $R\subseteq R'$. Therefore, we need to adjust the security model carefully and also show that the extended guarantees are still meaningful and sufficient for practical applications. To this end, we extend the formal model of adaptor signatures introduced recently in [3], and show how to overcome the technical difficulties in our applications.

Organization of the paper. In Sect. 2, we present our security assumptions, lattice-based signatures and the rejection sampling technique as well as our extended formal definition for adaptor signatures. We introduce $\mathsf {LAS}$, our adaptor signature, in Sect. 3, where the security and performance analyses and the effect of the knowledge gap are also given. We discuss the application of $\mathsf {LAS}$ to atomic swaps and payment channel networks in Sect. 4.

2 Preliminaries

We define $\mathcal {R}_q=\mathbb {Z}_q[X]/(X^d+1)$ to be a cyclotomic ring of power-of-2 degree d for an odd modulus q. We denote by $\mathbb {S}_c$ the set of polynomials in $\mathcal {R}_q$ whose maximum absolute coefficient is at most $c\in \mathbb {Z}^+$. Similarly, $\mathcal {R}=\mathbb {Z}[X]/(X^d+1)$.

We denote by $\textit{\textbf{I}}_n$ the n-dimensional identity matrix. Vectors and matrices over $\mathcal {R}$ are denoted by lower-case and capital bold letters such $\textit{\textbf{a}}$ and $\textit{\textbf{A}}$, respectively. For a polynomial $f=f_0+f_1X+\cdots +f_{d-1}X^{d-1}\in \mathcal {R}$, we define the norms in the typical way: $\left\| f\right\| = \sqrt{\sum _{i=0}^{d-1}f_i^2}$, $\Vert f\Vert _{_\infty }=\max _i|f_i|$ and $\Vert f\Vert _{_1}=\sum _{i=0}^{d-1}|f_i|$. For a vector $\textit{\textbf{v}}=(v_0,\ldots ,v_{s-1})\in \mathcal {R}^s$ of polynomials with $s\ge 1$, we further define $\left\| \textit{\textbf{v}}\right\| = \sqrt{\sum _{i=0}^{s-1}\left\| v_i\right\| ^2}$, $\Vert \textit{\textbf{v}}\Vert _{_1} = \sum _{i=0}^{s-1}\Vert v_i\Vert _{_1}$, $\Vert \textit{\textbf{v}}\Vert _{_\infty } = \max _i\Vert v_i\Vert _{_\infty }$.

2.1 Security Assumptions: Module-SIS and Module-LWE

The security assumptions on which our constructions rely are the two well-known lattice problems, namely Module-SIS (M-SIS) and Module-LWE (M-LWE) [18]. They are generalizations of SIS [2] and LWE [28] problems, respectively. These problems are widely believed to resist attacks against powerful quantum adversaries. As in [9, 12, 13], we define below M-SIS in “Hermite normal form”, which is as hard as M-SIS with a completely random matrix $\textit{\textbf{A}}$.

Definition 1

(M-SIS$_{n,m,q,\beta _{\text {SIS}}}$). Let $\textit{\textbf{A}}'\overset{\$}{\leftarrow }\mathcal {R}_q^{n\times (m-n)}$ and $\textit{\textbf{A}}=[\, \textit{\textbf{I}}_n \, \Vert \, \textit{\textbf{A}}' \, ]$. Given $\textit{\textbf{A}}$, M-SIS problem with parameters $m>n>0$ and $0<\beta _{\text {SIS}}<q$ asks to find a short non-zero $\textit{\textbf{v}}\in \mathcal {R}_q^m$ such that $\textit{\textbf{A}}\textit{\textbf{v}}=\textit{\textbf{0}}$ over $\mathcal {R}_q$ and $\left\| \textit{\textbf{v}}\right\| \le \beta _{\text {SIS}}$.

We use a standard variant of M-LWE where both the error and secret coefficients are sampled uniformly from $\{-1,0,1\}$. This variant is commonly used in many recent proposals such as [12,13,14].

Definition 2

(M-LWE$_{\ell ,m,q}$). M-LWE problem with parameters $\ell ,m>0$ asks to distinguish between the following two cases: 1) $(\textit{\textbf{A}},\textit{\textbf{b}})\overset{\$}{\leftarrow }\mathcal {R}_q^{m\times \ell } \times \mathcal {R}_q^m$, and 2) $(\textit{\textbf{A}},\textit{\textbf{A}}\textit{\textbf{s}}+\textit{\textbf{e}})$ for $\textit{\textbf{A}}\overset{\$}{\leftarrow }\mathcal {R}_q^{m\times \ell }$, a secret vector $\textit{\textbf{s}}\overset{\$}{\leftarrow }\mathbb {S}_1^\ell$ and an error vector $\textit{\textbf{e}}\overset{\$}{\leftarrow }\mathbb {S}_1^m$.

It is well-known that if the error and the secret coefficients are sampled from $\mathbb {S}_\gamma$ for $\gamma >1$, then M-LWE problem gets harder. Therefore, M-LWE$_{\ell ,m,q}$ hardness assumption implies that $\textit{\textbf{t}}=\textit{\textbf{A}}\textit{\textbf{s}}+\textit{\textbf{e}}$ is (computationally) indistinguishable from a uniformly random element of $\mathcal {R}_q^m$ when $\textit{\textbf{s}}\overset{\$}{\leftarrow }\mathbb {S}_\gamma ^\ell$ and $\textit{\textbf{e}}\overset{\$}{\leftarrow }\mathbb {S}_\gamma ^m$ for any $\gamma \ge 1$.

2.2 Lattice-Based Signature and Rejection Sampling

The (ordinary) signature part of our construction can be seen as a simplified version of Dilithium [9], which is a 2nd round signature candidate in NIST’s post-quantum standardization process. This signature scheme itself is based on Lyubashevsky’s signatures [19, 20]. In our construction, we do not employ the optimizations in Dilithium in order to simplify the presentation.

To make sure that the signature does not leak information about the secret key, we employ the rejection sampling technique from [19] as also done in Dilithium. The idea for this works as follows. Let $\textit{\textbf{s}}\in \mathcal {R}_q^k$ be a secret-dependant vector with $\Vert \textit{\textbf{s}}\Vert _{_\infty }\le p\in \mathbb {Z}^+$. In order to tie the security to M-SIS, we require the masked vector $\textit{\textbf{z}}=\textit{\textbf{y}}+\textit{\textbf{s}}$ to be short relative to q. Therefore, $\textit{\textbf{y}}$ cannot be sampled uniformly at random from $\mathcal {R}_q^k$. Instead, we sample $\textit{\textbf{y}}\overset{\$}{\leftarrow }\mathbb {S}_\gamma ^k$ for $\gamma \approx kd\cdot p$. Then, we restart signing (i.e., reject $\textit{\textbf{z}}=\textit{\textbf{y}}+\textit{\textbf{s}}$) if $\Vert \textit{\textbf{z}}\Vert _{_\infty }>\gamma -p$. It is easy to see that conditioned on $\textit{\textbf{z}}$ being accepted, the distribution of $\textit{\textbf{z}}$ is identical to the uniform distribution on $S_{\gamma -p}^k$. That is, the distribution of $\textit{\textbf{z}}$ is forced to be uniform in a box, and thus is (perfectly) simulatable using public information.

2.3 Adaptor Signatures

In  [3], an adaptor signature $\varPi _{R, \varSigma }$ is defined with respect to a hard relation R and a signature scheme $\varSigma = (\mathsf {KeyGen},\mathsf {Sign}, \mathsf {Verify})$. A relation R with a language $L_R:=\{Y\mid \exists y: (Y,y) \in R \}$ is said to be hard  [6] if: (i) there exists a probabilistic polynomial time ( ) generator $\mathsf {Gen}(1^n)$ that outputs $(Y,y)\in R$, (ii) for every algorithm , given $Y\in L_R$, the probability of outputting $y$ is negligible. A signature scheme $\varSigma$ is defined by three algorithms: (i) $\mathsf {KeyGen}$ generates a public-secret key pair , (ii) $\mathsf {Sign}$ produces a signature $\sigma$ using the key and message M, (iii) $\mathsf {Verify}$ verifies the correctness of a signature $\sigma$ on a message M using a public key . Our underlying signature, Dilithium [9], is SUF-CMA (Strong existential unforgeability under chosen message attacks) secure.

In the lattice setting, we need to define two relations $R,R'$ with $R\subseteq R'$. Here, R constitutes the relation for the statement-witness pairs output by $\mathsf {Gen}$ (i.e., those used by honest users) whereas $R'$ is an extended relation that defines the relation for extracted witnesses. The reason for this extension is detailed in Section 3, and stems from the knowledge/soundness gap inherent in efficient lattice-based zero-knowledge proofs (see, e.g., the soundness definition in [13, Section 2.3]). We denote an adaptor signature scheme in this setting by $\varPi _{R, R', \varSigma }$, which extends the definition given in  [3], and elaborate further below the reason why this extension is necessary.

Definition 3

(Adaptor Signature Scheme). An adaptor signature scheme $\varPi _{R, R', \varSigma }$ consists of four algorithms $(\mathsf {PreSign}, \mathsf {PreVerify}, \mathsf {Adapt}, \mathsf {Ext})$ defined below.

 

::

on input a key pair , a statement $Y\in L_R$ and a message $M \in \{0,1\}^*$, outputs a pre-signature $\hat{\sigma }$.

::

on input a statement $Y\in L_R$, a pre-signature $\hat{\sigma }$, a public key and a message $M \in \{0,1\}^*$, outputs a bit b.

::

on input a statement-witness pair $(\hat{\sigma },y)$, a public key , a pre-signature $\hat{\sigma }$ and a message $M \in \{0,1\}^*$, outputs a signature $\sigma$.

$\mathsf {Ext}(Y,\sigma ,\hat{\sigma })$::

on input a statement $Y\in L_R$, a signature $\sigma$ and a pre-signature $\hat{\sigma }$, outputs a witness $y$ such that $(Y,y)\in R'$, or $\bot$.

 

Note that an adaptor signature $\varPi _{R, R', \varSigma }$ also inherits $\mathsf {KeyGen}$, $\mathsf {Sign}$ and $\mathsf {Verify}$ algorithms from the signature scheme $\varSigma$. The authors in  [3] define the security properties for an adaptor signature: security, pre-signature adaptability and witness extractability. In addition, they extend the standard correctness definition of signature algorithms with pre-signature correctness, which states that an honestly generated pre-signature of a statement $Y\in L_R$ passes $\mathsf {PreVerify}$ and can be completed into a signature where the witness $y$ can be extracted. We extend further the formal definitions of the security properties in  [3], where $R=R'$ yields the setting in  [3].

Definition 4

( security). An adaptor signature scheme $\varPi _{R, R', \varSigma }$ is secure if for every  adversary there exists a negligible function such that where the experiment is defined as follows:

Definition 5

(Weak pre-signature adaptability). An adaptor signature scheme $\varPi _{R, R', \varSigma }$ is weak pre-signature adaptable if for any message $M \in \{0,1\}^*$, any statement/witness pair $(Y, y)\in R$, any key pair and any pre-signature $\hat{\sigma }\leftarrow \{0,1\}^*$ with , we have .

We call our pre-signature adaptability definition weak because only statement-witness pairs satisfying R are guaranteed to be adaptable, and not those satisfying $R'$. This is similar to the knowledge gap of the ZKP underlying Dilithium, where the soundness only guarantees extraction of a witness from an extended relation. Therefore, pre-signature adaptability does not guarantee, for example, that an extracted witness can be used to adapt a pre-signature successfully (see Remark 1). This issue becomes effective in the applications of our adaptor signature, and we show how to overcome it in Section 4. Note that still the pre-signature $\hat{\sigma }$ in the above definition can be adversarially generated as in  [3].

Definition 6

(Witness extractability). An adaptor signature scheme $\varPi _{R, R', \varSigma }$ is witness extractable if for every  adversary , there exists a negligible function such that the following holds: where the experiment is defined as follows

Note that, in the above witness extractability definition, the adversary’s winning condition is restricted to the extracted witness not being in $R'$. Since $R\subseteq R'$, $(Y,y')\notin R'$ implies that $(Y,y')\notin R$. Therefore, it is sufficient to ensure that $R'$ is a hard relation, which itself implies that R is also a hard relation. As a result, in our security assumptions, we make sure that $R'$ is a hard relation.

3 $\mathsf {LAS}$: An Efficient Adaptor Signature from Lattices

In this section, we describe our lattice-based adaptor signature, $\mathsf {LAS}$. Let $\textit{\textbf{A}}=[\, \textit{\textbf{I}}_n \, \Vert \, \textit{\textbf{A}}' \, ] \in R_q^{n\times (n+\ell )}$ for $\textit{\textbf{A}}'\overset{\$}{\leftarrow }R_q^{n\times \ell }$ and be a hash function (modelled as a random oracle). We assume that the public parameters are publicly available and can be used by any algorithm. In practice, $\textit{\textbf{A}}'$ can be generated from a small seed using an extendable output function (modelled as a random oracle) as done in Dilithium [9]. The function $f_{\textit{\textbf{A}}}(\textit{\textbf{x}})=\textit{\textbf{Ax}}$ over $\mathcal {R}_q$ is Ajtai’s hash function [2] defined over module lattices where the matrix $\textit{\textbf{A}}$ is in Hermite normal form (HNF). It is clear that the function is additively homomorphic, and Ajtai [2] showed that it is one-way in the setting of SIS. In our case, the security is based on M-SIS (in HNF). Collision-resistance is also clear as a collision $(\textit{\textbf{x}},\textit{\textbf{x}}')$ yields an immediate M-SIS solution: $\textit{\textbf{A}}(\textit{\textbf{x}}-\textit{\textbf{x}}')=0$.

Table 1. Identifiers for $\mathsf {LAS}$.

In Table 1, we first summarize the identifiers used for $\mathsf {LAS}$, where the hard relations $R,R'$ are given by $\mathfrak {R}_{\textit{\textbf{A}}},\mathfrak {R}_{\textit{\textbf{A}}}'$ with $\mathfrak {R}_{\textit{\textbf{A}}}\subseteq \mathfrak {R}_{\textit{\textbf{A}}}'$. The statement-witness generation $\mathsf {Gen}$ for $\mathfrak {R}_{\textit{\textbf{A}}}$ runs exactly as $\mathsf {KeyGen}$. It is easy to see that if M-SIS$_{n,n+\ell +1,q,\beta }$ for $\beta =2\gamma d (n+\ell )$ is hard, then $\mathfrak {R}_{\textit{\textbf{A}}}$ and $\mathfrak {R}_{\textit{\textbf{A}}}'$ are hard relations. This is because if one can find $\textit{\textbf{r}}$ such that $(\textit{\textbf{t}},\textit{\textbf{r}})\in \mathfrak {R}_{\textit{\textbf{A}}}'$ for a random $\textit{\textbf{t}}$, then $[\, \textit{\textbf{A}} \, \Vert \, \textit{\textbf{t}} \, ]\cdot \left( \begin{array}{c} \textit{\textbf{r}} \\ -1 \end{array}\right) =0$. Hence, $\left( \begin{array}{c} \textit{\textbf{r}} \\ -1 \end{array}\right)$ is a solution to M-SIS$_{n,n+\ell +1,q,\beta }$ for $\beta =2\gamma d (n+\ell )$ since $\left\| \textit{\textbf{r}}\right\| \le \beta$.

We present the ordinary signature procedures in Algorithm 1, and then the procedures for the adaptor signature in Algorithm 2. The idea for the signature is similar to the Schnorr signature [29] with the main difference being the use of rejection sampling at Step 11. This is the so-called “Fiat-Shamir with Aborts” technique [19, 20].

In the adaptor signature part in Algorithm 2, $\mathsf {PreSign}$ and $\mathsf {PreVerify}$ operate very similar to $\mathsf {Sign}$ and $\mathsf {Verify}$, respectively. The main issue is that the signer may not know (at the time of running $\mathsf {PreSign}$) the witness $y$ to the statement $Y$, and yet for many applications in practice (such as payment channel networks), one would want to make sure that having access only to the signature (but not the pre-signature) does not reveal any information on the witness $y$.

To this end, we need to modify the rejection sampling step. Even though the signer does not know the witness $y$, he does know how it is supposed to be generated in an honest run. Therefore, he knows that the maximum absolute coefficient of any honestly-generated witness is at most 1 (recall that $\mathsf {Gen}$ runs exactly as $\mathsf {KeyGen}$). Since we have $\textit{\textbf{z}}=\textit{\textbf{y}}+c\textit{\textbf{r}}+\textit{\textbf{r}}'$ for $\textit{\textbf{r}}':=y$ in an honestly-generated full signature, we know that the secret-dependant part $c\textit{\textbf{r}}+\textit{\textbf{r}}'$ has infinity norm at most $\kappa +1$. Therefore, the signer artificially performs a stronger rejection sampling step in $\mathsf {PreSign}$, where $\Vert \varvec{\hat{z}}\Vert _{_\infty }\le \gamma -\kappa -1$ is required. This ensures that even when the witness is added to the response in $\mathsf {Adapt}$, the response $\varvec{{z}}$ still satisfies the rejection sampling condition in $\mathsf {Sign}$, and thus remains publicly simulatable, i.e., no secret information including the witness is revealed.

In fact, there are further reasons for this important modification. One is in regards to adaptability. If the rejection sampling in $\mathsf {PreSign}$ is done exactly as in $\mathsf {Sign}$, then verification of an adapted pre-signature (i.e., output of $\mathsf {Adapt}$) via $\mathsf {Verify}$ may not succeed as the infinity norm condition may be violated due to the addition of $\textit{\textbf{r}}':=y$. Another reason comes from the security analysis. In order to be able to simulate the outputs of both $\mathsf {Sign}$ and $\mathsf {PreSign}$, this change to rejection sampling plays a crucial role.

Let us summarize the following two facts as we will make use of them repeatedly in the security proofs.

Fact 1

We can see that $\Vert c\textit{\textbf{r}}\Vert _{_\infty }\le \kappa$ since $\Vert c\Vert _{_1}\le \kappa$ and $\Vert \textit{\textbf{r}}\Vert _{_\infty }\le 1$. Therefore, both $\varvec{\hat{z}}$ in $\mathsf {PreSign}$ and $\textit{\textbf{z}}$ in $\mathsf {Sign}$ can be simulated publicly as they follow uniform distributions on $\mathbb {S}_{\gamma -\kappa -1}^{n+\ell }$ and $\mathbb {S}_{\gamma -\kappa }^{n+\ell }$, respectively, due to the rejection sampling.

Fact 2

Assuming the hardness of M-LWE$_{\ell ,n,q}$, the result of $\textit{\textbf{Ax}}$ is (computationally) indistinguishable from a uniformly random element in $\mathcal {R}_q^n$ whenever $\textit{\textbf{x}}\overset{\$}{\leftarrow }\mathbb {S}_c^{n+\ell }$ for some $c\ge 1$. We can see this by realizing that $\textit{\textbf{Ax}}=[\, \textit{\textbf{I}}_n \, \Vert \, \textit{\textbf{A}}' \, ]\cdot \left( \begin{array}{c} \textit{\textbf{x}}_0 \\ \textit{\textbf{x}}_1 \end{array}\right) = \textit{\textbf{x}}_0 + \textit{\textbf{A}}'\textit{\textbf{x}}_1$. This is an M-LWE instance with the secret vector $\textit{\textbf{x}}_1\in \mathbb {S}_c^\ell$ and the error vector $\textit{\textbf{x}}_0\in \mathbb {S}_c^n$.

Note that there is a knowledge gap between a witness used by an honest user and a witness extracted by $\mathsf {Ext}$ for a statement $Y$. In particular, an honest user’s witness $y=\textit{\textbf{r}}$ satisfies $\Vert \textit{\textbf{r}}\Vert _{_\infty }\le 1$ (i.e., $(Y,y)\in \mathfrak {R}_{\textit{\textbf{A}}}$), whereas an extracted witness $y'=\textit{\textbf{r}}'$ is only guaranteed to satisfy $\Vert \textit{\textbf{r}}'\Vert _{_\infty }\le 2(\gamma -\kappa )$ (i.e., $(Y,y')\in \mathfrak {R}_{\textit{\textbf{A}}}'$). Such a knowledge gap is inherent in the existing efficient lattice-based zero-knowledge proofs such as the one underlying Dilithium. However, we emphasize that this knowledge gap does not raise a security concern as our hardness assumptions require that finding even a witness as big as an extracted witness is still hard, which itself implies that finding an honest user’s witness is also hard. In the next section, we study the security aspects more rigorously.

3.1 Security Analysis

Pre-signature correctness follows via a straightforward investigation. In the following sequence of lemmas, we prove the security properties.

Lemma 1

(Weak pre-signature adaptability). $\mathsf {LAS}$ satisfies weak pre-signature adaptability with respect to the relation $\mathfrak {R}_{\textit{\textbf{A}}}$ given in Table 1.

Proof

Let $\hat{\sigma }=(c,\varvec{\hat{z}})$ be a valid pre-signature with and $y=\textit{\textbf{r}}'\in \mathbb {S}_1^{n+\ell }$ be a witness corresponding to $Y$. Note that $\Vert \varvec{\hat{z}}\Vert _{_\infty }\le \gamma -\kappa -1$ since $\hat{\sigma }$ is valid. Then, Now, we have

$$\begin{aligned} \Vert \textit{\textbf{z}}\Vert _{_\infty }=\Vert \varvec{\hat{z}}+\textit{\textbf{r}}'\Vert _{_\infty }\le \Vert \varvec{\hat{z}}\Vert _{_\infty }+\Vert \textit{\textbf{r}}'\Vert _{_\infty }= (\gamma -\kappa -1)+1 = \gamma -\kappa . \end{aligned}$$

(1)

We further have

(2)

From (1) and (2), it follows that $\sigma$ is valid, i.e., .    $\square$

Remark 1

Observe in the proof of Lemma 1 that we crucially rely on the fact that for a witness $y=\textit{\textbf{r}}'$ in $\mathfrak {R}_{\textit{\textbf{A}}}$, we have $\Vert \textit{\textbf{r}}'\Vert _{_\infty }\le 1$. An extracted witness $\textit{\textbf{s}}$ does not necessarily obey this rule as the relation $\mathfrak {R}_{\textit{\textbf{A}}}'$ only requires $\Vert \textit{\textbf{s}}\Vert _{_\infty }\le 2(\gamma -\kappa )$. Therefore, extra care needs to be taken when dealing with the cases where an extracted witness is used to adapt a pre-signature.

Lemma 2

(Witness extractability). If M-LWE$_{\ell ,n,q}$ and M-SIS$_{n,n+\ell +1,q,\beta }$ for $\beta =2\gamma \sqrt{d (n+\ell )}$ are hard, then $\mathsf {LAS}$ is witness extractable in the random oracle model.

Proof

Here, we only investigate the case that the signature output by the adversary shares the same challenge with the pre-signature. The other case (where the two challenges are distinct) can be proven exactly as in Case 2 of the proof of Lemma 3 because how $Y$ is generated is irrelevant for that case.

For a given pair of public key and statement and a message M, let $\hat{\sigma }=(c,\varvec{\hat{z}})$ and $\sigma =(c,\textit{\textbf{z}})$ be a valid pre-signature and a valid signature, respectively. Then, from the corresponding verification algorithms (i.e., $\mathsf {Verify}$ and $\mathsf {PreVerify}$), we have . Since is modelled as a random oracle, this holds only when $\textit{\textbf{Az}}-c\textit{\textbf{t}}=\varvec{A\hat{z}}-c\textit{\textbf{t}}+\textit{\textbf{t}}'$, which implies that $\textit{\textbf{Az}}-\varvec{A\hat{z}}=\textit{\textbf{A}}(\textit{\textbf{z}}-\varvec{\hat{z}})=\textit{\textbf{t}}'$. It is easy to see that $\Vert \textit{\textbf{z}}-\varvec{\hat{z}}\Vert _{_\infty }\le 2(\gamma -\kappa )$. Therefore, for the output $\textit{\textbf{s}}=\textit{\textbf{z}}-\varvec{\hat{z}}$ of $\mathsf {Ext}(Y,\sigma ,\hat{\sigma })$, we have $(\textit{\textbf{t}}',\textit{\textbf{s}})\in \mathfrak {R}_{\textit{\textbf{A}}}'$. Note also that $\textit{\textbf{s}}$ is non-zero since $\textit{\textbf{t}}'$ is non-zero except for a negligible probability.    $\square$

Lemma 3

(Unforgeability). If M-SIS$_{n,n+\ell +1,q,\beta }$ for $\beta =2\gamma \sqrt{d (n+\ell )}$ and M-LWE$_{\ell ,n,q}$ are hard, then $\mathsf {LAS}$ is secure in the random oracle model.

Proof

First, from the assumptions in the statement, we know that

• 1. both $\mathfrak {R}_{\textit{\textbf{A}}}$ and $\mathfrak {R}_{\textit{\textbf{A}}}'$ are hard relations,

• 2. any public key output by $\mathsf {KeyGen}$ and any statement output by $\mathsf {Gen}$ is indistinguishable from a uniformly random element in $\mathcal {R}_q^n$ due to Fact 2.

Let $\mathcal {F}$ be a PPT adversary who wins the security game with non-negligible probability. We will build an adversary $\mathcal {S}$ that solves M-SIS$_{n,n+\ell +1,q,\beta }$. Let $\beta =2\gamma \sqrt{d (n+\ell )}$ and $\textit{\textbf{B}}=[\, \textit{\textbf{I}}_n \, \Vert \, \textit{\textbf{A}}' \, \Vert \, \textit{\textbf{a}} \, ]\in \mathcal {R}_q^{n\times (n+\ell +1)}$ for $\textit{\textbf{A}}'\overset{\$}{\leftarrow }\mathcal {R}_q^{n\times \ell }$ and $\textit{\textbf{a}}\overset{\$}{\leftarrow }\mathcal {R}_q^{n}$. Assume that $\mathcal {S}$ wants to solve M-SIS w.r.t. $\textit{\textbf{B}}$. Let $\textit{\textbf{A}}$ denote $[\, \textit{\textbf{I}}_n \, \Vert \, \textit{\textbf{A}}' \, ]$.

Setup. $\mathcal {S}$ sets $\textit{\textbf{A}}$ together with some hash function as the public parameters. It is clear that $\textit{\textbf{A}}$ has the correct distribution. Then, it sets where $\textit{\textbf{r}}=\left( \begin{array}{c} \textit{\textbf{r}}' \\ 1 \end{array}\right)$ for $\textit{\textbf{r}}'\overset{\$}{\leftarrow }\mathbb {S}_1^{n+\ell }$. $\mathcal {S}$ sends to $\mathcal {F}$. By M-LWE$_{\ell ,n,q}$, is indistinguishable from a public key output by $\mathsf {KeyGen}$ since $\textit{\textbf{Br}}=\varvec{Ar'}+\textit{\textbf{a}}$ looks uniformly random as $\varvec{Ar'}$ does. Note also that is non-zero with overwhelming probability.

Oracle simulation. For $\mathcal {O}_\text {S}(M)$, $\mathcal {S}$ picks $\textit{\textbf{z}}\overset{\$}{\leftarrow }\mathbb {S}_{\gamma -\kappa }^{n+\ell }$ and $c\overset{\$}{\leftarrow }\mathcal {C}$, and programs the random oracle such that . If the input of has been queried before, $\mathcal {S}$ aborts. Otherwise, $\mathcal {S}$ returns $\sigma =(c,\textit{\textbf{z}})$. The simulated output is indistinguishable from a real one due to Fact 1.

For $\mathcal {O}_\text {pS}(M,Y)$, the simulator picks $\varvec{\hat{z}}\overset{\$}{\leftarrow }\mathbb {S}_{\gamma -\kappa -1}^{n+\ell }$ and $c\overset{\$}{\leftarrow }\mathcal {C}$, and programs the random oracle such that for $\textit{\textbf{t}}':=Y$. If the input of has been queried before, $\mathcal {S}$ aborts. Otherwise, the simulator returns $\hat{\sigma }=(c,\varvec{\hat{z}})$. The simulated output is indistinguishable from a real one due to Fact 1.

In both cases, the probability of an abort is negligible as $\mathcal {F}$ can make at most polynomially many queries to .

Forgery. $\mathcal {F}$ returns the target message $M^*$ to $\mathcal {S}$. $\mathcal {S}$ sets $Y=-\textit{\textbf{a}}$ and computes a pre-signature $\hat{\sigma }^*=(c^*,\varvec{\hat{z}}^*)$ using the simulation method above. $\mathcal {S}$ sends $(Y,\hat{\sigma }^*)$ to $\mathcal {F}$. Again, note that $Y$ is indistinguishable from a real output by $\mathsf {Gen}$, and $\hat{\sigma }^*$ is indistinguishable from a real output of $\mathsf {PreSign}$. Finally, $\mathcal {F}$ returns a forged signature $\sigma =(c,\textit{\textbf{z}})$ on $M^*$.

Case 1 $(c^*=c):$ If this is the case, then as shown in the proof of Lemma 2, $\mathcal {S}$ can extract a witness to $\mathfrak {R}_{\textit{\textbf{A}}}'$. That is, $\mathcal {S}$ gets $(Y,y)\in \mathfrak {R}_{\textit{\textbf{A}}}'$ with $\textit{\textbf{s}}':=y$, which implies that $\varvec{As'}=-\textit{\textbf{a}}$ (since $Y=-\textit{\textbf{a}}$) and $\Vert \textit{\textbf{s}}'\Vert _{_\infty }\le 2(\gamma -\kappa )$. This is equivalent to $\varvec{B\textit{\textbf{s}}}=\textit{\textbf{0}}$ for $\textit{\textbf{s}}=\left( \begin{array}{c} \textit{\textbf{s}}' \\ 1 \end{array}\right)$. Note that $\left\| \textit{\textbf{s}}\right\| \le \beta$. Hence, $\mathcal {S}$ finds a solution to M-SIS$_{n,n+\ell +1,q,\beta }$.

Case 2 $(c^*\ne c):$ In this case, we know that the forged signature’s challenge comes from a random oracle query output (with overwhelming probability). Therefore, we can use a standard rewinding argument as in [26], where $\mathcal {S}$ rewinds $\mathcal {F}$ to get another forgery $\sigma '=(c',\textit{\textbf{z}}')$ such that $c'\ne c$ and . Therefore, we have

$$\begin{aligned} \textit{\textbf{A}}\textit{\textbf{z}}'-c'\textit{\textbf{t}}=\textit{\textbf{A}}\textit{\textbf{z}}-c\textit{\textbf{t}} \quad \iff \quad \textit{\textbf{A}}\left( \textit{\textbf{z}}'-\textit{\textbf{z}}\right) = (c'-c)\textit{\textbf{t}}. \end{aligned}$$

(3)

Since $c'\ne c$, we have $\textit{\textbf{z}}'-\textit{\textbf{z}}\ne 0$. The above equation (3) can be equivalently written as

$$\begin{aligned} \textit{\textbf{B}}\left( \begin{array}{c} \textit{\textbf{z}}'-\textit{\textbf{z}} \\ 0 \end{array}\right) = (c'-c)\textit{\textbf{t}}. \end{aligned}$$

(4)

Now recalling that $\textit{\textbf{t}}=\textit{\textbf{Br}}$, we also have

$$\begin{aligned} (c'-c)\textit{\textbf{t}} = \textit{\textbf{B}}\cdot (c'-c)\textit{\textbf{r}}. \end{aligned}$$

(5)

Subtracting (3) from (5), we get

$$\begin{aligned} \textit{\textbf{B}} \left[ (c'-c)\textit{\textbf{r}} - \left( \begin{array}{c} \textit{\textbf{z}}'-\textit{\textbf{z}} \\ 0 \end{array}\right) \right] = \textit{\textbf{0}}. \end{aligned}$$

(6)

Recalling that the last coordinate of $\textit{\textbf{r}}$ is 1, i.e., non-zero, the above gives a non-trivial solution to M-SIS$_{n,n+\ell +1,q,\beta }$. Here note that $\left\| \textit{\textbf{z}}'-\textit{\textbf{z}}\right\| \le 2(\gamma -\kappa )\sqrt{d(n+\ell )}<\beta$ and $\left\| (c'-c)\textit{\textbf{r}}\right\| \le 2\kappa \sqrt{d(n+\ell +1)}$. Since $\gamma \gg \kappa$, the total norm of the M-SIS solution remains below $\beta =2\gamma \sqrt{d(n+\ell )}$.    $\square$

3.2 Parameter Setting and Performance Analysis

First, we set $\gamma =\kappa d(n+\ell )$ so that the average number of restarts in $\mathsf {Sign}$ and $\mathsf {PreSign}$ is about $e<3$. Then, we set $d=256$ and $\kappa =60$, which ensures that the challenge set $\mathcal {C}$ has more than $2^{256}$ elements. Finally, in order to meet the M-SIS$_{n,n+\ell +1,q,\beta }$ and M-LWE$_{\ell ,n,q}$ security requirements for $\beta =2\gamma \sqrt{d(n+\ell )}$, we set $n=\ell =4$ and $q\approx 2^{24}$. Only the size of the modulus q is important, and therefore the concrete value can be chosen to allow fast computation such as Number Theoretic Transformation (NTT).

In estimating the practical security of M-SIS and M-LWE, we follow the methodology outlined in [10, Section 3.2.4] and measure the practical hardness in terms of “root Hermite factor” $\delta$. This parameter setting yields $\delta <1.0045$ for both M-SIS and M-LWE. $\delta \approx 1.0045$ has been used in recent works, e.g., [12,13,14] for targeting 128-bit post-quantum security. From here, we can compute the concrete signature length as

$$\begin{aligned} |\sigma | = d(n+\ell )\log (2\gamma )/8 + 32 \text{ bytes } \approx 3210 \text{ bytes }. \end{aligned}$$

(7)

This length is slightly larger than the size of Dilithium (2701 bytes) [9] with recommended parameters. The main reason is because we do not employ the optimizations for ease of presentation.

In terms of the computational efficiency, the operations performed in $\mathsf {LAS}$ are almost identical to those in Dilithium. Thus, hundreds of signing (and even more verification) can be done per second on a standard PC as shown in [9, Table 2].

4 Applications

In this section, we present two blockchain applications of our adaptor signature, namely atomic swaps and payment channel networks. To match with the existing adaptor signature applications, we assume an Unspent Transaction Output (UTXO)-based blockchain like Bitcoin where the signature algorithm is replaced with a lattice-based signature scheme given in Algorithm 1 . In the UTXO model, coins are kept in addresses where each address consists of the amount and the spending condition. The spending condition is defined by the scripting language and the most common ones are signature and hash preimage verifications, and timing conditions. For our applications, we also assume that the underlying blockchain supports these scripts.

4.1 Atomic Swaps

An atomic swap can be defined between two users $u_1$ and $u_2$ who want to exchange two different cryptocurrencies $c_1$ and $c_2$. The crucial point of the exchange is ensuring fairness, i.e., either both parties receive their expected output or none do. In [23], an atomic swap protocol is presented with the following steps.

Setup. First, $u_1$ shares a hash value of a secret $r_1$ to $u_2$. Then, $u_1$ creates a transaction on the coins $c_1$ such that it can be spendable by $u_2$ only if the preimage of $h_1$ is presented. Similarly, $u_2$ also creates a transaction on the coins $c_2$ with the same preimage condition for $u_1$. Here, both transactions have timeouts $t_i$ such that, once $t_i$ elapses, $u_i$ can redeem $c_i$ if the counterparty does not continue to the exchange. Also, the timelock, $t_2$, on $u_2$’s transaction is shorter (i.e., $t_2<t_1$) to ensure that $u_2$ would have enough time to react. First, $u_1$ publishes her transaction on-chain, then $u_2$ does the same.

Swap. Once both transactions are on-chain, $u_1$ can obtain $c_2$ by revealing $r_1$, which yields to $u_2$ obtaining $c_1$. Note that this protocol requires both scripting languages of the cryptocurrencies to have preimage conditioned scripts. Later on, in [24], the scriptless version of the protocol is presented where the hash condition is embedded into the signature algorithm.

Let us explain how to achieve atomic swaps using $\mathsf {LAS}$, which requires careful analysis because of the aforementioned knowledge gap. In the scenario below, an extracted witness, which satisfies an extended relation (i.e., $\mathfrak {R}_{\textit{\textbf{A}}}'$, but not necessarily $\mathfrak {R}_{\textit{\textbf{A}}}$), will constitute the opening condition to receive coins.

Let be the public-secret key pair for user $u_i$ for $i=1,2$. First, $u_1$ generates a statement-witness pair $(Y,y)=(\textit{\textbf{t}},\textit{\textbf{r}})\in \mathfrak {R}_{\textit{\textbf{A}}}$ as in Section 3, and sends Y to $u_2$ along with a proof $\pi$ of knowledge of a witness $\textit{\textbf{r}}$ such that $\textit{\textbf{t}}=\textit{\textbf{Ar}}$ and $\Vert \textit{\textbf{r}}\Vert _{_\infty }\le 1$. Such a proof can be realized using the recent Esgin-Nguyen-Seiler proof system [11]. Then, $u_1$ also creates a pre-signature for $\mathsf {tx}_1$ spending the coins $c_1$ to $u_2$. After verifying the proof $\pi$, $u_2$ similarly creates a pre-signature for $\mathsf {tx}_2$ spending the coins $c_2$ to $u_1$. Then, the two pre-signatures are exchanged between the parties. Now $u_1$ adapts the pre-signature $\hat{\sigma }_2$ as $\hat{\sigma }_2,\mathsf {tx}_2)$, and aborts if $\sigma _2=\perp$. Otherwise, he publishes the full signature $\sigma _2$ on the second cryptocurrency’s blockchain in order to receive the coins $c_2$. Then, seeing $\sigma _2$, $u_2$ runs $y'=\textit{\textbf{s}}\leftarrow \mathsf {Ext}(Y,\sigma _2,\hat{\sigma }_2)$ and . If any of them returns $\perp$, $u_2$ aborts. Otherwise, $u_2$ publishes $\sigma _1$ on the first cryptocurrency’s blockchain to receive the coins $c_1$. This interaction is depicted in Figure 1.

Fig. 1.

Atomic swap protocol using $\mathsf {LAS}$.

Let us now analyze whether $u_1$ receives $c_2$ if and only if $u_2$ receives $c_1$. If $u_1$ does not receive $c_2$, i.e., $u_1$ aborts, then $u_2$ clearly cannot receive $c_1$ due to the security of $\mathsf {LAS}$ as $u_2$ only has the pre-signature $\hat{\sigma }_1$ and the statement Y (without a witness to Y). On the other hand, if $u_1$ does receive $c_2$, this means that $\sigma _2$ is valid signature published on a blockchain, i.e., accessible by $u_2$. Therefore, by the witness extractability of $\mathsf {LAS}$, $u_2$ can extract a witness $\textit{\textbf{s}}$ to $Y=\textit{\textbf{t}}$ such that $\textit{\textbf{t}}=\textit{\textbf{As}}$. Recall that $u_1$ proved knowledge of a witness $\textit{\textbf{r}}$ to $Y=\textit{\textbf{t}}$ such that $\Vert \textit{\textbf{r}}\Vert _{_\infty }\le 1$. By the hardness of M-SIS, it must be the case that $\textit{\textbf{s}}=\textit{\textbf{r}}$ as otherwise $\textit{\textbf{A}}(\textit{\textbf{s}}-\textit{\textbf{r}})=0$ gives a solution to M-SIS$_{n,n+l,q,\beta }$ for $\beta =2\gamma \sqrt{d(n+\ell )}$. As a result, we have that $\Vert \textit{\textbf{s}}\Vert _{_\infty }=\Vert \textit{\textbf{r}}\Vert _{_\infty }\le 1$. Therefore, $\textit{\textbf{s}}\in \mathfrak {R}_{\textit{\textbf{A}}}$ and the pre-signature adaptability works, and hence the signature $\sigma _1$ adapted by $u_2$ passes the verification. Note that without the proof of knowledge $\pi$, we cannot guarantee that the extracted witness $\textit{\textbf{s}}$ will satisfy $\Vert \textit{\textbf{s}}\Vert _{_\infty }\le 1$, and hence pre-signature adaptability would not have been guaranteed without $\pi$. In other words, $\pi$ is essential to make sure that $u_2$ receives the coins $c_1$.

We also note that even though a lattice-based proof of knowledge, $\pi$, is relatively costly in terms of communication in practice (but very efficient in computation), this proof is only exchanged between the parties, and not published on blockchain. Therefore, it does not incur additional on-chain storage costs.

4.2 Payment Channel Networks

Payment channel networks (PCNs)  [7, 16, 21, 27] are one of the promising solutions to the scalability issues of blockchains. More specifically, many blockchains have poor transaction throughput compared to alternatives like credit card networks because of their consensus mechanisms, where every party (miner) approves and stores every transaction. PCNs improve the throughput by moving some transactions off-chain while relying on the security of the blockchain. In a PCN, two parties can lock coins into a channel where they can make instant and arbitrarily many transactions between each other so long as they have enough balances. One of the most popular PCNs built on Bitcoin is the Lightning network  [27]. The overall structure of our post-quantum PCN resembles the Lightning network.

A payment channel consists of three steps: create, update, and close. In the creation phase, parties deposit some coins into the channel and create a funding transaction that spends the input addresses into a single output of the channel. The funding transaction is published on the blockchain and afterward, all of the updates are done off-chain until the closing part. The output condition of funding is spendable only if both parties sign it, which ensures an agreement by both parties. The condition can be implemented by a two-party multi-signature.

In realizing a two-party multi-signature, a straightforward option is to simply combine two individual signatures. Alternatively, there is a lattice-based multi-signature in [4], which can be used in the two-party setting. The underlying signature uses the same “Fiat-Shamir with Aborts” technique, and as stated in [4], the multi-signature can be realized over module lattices as in our work.

When parties want to send/receive coins in the channel, they make off-chain transactions and update the channel balances. In each update, parties create new commit transactions that spend the output of the funding transaction into the two new addresses of the parties with their corresponding balances. Also, parties revoke the previous commits by sharing the signing keys with each other. The revocation can be seen as a punishment mechanism to prevent a malicious party from publishing an old commitment. Once parties are done with the channel, they can close it and obtain their coins by publishing the latest commitment on-chain. A payment channel creation, update, and closing can be done in the same manner as the Lightning network. Now, we investigate how to achieve multi-hop payments with our adaptor signature scheme.

A network of channels allows parties to make multi-hop payments. More specifically, parties, who do not have a direct channel, can route a payment using the channels of some intermediary nodes. In these multi-hop payments, it is crucial to synchronize each channel on the route so that either all of them update accordingly or no one does. The Lightning network achieves this by using HTLC (hash-time lock contract). However, in  [21], the authors presented privacy concerns as well as the wormhole attack for the HTLC mechanism. In this manner, we adopt the AMHL (anonymous multi-hop lock) technique  [21] for the multi-hop payments. Also, it is stated that AMHLs are sufficient to construct a payment channel network  [21, Theorem 4]. In a scenario where sender S (or $I_0$) wants to send payment through the intermediary nodes $I_1,\ldots ,I_{k-1}$ to the receiver R (or $I_{k}$), AMHL-based multi-hop payment works as follows (for simplicity, we omit the fees given to the intermediary nodes).

Setup. S chooses random strings $\ell _0,\ell _1,\ldots ,\ell _{k-1}$, and computes $y_j := \sum _{i=0}^{j} \ell _i$ and for $j=0,\ldots ,k-1$ where is an additively homomorphic one-way function. Then, S shares $(Y_{j-1},Y_j,\ell _j)$ with each intermediary $I_j$ for $i=1,\ldots ,k-1$ and $(Y_{k-1},y_{k-1})$ with R. Each intermediary party $I_j$ validates the correctness of values by using the homomorphism, i.e., checking that , where $\oplus$ denotes the operation in the range of .

Payment. S makes a conditional payment to $I_1$ requiring preimage of $Y_0$, while each intermediary party $I_j$, for $j=1,\ldots ,k-1$, makes a payment of the same amount to $I_{j+1}$ with a condition on preimage of $Y_j$ after they receive a similar payment from $I_{j-1}$. Once all conditional payments are placed, S reveals the preimage $y_{k-1}$ to $R=I_k$ showing that she can redeem the payment. This creates a chain reaction as follows. When an intermediary party $I_j$ receives $y_j$ from $I_{j+1}$, he can compute $y_{j-1} = y_j - \ell _j$ and redeem the payment by revealing $y_{j-1}$ to $I_{j-1}$. The procedure is completed once all the channels are updated accordingly.

We can realize AMHL in the post-quantum setting using $\mathsf {LAS}$, but again a special care is required due to the knowledge gap and the use of rejection sampling. First of all, we assume that the length of the PCN is at most $K\ll q$ (i.e., $k\le K\ll q$) and update the norm check at Steps 6 and 11 in Algorithm 2 by $\Vert \varvec{\hat{z}}\Vert _{_\infty }>\gamma -\kappa -K$. Now, S samples $\textit{\textbf{r}}_j\overset{\$}{\leftarrow }\mathbb {S}_1^{n+\ell }$, and computes $\textit{\textbf{s}}_j=\sum _{i=0}^{j}\textit{\textbf{r}}_i$ and $\textit{\textbf{t}}_j=\textit{\textbf{As}}_j$ for $j=0,\ldots ,k-1$. Observe that we have $\Vert \textit{\textbf{s}}_j\Vert _{_\infty } \le k \le K \text{ for } \text{ all } j=0,\ldots ,k-1.$ Then, S treats $Y_j=\textit{\textbf{t}}_j$, $y_j=\textit{\textbf{s}}_j$ and $\ell _j=\textit{\textbf{r}}_j$ for $j=0,\ldots ,k-1$. The additively homomorphic function is $f_{\textit{\textbf{A}}}(\textit{\textbf{x}})=\textit{\textbf{Ax}}$ (over $\mathcal {R}_q$) mentioned in Section 3. Then, the Setup phase of AMHL described above is run. Additionally, for each $j=0,\ldots ,k-2$, S sends $I_{j+1}$ a NIZK proof $\pi _{j+1}$ that she knows a witness $y_{j}=\textit{\textbf{s}}_{j}$ to $Y_{j}=\textit{\textbf{t}}_{j}$ such that

$$\begin{aligned} \Vert \textit{\textbf{s}}_{j}\Vert _{_\infty }\le K. \end{aligned}$$

(8)

Fig. 2.

Anonymous multi-hop payments using $\mathsf {LAS}$. We assume that (i) $T_j$’s are transmitted confidentially, (ii) pre-signature transmission from $I_j$ to $I_{j+1}$ happens only if that from $I_{j-1}$ to $I_{j}$ already happened, and (iii) signature transmission from $I_{j+1}$ to $I_{j}$ happens only if that from $I_{j+2}$ to $I_{j+1}$ already happened.

After this setup, payment phase begins. Let be $I_j$’s public-secret key pair used in his channel with $I_{j+1}$, and $\mathsf {tx}_j$ be the transaction transferring the relevant coins from $I_j$ to $I_{j+1}$. S creates a pre-signature and sends it to $I_1$. Then, for $j=1,\ldots ,k-1$, each user $I_j$ creates a pre-signature after receiving the pre-signature $\hat{\sigma }_{j-1}$ from $I_{j-1}$. Once all pre-signatures are generated and transferred, S reveals $y_{k-1}$ to R, which allows R to adapt the pre-signature $\hat{\sigma }_{k-1}$ to $\sigma _{k-1}$ in order to receive the relevant coins from $I_{k-1}$. R sends $\sigma _{k-1}$ to $I_{k-1}$. From here, $I_{k-1}$ extracts a witness $y_{k-1}'$ to $Y_{k-1}$. Then, she computes $y_{k-2}''=y_{k-1}'-\ell _{k-1}$ and uses it to complete the pre-signature $\hat{\sigma }_{k-2}$. Continuing this way, completion of a pre-signature by $I_j$ enables $I_{j-1}$ to obtain a witness to $Y_{j-1}$ and then compute a witness to $Y_{j-2}$ using $\ell _j$. The process ends with S receiving $\sigma _0$. This anonymous multi-hop payment procedure is depicted in Figure 2.

Let us analyze the details now. First of all, each party $I_j$ has a proof that S knows a witness $y_{j-1}=\textit{\textbf{s}}_{j-1}$ to $Y_{j-1}$ satisfying (8). Due to the M-SIS hardness as before, no party $I_j$ can obtain another witness to $Y_{j-1}$, but $y_{j-1}$ generated by S. Therefore, each party $I_j$ is ensured that the witness he extracts will have infinity norm at most K. As a result, each party $I_j$ will be able to adapt the pre-signature $\hat{\sigma }_{j-1}$ successfully and claim his coins thanks to the aforementioned change to Steps 6 and 11 in Algorithm 2.

We emphasize again the importance of the proof $\pi _j$’s that guarantee pre-signature adaptability. These proofs are only communicated off-chain and thus do not incur any additional on-chain cost, and can be realized using the techniques in [11]. Moreover, the change to Steps 6 and 11 in Algorithm 2 is also important as, in this setting, even honestly-generated witnesses have potentially absolute coefficients greater than 1, but still at most K. Note that this change does not affect the security assumptions as still the original conditions (and even stronger ones) in Algorithms 1 and 2 hold. The only effect is that $\mathsf {PreSign}$ may have more restarts, but for most practical settings of, say, $K\le 50$ (i.e., the length of the PCN is at most 50), the effect will be minimal. In practice, for example, in Lightning Network, the route search algorithm typically stops after $K=20$  [1].

5 Conclusion

In this work, we constructed the first post-quantum adaptor signature based on standard lattice assumptions. We also showed that our construction, $\mathsf {LAS}$, leads to efficient atomic swaps and payment channel networks in the post-quantum world. In particular, our applications do not incur additional costs on the blockchain, other than the cost of an ordinary lattice-based signature.