Abstract
The development of threshold protocols based on lattice-signature schemes has been of increasing interest in the past several years. The main research focus has been towards protocols constructed for various variants of Crystals-Dilithium, future NIST digital signature standard known as ML-DSA. In this work, we propose TOPCOAT, a two-party lattice-based signature algorithm that embodies Dilithium’s compression techniques. The aforesaid result is achieved by introducing a new hinting mechanism that allows parties to collaboratively calculate \(\textsf {HighBits}\). Our hinting mechanism allows public key compression similar to Dilithium. Additionally, we suggest an optimization technique to minimize number of restarts both parties need to produce a valid signature. Our approach allows to produce \(\approx 10\) KB signatures within 3 rounds of communication. We prove security of our scheme under MLWE and MSIS assumptions in ROM, and provide implementation of our proposed scheme. As additional contribution, we present vulnerabilities and inconsistencies found in Liu et al. work (Future Generation Computer Systems 2023) which aimed to construct distributed lattice-based signature protocol.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Threshold cryptography, particularly threshold signature schemes, has become a compelling research topic in recent years. Using these protocols, a certain set of parties may transfer their joint right to generate a signature to any subset among themselves equal to or larger than a specific threshold. There are threshold variants of RSA [23, 32, 63], Schnorr [28, 30, 50, 57], EdDSA [16, 45, 51, 58] and ECDSA [1, 24, 36, 53, 68] signatures, which could be used in the blockchain infrastructure or as an authentication solution [22]. With several parties being required to participate in the generation of a signature, it is not unreasonable to somewhat relax the security requirements on any single party, related to the storage or handling of its private key material.
In the authentication use-case, the mobile device of a user is a party that cannot securely manage the key material on its own (unless we rely on some trusted hardware that is part of the mobile platform). However, the mobile’s device security measures could be deemed acceptable in a threshold signing process, where it would hold one share of the private key, and an assisting server would hold another share. In this case, both parties need to interact in order to create a single signature. If the adversary gets access to the mobile device, it will be unable to create valid signatures on behalf of the user without communicating with the server. Following this principle, QSCD (Qualified Signature Creation Device) level service Smart-ID Footnote 1 was developed in Baltic States allowing millions of users to securely authenticate in public and private services. Smart-ID underlying cryptographic protocol, SplitKey Footnote 2 is build upon two-party RSA digital signature scheme by Buldas et al [22].
Security of Smart-ID relies on hardness of mathematical problems such as factorisation and RSA problem [21]. In 1994, Peter Shor [62] described a quantum algorithm that allows solving factorisation problem (alongside with discrete logarithm problem [56]) in polynomial time. When a cryptographically significant quantum computer will be constructed, the security of RSA alongside with Schnorr, EdDSA, ECDSA signature schemes and their threshold variants will be broken. To prevent information security systems from total breakdown, in 2016, the National Institute of Standards and Technology (NIST) announced a Post-Quantum Cryptography Standardization Process to select future quantum-safe key encapsulation mechanism and digital signature algorithms .Footnote 3 Out of 69 candidates, the Crystals-Kyber [17] was selected for KEM category and Crystals-Dilithium [38], Sphincs\(^{+}\) [13], Falcon [42] for signature category .Footnote 4 In this paper, we aim to construct a two-party signature scheme based on the Crystals-Dilithium signature—the primary post-quantum signature scheme that will be standardised by NIST as ML-DSA [47]. Our main focus is to design a two-party signature scheme that would fit in the server-supported authentication use case described above and implemented in Smart-ID. Hence we aspire to create a 2-out-of-2 threshold scheme, leaving different thresholds and numbers of parties out of the scope of this work.
1.1 Contributions
In this work, we introduce TOPCOAT—a lattice-based 2-out-of-2 distributed signature protocol which is built upon Crystal-Dillithium (ML-DSA). Our construction benefits from the public key compression and the \(\textsf {HighBits}\) compression techniques. It is worth to mention that the adoption of the compression techniques leads to the problem of accommodating a bit carry. We solve it with the introduction of a hinting technique as an additional part of the protocol. The hint component is added to the final signature and the length this hint is (less than) three bits for each coefficient of each polynomial in \(\textbf{z}\) component of the Dilithium signature. While it increases the length of the resulting signature, the total size is still much less than doubling the number of polynomials. We show that the unforgeability of the signature scheme with the hint still reduces to the hardness of the Module-SIS and Module-LWE problems. Our hints are different from the hints applied in Crystals-Dilithium to support public key compression. Nevertheless, our hinting technique also supports the public key compression, i.e., we propose the first threshold Dilithium-like signature scheme with the public key compression and Bai-Galbraith compression mechanism [7].
Our second improvement concerns rejection sampling. In the Fiat-Shamir with Aborts (FSwA) paradigm, the signature component \(\textbf{z}\) may be output only if its norm is less than a certain bound, otherwise a portion of a private key will be leaked. If \(\textbf{z}\) does not fall inside these bounds, it has to be rejected and the signing procedure has to be restarted. The parameters of the “standard” Crystals-Dilithium have been selected so that a signature is computed on average after 4–5 tries. In the threshold signing protocols with similar parameters, where rejection conditions are checked locally (in [33], as well as in our protocol), this number has to be exponentiated with the number of participants.
To increase the chances of passing rejection sampling, we increase the number of possible challenges by combining the first party’s share from a protocol instance with the second party’s share from any protocol instance. In this manner, if both parties execute n sessions of generating shares of the challenge, we have \(n^2\) possible challenges to try out, reducing the probability of rejection by exactly the same amount that was introduced due to the existence of several protocol parties.
We prove the security of our scheme in the classical random oracle model and show that the security of our scheme follows from the hardness of Module-SIS and Module-LWE problems. Additionally, we present results of the implementation of TOPCOAT, propose a set of parameters and compare our proposed scheme with the other approaches.
As minor contribution, we outline a set of inconsistencies of Liu et al. work [54] in Sect. 7.
2 Related work
Since our main focus is on the 2-out-of-2 case, we outline the recent work on various distributed signature schemes based on Crystals-Dilithium and its variants. The first work to propose threshold version of Crystals-Dilithium was by Cozzo and Smart [29] that studied signature schemes that participated in the second round of the NIST PQC competition to develop threshold variants. For the proposed protocol, estimated time to produce one Dilithium signature is about 12 seconds. Such slow execution is caused by the usage of generic multiparty computation techniques. Authors only explained how to build threshold signature of simplified Crystals-Dilithium which does not include public key compression.
Fukumitsu and Hasegawa [44] proposed a lattice-based multisignature scheme based on the Dilithium-QROM [49]. The work provided a security analysis of the proposed protocol against quantum adversary. Unfortunately, as noticed by Boudgoust and Takahashi [19], this protocol is vulnerable to the partial key extraction attack.
Later Damgård et al. [33] proposed two n-out-of-n threshold signature schemes based on Dilithium-G [38]. The first (\(\textsf {DS}_2\)) is a two-round threshold signature scheme utilizing statistically hiding trapdoor homomorphic commitment scheme. The second (\(\textsf {DS}_3\)) is a three-round threshold signature protocol with a statistically binding homomorphic commitment scheme [9]. The signature sizes in \(\textsf {DS}_2\) and \(\textsf {DS}_3\) protocols are bigger compared to the Crystals-Dilithium, since those protocols avoid the Bai-Galbraith compression mechanism [7]. Dobias et al. [35] introduced a variant of (\(\textsf {DS}_2\)) with the public key compression, but without providing a security proof and adding the Bai-Galbraith compression.
Similar protocol was proposed by Vakarjuk et al. [66], but it is built on homomorphic hash function [55] instead of a homomorphic commitment scheme. One of the disadvantages of this work, is that its security proof relies on a variant of non-standard rejected Module-LWE assumption introduced in [44]. Another serious issue is that SWIFFT hash function, suggested to be used by authors, is not additively homomorphic for all inputs.
A multisignature scheme \(\textsf {MuSig}\)-\(\textsf {L}\) was proposed by Boschini et al. [18]. Their construction does not rely on additional primitives such as homomorphic commitments or homomorphic encryption. Still it does utilise key and/or signature compression techniques from the Crystals-Dilithium.
There was an attempt to construct two-party Crystals-Dilithium signature by Fu et al.[43] using BFV homomorphic encryption [20, 39]. However, recently, Wu et al.[67] showed that their protocol does not achieve completeness and is vulnerable to the private key extraction attack.
A version of the multisignature protocol from [33] was proposed by Liu et al. [54] with added deterability functionality. This functionality allows to punish one of the participants for malicious behavior by publishing its private key. Alas, their protocol has correctness mistakes and inaccurate security claims as we point out in the Sect. 7.
More recent works by Tang et al. [64] and Alkadri et al. [3] propose protocols based on different versions of Crystals-Dilithium signature scheme. Tang et al. [64] proposed t-out-of-n threshold digital signature which is functionally interchangeable (i.e. t parties produce the same signature, as one party does) with a variant of Crystal-Dilithium introduced by the authors. In other words, t parties produce the same signature, as one party does. Their construction could be seen as \(\textsf {DS}_3\) [33] utilising SPDZ protocol [31] to achieve t-out-of-n use-case. Alkadri et al. [3] proposed a lattice-based distributed signature protocol based on Dilithium-G which is claimed to be efficient for small number of participants. Their protocol relies on linear combinations like \(\textsf {MuSig}\)-\(\textsf {L}\) [18] and on tree of commitments [4] to reduce the number of restarts.
We take note of the fact that the substantial progress has been made in the field of lattice-based distributed signatures based not upon Crystals-Dilithium signature [11, 14, 15, 25,26,27, 40, 41, 46, 59], but all these approaches are out of scope of this paper.
3 Preliminaries
3.1 Notation
Let \(a \leftarrow A\) denote a sampling of an element uniformly at random from the set A. \(a \leftarrow \chi (A)\) denotes sampling an element from the distribution \(\chi\) defined over the set A. \(\perp\) is used to indicate a failure or rejection, \(\oplus\)—exclusive disjunction (XOR). \(\mathbb {Z}\) denotes the set of integers, \(\mathbb {Z}_{q}\)—the set of integers modulo q.
Let R and \(R_q\) denote the rings \(\mathbb {Z}[x]/(x^N + 1)\) and \(\mathbb {Z}_q[x]/(x^N + 1)\) respectively, where q is a prime number and \(N \in \mathbb {N}\). We denote elements of R and \(R_q\) by italic lowercase letters p. We denote vectors with elements in R and \(R_q\) by bold lowercase \(\textbf{v}\) and matrices with elements in R and \(R_q\) by bold uppercase \(\textbf{A}\).
We follow the notation from Ducas et al. [38] for centered modular reduction \(\mathbin {\bmod ^\pm }{\alpha }\). For a positive integer \(\alpha\) and for \(x \in \mathbb {Z}\), define \(x' = x \mathbin {\bmod ^\pm }{\alpha }\), if \(x' \equiv x \pmod {\alpha }\) and either \(-\frac{\alpha }{2} < x' \le \frac{\alpha }{2}\) (if \(\alpha\) is even) or \(-\frac{\alpha - 1}{2} \le x' \le \frac{\alpha - 1}{2}\) (if \(\alpha\) is odd).
For an element \(x \in \mathbb {Z}_q\), its infinity norm is defined as \(\Vert x \Vert _{\infty } = |x \mathbin {\bmod ^\pm }{q}|\), where |x| denotes the absolute value of the element. For an element \(p \in R_q\), its infinity norm is defined as \(\Vert p \Vert _{\infty } = \max _{i} \Vert p_i \Vert _{\infty }\) and its \(l_2\) norm is defined as \(\Vert p \Vert _{2} = \sqrt{(\sum _i \Vert p_i\Vert ^{2}_{\infty })}\). \(S_{\eta }\) denotes the set of all elements \(p \in R_q\) such that \(\Vert p \Vert _{\infty } \le \eta\).
3.2 Hardness assumptions
Definition 1
(Decisional Module-LWE, D-MLWE) Let \(\chi\) be a probability distribution and \(n,m,q,\eta \in \mathbb {N}\). We define the advantage of adversary \(\mathcal {A}\) in breaking decisional Module-LWE for the set of parameters (\(q,n,m, \eta , \chi\)) as \(\textsf {Adv}_{(q,n,m,\eta , \chi )}^{\textsf {D-MLWE}}(\mathcal {A}):= |P_0^{\textsf {D-MLWE}} - P_1^{\textsf {D-MLWE}}|\), where:
\(P_0^{\textsf {D-MLWE}} = \textrm{Pr}[b=1: \textbf{A} \leftarrow R_q^{n \times m}, (\textbf{s}_1, \textbf{s}_2) \leftarrow \chi (S_{\eta }^m \times S_{\eta }^n),\textbf{t}:= \textbf{As}_1 + \textbf{s}_2, b \leftarrow \mathcal {A}(\textbf{A}, \textbf{t})\)
\(P_1^{\textsf {D-MLWE}} = \textrm{Pr}[b=1:\textbf{A} \leftarrow R_q^{n \times m}, \textbf{t} \leftarrow R_q^{n}, b \leftarrow \mathcal {A}(\textbf{A}, \textbf{t}).\)
Definition 2
(Computational Module-LWE, C-MLWE) Let \(\chi\) be a probability distribution and \(n,m,q,\eta \in \mathbb {N}\). We define the advantage of adversary \(\mathcal {A}\) in breaking computational Module-LWE for the set of parameters (\(q,n,m, \eta , \chi\)) as follows: \(\textsf {Adv}_{(q,n,m,\eta , \chi )}^{\textsf {C-MLWE}}(\mathcal {A}):=\textrm{Pr}[\textbf{s}_1 = \textbf{s}_1': \textbf{A} \leftarrow R_q^{n \times m}, (\textbf{s}_1, \textbf{s}_2) \leftarrow \chi (S_{\eta }^m \times S_{\eta }^n), \textbf{t}:= \textbf{As}_1 + \textbf{s}_2, \textbf{s}'_1 \leftarrow \mathcal {A}(\textbf{A}, \textbf{t})].\)
Definition 3
(Module-SIS, MSIS) Let \(n,m,q,\eta \in \mathbb {N}\). We define the advantage of adversary \(\mathcal {A}\) in breaking Module-SIS for the set of parameters (\(q,n,m,\eta\)) as follows: \(\textsf {Adv}_{(q,n,m,\eta )}^{\textsf {MSIS}}(\mathcal {A}):=\textrm{Pr}[\begin{bmatrix} \textbf{A}&|&\textbf{I} \end{bmatrix} \cdot \textbf{x} = \textbf{0} \pmod {q} \text { and }\) 0 \(< \Vert \textbf{x} \Vert _{\infty } \le \eta : \textbf{A} \leftarrow R_q^{n \times m}, \textbf{x} \leftarrow \mathcal {A}(\textbf{A})].\)
3.3 Crystals-Dilithium
Crystals-Dilithium is a lattice-based signature scheme that is constructed from an identification protocol using the Fiat-Shamir with aborts (FSwA) approach [38]. NIST selected to standardise Crystals-Dilithium as Module Lattice-Based Digital Signature Standard (ML-DSA) [47]. Security of this signature scheme is based on the hardness of Module-SIS and Module-LWE problems.
To achieve high performance, Crystals-Dilithium uses supporting algorithms to extract high-order and low-order bits out of each coefficient of an element from the ring \(R_q\). \(\textsf {Decompose}_q(r,\alpha )\) decomposes input \(r\in \mathbb {Z}_q\) to \(r = r_H \cdot \alpha + r_L\), such that \(0 \le r_H < \frac{(q - 1)}{\alpha }\) and \(\Vert r_L \Vert _{\infty } \le \frac{\alpha }{2}\). To apply \(\textsf {Decompose}_q(\cdot ,\alpha )\) algorithm to an element (or vector of elements) from the ring \(R_q\), one needs to apply \(\textsf {Decompose}_q(\cdot ,\alpha )\) to each coefficient separately. Algorithms \(\textsf {MakeHint}_q\) and \(\textsf {UseHint}_q\) produce a hint and, respectively, use the hint that helps to recover the high-order bits of the sum.
Figure 2 presents a Crystals-Dilithium signature scheme [38] and supporting algorithms, on which TOPCOAT protocol presented in this work is based. The challenge space \(\mathcal {C} = \{c \in R_q: \Vert c \Vert _{\infty } = 1 \text { and } \Vert c \Vert _{2} = \sqrt{\tau }\}\) is parameterised by \(\tau\) and consists of polynomials with small infinity norm. \(\mathcal {C}\) is used as the image of the random oracle \(\textsf {H}_0\).
3.4 Distributed signature protocol
Definition 4
(Distributed signature protocol) A distributed signature protocol between \(P_1,...,P_n\) parties consists of the following algorithms:
-
\(\textsf {Setup}(1^{\lambda })\) is an algorithm that takes as input a security parameter \(\lambda\) and generates a set of public parameters \(\textsf {par}\) for the protocol.
-
\(\textsf {KeyGen}_j(\textsf {par})\) is an interactive key generation protocol that is run by each party \(P_j\), which takes as input public parameters \(\textsf {par}\) and outputs a public key \(\textsf{pk}\) and the secret key share \(\textsf{sk}_j\) of \(P_j\).
-
\(\textsf {Sign}_j(\textsf{sk}_j,m)\) is an interactive signing protocol that is run by each party \(P_j\). It takes as input a secret key share \(\textsf{sk}_j\) of a party \(P_j\) and a message m and outputs a single signature \(\sigma\).
-
\(\textsf {Verify}(\textsf{pk},m,\sigma )\) is a verification algorithm that takes as input a public key \(\textsf{pk}\), a message m, and a signature \(\sigma\). It outputs 1 if the signature is valid and 0 if it is invalid.
Definition 5
(Existential Unforgeability under Chosen Message Attack ([33], Definition 6)) Distributed signature protocol is Existentially Unforgeable under Chosen Message Attack (DS-UF-CMA) if for any probabilistic polynomial time adversary \(\mathcal {A}\), its advantage of creating a successful signature forgery is negligible in \(\lambda\). The advantage of \(\mathcal {A}\) is defined as a probability of winning in the experiment \(\textsf {Exp}^{\textsf {DS-UF-CMA}}\) given in Fig. 1:
\(\textsf {DS}_b(\cdot )\) in the experiment \(\textsf {Exp}^{\textsf {DS-UF-CMA}}\) refers to the honest party \(P_b\) oracle that answers queries by invoking the protocols \(\textsf {KeyGen}_b\) (may be invoked only once) and \(\textsf {Sign}_b\).
3.5 Commitment scheme
We present a description of an additively homomorphic commitment scheme by Baum et al. [9] that is used in our TOPCOAT protocol and corresponding definitions.
Definition 6
(Commitment scheme) A commitment scheme consists of the following algorithms:
-
\(\textsf {CSetup}(1^{\lambda })\) is an algorithm that takes as input security parameter \(\lambda\) and outputs a public set of parameters \(\textsf {par}\) that define set of commitment keys \(\mathcal {K}\), set of messages \(\mathcal {M}\), set of random elements \(\mathcal {R}\), and set of commitments \(\mathcal {C}\).
-
\(\textsf {CKeyGen}(\textsf {par})\) is a key generation algorithm that takes as input the set of parameters \(\textsf {par}\) and outputs a commitment key \(ck \in \mathcal {K}\).
-
\(\textsf {Commit}_{ck}(m,r)\) is an algorithm that takes as input a message \(m \in \mathcal {M}\) and a randomness \(r \in \mathcal {R}\) and outputs a commitment \(c \in \mathcal {C}\).
-
\(\textsf {Open}_{ck}(m,r,c)\) is an algorithm that outputs 1 if the input contains a valid commitment on a message m and outputs 0 otherwise.
Definition 7
(Correctness) Commitment scheme is correct if for any message \(m \in \mathcal {M}\) it holds that
\(\textrm{Pr}[\textsf {Open}_{ck}(m,r,c)=1: \textsf {par}\leftarrow \textsf {CSetup}(1^{\lambda }); ck \leftarrow \textsf {CKeyGen}(\textsf {par}); r \leftarrow \mathcal {R}; com \leftarrow \textsf {Commit}_{ck}(m,r)] = 1\).
Definition 8
(Hiding) We define the advantage of a probabilistic polynomial time adversary \(\mathcal {A}\) in breaking the hiding property of the commitment scheme as \(\textsf {Adv}^{\textsf {Hiding}}(\mathcal {A}):= |P_0^{\textsf {Hiding}} - P_1^{\textsf {Hiding}}|\), where:
Definition 9
(Binding) We define the advantage of a probabilistic polynomial time adversary \(\mathcal {A}\) in breaking the binding property of the commitment scheme as follows:
Definition 10
(Uniform key) A commitment scheme is called uniform if the output of the key generation algorithm \(\textsf {CKeyGen}(\textsf {par})\) is distributed uniformly over the set of commitment keys \(\mathcal {K}\).
Definition 11
(Min-entropy) A commitment scheme is said to have at least \(\xi\)-bits of min-entropy if for all \(ck\in \mathcal {K}\) and \(m\in \mathcal {M}\)
Definition 12
(Additively homomorphic commitment scheme) Let \(c \leftarrow \textsf {Commit}_{ck}(m)\) (computed with r) and \(c' \leftarrow \textsf {Commit}_{ck}(m')\) (computed with \(r'\)). A commitment scheme is additively homomorphic if for any \(m, m' \in \mathcal {M}\) it holds that \(\textsf {Open}_{ck}(c + c', m + m', r + r') = 1\).
Figure 3 presents an additively homomorphic commitment scheme from Baum et al. [9].
4 TOPCOAT: two-party signature scheme
In this section, we introduce our two party signature scheme that consists of \((\textsf {Setup},\textsf {KeyGen}_{P_i},\textsf {Sign}_{P_i},\textsf {Verify})\) protocols and algorithms. We start with defining parameters in Table 1.
4.1 Key generation
Before initiating the key generation protocol, both parties invoke the algorithm \(\textsf {Setup}(1^{\lambda })\) (with \(\lambda\) being a security parameter) that outputs a set of public parameters \(\textsf {par}\) that are defined in Table 1.
The steps of the party \(P_b\) (\(b\in \{1,2\}\)) of the key generation protocol are presented in Fig. 4. The parties start with jointly generating public matrix \(\textbf{A}\) in steps 1–6 in Fig. 4. They sample bitstring seeds \(seed_{\mathbf {A_{b}}}\) and exchange hash commitments on their seeds \(\textsf {H}_1(seed_{\mathbf {A_{b}}})\). This prevents a malicious party from choosing their share based on the share of the honest party. Upon receiving the commitment from the other party, they proceed by revealing corresponding bitstrings and verifying that the commitment was opened correctly. If the verification succeeds, parties XOR both seeds and derive a combined matrix \(\textbf{A}\) using \(\textsf{ExpandA}(seed_{\textbf{A}})\) function (which could be built from extendable-output function (XOF)). The next step consists of generating secret key shares \((\textbf{s}^b_1, \textbf{s}^b_2)\) and computing shares of a public vector \(\textbf{t}_b\). As in the previous step, parties exchange hash commitments \(\textsf {H}_2(\textbf{t}_b)\) to prevent rogue key attack [61]. Upon receiving a commitment from the other party, they exchange vector shares \(\textbf{t}_b\). Parties proceed by verifying commitment opening and computing the second part of the public key \(\textbf{t}\). The final step of the key generation protocol consists of decomposing the combined vector \(\textbf{t}\) into high order (\(\textbf{t}_H\)) and low order (\(\textbf{t}_L\)) bits. High order bits are part of the final public key \(\textsf{pk}\). Each party stores the other parties’ vector \(\textbf{t}\) share as a part of the secret key as it will be needed in the signing process.
TOPCOAT utilises the public key compression technique from the Crystals-Dilithium that makes our scheme more similar to the ML-DSA. Still, we do not use the hinting mechanism of Dilithium as our hinting technique helps to accommodate both possible bit carries: one from adding the commitments and one from knowing only the high order bits of the composed public key \(\textbf{t}\).
4.2 Signing
The pseudocode of the signing protocol without parallel sessions is presented in Fig. 4. We have chosen to give its presentation in such manner, in order to simplify the notation. In this section, we describe the signing protocol together with optimisation through parallel sessions.
The first step of the signing protocol (after generating the commitment key ck and deriving public matrix \(\textbf{A}\)) consists of generating a value that will be hashed to get a challenge \(c \in \mathcal {C}\) in the underlying identification protocol. Parties cannot straightforwardly exchange their vectors \(\textbf{w}_b\) and \(\textbf{w}_{3-b}\). If one of the parties knows vectors \(\textbf{w}_b\) and \(\textbf{z}_b\) of the other party, they could extract \(c\textbf{s}^b_2\) from \(\textbf{z}_b\) and retrieve a part of the other party’s secret key \(\textbf{s}^b_2\) (as shown by Boudgoust and Takahashi [19]). For the standard Crystal-Dilithium/ML-DSA parameters, the knowledge of \(\textbf{w}_b\) allows adversary to reconstruct \(\textbf{s}^b_1\) (as shown by Azouaoui et al. [6]).
Then, in order not to reduce efficiency due to rejection sampling, party \(P_b\) generates not just a single share \(\textbf{y}_b\), but \(\theta\) different shares \(\{ \textbf{y}_{b,i} \}_{i=1}^{\theta }\in (S^l_{\gamma -1})^\theta\). The steps 3–7 in Fig. 4 are executed \(\theta\) times in parallel. This way, we increase the probability of outputting the valid signature without the need to restart the whole \(\textsf {Sign}\) protocol.
The parties continue by computing and exchanging the commitments \(\{ \textbf{c}_{b,i} \}_{i=1}^{\theta }\), which are opened only if the signature shares pass the rejection sampling. Steps 8–10 perform the fair exchange of these commitments; the argument of \(\textsf {H}_3\) in steps 8 and 10 is the entire batch of commitments. These steps are analogous to step 2–4 and 9–11 in the key generation protocol, without it an adversary could adaptively choose a malicious \(\textbf{c}'_b\) after seeing the honest party’s share. Such execution of the protocol allows preventing Wagner’s style and ROS attacks [12, 37].
The exchanged commitments are aggregated using the homomorphic property of the commitment scheme as \(\textbf{c}(i,j):= \textbf{c}_{b,{i}} + \textbf{c}_{(3-b),{j}}\) for \(i,j \in \{1, \dots \theta \}\); each of resulting values serves as input to the hash function \(\textsf {H}_0\) to compute a challenge \(c(i,j) \in \mathcal {C}\) for \(i,j \in \{1, \dots \theta \}\). Steps 11–12, as well as the comparisons in step 13 are executed \(\theta ^2\) times (note that they only contain local computations).
In step 12, parties compute \(\theta ^2\) signature shares \(\textbf{z}_b(i,j):= \textbf{y}_i + c(i,j) \cdot \textbf{s}^b_1\) for \(i,j \in \{1, \dots \theta \}\) and perform rejection sampling checks (step 13). Now, they need to prepare vector of \(\textsf {good}_b\) that indicates the indices of the partial signatures that passed both rejection sampling checks. In the final communication round (step 14), the parties exchange their arrays of signature shares that passed rejection sampling checks \(\{\textbf{z}_b(i,j)\}_{(i,j)\in \textsf {good}_b}\) together with the randomness \(\{ seed_{\textbf{r}_{b,i}}\}_{(i,j)\in \textsf {good}_b}\) used to generate corresponding commitments and the vector \(\textsf {good}_b\). Only if \(\textsf {good}_1\cap \textsf {good}_2=\emptyset\), will parties restart the signing protocol.
Finally, the parties locally compute the hint value \(\textbf{h}\) at Step 20 which helps to accommodate bit carry that can occur when adding high order bits of \(\textbf{w}\).
4.3 Verification
The pseudocode of the verification algorithm is presented in Fig. 4. The verification algorithm in our scheme is different from the original Dilithium verification because we introduce additional components to the signature. This causes verifier to recompute matrix \(\textbf{A}\), commitment \(\textbf{c}\) alongside with corresponding randomness \(\textbf{r}\) which is reconstructed using function \(\mathsf {ExpandR(\cdot )}\) built on XOF and apply our own \(\textsf {UseHint}\) algorithm.
4.4 TOPCOAT correctness
To achieve the correctness of our protocol, we introduce a new hinting technique via pair of algorithms \(\textsf {Hint}()\) and \(\textsf {UseHint}()\) presented in Fig. 4.
Lemma 1
For any hint value h such that
there are only seven possible values for h:
Detailed proof for Lemma 1 is presented in Appendix A.
Instead of allowing hint to have one of the seven values presented above, we reduce the size of hint, by produce two values in \(\{-1,0,1 \}\) for each integer coefficient h of \(\textbf{h}:= \widehat{\textbf{w}^H} - \textbf{w}^H\):
-
1.
\(h_1:= \Bigl \lfloor \frac{h}{(\frac{q-1}{\alpha })}\Bigr \rceil = {\left\{ \begin{array}{ll} - 1 &{} \text {for } h \in \{-\frac{q-1}{\alpha }+1 \}\\ 0 &{} \text {for } h \in \{ -1,0,1 \} \\ 1 &{} \text {for } h \in \{ \frac{q-1}{\alpha }-1, \frac{q-1}{\alpha },\frac{q-1}{\alpha }+1 \} \end{array}\right. }\)
Value \(h_1\) indicates whether and in which direction the roll-out by \(\frac{q-1}{\alpha }\) happened.
-
2.
\(h_2:=\)
\(h \quad \mathbin {\bmod ^\pm }\frac{q-1}{\alpha } = {\left\{ \begin{array}{ll} -1 &{} \text {for } h \in \{\frac{q-1}{\alpha } -1, 1 \}\\ 0 &{} \text {for } h \in \{0, \frac{q-1}{\alpha } \}\\ 1 &{} \text {for } h \in \{ -\frac{q-1}{\alpha } + 1, 1, \frac{q-1}{\alpha } + 1 \}\\ \end{array}\right. }\)
Value \(h_2\) indicates whether the bit carry happened.
The main idea behind this approach is to scale the component \(h_1\) by \(\frac{q-1}{\alpha }\) performing the roll-out for those coefficients where it is needed. Then to add the component \(h_2\) which accommodates the bit carry. Thus, we get back all the seven possible values of h. Therefore, it holds that
Let us now examine two verification conditions separately. The first check is \(\textsf {Open}_{ck}(\textbf{c}, \widehat{\textbf{w}^H}, \textbf{r}) = 1\), where:
Therefore, we have \(\textsf {Open}_{ck}(\textsf {Commit}_{ck}(\textbf{w}^H_1 + \textbf{w}^H_2,\textbf{r}_1 + \textbf{r}_2), \textbf{w}^H_1 + \textbf{w}^H_2, \textbf{r}_1 + \textbf{r}_2) = 1\) which guarantees that the first verification condition passes.
The second verification condition is \(\Vert \textbf{z} \Vert _{\infty } < 2(\gamma - \beta )\). As all the rejection sampling steps have been successfully passed, it holds that \(\Vert \textbf{z}_b \Vert _{\infty } < \gamma - \beta\). It follows that \(\Vert \textbf{z} \Vert _{\infty } = \Vert \textbf{z}_1 + \textbf{z}_2 \Vert _{\infty } \le \Vert \textbf{z}_1 \Vert _{\infty } + \Vert \textbf{z}_2 \Vert _{\infty } < \gamma - \beta + \gamma - \beta = 2(\gamma - \beta )\).
Let us additionally examine Step 13 of the signing protocol, where the partial signature of \(P_i\) is verified. \(\textbf{w}^H_b = \textsf {HighBits}_q(\textbf{Az}_b-c\textbf{t}_b, 2\gamma ') = \textsf {HighBits}_q(\textbf{Ay}_b-c\textbf{s}_2^b, 2\gamma ') \overset{\textrm{lemma}\,2}{=} \textsf {HighBits}_q(\textbf{w}_b, 2 \gamma ')\). Thus, we have
\(\textsf {Open}_{ck}(\textsf {Commit}_{ck}(\textbf{w}^H_b,\textbf{r}_b), \textbf{w}^H_b, \textbf{r}_b) = 1\).
5 Security
Theorem 1
Assume the used commitment scheme is computationally binding, computationally hiding, uniform, additively homomorphic, and has \(\xi\)-bit min-entropy. Then for any probabilistic polynomial time adversary \(\mathcal {A}\) that makes a single query to the key generation oracle, the distributed signature protocol is DS-UF-CMA secure in the random oracle model under the decisional Module-LWE assumption for the parameters \((q,k,l,\eta ,U)\), and the Module-SIS assumptions for the parameters \((q,k,l+1, 2^d \cdot \tau +6 \cdot \gamma ')\), where U is the uniform distribution, and \(2^\xi\) is superpolynomial in the running time of \(\mathcal {A}\).
The main idea behind our security proof is to show that having an adversary \(\mathcal {A}\) against our threshold signature scheme, we can construct an adversary against Module-SIS problem or adversary that breaks the binding property of used commitment scheme. We begin with constructing a simulator \(\mathcal {S}\) that interacts with adversary \(\mathcal {A}\) on behalf of the single honest party in the protocol. Next, we construct \(\mathcal {B}\) around \(\mathcal {S}\) that receives a Module-SIS instance and a challenge commitment key as an input. \(\mathcal {B}\) runs a forking algorithm \(\textsf {F}\), which forks \(\mathcal {S}\) on the query to \(\textsf {H}_0\) corresponding to the forgery. This enables \(\mathcal {B}\) to produce a solution to Module-SIS problem or break the binding property of the commitment scheme.
The full security proof is presented in Appendix C.
6 Evaluation
We present the set of parameters for the TOPCOAT scheme in Table 2. TOPCOAT-256 parameters are chosen to provide at least 128 bits of security, TOPCOAT-512—at least 256 bits of security. An estimation of presented parameters was perforemed with Albrecht et al. [2] LWE-estimator .Footnote 5
Additionally, we implemented TOPCOAT in Go 1.22 and run experiments on Apple M2 Pro with 16 GB RAM.
6.1 Optimising number of rejections
As discussed above, we propose to run TOPCOAT signing protocol with several parallel sessions that reduces the probability of restarting the entire signing protocol from the beginning. This solution requires the client and server to exchange an additional information about which shares from the batch are secure to use (for which signatures from the batch step 13 verification passes on both sides). Revealing this information does not affect the security of the scheme since the parties do not reveal partial signatures that did not pass the rejection sampling checks. The only information about rejected signature shares that gets revealed is the commitment on \(\textbf{Ay}_b\) that hides \(\textbf{y}_b\) due to the commitment scheme’s hiding property.
In Table 3 we present the correlation between number of parallel sessions and number of interactions of signing protocol for TOPCOAT-256 and TOPCOAT-512 parameter sets. Results presented in Table 3 are collected via empirical experiments with our Go implementation. Using obtained results, we selected \(\theta\) parameter to achieve small number of restarts with adequate communication cost.
6.2 Comparison with related work
Comparison of TOPCOAT with the existing protocols is presented in Table 4. Values for Cozzo and Smart [29] are taken from Tang et al. [64]; values for Damgård et al. [33] are taken from Alkadri et al [3]. All presented metrics in Table 4 (except TOPCOAT-512) are given for parameters that provide around 128 bits of security. As it may be seen, TOPCOAT-256 and TOPCOAT-512 have the smallest public key sizes compared to other existing works. The signature size for TOPCOAT-256 is the second best after Cozzo and Smart [29] but it is worth noticing that our approach requires much less communication. In terms of bandwidth per signer, TOPCOAT-256 and TOPCOAT-512 looses only to Alkadri et al. [3], however, TOPCOAT-256 outperforms or equal to Alkadri et al. protocol on all other metrics.
We do not compare time performance of each approach, since it would require re-implementation of every protocol to be measured in one environment. We leave it for the future work.
7 On Inconsistencies of Liu et al.
Liu et al. [54] proposed a lattice-based distributed digital signature scheme based on Dilithium with deterability property [60]. They build their approach based on the outdated pre-print version of this paper [52] .Footnote 6 We point out the main issues with their approach. Notation of Liu et al. work is slightly modified to accommodate ours:
-
1.
The hinting technique taken from [52] in the Subsection 5.3 [54] does not take into account all the possible bit carries. This hinting technique does not work since it lacks to accommodate all the possible hint values stated in Lemma 1.
-
2.
In the [54, Subsection 5.3], the challenge value, which is a part of the signature is calculated as
\(c:= \textsf {H}_0(PID, a, \textbf{c})\). The homomorphic commitment is calculated as \(\textbf{c}=\varSigma ^{n}_{i= 1}\textbf{c}_{i}\), where \(\textbf{c}_i:= \textsf {Commit}_{ck}(\textbf{w}^H_i,\textbf{r}_i)\). Note that \(\textbf{r}_i\) is sampled randomly and \(\textbf{w}^H_i\) is calculated from vector \(\textbf{y}_{i}\), which is sampled uniformly at random as well. It means that two messages \(\mu =(a,p)\) and \(\mu '=(a,p')\) with the same value a in most of the cases would not have equal challenges c during signing process. Therefore, equation \(\sum ^{n}_{i= 1}\textbf{z}=\sum ^{n}_{i= 1}\textbf{y}_{i}+\sum ^{n}_{j= 1, j \ne i} (c \cdot p \cdot \textsf{sk}_{j,1} + c \cdot p' \cdot \textsf{sk}_{i,1})\) from 5.3 subsection does not hold.
-
3.
In the Subsection 5.3 Liu et al. [54] state that: "Compute \(\textsf{sk}_{i,1}=\frac{\textbf{z}_{i}-\textbf{z}'_{i}}{c \cdot (p-p')}\)". Value \((p-p')\) for the specific parameters could not be always invertible in the ring \(R_{q}\).
Application of a new TOPCOAT hinting technique introduced in this work could fix the correctness issues for the verifiability but not for the deterability property.
8 Conclusion
In this paper, we presented TOPCOAT, a Crystals-Dilithium-based two-party protocol which utilises \(\textsf {HighBits}\) and \(\textsf {LowBits}\) compression techniques. We prove our protocol secure in Random Oracle Model and provide comparison with the existing approaches. For 128 bit security parameters, our protocol produces signatures of 9.88 KB size and 1.39 KB public key. The size of signature potentially could be improved together with a bandwidth cost by more tailored parameters or substitution of a commitment scheme. We leave the proof in quantum random oracle model (QROM) as future work. Even though there are proofs of Crystals-Dilithium in the quantum setting [8, 34, 48, 49], to our best knowledge, no work on the distributed Crystal-Dilithium has provided yet a valid security proof in QROM. One of the obstacles of proving security of our construction in QROM would be proving collapse-binding property [65] of Baum et al. commitments to assure the security against quantum adversaries [5].
Data availability
The TOPCOAT implementation code that support the findings of this study is available from the corresponding author upon reasonable request.
Notes
References
Abram D, Nof A, Orlandi C, Scholl P, Shlomovits O. Low-bandwidth threshold ECDSA via pseudorandom correlation generators. In: 2022 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA, 2022, p. 2554–72. https://doi.org/10.1109/SP46214.2022.9833559.
Albrecht MR, Player R, Scott S. On the concrete hardness of learning with errors. J Math Cryptol. 2015;9(3):169–203. https://doi.org/10.1515/jmc-2015-0016.
Alkadri NA, Döttling N, Pu S. Practical lattice-based distributed signatures for a small number of signers. In: Pöpper C, Batina L, editors. Applied cryptography and network security. ACNS 2024. Cham: Springer Nature Switzerland; 2024. p. 376–402. https://doi.org/10.1007/978-3-031-54770-6_15.
Alkeilani Alkadri N, El Bansarkhani R, Buchmann J. On lattice-based interactive protocols: an approach with less or no aborts. In: Liu JK, Cui H, editors. Information security and privacy. ACISP 2020. Cham: Springer International Publishing; 2020. p. 41–61. https://doi.org/10.1007/978-3-030-55304-3_3.
Ambainis A, Rosmanis A, Unruh D. Quantum attacks on classical proof systems: the hardness of quantum rewinding. In: 2014 IEEE 55th Annual symposium on foundations of computer science (FOCS), p. 474–83. IEEE Computer Society, Los Alamitos, CA, USA, 2014. https://doi.org/10.1109/FOCS.2014.57. https://doi.ieeecomputersociety.org/10.1109/FOCS.2014.57.
Azouaoui M, Bronchain O, Cassiers G, Hoffmann C, Kuzovkova Y, Renes J, et al. Protecting Dilithium against leakage: revisited sensitivity analysis and improved implementations. IACR Trans Cryptogr Hardw Embed Syst. 2023;(4):58–79. https://doi.org/10.46586/tches.v2023.i4.58-79.
Bai S, Galbraith SD. An improved compression technique for signatures based on learning with errors. In: Benaloh J, editor. Topics in cryptology-CT-RSA 2014. Cham: Springer International Publishing; 2014. p. 28–47. https://doi.org/10.1007/978-3-319-04852-9_2.
Barbosa M, Barthe G, Doczkal C, Don J, Fehr S, Grégoire B, et al. Fixing and mechanizing the security proof of Fiat-Shamir with aborts and Dilithium. In: Handschuh H, Lysyanskaya A, editors. Advances in cryptology-CRYPTO 2023. Cham: Springer Nature Switzerland; 2023. p. 358–89. https://doi.org/10.1007/978-3-031-38554-4_12.
Baum C, Damgård I, Lyubashevsky V, Oechsner S, Peikert C. More efficient commitments from structured lattice assumptions. In: Catalano, D., De Prisco, R, editors. Security and cryptography for networks. SCN 2018. Lecture notes in computer science, vol 11035. Springer, Cham. https://doi.org/10.1007/978-3-319-98113-0_20.
Bellare M, Neven G. Multi-signatures in the plain public-key model and a General Forking Lemma. In: Juels A, Wright RN, di Vimercati SDC, editors. Proceedings of the 13th ACM Conference on computer and communications security, CCS 2006, Alexandria, VA, USA, October 30–November 3, 2006, p. 390–99. ACM; 2006. https://doi.org/10.1145/1180405.1180453.
Bendlin R, Krehbiel S, Peikert C. How to share a lattice trapdoor: threshold protocols for signatures and (H)IBE. In: Jacobson M, Locasto M, Mohassel P, Safavi-Naini R, editors. Applied cryptography and network security. ACNS 2013. Berlin: Springer; 2013. p. 218–36. https://doi.org/10.1007/978-3-642-38980-1_14.
Benhamouda F, Lepoint T, Loss J, Orrù M, Raykova M. On the (in)security of ROS. J Cryptol. 2022;35(4):25. https://doi.org/10.1007/s00145-022-09436-0.
Bernstein DJ, Hülsing A, Kölbl S, Niederhagen R, Rijneveld J, Schwabe P. The SPHINCS+ signature framework. In: Proceedings of the 2019 ACM SIGSAC Conference on computer and communications security, CCS ’19, p. 2129–46. Association for computing machinery, New York, NY, USA; 2019. https://doi.org/10.1145/3319535.3363229.
Boneh D, Gennaro R, Goldfeder S, Jain A, Kim S, Rasmussen PMR, et al. Threshold cryptosystems from threshold fully homomorphic encryption. In: Shacham H, Boldyreva A, editors. Advances in cryptology-CRYPTO 2018. Cham: Springer International Publishing; 2018. p. 565–96. https://doi.org/10.1007/978-3-319-96884-1_19.
Boneh D, Partap A, Waters B. Accountable multi-signatures with constant size public keys. Cryptology ePrint Archive, Paper 2023;1793. https://eprint.iacr.org/2023/1793.
Bonte C, Smart NP, Tanguy T. Thresholdizing HashEdDSA: MPC to the rescue. Int J Inf Secur. 2021;20(6):879–94. https://doi.org/10.1007/s10207-021-00539-6.
Bos J, Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, Schanck JM, et al. CRYSTALS–Kyber: A CCA-secure module-lattice-based KEM. In: 2018 IEEE European symposium on security and privacy (EuroS &P). 2018; p. 353–67. IEEE. https://doi.org/10.1109/EuroSP.2018.00032.
Boschini C, Takahashi A, Tibouchi M. MuSig-L: Lattice-based multi-signature with single-round online phase. In: Dodis Y, Shrimpton T, editors. Advances in cryptology-CRYPTO 2022. Cham: Springer Nature Switzerland; 2022. p. 276–305. https://doi.org/10.1007/978-3-031-15979-4_10.
Boudgoust K, Takahashi A. Sequential half-aggregation of lattice-based signatures. In: Tsudik G, Conti M, Liang K, Smaragdakis G, editors. Computer security – ESORICS 2023. ESORICS 2023. Lecture notes in computer science, vol 14344. Springer, Cham. https://doi.org/10.1007/978-3-031-50594-2_14.
Brakerski Z. Fully homomorphic encryption without modulus switching from classical GapSVP. In: Safavi-Naini R, Canetti R, editors. Advances in cryptology-CRYPTO 2012. Berlin: Springer; 2012. p. 868–86. https://doi.org/10.1007/978-3-642-32009-5_50.
Brown, D R L. Breaking RSA may be as difficult as factoring. J Cryptol. 2016;29(1):220–41. https://doi.org/10.1007/s00145-014-9192-y.
Buldas A, Kalu A, Laud P, Oruaas M. Server-supported RSA signatures for mobile devices. In: Foley SN, Gollmann D, Snekkenes E, editors. Computer security-ESORICS 2017. Cham: Springer International Publishing; 2017. p. 315–33. https://doi.org/10.1007/978-3-319-66402-6_19.
Camenisch J, Lehmann A, Neven G, Samelin K. Virtual smart cards: how to sign with a password and a server. In: Zikas V, De Prisco R, editors. Security and cryptography for networks. SCN 2016. Cham: Springer International Publishing; 2016. p. 353–71. https://doi.org/10.1007/978-3-319-44618-9_19.
Castagnos G, Catalano D, Laguillaumie F, Savasta F, Tucker I. Bandwidth-efficient threshold EC-DSA. In: Kiayias A, Kohlweiss M, Wallden P, Zikas V, editors. Public-key cryptography-PKC 2020. Cham: Springer International Publishing; 2020. p. 266–96. https://doi.org/10.1007/978-3-030-45388-6_10.
Chairattana-Apirom R, Tessaro S, Zhu C. Partially non-interactive two-round lattice-based threshold signatures. Cryptology ePrint Archive, Paper 2024; 467. https://eprint.iacr.org/2024/467.
Chen Y. DualMS: efficient lattice-based two-round multi-signature with trapdoor-free simulation. In: Handschuh H, Lysyanskaya A, editors. Advances in cryptology-CRYPTO 2023. Cham: Springer Nature Switzerland; 2023. p. 716–47. https://doi.org/10.1007/978-3-031-38554-4_23.
Chou CN, Love PJ, Sandhu JS, Shi J. Limitations of local quantum algorithms on random Max-k-XOR and beyond. In: Bojańczyk M, Merelli E, Woodruff DP, editors. 49th International colloquium on automata, languages, and programming (ICALP 2022), Leibniz International Proceedings in Informatics (LIPIcs), vol 229, p. 41:1–41:20. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany; 2022. https://doi.org/10.4230/LIPIcs.ICALP.2022.41. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.41.
Chu H, Gerhart P, Ruffing T, Schröder D. Practical Schnorr threshold signatures without the algebraic group model. In: Handschuh H, Lysyanskaya A, editors. Advances in cryptology-CRYPTO 2023. Cham: Springer Nature Switzerland; 2023. p. 743–73. https://doi.org/10.1007/978-3-031-38557-5_24.
Cozzo D, Smart NP. Sharing the LUOV: Threshold post-quantum signatures. In: Albrecht M. editors. Cryptography and coding—17th IMA International conference, IMACC 2019, Oxford, UK, December 16-18, 2019, Proceedings, Lecture Notes in Computer Science, vol. 11929, p. 128–53. Springer; 2019. https://doi.org/10.1007/978-3-030-35199-1_7.
Crites E, Komlo C, Maller M. Fully adaptive Schnorr threshold signatures. In: Handschuh H, Lysyanskaya A, editors. Advances in cryptology-CRYPTO 2023. Cham: Springer Nature Switzerland; 2023. p. 678–709. https://doi.org/10.1007/978-3-031-38557-5_22.
Damgård I, Keller M, Larraia E, Pastro V, Scholl P, Smart NP. Practical covertly secure MPC for dishonest majority – Or: breaking the SPDZ limits. In: Crampton J, Jajodia S, Mayes K, editors. Computer security-ESORICS 2013. Berlin Heidelberg, Berlin, Heidelberg: Springer; 2013. p. 1–18. https://doi.org/10.1007/978-3-642-40203-6_1.
Damgård I, Mikkelsen GL, Skeltved T. On the security of distributed multiprime RSA. In: Lee J, Kim J, editors. Information security and cryptology-ICISC 2014. Cham: Springer International Publishing; 2015. p. 18–33. https://doi.org/10.1007/978-3-319-15943-0_2.
Damgård I, Orlandi C, Takahashi A, Tibouchi M. Two-round n-out-of-n and multi-signatures and trapdoor commitment from lattices. J Cryptol. 2022;35:14. https://doi.org/10.1007/s00145-022-09425-3.
Devevey J, Fallahpour P, Passelègue A, Stehlé D. A detailed analysis of Fiat-Shamir with aborts. In: Handschuh H, Lysyanskaya A, editors. Advances in Cryptology – CRYPTO 2023. CRYPTO 2023. Lecture notes in computer science, vol 14085. Springer, Cham. https://doi.org/10.1007/978-3-031-38554-4_11.
Dobias P, Ricci S, Dzurenda P, Malina L, Snetkov N. Lattice-based threshold signature implementation for constrained devices. In: Proceedings of the 20th international conference on security and cryptography - SECRYPT, p. 724–730. INSTICC, SciTePress; 2023. https://doi.org/10.5220/0012112700003555.
Doerner J, Kondi Y, Lee E, Shelat A. Secure two-party threshold ECDSA from ECDSA assumptions. In: 2018 IEEE Symposium on security and privacy (SP). 2018;p. 980–997. https://doi.org/10.1109/SP.2018.00036.
Drijvers M, Edalatnejad K, Ford B, Kiltz E, Loss J, Neven G, Stepanovs I. On the security of two-round multi-signatures. In: 2019 IEEE symposium on security and privacy (SP)/ 2019;p. 1084–1101. https://doi.org/10.1109/SP.2019.00050.
Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, Schwabe P, Seiler G, Stehlé D. CRYSTALS-Dilithium: a lattice-based digital signature scheme. IACR Trans Cryptogr Hardw Embed Syst. 2018;2018(1):238–68. https://doi.org/10.13154/tches.v2018.i1.238-268.
Fan J, Vercauteren F. Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Paper 2012;144. https://eprint.iacr.org/2012/144.
Fleischhacker N, Herold G, Simkin M, Zhang Z. Chipmunk: better synchronized multi-signatures from lattices. In: Proceedings of the 2023 ACM SIGSAC conference on computer and communications security, CCS ’23, p. 386–400. Association for Computing Machinery, New York, NY, USA; 2023. https://doi.org/10.1145/3576915.3623219.
Fleischhacker N, Simkin M, Zhang Z. Squirrel: efficient synchronized multi-signatures from lattices. In: Proceedings of the 2022 ACM SIGSAC conference on computer and communications security, CCS ’22, p. 1109-1123. Association for Computing Machinery, New York, NY, USA; 2022. https://doi.org/10.1145/3548606.3560655.
Fouque PA, Hoffstein J, Kirchner P, Lyubashevsky V, Pornin T, Prest T, et al. Falcon: fast-fourier lattice-based compact signatures over NTRU. Submission to the NIST’s post-quantum cryptography standardization process. 2018;36(5).
Fu Y, Zhao X. Secure Two-party Dilithium signing protocol. In: 2021 17th International conference on computational intelligence and security (CIS). 2021;pp. 444–448. IEEE. https://doi.org/10.1109/CIS54983.2021.00098.
Fukumitsu M, Hasegawa S. A lattice-based provably secure multisignature scheme in quantum random oracle model. In: Nguyen K, Wu W, Lam KY, Wang H, editors. Provable and practical security. ProvSec 2020. Cham: Springer International Publishing; 2020. p. 45–64. https://doi.org/10.1007/978-3-030-62576-4_3.
Garillot F, Kondi Y, Mohassel P, Nikolaenko V. Threshold Schnorr with stateless deterministic signing from standard assumptions. In: Malkin T, Peikert C, editors. Advances in cryptology-CRYPTO 2021. Cham: Springer International Publishing; 2021. p. 127–56. https://doi.org/10.1007/978-3-030-84242-0_6.
Gur KD, Katz J, Silde T. Two-Round Threshold lattice-based signatures from threshold homomorphic encryption. In: Saarinen MJ, Smith-Tone D, editors. Post-quantum cryptography. PQCrypto 2024. Lecture notes in computer science, vol 14772. Springer, Cham. https://doi.org/10.1007/978-3-031-62746-0_12.
Information Technology Laboratory, National Institute of Standards and Technology: module-lattice-based digital signature standard (Initial public draft); 2023. FIPS PUB 204, https://csrc.nist.gov/pubs/fips/204/ipd.
Jackson KA, Miller CA, Wang D. Evaluating the security of CRYSTALS-Dilithium in the quantum random Oracle model. In: Joye M, Leander G, editors. Advances in cryptology–EUROCRYPT 2024. EUROCRYPT 2024. Lecture notes in computer science, vol 14656. Springer, Cham. https://doi.org/10.1007/978-3-031-58751-1_15.
Kiltz E, Lyubashevsky V, Schaffner C. A Concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model. In: Nielsen JB, Rijmen V. editors. Advances in cryptology-EUROCRYPT 2018-37th Annual international conference on the theory and applications of cryptographic techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part III, Lecture notes in computer science, vol. 10822, p. 552–86. Springer; 2018. https://doi.org/10.1007/978-3-319-78372-7_18.
Komlo C, Goldberg I. FROST: flexible round-optimized Schnorr threshold signatures. In: Dunkelman O, Jacobson MJ Jr, O’Flynn C, editors. Selected areas in cryptography. SAC 2020. Cham: Springer International Publishing; 2021. p. 34–65. https://doi.org/10.1007/978-3-030-81652-0_2.
Kondi Y, Orlandi C, Roy L. Two-round stateless deterministic two-party Schnorr signatures from pseudorandom correlation functions. In: Handschuh H, Lysyanskaya A, editors. Advances in cryptology – CRYPTO 2023. CRYPTO 2023. Lecture Notes in Computer Science, vol 14081. Springer, Cham. https://doi.org/10.1007/978-3-031-38557-5_21.
Laud P, Snetkov N, Vakarjuk J. Dilizium 2.0: Revisiting two-party Crystals-Dilithium. Cryptology ePrint Archive, Paper 2022; 644. https://eprint.iacr.org/2022/644.
Lindell Y. Fast secure two-party ECDSA signing. In: Katz J, Shacham H, editors. Advances in cryptology-CRYPTO 2017. Cham: Springer International Publishing; 2017. p. 613–44. https://doi.org/10.1007/978-3-319-63715-0_21.
Liu J, Wen J, Zhang B, Dong S, Tang B, Yu Y. A post quantum secure multi-party collaborative signature with deterability in the industrial internet of things. Future Gener Comput Syst. 2023;141:663–76. https://doi.org/10.1016/j.future.2022.11.034.
Lyubashevsky V, Micciancio D, Peikert C, Rosen A. SWIFFT: A modest proposal for FFT hashing. In: Nyberg, K, editor. Fast software encryption. FSE 2008. Lecture Notes in Computer Science, vol 5086. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-71039-4_4.
McCurley KS. The discrete logarithm problem. In: Proc. of Symp. in Applied Math, vol. 42, pp. 49–74. USA; 1990.
Nick J, Ruffing T, Seurin Y. MuSig2: simple two-round Schnorr multi-signatures. In: Malkin T, Peikert C, editors. Advances in cryptology-CRYPTO 2021. Cham: Springer International Publishing; 2021. p. 189–221. https://doi.org/10.1007/978-3-030-84242-0_8.
Nick J, Ruffing T, Seurin Y, Wuille P. MuSig-DN: Schnorr multi-signatures with verifiably deterministic nonces. In: Proceedings of the 2020 ACM SIGSAC conference on computer and communications security, CCS ’20, p. 1717–31. Association for computing machinery, New York, NY, USA; 2020. https://doi.org/10.1145/3372297.3417236.
Pino del R, Katsumata S, Maller M, Mouhartem F, Prest T, Saarinen MJ. Threshold raccoon: practical threshold signatures from standard lattice assumptions. In: Joye, M., Leander, G. (eds) Advances in cryptology – EUROCRYPT 2024. EUROCRYPT 2024. Lecture notes in computer science, vol. 14652. Springer, Cham. https://doi.org/10.1007/978-3-031-58723-8_8.
Poettering B, Stebila D. Double-authentication-preventing signatures. Int J Inf Secur. 2017;16(1):1–22. https://doi.org/10.1007/s10207-015-0307-8.
Ristenpart T, Yilek S. The power of proofs-of-possession: securing multiparty signatures against Rogue-Key attacks. In: Naor M, editor. Advances in cryptology-EUROCRYPT 2007. Berlin Heidelberg, Berlin, Heidelberg: Springer; 2007. p. 228–45. https://doi.org/10.1007/978-3-540-72540-4_13.
Shor P. Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual symposium on foundations of computer science. 1994; pp. 124–134. https://doi.org/10.1109/SFCS.1994.365700.
Shoup V. Practical threshold signatures. In: Preneel, B. (eds) Advances in Cryptology—EUROCRYPT 2000. EUROCRYPT 2000. Lecture notes in computer science, vol 1807. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45539-6_15.
Tang G, Pang B, Chen L, Zhang Z. Efficient lattice-based threshold signatures with functional interchangeability. IEEE Transactions on Information Forensics and Security. 2023;18:4173–87. https://doi.org/10.1109/TIFS.2023.3293408.
Unruh D. Computationally binding quantum commitments. In: Fischlin M, Coron JS, editors. Advances in cryptology-EUROCRYPT 2016. Berlin: Springer; 2016. p. 497–527. https://doi.org/10.1007/978-3-662-49896-5_18.
Vakarjuk J, Snetkov N, Willemson J. DiLizium: A two-party lattice-based signature scheme. Entropy. 2021;23(8). https://doi.org/10.3390/e23080989.
Wu X, Li B, Zhang B, Liu X, Ren W, Choo KKR. Attack analysis on two-party signature and threshold signature based on Dilithium. In: 2023 IEEE Symposium on computers and communications (ISCC). 2023; p. 291–97. https://doi.org/10.1109/ISCC58397.2023.10217977.
Xue H, Au MH, Xie X, Yuen TH, Cui H. Efficient Online-friendly Two-Party ECDSA signature. In: Proceedings of the 2021 ACM SIGSAC conference on computer and Communications Security, CCS ’21, p. 558–73. Association for computing machinery, New York, NY, USA; 2021. https://doi.org/10.1145/3460120.3484803.
Acknowledgements
This work was funded by the Estonian Research Council under the grant number PRG1780. We would like to thank Petr Muzikant for working on implementation of the TOPCOAT.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Competing interests
We have no competing interest to disclose.
Ethical approval and consent to participate
This work has no ethical implications.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix A: Proof for Lemma 1
Proof
Let us denote \(\alpha =2\gamma '\). Given a number \(x\in \mathbb {Z}_q\), we can write it \(x\equiv x^H\cdot \alpha +x^L \pmod {q}\), where
and this choice of \((x^H,x^L)\) is unique. Let the values \(x^H\) and \(x^L\) be the high bits and low bits of x.
Let \(y=ct_0\), where \(t_0\) is a coefficient of a component of \(\textbf{t}_0\). The value of y belongs to a segment of \(\mathbb {Z}\) that is centered around 0, and whose maximum values are less than \(\alpha /2\). Let the range of y be \([-\alpha /2+\delta , \alpha /2-\delta ]\) for some small \(\delta \in \mathbb {N}\). In other words, \(y^H=0\) and \(y^L=y\). We want to find the possible values of
Let us analyse, what are the possible values of h, considering the different possible values of \(x_1\) and \(x_2\):
-
\(x_1\ge q-\frac{\alpha }{2}\), \(x_2\ge q-\frac{\alpha }{2}\). In this case, \(x_1^H=x_2^H=0\). The value \(x_1+x_2+y\) is between \(2q-3\alpha /2+\delta\) and \(2q-2+\alpha /2-\delta\). We have
$$\begin{aligned} \left( 2q-3\frac{\alpha }{2}+\delta \right) ^H = \left( -3\frac{\alpha }{2}+\delta \right) ^H = \frac{q-1}{\alpha } - 1 \end{aligned}$$and
$$\begin{aligned} (2q-2+\alpha /2-\delta )^H = (\alpha /2-2-\delta )^H=0 \hspace{5.0pt}. \end{aligned}$$We note there are no more possible values in between these two, because we wrap around from \((q-1)/\alpha -1\) directly to 0. Hence, in this case, we have \(h\in \{0,-\frac{q-1}{\alpha }+1\}\). The hint is 0 if \(x_1^L+x_2^L+y\ge -\alpha /2\). If that sum is smaller, then the hint is \(-\frac{q-1}{\alpha }+1\).
-
\(x_1\ge q-\frac{\alpha }{2}\), \(x_2<q-\frac{\alpha }{2}\). In this case, \(x_1^H=0\) and we have to compare \(x_2^H\) against \((x_1+x_2+y)^H\). The value \(x_1^L\) is non-positive, hence it can create a carry for \(x_2^H\), pulling it down by one. The value \(y^L\) can create a carry of either \((-1)\) or 1. In general, the downwards shift cannot be more than 1, because both \(x_1^L\) and \(y^L\) change the sum by less than \(\alpha /2\). Also, the possible upwards shift caused by positive \(x_2^L\) and \(y^L\) is at most 1.
-
✳ If \(x_2^H=0\), then \(0\le x_2\le \alpha /2\). In this case:
$$\begin{aligned}{} & {} -\alpha +\delta \le ((x_1-q)+x_2+y) \le -1 + \frac{\alpha }{2}+ \frac{\alpha }{2}-\delta \\{} & {} \quad =\alpha -\delta -1, \end{aligned}$$meaning that in the lower end, we may get the jump to \(\frac{q-1}{\alpha }-1\). The hint h is then equal to \(-\frac{q-1}{\alpha }+1\).
-
✳ If \(x_2^H=\frac{q-1}{\alpha }-1\), then \(q-3\alpha /2 \le x_2 \le q-1-\alpha /2\). A shift up makes the high bits of \((x_1+x_2+y)\bmod q\) equal to 0, meaning that the hint is \(\frac{q-1}{\alpha }-1\).
-
-
\(x_1<q-\frac{\alpha }{2}\), \(x_2\ge q-\frac{\alpha }{2}\). This is symmetric to previous case.
-
\(x_1<q-\frac{\alpha }{2}\), \(x_2<q-\frac{\alpha }{2}\), \(-\alpha /2+1\le x_1+x_2+y<q-\frac{\alpha }{2}\). Then \(h\in \{-1,0,1\}\), depending on the segment into which \(x_1^L+x_2^L+y^L\) falls. Indeed, in this case,
$$\begin{aligned} h = x_1^H + x_2^H - ((x_1^H+x_2^H)\cdot \alpha +x_1^L+x_2^L+y^L)^H \end{aligned}$$If \(x_1^L+x_2^L+y\in [\frac{\alpha }{2}+1,\frac{3\alpha }{2}-\delta ]\), then \(h=-1\). If \(x_1^L+x_2^L+y\in [-\frac{3\alpha }{2}+2+\delta ,-\frac{\alpha }{2}]\), then \(h=1\). If \(x_1^L+x_2^L+y\) falls somewhere in the middle, then \(h=0\).
-
\(x_1<q-\frac{\alpha }{2}\), \(x_2<q-\frac{\alpha }{2}\), \(x_1+x_2+y=q-\frac{\alpha }{2}\). If \(x_1+x_2+y=q-\frac{\alpha }{2}\), then the only possible values of \(x_1^L+x_2^L+y\) are \(-\alpha /2+1\) and \(\alpha /2+1\). The possible values of the hint are \(\frac{q-1}{\alpha }\) and \(\frac{q-1}{\alpha }-1\).
-
\(x_1<q-\frac{\alpha }{2}\), \(x_2<q-\frac{\alpha }{2}\), \(q-\frac{\alpha }{2}< x_1+x_2+y\). In this case, \((x_1+x_2)^H\) “rolls over”, the roll-over is by \(\frac{q-1}{\alpha }\).
-
✳ If \(x_1^L+x_2^L+y \le -\alpha /2+1\), then \(h=\frac{q-1}{\alpha }+1\).
-
✳ If \(-\alpha /2+2\le x_1^L+x_2^L+y \le \alpha /2+1\), then \(h=\frac{q-1}{\alpha }\).
-
✳ If \(x_1^L+x_2^L+y \ge \alpha /2+2\), then \(h=\frac{q-1}{\alpha }-1\).
-
Hence there are seven possible values for h:
\(\square\)
Appendix B: Supporting lemmas
The following two lemmas that are adapted form [38] and required for the Crystals-Dilithium signature scheme correctness and security.
Lemma 2
([38], Lemma 2) If \(\Vert s \Vert _{\infty } \le \beta\) and
\(\Vert \textsf {LowBits}_q(r, \alpha ) \Vert _{\infty } \le \frac{\alpha }{2} - \beta\), then \(\textsf {HighBits}_q (r, \alpha ) = \textsf {HighBits}_q (r + s, \alpha )\).
Lemma 3
([49], Lemma 4.3) Let \((\textbf{s}_1, \textbf{s}_2) \in S^{l}_{\eta } \times S^{k}_{\eta }\). If \(\Vert c \textbf{s} \Vert _{\infty } \le \beta\) then the following holds:
For any \(c \in \mathcal {C}\) and \(\textbf{z} \in S^l_{\gamma - \beta - 1}\)
Lemma 4
(General forking lemma [10]) Fix an integer \(Q \ge 1\) to be the number of queries. Fix set C of size \(|C| \ge 2\). Let \(\textsf {B}\) be a randomised algorithm that takes as input \(x, h_1, \ldots , h_Q\), where \(h_1, \ldots , h_Q \in C\), and returns a pair (i, out) where i is an index (integer in the range \(\{0, \ldots , Q\}\)) and out is a side output. Let \(\textsf {IG}\) be a randomised input generation algorithm. Let \(\textsf {F}\) be a forking algorithm connected with \(\textsf {B}\) that is defined in Fig. 5.
Let us define the following probabilities:
Then, \(frk \ge acc \cdot \left( \frac{acc}{Q} - \frac{1}{|C|} \right)\). Alternatively,
Appendix C: Full security proof
In this section, we provide a detailed proof for the Theorem 1. Since there are no differences between the operations run by \(P_1\) and \(P_2\) in the TOPCOAT, this security proof covers both malicious cases.
Proof
Let us have an adversary algorithm \(\mathcal {A}\) against our distributed signature protocol. We construct an algorithm \(\mathcal {S}\) around \(\mathcal {A}\) that simulates the behaviour of an honest party in the protocol and does not use an actual secret key of the honest party. Algorithm \(\mathcal {S}\) uses instructions from \(\textsf {SimKeyGen}(\cdot )\) and \(\textsf {SimSign}(\cdot )\) oracles defined in Fig. 15 and Fig. 16 respectively. We construct \(\mathcal {S}\) through the sequence of intermediate games and for each game, we evaluate its difference from the previous one. The changes made in each game are presented in Figs. 8-14. The final description of algorithm \(\mathcal {S}\) is given in Figs. 15, 16 and 17. We proceed by constructing an algorithm \(\mathcal {B}\) around \(\mathcal {S}\) that invokes the forking algorithm (Fig. 5) to obtain two valid forgeries with distinct challenges, which in turn allow us to find a solution to Module-SIS or to break the computational binding of the commitment scheme.
Game 0:In this game, \(\mathcal {S}\) interacts with the adversary following the instructions from Fig. 6, where \(Q_h\) is the number of queries \(\mathcal {A}\) makes to the random oracles \(\textsf {H}_0,\textsf {H}_1,\textsf {H}_2,\textsf {H}_3,\textsf {H}_4\) (presented in Fig. 7). Let us denote the probability that \(\mathcal {S}\) does not output \((0, \perp )\) in the i-th game as \(\textrm{Pr}[\textbf{G}_i]\). Then we can define \(\textrm{Pr}[\textbf{G}_0]:= \textsf {Adv}^{\textsf {DS-UF-CMA}}(\mathcal {A})\). The \(\mathcal {S}\) for this game is presented in Fig. 6
Game 1:In this game, we only change the signing process of \(\mathcal {S}\) with respect to the previous game, detailed simulation is presented in Fig. 8. The main change is that a challenge is sampled randomly as \(c{\mathop {\leftarrow }\limits ^{\$}}\mathcal {C}\). Simulator \(\mathcal {S}\) calculates signature share \(\textbf{z}_b\) without communicating with \(\mathcal {A}\).
Upon receiving \(h_{3-b}\), \(\mathcal {S}\) runs \(\textsf {SearchHash}(\mathcal {T}_3,h_{3-b})\) to find a preimage \(\textbf{c}_{3-b}\) and calculates \(\textbf{c} = \textbf{c}_b + \textbf{c}_{3-b}\). Finally, \(\mathcal {S}\) programs random oracle \(\textsf {H}_0\) to respond the query \((m,\textbf{c},\textsf{pk})\) with the value c. Game 1 and Game 0 are identical except for the events during which the simulation in Game 1 fails. In our notation, \(\textrm{Pr}[bad_i]\) is the probability of the event \({\textbf {bad}}_i\).
-
\({\textbf {bad}}_1\): at least one collision occurs during at most \(Q_h + 2Q_s\) queries to the random oracle \(\textsf {H}_3\) made by \(\mathcal {S}\) or \(\mathcal {A}\).
-
\({\textbf {bad}}_2\): programming random oracle \(\textsf {H}_0\) fails at least once during \(Q_s\) queries. This event happens in two cases:
-
✳ \(\textsf {H}_3(\textbf{c}_{b})\) has been already queried by \(\mathcal {A}\) during at most \(Q_h + 2Q_s\) queries to \(\textsf {H}_3\). This means that \(\mathcal {A}\) has guessed the output of \(\textsf {Commit}_{ck}(\cdot )\) algorithm.
-
✳ \(\mathcal {T}_0(m, \textbf{c}, \textsf{pk})\) has been set by \(\mathcal {S}\) or \(\mathcal {A}\) during at most \(Q_h + Q_s\) prior queries to the \(\textsf {H}_0\).
-
-
\({\textbf {bad}}_3\): \(\mathcal {A}\) predicts at least one of two outputs of the random oracle \(\textsf {H}_3\) without making a query to it.
Game 2:In this game, we again change only signing process, detailed simulation is presented in Fig. 9. If \(\Vert \textbf{z}_b \Vert _{\infty } \ge \gamma - \beta\), then sample \(\textbf{w}_b \leftarrow R^k_q\). Else define \(\textbf{w}_b:= \textbf{Ay}_b\) with \(\textbf{y}_b \leftarrow S^l_{\gamma -1}\). \(\mathcal {S}\) proceeds as before by committing to high order bits of \(\textbf{w}_b\) and sending hash of corresponding commitment \(\textsf {H}_3(\textbf{c}_b)\) to \(\mathcal {A}\), where \(\textbf{c}_b:= \textsf {Commit}_{ck}(\textbf{w}^H_b, \textbf{r}_b)\) and \(\textbf{r}_b \leftarrow S^{\kappa }_{\alpha }\). The difference between Game 1 and Game 2 is in the advantage of \(\mathcal {A}\) in distinguishing simulated commitment from the real one during \(Q_s\) queries, which means breaking hiding property of the commitment scheme.
Game 3: In this game \(\mathcal {S}\) simulates rejection sampling instead of generating share \(\textbf{z}_b\) and running both rejection checks, detailed simulation is presented in Fig. 10. \(\mathcal {S}\) with probability \(1 - \frac{|S^l_{\gamma - \beta - 1}|}{|S^l_{\gamma -1}|}\), outputs \(\textbf{w}_b \leftarrow R^k_q\); and with probability \(\frac{|S^l_{\gamma - \beta - 1}|}{|S^l_{\gamma -1}|}\), outputs \(\textbf{z}_b \leftarrow S_{\gamma - \beta - 1}^l\) and calculates \(\textbf{w}_b:= \textbf{Az}_b - c(\textbf{t}_b - \textbf{s}^b_2)\). The difference between Game 2 and Game 3 is in the advantage of \(\mathcal {A}\) in distinguishing randomly sampled signature shares from the real ones. From Lemma 3, it follows that in the real protocol execution every \(\textbf{z} \in S_{\gamma - \beta - 1}^l\) has an equal probability to be generated and this probability is \(\frac{|S^l_{\gamma - \beta - 1}|}{|S^l_{\gamma -1}|}\). Also, we can write out \(\textbf{w}_b\) in case of no rejection from Game 2 as \(\textbf{Az}_b - c(\textbf{t}_b - \textbf{s}^b_2) = \textbf{Ay}_b + \textbf{A}c\textbf{s}^b_1 - c\textbf{As}^b_1 - c\textbf{s}^b_2 + - c\textbf{s}^b_2 = \textbf{Ab}_n = \textbf{w}_n\). Therefore, the way how the vector \(\textbf{w}_n\) is generated is indistinguishable in both games.
Game 4:In this game, the usage of secret keys \(\textbf{s}_1^b, \textbf{s}_2^b\) by \(\mathcal {S}\) is removed entirely from \(\textsf {Sign}_{P_b}(\cdot )\) protocol. Thus, in case of no rejection, \(\textbf{w}_b:= \textbf{Az}_b - c\textbf{t}_b\). The detailed simulation is presented in Fig. 11.
Since \(\Vert c\textbf{s}^b_2 |_{\infty } < \beta\) and \(\Vert \textsf {LowBits}_q(\textbf{Az}_b - c\textbf{t}_b, 2 \gamma ') \Vert _{\infty } < \gamma ' - \beta\), we can observe that by Lemma 2 it holds that
where \(\textbf{x}_b:= \textbf{Az}_b - c\textbf{t}_b\).
Therefore, the distribution of the high order bits of \(\textbf{w}_b\) in Game 4 is equal to the distribution in Game 3.
Game 5:In this game, we begin altering the key generation process, detailed simulation is presented in Fig. 12. \(\mathcal {S}\) is given a random input matrix \(\textbf{A}\), samples \(seed_{\textbf{A}} \leftarrow \{0,1\}^{l_{seed}}\), then programs random oracle \(\textsf{ExpandA}\) s.t. on the input \(seed_{\textbf{A}}\), it outputs \(\textbf{A}\). After that, \(\mathcal {S}\) samples \(hk_b \leftarrow \{0,1\}^{l_1}\) and sends it to \(\mathcal {A}\). Upon receiving \(hk_{3-b}\), \(\mathcal {S}\) runs \(\textsf {SearchHash}(\mathcal {T}_1, hk_{3-b})\) to find a preimage \(seed_{\textbf{A}_{3-b}}\) and calculates \(seed_{\textbf{A}_b}:= seed_{\textbf{A}} \oplus seed_{\textbf{A}_{3-b}}\). Finally, \(\mathcal {S}\) programs random oracle \(\textsf {H}_1\) to respond the query \(seed_{\textbf{A}_{b}}\) with \(hk_{b}\). The distributions of the public matrix \(\textbf{A}\) and bitstring \(seed_{\textbf{A}_b}\) do not change between Game 4 and Game 5. Therefore, Game 4 and Game 5 are identical except for the events during which the simulation in Game 5 fails.
-
\({\textbf {bad}}_4\): at least one collision occurs during at most \(Q_h\) queries to the random oracle \(\textsf {H}_1\) made by \(\mathcal {S}\) or \(\mathcal {A}\).
-
\({\textbf {bad}}_5\): programming random oracle \(\textsf {H}_1\) fails. It happens if \(\textsf {H}_1(\textbf{A}_b)\) has been previously asked by \(\mathcal {A}\) during at most \(Q_h\) queries to the random oracle \(\textsf {H}_1\).
-
\({\textbf {bad}}_6\): \(\mathcal {A}\) predicts at least one of two outputs of the random oracle \(\textsf {H}_1\) without making a query to it.
-
\({\textbf {bad}}_7\): at least one collision occurs during at most \(Q_h\) queries to the random oracle \(\textsf{ExpandA}\) made by \(\mathcal {S}\) or \(\mathcal {A}\).
-
\({\textbf {bad}}_8\): programming random oracle \(\textsf{ExpandA}\) fails. It happens if \(\textsf{ExpandA}(seed_{\textbf{A}})\) has been previously asked by \(\mathcal {A}\) during at most \(Q_h\) queries to the random oracle \(\textsf{ExpandA}\).
-
\({\textbf {bad}}_9\): \(\mathcal {A}\) predicts outputs of the random oracle \(\textsf{ExpandA}\) without making a query to it.
Game 6:In this game, we proceed with adjustments to the key generation process,detailed simulation is presented in Fig. 13. \(\mathcal {S}\) samples \(\textbf{t}_b \leftarrow R^k_q\), instead of computing \(\textbf{t}_n:= \textbf{As}_1^b + \textbf{s}_2^b\). If \(\mathcal {A}\) can distinguish between Game 5 and Game 6, then this \(\mathcal {A}\) can break the decisional Module-LWE problem for parameters \((q, k, l,\eta , U)\), where U is the uniform distribution. Thus, the difference between the two games is bounded by the advantage of the adversary in breaking decisional Module-LWE:
Game 7: In this game, \(\mathcal {S}\) gets as an input a random final public key \(\textbf{t} \in R_q^k\), \(\mathcal {S}\) samples \(comk_b \leftarrow \{0,1\}^{l_2}\) and sends it to \(\mathcal {A}\). The detailed description of the simulation is presented in Fig. 14. Upon receiving \(comk_{3-b}\) from \(\mathcal {A}\), \(\mathcal {S}\) runs \(\textsf {SearchHash}(\mathcal {T}_2, comk_{3-b})\) to find a preimage \(\textbf{t}_{3-b}\) and calculates \(\textbf{t}_b:= \textbf{t}-\textbf{t}_{3-b}\). Finally, \(\mathcal {S}\) programs random oracle \(\textsf {H}_2\) to respond the query \(\textbf{t}_b\) with \(comk_b\). The distributions of \(\textbf{t}, \textbf{t}_b, \textbf{t}_{H}\) do not change with respect to Game 6. Game 6 and Game 7 are identical except for the events during which the simulation in Game 7 fails.
-
\({\textbf {bad}}_{11}\): at least one collision occurs during at most \(Q_h\) queries to the random oracle \(\textsf {H}_2\) made by \(\mathcal {S}\) or \(\mathcal {A}\).
-
\({\textbf {bad}}_{12}\): programming random oracle \(\textsf {H}_2\) fails, which happens if \(\textsf {H}_2(\textbf{t}_b)\) was previously asked by \(\mathcal {A}\) during at most \(Q_h\) queries to the random oracle \(\textsf {H}_2\).
-
\({\textbf {bad}}_{13}\): \(\mathcal {A}\) predicted at least one of two outputs of the random oracle \(\textsf {H}_2\) without making a query to it.
Game 8:Our next step consists of embedding an instance of Module-SIS to our proof, the detailed description of the simulation is presented in Fig. 16. Module-SIS instance is of the form \([\textbf{A}' | \textbf{I}]\) with \(\textbf{A}' \leftarrow R_q^{k \times (l+1)}\). In Game 7, a pair \((\textbf{A},\textbf{t})\) is uniformly distributed over \(R_q^{k \times l} \times R_q^k\). Let us define \(\textbf{A}':= [\textbf{A} | \textbf{t}]\), this does not change distribution as pair \((\textbf{A},\textbf{t})\) is already distributed uniformly.
Additionally, we need to embed a challenge commitment key \(ck^{\star } \leftarrow \textsf {CKeyGen}(\textsf {par})\). Currently, \(\textsf {H}_4\) is simulated such that commitment keys follow the uniform distribution over the key space \(\mathcal {K}\) that is indistinguishable from the honestly generated keys since the keys are uniform. Suppose \(\mathcal {S}\) is given a challenge commitment key \(ck^{\star }\) as input and we want \(\mathcal {S}\) to return simulated keys for all the queries but one. In the case of a query that is used to create a forgery, \(\mathcal {S}\) should use a predefined key \(ck^{\star }\). Therefore, we change the way how the oracle \(\textsf {H}_4\) is simulated. Upon receiving a query to the oracle \(\textsf {H}_4\), sample \(ck \leftarrow \mathcal {K}\) with probability \(\omega\) and sample \(ck^{\star } \leftarrow \mathcal {K}\) with probability \((1- \omega )\). We modify Forgery algorithm by introducing an additional check: if \(\textsf {H}_4(m^*,pk) \ne ck^{\star }\), return \((0, \perp )\). If the simulation is successful (i.e. \(\mathcal {S}\) does not return \((0, \perp )\)), it holds that \(ck^{\star } = ck = \textsf {H}_4(m^*,pk)\).
We need to adjust the probability that \(\mathcal {S}\) does not return \((0, \perp )\) taking into account modifications we made:
Next, we define an input generation algorithm \(\textsf {IG}\) for the forking lemma (Lemma 4) such that it outputs a tuple \((\textbf{A}, \textbf{t}, ck^{\star })\).
We proceed by constructing an algorithm \(\mathcal {B}\) around \(\mathcal {S}\) that either breaks the binding of the commitment scheme with respect to \(ck^{\star }\) or finds a solution to Module-SIS on input \(\textbf{A}' = [\textbf{A} | \textbf{t}]\). Algorithm \(\mathcal {B}\) invokes the forking algorithm \(\textsf {F}\) (Fig. 5) on input \((\textbf{A}, \textbf{t}, ck^{\star })\). With probability frk we obtain two valid forgeries \(out=(\textbf{z}^*, \textbf{c}^*, {seed_{\textbf{r}_{b}}^*, seed_{\textbf{r}_{3-b}}^*}, \textbf{h}^*, c^*, m^*, ck^*)\) and \(out'=(\textbf{z}', \textbf{c}', {seed_{\textbf{r}_{b}}', seed_{\textbf{r}_{3-b}}'}, \textbf{h}', c', m', ck')\). According to Eq. B.5, frk satisfies
By the construction of the forking algorithm, it holds that all the values generated before the fork are the same in both forgeries: \(\textbf{c}^* = \textbf{c}'\), \(m^* = m'\) and \(ck^* = ck' = ck^{\star }\). We also know that \(c^* \ne c'\) by the definition of forking algorithm. Therefore, it holds that \(\textsf {Open}_{ck^*}(\textbf{c}^*,\widehat{\textbf{w}^{{H}^*}},\textbf{r}^*) = \textsf {Open}_{ck^*}(\textbf{c}^*,\widehat{\textbf{w}^{{H}'}},\textbf{r}') = 1\), where \(\widehat{\textbf{w}^{{H}^*}} = \textsf {UseHint}(\textbf{w}^{{H}^*},\textbf{h}^*_1, \textbf{h}^*_2, \frac{q-1}{2 \gamma '}) = \textbf{w}^{{H}^*} - (\textbf{h}^*_1 \cdot \frac{q-1}{2 \gamma '} + \textbf{h}^*_2)\) and \(\widehat{\textbf{w}^{{H}'}} = \textsf {UseHint}(\textbf{w}^{{H}'},\textbf{h}'_1, \textbf{h}'_2, \frac{q-1}{2 \gamma '}) = \textbf{w}^{{H}'} - (\textbf{h}'_1 \cdot \frac{q-1}{2 \gamma '} + \textbf{h}'_2)\).
Let us analyse two cases – \(\widehat{\textbf{w}^{{H}^*}} \ne \widehat{\textbf{w}^{{H}'}}\) (Case 1) and \(\widehat{\textbf{w}^{{H}^*}} = \widehat{\textbf{w}^{{H}'}}\) (Case 2). From the first case it follows that \(\mathcal {A}\) has found two valid openings for the commitment \(\textbf{c}^*\) under the same commitment key \(ck^{\star }\). This means that \(\mathcal {A}\) has broken the binding property of the commitment scheme, which can happen with probability \(\textsf {Adv}^{\textsf {Binding}}(\mathcal {A})\).
In the second case, we have \(\textsf {HighBits}_q(\textbf{Az}^* - c^*\textbf{t}_{H} \cdot 2^d, 2 \gamma ') - (\textbf{h}^*_1 \cdot \frac{q-1}{2 \gamma '} + \textbf{h}^*_2) = \textsf {HighBits}_q(\textbf{Az}' - c'\textbf{t}_{H} \cdot 2^d, 2 \gamma ') - (\textbf{h}'_1 \cdot \frac{q-1}{2 \gamma '} + \textbf{h}'_2)\).
We can rewrite \(\textbf{Az}^* - c^*\textbf{t}_{H} \cdot 2^d = \textbf{Az}^* - c^*(\textbf{t} - \textbf{t}_{L})\).
Thus, we have \(\textsf {HighBits}_q(\textbf{Az}^* - c^*(\textbf{t} - \textbf{t}_{L}), 2 \gamma ') - (\textbf{h}^*_1 \cdot \frac{q-1}{2 \gamma '} + \textbf{h}^*_2) = \textsf {HighBits}_q(\textbf{Az}' - c'(\textbf{t} - \textbf{t}_{L}), 2 \gamma ') - (\textbf{h}'_1 \cdot \frac{q-1}{2 \gamma '} + \textbf{h}'_2)\).
Which, in turn, can be rewritten as \(\textbf{Az}^* - c^*(\textbf{t} - \textbf{t}_{L}) - \textsf {LowBits}_q(\textbf{Az}^* - c^*(\textbf{t} - \textbf{t}_{L})) - 2\cdot \gamma ' \cdot (\textbf{h}^*_1 \cdot \frac{q-1}{2 \gamma '} + \textbf{h}^*_2) = \textbf{Az}' - c'(\textbf{t} - \textbf{t}_{L}) - \textsf {LowBits}_q(\textbf{Az}' - c'(\textbf{t} - \textbf{t}_{L}), 2\gamma ') - 2 \cdot \gamma ' \cdot (\textbf{h}'_1 \cdot \frac{q-1}{2 \gamma '} + \textbf{h}'_2)\).
When setting \(x^*:= c^*\textbf{t}_{L} + \textsf {LowBits}_q(\textbf{Az}^* - c^*(\textbf{t} - \textbf{t}_{L})) - 2\cdot \gamma ' \cdot (\textbf{h}^*_1 \cdot \frac{q-1}{2 \gamma '} + \textbf{h}^*_2)\) (and equivalently for \(x'\)), we get \(\textbf{Az}^* - c^*\textbf{t} - \textbf{x}^* = \textbf{Az}' - c'\textbf{t} - \textbf{x}'\) that can be rearranged to obtain
where \([\textbf{A} | \textbf{t} | \textbf{I}]\) is an instance of Module-SIS problem.
Let us now analyse the size of component \(\textbf{x}' + \textbf{x}^*\):
-
\(|| c^*\textbf{t}_{L} ||_{\infty } = 2^d/2 \cdot \tau\)
-
\(|| \textsf {LowBits}_q(\textbf{Az}^* - c^*(\textbf{t} - \textbf{t}_{L})) ||_{\infty } = \gamma '\)
-
\(|| 2\cdot \gamma ' \cdot (\textbf{h}^*_1 \cdot \frac{q-1}{2 \gamma '} + \textbf{h}^*_2) ||_{\infty } = 2\cdot \gamma '\)
Therefore, \(\Vert \textbf{x}' + \textbf{x}^* \Vert _{\infty } \le 2^d \cdot \tau + 6 \gamma '\).
Therefore, it means that \(\mathcal {A}\) has found a solution for Module-SIS problem with parameters \((q,k,l+1, \phi )\), where \(\phi\) depends on a choice of parameters and is equal to \(\Vert \textbf{x}' + \textbf{x}^* \Vert _{\infty } \le 2^d \cdot \tau + 6 \gamma '\). Finally, we obtain the following probability \(frk \le \textsf{Adv}^{\textsf{Binding}}(\mathcal {A}) + \textsf{Adv}_{(q,k,l+1, \phi )}^{\text {MSIS}}\) and the advantage of adversary in forging a signature is
\(\square\)
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Snetkov, N., Vakarjuk, J. & Laud, P. TOPCOAT: towards practical two-party Crystals-Dilithium. Discov Computing 27, 18 (2024). https://doi.org/10.1007/s10791-024-09449-2
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10791-024-09449-2