A Provably-Unforgeable Threshold Schnorr Signature With an Offline Recovery Party Michele Battagliola1,∗,† , Alessio Galli1,† , Riccardo Longo1,† and Alessio Meneghetti1,† 1 Department of Mathematics, University Of Trento, 38123 Povo, Trento, Italy Abstract The increase in the interest in cryptocurrencies, and the consequent need for technological maturity of blockchain-based platforms, has been the fuel for some recent advances in cryp- tographic research. In this context, digital signature protocols have a central role since they guarantee ownership and control of digital assets. The absence of trusted central authorities in public blockchains, which is the very foundation of this technology, poses some interesting challenges on the management of digital identities. In particular, the computational infeasibility of restoring a lost key is a threat to anyone possessing this kind of digital assets. A possible solution to this problem is to use threshold multi-signatures, partially relying on a recovery-party whose only role, even though of paramount importance, is to intervene in case of key loss. We present a Schnorr multi-party digital signature scheme that supports an offline par- ticipant during the key-generation phase, without relying on a trusted third party. Under standard assumptions we prove our scheme secure against adaptive malicious adversaries and capable of achieving the resiliency of the recovery in the presence of a malicious party. Keywords 94A60 cryptography, 12E20 finite fields, 14H52 elliptic curves, 94A62 authentication and secret sharing, 68W40 analysis of algorithms. 1. Introduction Custody of cryptocurriencies, and in general of crypto-assets, is at the very core of the burgeoning digital-asset market. Ownership is guaranteed by digital signatures and making them available and usable by the general public presents many issues: to provide a few examples, in case of inheritance heirs cannot access the crypto-assets unless unless they already have access to the private key, and, in general, private keys can be easily lost or forgotten, leading to the inaccessibility of the related assets. Many solutions have been devised to mitigate these problems and to enable safe custody. Some rely on DLT 2022: 4th Distributed Ledger Technology Workshop, June 20, 2022, Rome, Italy ∗ Corresponding author. † These authors contributed equally. Envelope-Open battagliola.michele@gmail.com (M. Battagliola); alessio.galli014@gmail.com (A. Galli); riccardolongomath@gmail.com (R. Longo); alessio.meneghetti@unitn.it (A. Meneghetti) Orcid 0000-0002-8269-2148 (M. Battagliola); 0000-0003-2104-7871 (A. Galli); 0000-0002-8739-3091 (R. Longo); 0000-0002-5159-7252 (A. Meneghetti) © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) 60 personal efforts (e.g., cold storage), others simply delegate full control of the assets to a third party. Unfortunately, these kinds of solutions are partial: most either sacrifice usability or completely rely on the trustworthiness of a third party. An alternative and viable solution is to use threshold digital signatures [8]. This kind of technique addresses more comprehensively the problems above. It relies on multiple private keys, instead of a single one, which are distributed among parties, and a subset of them are required to control the crypto-assets. This approach is resilient with respect to the unavailability or loss of one party. In particular we design a three-parties protocol, that allows users to distribute their key to a custodian and a third party, like a bank or another financial institute. Security is guaranteed as long as the two helping parties do not collude, i.e., it is sufficient that one of the two remains honest to preserve the safety of the system. Furthermore, this solution is effectively agnostic to the underlying blockchain, i.e., it does not have to be supported by special features. Starting from the highly influential work of Gennaro et al [14], several authors proposed both novel schemes [7, 19, 20] and improvements to existing protocols [4, 9, 10, 12, 13, 17, 18, 21]. Recently, in [1] and [2] the authors propose an ECDSA-compatible and an EdDSA- compatible (2, 3)-threshold multi-signature protocol in which one of the users plays the role of the recovery party: a user involved only once in a preliminary setup prior even to the key-generation step of the protocol. In this paper we propose a third, Schnorr-based, variant of [2]. The Schnorr signature algorithm has recently gained popularity in the world of cryptocurrencies, especially since its addition to Bitcoin with BIP3401 . Schnorr signatures have many advantages, such as linearity, non-malleability and provable security. In particular, they are strongly unforgeable under chosen message attacks: in the random oracle model assuming the hardness of the discrete logarithm problem, in the generic group model assuming variants of preimage and second preimage resistance of the used hash function. In contrast, the best known results for the provable security of ECDSA rely on stronger assumptions. Moreover, the threshold version presented here allows for fast computation with fewer rounds of communication with respect to ECDSA, and unlike EdDSA does not require expensive computation to derive a deterministic nonce. We prove the protocol secure against adaptive adversaries by reducing it to the classical Schnorr scheme, assuming the security of a non-malleable commitment scheme, and an IND-CPA encryption scheme. Moreover we make some considerations about the resiliency of the recovery, an interesting aspect due to the presence of an offline party, analyzing possible changes that allow us to achieve this higher level of security. 2. Preliminaries In this section we present some preliminary definitions and primitives that will be used in the protocol and its proof of security. 1 see https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki 61 Notation We use the symbol || to indicate the concatenation of bit-strings. Sometimes we slightly abuse the notation and concatenate a bit-string 𝑀 with a group element 𝒫, in those cases we assume that there has been fixed an encoding 𝜑 that maps group elements into bit-strings, so 𝑀||𝒫 ∶= 𝑀||𝜑(𝒫 ). In the following when we say that an algorithm is efficient we mean that it runs in (expected) polynomial time in the size of the input, possibly using a random source. We use a blackboard-bold font to indicate algebraic structure (i.e. sets, groups, rings, fields), a calligraphic font will generally denote elements of a finite group. 2.1. Cryptographic Hash Functions In the Schnorr scheme (and therefore in our threshold protocol) a cryptographic hash function 𝐻 is used as a Pseudo-Random Number Generator (PRNG), employed to derive secret scalars and nonces. The requirements needed for the hash function used in Schnorr signatures are analyzed in [23]. 2.1.1. Schnorr Signature Schnorr’s digital signature algorithm is an efficient algorithm able to generate short signatures without sacrificing security. It is one of the first signatures that bases its security on the difficulty of discrete logarithm problem [24]. If Alice wants to send a signed message to Bob, she has to choose group 𝔾 with generator 𝑔 of prime order 𝑞 where the discrete logarithm problem is considered to be hard and a cryptographic hash function 𝐻. Then they can do the following: 1. Key Generation: Alice chooses randomly a private key 𝑥 ∈ ℤ∗𝑞 and computes the public key 𝑦 = 𝑔 𝑥 ; 2. Signature Generation: to sign a message 𝑚, Alice performs the following: a) Choose randomly 𝑘 ∈ 𝑍𝑞∗ ; b) Compute 𝑟 = 𝑔 𝑘 ; c) Compute 𝑒 = 𝐻 (𝑚||𝑟); d) Compute 𝑠 = (𝑘 − 𝑥𝑒); e) The signature is the pair (𝑒, 𝑠). 3. Signature Verification: to verify the signature after receiving 𝑚 and (𝑒, 𝑠), Bob performs the following: a) Compute 𝑟𝑣 = 𝑔 𝑠 𝑦 𝑒 ; b) Compute 𝑒𝑣 = 𝐻 (𝑚||𝑟𝑣 ); c) The signature is valid only if 𝑒𝑣 = 𝑒. 62 2.2. Encryption Scheme In our protocol we need an asymmetric encryption scheme to communicate with the offline party. The minimum requirement we ask for our protocol to be secure is that the encryption scheme chosen by the offline party has the property of IND-CPA [3, 22]. This hypothesis will be enough to prove the unforgeability of the protocol, but it is possible to achieve a higher notion of security by using a more sophisticated encryption scheme that supports Zero-Knowledge Proofs for the Discrete Logarithm. This will be more clearly explained in Section 4.5. 2.3. Commitment Schemes A commitment scheme [5] is composed by two algorithms: • Com(𝑀) ∶ {0, 1}∗ → {0, 1}∗ × {0, 1}∗ : takes in input the value 𝑀 to commit2 and, using a random source, outputs the commitment string 𝐶 and the decommitment string 𝐷. • Ver(𝐶, 𝐷) ∶ {0, 1}∗ × {0, 1}∗ → {0, 1}∗ ∪ {⟂}: takes the commitment and decommitment strings 𝐶, 𝐷 and outputs the originally committed value 𝑀 if the input pair is valid, ⟂ otherwise3 . We require a commitment scheme to have the following properties: • Correctness: for every value 𝑀 it holds Ver(Com(𝑀)) = 𝑀. • Binding: for every commitment string 𝐶 it is infeasible to find 𝑀 ≠ 𝑀 ′ and 𝐷 ≠ 𝐷 ′ such that Ver(𝐶, 𝐷) = 𝑀 and Ver(𝐶, 𝐷 ′ ) = 𝑀 ′ with both 𝑀, 𝑀 ′ ≠⟂. • Hiding: Let (𝐶, 𝐷) = Com(𝑀𝑏 ) with 𝑏 ∈ {0, 1}, 𝑀1 ≠ 𝑀0 , then it is infeasible for an attacker that may choose 𝑀0 ≠ 𝑀1 and sees only 𝐶, to correctly guess 𝑏 with more than negligible advantage. • Non Malleability: Given 𝐶 = Com(𝑀), it is infeasible for an adversary A to produce another commitment string 𝐶 ′ such that after seeing 𝐷 such that Ver(𝐶, 𝐷) = 𝑀, A can find a decommit string 𝐷 ′ such that Ver(𝐶 ′ , 𝐷 ′ ) = 𝑀 ′ with 𝑀 ′ related to 𝑀, that is A can only create commitments to values that are independent from 𝑀. 2.4. Zero-Knowledge Proofs In the protocol, various Zero-Knowledge Proofs (ZKP) [16] are used to enforce the respect of the passages prescribed by the specifications. In fact, in the proof of security we can exploit the soundness of these sub-protocols to extract valuable information from the 2 In the protocol and the simulations we implicitly encode every value we need to commit into a bit-string, assuming there is a standard encoding understood by all parties 3 Again, in the protocol we implicitly decode valid decommitment outputs (i.e. ≠⟂) into the original value, assuming that the decoding is also standard and understood by all parties 63 adversary, and their zero-knowledge property to simulate correct executions even without knowing some secrets. We can do so because we see the adversary as a (black-box) algorithm that we can call on arbitrary input, and crucially we have the faculty of rewinding its execution. In particular we use ZKP of Knowledge (ZKPoK) to guarantee the usage of secret values that properly correspond to the public counterpart, specifically the Schnorr protocol for discrete logarithms, and its variant that proves that two public values are linked to the same secret (see [24, 27]). The soundness property of a ZKPoK guarantees that the adversary must know the secret input, and appropriate rewinds and manipulations of the adversary’s execution during the proof allows us to extract those secrets and use them in the simulation. Conversely exploiting the zero-knowledge property we can trick the adversary in believing that we know our secrets even if we do not, thus we still obtain a correct simulation of our protocol form the adversary’s point of view. 2.5. Feldman-VSS Feldman’s VSS scheme [11] is a verifiable secret sharing scheme built on top of Shamir’s scheme [26]. A secret sharing scheme is verifiable if auxiliary information is included, that allows players to verify the consistency of their shares. We use a simplified version of Feldman’s protocol: if the verification fails the protocol does not attempt to recover excluding malicious participants, instead it aborts altogether. In a sense we consider somewhat honest participants, for this reason we do not need stronger schemes such as [15, 25]. The scheme works as follows: 1. A cyclic group 𝔾 of prime order 𝑞 is chosen, as well as a generator 𝑔 ∈ 𝔾. The group 𝔾 must be chosen such that the discrete logarithm is hard to compute. 2. The dealer computes a random polynomial 𝑃 of degree 𝑡 with coefficients in ℤ𝑞 , such that 𝑃(0) = 𝑠 where 𝑠 ∈ ℤ𝑞 is the secret to be shared. 3. Each of the 𝑛 share holders receive a value 𝑃(𝑖) ∈ ℤ𝑞 . So far, this is exactly Shamir’s scheme. 4. To make these shares verifiable, the dealer distributes commitments to the coeffi- 𝑛 cients of 𝑃. Let 𝑃(𝑋 ) = 𝑠 + ∑𝑖=1 𝑎𝑖 𝑋 𝑖 , then the commitments are 𝒞0 = 𝑔 𝑠 and 𝒞𝑖 = 𝑔 𝑎𝑖 for 𝑖 ∈ {1, … , 𝑛}. 5. Any party can verify its share in the following way: let 𝛼 be the share received by the 𝑖-th party, then it can check if 𝛼 = 𝑃(𝑖) by verifying if the following equality holds: 𝑡 𝑡 𝑡 𝑗 𝑗 𝑗 𝑔 𝛼 = ∏(𝒞𝑗 )𝑖 = 𝑔 𝑠 ⋅ 𝑔 ∑𝑗=1 𝑎𝑗 (𝑖 ) = 𝑔 𝑠+∑𝑗=1 𝑎𝑗 (𝑖 ) = 𝑔 𝑃(𝑖) . 𝑗=0 64 3. Threshold Schnorr Signature In this section we describe the main protocol: a (2, 3)-threshold variant of Schnorr digital signature algorithm with an offline participant. Let 𝑃1 , 𝑃2 , 𝑃3 the parties involved in the protocol, as already mentioned the goal is to allow to one of them, namely 𝑃3 to remain offline during the key generation phase. Moreover our goal is to allow for a trustless setup, where the parties does not have to rely to a third trusted party to generate the credential. From now on we refer to 𝑃3 as the offline or recovery party, since its role is to take part in the signing protocol if for any reason one of the two is no more able (secret key loss, unreachability, etc.). The protocol is dividend into four algorithms: 1. Setup Phase (3.1): in this phase all three players interact to set some common parameters. Note that in a practical implementation this phase can be performed ahead of time without any real communication, because these parameters are usually fixed (e.g. for Bitcoin applications which have to use secp256k1 and SHA-256). 2. Key-Generation (3.2): performed by 𝑃1 and 𝑃2 to create the public key for the signature scheme and the private shards for themselves and 𝑃3 ; 3. Ordinary Signature (3.3): used whenever 𝑃1 and 𝑃2 want to perform a signature. It is called ordinary signature as this should be the standard signing procedure; 4. Recovery Signature (3.4): ideally, this algorithm is executed when either 𝑃1 or 𝑃2 is no more able to sign. 𝑃3 steps in and performs a signature with the remaining party. It is important to emphasize that the final signature is still a standard one, same as the one generated in an ordinary signature and indistinguishable to one obtained in the centralized protocol. From now on “𝑃𝑖 does something” means that both 𝑃1 and 𝑃2 perform that action. Also by saying “ 𝑃𝑖 sends a message to 𝑃𝑗 ” means that 𝑃1 sends data to 𝑃2 and viceversa. 3.1. Setup Phase The aim of this phase is to make 𝑃1 and 𝑃2 agree on all the parameters required in the protocol and set up the private/public key pair used to contact 𝑃3 in case of need. Player 1 and 2 Player 3 Input: Input: Private Output: Private Output: sk3 Public Output: 𝔾, 𝑔, 𝑞, 𝐻 Public Output: pk3 𝑃3 picks a key pair (pk3 , sk3 ) for a suitable asymmetric encryption algorithm. Then 𝑃1 and 𝑃2 agree on a secure hash function 𝐻 whose outputs can be interpreted as elements of ℤ𝑞 and a group 𝔾 with generator 𝑔 of prime order 𝑞 in which the discrete logarithm problem is considered to be hard. 65 3.2. Key generation This part of the protocol is performed by 𝑃1 and 𝑃2 to produce a common public key 𝒜 and to distribute shards of the corresponding private key to each player. Player 1 Player 2 Input: pk3 Input: pk3 Private Output: 𝜔1 Private Output: 𝜔2 Public Output: rec1,3 , rec2,3 , 𝒜 Public Output: rec1,3 , rec2,3 , 𝒜 1. Secret key generation and communication: a) 𝑃𝑖 randomly chooses 𝑎𝑖 , 𝑦3,𝑖 , 𝑚𝑖 ∈ ℤ𝑞 and sets 𝒜𝑖 = 𝑔 𝑎𝑖 , 𝒴3,𝑖 = 𝑔 𝑦3,𝑖 ; b) 𝑃𝑖 computes [KGC 𝑖 , KGD 𝑖 ] = Com((𝒜𝑖 , 𝒴3,𝑖 )); c) 𝑃𝑖 sends KGC 𝑖 to 𝑃𝑗 ; d) 𝑃𝑖 sends KGD 𝑖 to 𝑃𝑗 ; e) 𝑃𝑖 gets ((𝒜𝑖 , 𝒴3,𝑖 )) = Ver(KGC 𝑗 , KGD 𝑗 ) . 2. Feldman VSS and generation of 𝑃3 data: a) 𝑃𝑖 sets 𝑓𝑖 (𝑥) = 𝑎𝑖 + 𝑚𝑖 𝑥 and computes 𝑦𝑖,1 , 𝑦𝑖,2 , 𝑦𝑖,3 where 𝑦𝑖,𝑗 = 𝑓𝑖 (𝑗); b) 𝑃𝑖 encrypts 𝑦𝑖,3 , 𝑦3,𝑖 with pk3 and obtains rec𝑖,3 ; c) 𝑃𝑖 sends 𝑦𝑖,𝑗 and rec𝑖,3 to 𝑃𝑗 ; d) If the asymmetric encryption algorithm supports DLOG verification, the encryption rec𝑖,3 is accompanied by two NIZKPs: the first one proves that the first ciphertext in rec𝑖,3 is the encryption of the DLOG of 𝒴𝑖,3 = 𝒜𝑖 ⋅ (ℳ𝑖 )3 (where ℳ𝑖 = 𝑔 𝑚𝑖 is sent during the Feldman-VSS protocol), the second NIZKP proves that the second ciphertext is the encryption of the DLOG of 𝒴3,𝑖 . 𝑃𝑖 checks the NIZKPs attached to rec𝑗,3 . e) 𝑃𝑖 checks, as in the Feldman-VSS protocol, the integrity and consistency of the shards 𝑦𝑗,𝑖 ; f) 𝑃𝑖 computes 𝑥𝑖 = 𝑦1,𝑖 + 𝑦2,𝑖 + 𝑦3,𝑖 . 3. 𝑃𝑖 proves in ZK the knowledge of 𝑥𝑖 using Schnorrs protocol. 4. Public key and shards generation: 3 a) the public key is 𝒜 = ∏𝑖=1 𝒜𝑖 , where 𝒜3 = (𝒴3,1 )2 /𝒴3,2 so that 𝑎3 = 2𝑦3,1 − 𝑦3,2 . 3 From now on we will set 𝑎 = ∑𝑖=1 𝑎𝑖 and we have 𝑔 𝑎 = 𝒜; b) 𝑃1 computes 𝜔1 = 2𝑥1 , while 𝑃2 computes 𝜔2 = −𝑥2 . Note that 𝜔1 + 𝜔2 = 𝑎; 66 3.3. Signature Algorithm This algorithm is the general signature scheme in which two players, 𝑃𝐴 and 𝑃𝐵 , want to sign a message. Each of 𝑃1 , 𝑃2 , 𝑃3 can take the role of either 𝑃𝐴 or 𝑃𝐵 depending on the situation, we call Ordinary Signature the case in which 𝑃1 takes the role of 𝑃𝐴 and 𝑃2 takes the role of 𝑃𝐵 . Let 𝑀 be the message, the parameters involved are: Player A Player B Input: 𝑀, 𝜔𝐴 , 𝒜 Input: 𝑀, 𝜔𝐵 , 𝒜 Public Output: (𝑠, 𝑒) Public Output: (𝑠, 𝑒) The protocol proceeds as follows. 1. Generation of 𝑟: a) 𝑃𝑖 randomly chooses 𝑘𝑖 ∈ 𝔾; b) 𝑃𝑖 computes 𝑟𝑖 = 𝑔 𝑘𝑖 ; c) 𝑃𝑖 computes [KGC 𝑖 , KGD 𝑖 ] = Com(𝑟𝑖 ) and sends KGC 𝑖 ; d) 𝑃𝑖 sends KGD 𝑖 ; e) 𝑃𝑖 computes 𝑟𝑗 = Ver([KGC 𝑗 , KGD 𝑗 ]); f) 𝑃𝑖 computes 𝑟 = 𝑟𝐴 𝑟𝐵 . 2. Generation of 𝑠: a) 𝑃𝑖 computes 𝑒 = 𝐻 (𝑟||𝑀) and 𝑠𝑖 = 𝑘𝑖 − 𝜔𝑖 𝑒; b) 𝑃𝑖 computes [KGC ′𝑖 , KGD ′𝑖 ] = Com(𝑠𝑖 ) and sends KGC ′𝑖 ; c) 𝑃𝑖 sends KGD ′𝑖 ; d) 𝑃𝑖 computes 𝑠𝑗 = Ver([KGC ′𝑗 , KGD ′𝑗 ]); e) 𝑃𝑖 computes 𝑠 = 𝑠𝐴 + 𝑠𝐵 . 3. 𝑃𝑖 computes 𝑟𝑣 = 𝑔 𝑠 𝒜 𝑒 and checks that 𝐻 (𝑟𝑣 ||𝑀) = 𝑒. The output signature is (𝑠, 𝑒). If a check fails, the protocol aborts. 3.4. Recovery Signature This is the scenario where one between 𝑃1 or 𝑃2 is unable to sign. 𝑃3 has to come back online and perform a recovery signature with the other online party. There are two different situations, depending whether the other party is 𝑃1 or 𝑃2 . Firstly we consider the case where 𝑃2 is offline and 𝑃1 and 𝑃3 want to perform a signature. The parameters involved are: Player 1 Player 3 Input: 𝑀, 𝜔1 , 𝒜 , rec1,3 , rec2,3 Input: 𝑀, sk3 Public Output: (𝑠, 𝑒) Public Output: (𝑠, 𝑒) 67 The protocol is the following. 1. Communication: a) 𝑃1 contacts 𝑃3 and sends 𝒜 , rec1,3 , rec2,3 ; b) 𝑃3 decrypts rec1,3 , rec2,3 using its private key to obtain 𝑦1,3 , 𝑦3,1 , 𝑦2,3 , 𝑦3,2 ; c) 𝑃3 computes 𝑎3 = 2𝑦3,1 − 𝑦3,2 and 𝒜3 = 𝑔 𝑎3 . 2. 𝑃3 ’s key creation: a) 𝑃3 computes 𝑥3 = 𝑦1,3 + 𝑦2,3 + 2𝑦3,2 − 𝑦3,1 ; b) 𝑃𝑖 proves in ZK the knowledge of 𝑥𝑖 using Schnorrs protocol (𝑥1 = 12 𝜔1 ). 3. Signature generation: a) 𝑃1 computes 𝜔̃ 1 = 34 𝜔1 ; b) 𝑃3 computes 𝜔3 = − 12 𝑥3 ; c) 𝑃1 and 𝑃3 perform the signature algorithm with 𝑃𝐴 = 𝑃1 , 𝑃𝐵 = 𝑃3 using 𝜔𝐴 = 𝜔̃ 1 and 𝜔𝐵 = 𝜔3 . Note that it still holds that 𝜔𝐴 + 𝜔𝐵 = 𝑎. The other scenario is the one in which 𝑃1 is offline and 𝑃2 signs the message with 𝑃3 : Player 2 Player 3 Input: 𝑀, 𝜔2 , 𝒜 , rec1,3 , rec2,3 Input: 𝑀, sk3 Public Output: (𝑠, 𝑒) Public Output: (𝑠, 𝑒) The first two steps are the same as in the previous scenario, except that in the ZKP in [2b] we now have 𝑥2 = −𝜔2 . 3. Signature generation: a) 𝑃2 computes 𝜔̃ 2 = −3𝜔2 ; b) 𝑃3 computes 𝜔3 = −2𝑥3 ; c) 𝑃2 and 𝑃3 perform the signature algorithm with 𝑃𝐴 = 𝑃2 , 𝑃𝐵 = 𝑃3 using 𝜔𝐴 = 𝜔̃ 2 and 𝜔𝐵 = 𝜔3 . Note that also here 𝜔𝐴 + 𝜔𝐵 = 𝑎. 4. Security Proof In this section we discuss the security of the scheme in terms of the unforgeability properties defined below. We also discuss other security aspects, such as recovery resiliency in the subsequent Section 4.5. Definition 4.1 (Unforgeability). A (𝑡, 𝑛)-threshold signature scheme is unforgeable if no malicious adversary who corrupts at most 𝑡 − 1 players can produce the signature on a new message 𝑚 with non-negligible probability, given the view of the threshold sign on input messages 𝑚1 , … , 𝑚𝑘 (adaptively chosen by the adversary), as well as the signatures on those messages. 68 The unforgeability of our protocol is formally stated in the following theorem: Theorem 4.1. Assuming that: • the Schnorr signature scheme instantiated on the group 𝔾 of prime order 𝑞 with the hash function 𝐻 is unforgeable; • Com, Ver is a non-malleable commitment scheme; • the Decisional Diffie-Hellman Assumption holds; • the encryption algorithm used by 𝑃3 is IND-CPA; our threshold protocol is unforgeable. In Section 4.4 we will prove the theorem by showing that if there is an adversary A able to forge a signature for the threshold scheme with non negligible probability 𝜖 > 𝜆−𝑐 with 𝜆 a polynomial and 𝑐 > 0, then it is possible to build a forger F that forges a signature for the centralized Schnorr scheme also with non negligible probability. The simulation works by having an oracle that feeds inputs for the centralized scheme to F, our goal is to respond by generating a signature exploiting A. First, it has to simulate the key generation protocol in order to match the key received from the oracle, then it can proceed with the signature part. The core of this setup is that if A is able to crack our protocol, F will take advantage of that and will also create a forgery for the centralized version of the oracle. Following the definition of unforgeability, A will control one player while F controls the remaining two. We must consider two different scenarios: one where A controls 𝑃1 or 𝑃2 , and the case where A controls 𝑃3 . First, we suppose without loss of generality that A controls 𝑃2 . The adversary interacts by first participating in the key generation part to generate a public key 𝒜, then starts requesting signatures on some messages 𝑚1 , … , 𝑚𝑙 . Here it can either take part in the process or let 𝑃1 and 𝑃3 generate the signature. Eventually A outputs a message 𝑚 ≠ 𝑚𝑖 ∀𝑖 and its valid signature with probability at least 𝜖, where this is taken over the random tapes of the adversary and the honest player, respectively 𝜏A and 𝜏𝑖 . So we can write that ℙ𝜏𝑖 ,𝜏A (A(𝜏A )𝑃𝑖 (𝜏𝑖 ) = forgery) ≥ 𝜖, (1) where A(𝜏A )𝑃𝑖 (𝜏𝑖 ) is the output of A at the end of this process and ℙ𝜏𝑖 ,𝜏A denotes that the probability is taken over the random tape 𝜏𝑖 and the adversary tape 𝜏A . We say that a random tape is good if 𝜖 ℙ𝜏𝑖 (A(𝜏A )𝑃𝑖 (𝜏𝑖 ) = forgery) ≥ . (2) 2 We recall the following useful lemma, stated and proved in [2]. Lemma 4.1. If 𝜏A is chosen uniformly at random, the probability that 𝜏A is good is at least 2𝜖 . 69 4.1. Key generation simulation Now we see into details how the key generation phase is simulated. F receives from the challenger the public key 𝒜𝑐 for the centralized Schnorr protocol and a public key pk3 for the asymmetric encryption scheme. The simulation proceeds as follows: 1. 𝑃𝑖 selects random values 𝑎𝑖 , 𝑦3,𝑖 , 𝑚𝑖 ∈ ℤ𝑞 and computes 𝒜𝑖 = 𝑔 𝑎𝑖 , 𝒴3,𝑖 = 𝑔 𝑦3,𝑖 ; 2. 𝑃𝑖 computes the commitment [KGC 𝑖 , KGD 𝑖 ] = Com(𝒜𝑖 , 𝒴3,𝑖 ); 3. 𝑃𝑖 sends KGC 𝑖 , then, after receiving KGC 𝑗 , 𝑃𝑖 sends KGD 𝑖 ; 4. 𝑃𝑖 gets (𝒜𝑖 , 𝒴3,𝑖 ) = Ver(KGC 𝑗 , KGD 𝑗 ); 5. Now F knows all the parameters needed in the computation of 𝒜, so it rewinds A to step 3, aiming to get 𝒜 = 𝒜𝑐 ; 𝒜 6. F computes 𝒜 ̂ = 𝒜 𝒜𝑐 , computes the commitment [KGC ̂1 , KGD̂ 1 ] = Com(𝒜 ,̂ 𝒴3,1 ), and 2 3 sends it to A, so that it will receive 𝒜 ̂ as 𝒜1 which leads to 𝒜 = 𝒜𝑐 ; 7. F simulates a fake Feldman-VSS with 𝒜 (see e.g. [2]) since it cannot compute the polynomial 𝑓 (𝑥): it selects 𝑦1,2 , 𝑦1,3 randomly and computes 𝑐1,𝑗 = 1𝑖 (𝑔 𝑦1,𝑖 /𝒜 )̂ . 8. 𝑃𝑖 encrypts 𝑦𝑖,3 and 𝑦3,𝑖 with pk3 , getting rec𝑖,3 , then sends 𝑦𝑖,𝑗 , rec𝑖,3 ; 9. 𝑃𝑖 computes 𝑥𝑖 . Since F does not know the discrete logarithm of 𝒜,̂ it sets 𝑥1 randomly; 10. F participates in the ZK proofs rewinding A and selecting appropriate challenges in order to extract 𝑥2 from A; 11. 𝑃𝑗 can compute the key 𝒜 as described in the enrollment phase. A can also compute 𝜔2 , while F cannot, since it does not know 𝑥1 . Note that at the end of the protocol, F does not know 𝑥1 nor 𝜔1 , but F will still be able to complete correctly the signing part by querying the oracle. The proof of the correctness of the simulation is stated in the following lemmas. The proofs are trivial and use the same argument of the one presented in [2]. Lemma 4.2. If the Decisional Diffie-Hellman assumption holds, and the encryption algorithm used by 𝑃3 is IND-CPA, then the simulation terminates in expected polynomial time and is indistinguishable from the real protocol. Lemma 4.3. For a polynomial number of inputs the simulation terminates with output 𝒜𝑐 except with negligible probability. 70 Observation 1. It is important that in step 3 the adversary sends KGC 2 and KGD 2 before F, so that after the rewinding A cannot change its commitment (note that this applies also to the simulation in Section 4.2). If the order were inverted, A could also use the commitment of F to generate its value. Assuming the non-malleability property, A does not deduce anything about the content of the commitment, but it could still use it as a seed for a random generator. If this were to happen, F can guess 𝒜 ̂ with probability 1𝑞 with 𝑞 the size of the group, making the expected time exponential. It is possible to swap the order in the commitment step using an equivocable com- mitment scheme with a secret trapdoor. In this case we only need to rewind at the decommitment step and change 𝐾 𝐶𝐷1 in order to match 𝒜.̂ 4.2. Signature generation simulation After the the key generation, F has to deal with the signature requests issued by A. When A asks for a signature, F performs a simulation while having access to the signing oracle that uses the previously created public key. Here F can fully predict what A will output and, while it does not know any secret key of 𝑃1 , it knows everything of 𝑃2 since all the secret values were extracted from A during the ZK proofs. The simulation proceeds as follows: 1. A chooses a message 𝑚 to sign; 2. F queries its signing oracle for a signature for 𝑚 corresponding to the public key 𝒜 and gets (𝑠𝑓 , 𝑒𝑓 ); 3. 𝑃𝑖 randomly chooses 𝑘𝑖 ∈ ℤ∗𝑞 , then computes 𝑟𝑖 = 𝑔 𝑘𝑖 and [KGC 𝑖 , KGD 𝑖 ] = Com(𝑟𝑖 ); 4. 𝑃𝑖 sends KGC 𝑖 , then, after receiving KGC 𝑗 , sends KGD 𝑖 and gets 𝑟𝑖 = Ver([KGC 𝑖 , KGD 𝑖 ]); 5. F rewinds A to step 4; 𝑟𝑓 6. F computes 𝑟1̂ = 𝑟 , then its commitment [KGC ̂1 , KGD ̂1 ] = Com(𝑟1̂ ) and sends KGC ̂1 to 2 A so it receives 𝑟1̂ as 𝑟1 which leads to 𝑟 = 𝑟𝑓 ; 7. 𝑃𝑖 computes 𝑟 = 𝑟1 𝑟2 , 𝑒 = 𝐻 (𝑟||𝑚), and 𝑠𝑖 = 𝑘𝑖 − 𝜔𝑖 𝑒 (F picks 𝑠1 at random); 8. 𝑃𝑖 computes [KGC ′𝑖 , KGD ′𝑖 ] = Com(𝑠𝑖 ), then sends KGC ′𝑖 ; 9. 𝑃𝑖 sends KGD ′𝑖 and gets 𝑠𝑖 = Ver([KGC ′𝑖 , KGD ′𝑖 ]); 10. F computes 𝑟2′ = 𝑔 𝑠2 ⋅ 𝑔 −𝑒𝜔2 , if 𝑟2 = 𝑟2′ it rewinds A to step 8, otherwise it sends 𝑠1 and aborts; 11. F computes 𝑠1̂ = 𝑠𝑓 − 𝑠2 with its commitment [KGĈ ′ 1 , KGD̂ ′ 1 ] = Com(𝑠1̂ ) and sends KGĈ ′ 1 to A so it receives 𝑠1̂ as 𝑠1 which leads to 𝑠 = 𝑠𝑓 ; 12. 𝑃𝑖 computes 𝑠 = 𝑠1 + 𝑠2 and 𝑟𝑣 = 𝑔 𝑠 𝒜 𝑒 , then checks that 𝐻 (𝑟𝑣 ||𝑚) = 𝑒. If a check fails the protocol aborts, otherwise the signature is (𝑠, 𝑒). 71 Lemma 4.4. If Com is a secure non-malleable commitment scheme, the protocol above is a perfect simulation of the centralized one and terminates correctly with output (𝑠𝑓 , 𝑒𝑓 ). Proof. The simulation is identical to the real protocol except that here F does not know its secret shards. Nevertheless it is still able to retrieve the correct value from A by rewinding it. As above, if the protocol terminates, by construction it will terminate with output (𝑠𝑓 , 𝑒𝑓 ). If A is dishonest or refuses to decommit some values, the protocol aborts. Note that the check of step 10 is introduced to preserve any abort that the adversary may cause by sending an invalid 𝑠1 . 4.3. Recovery signature simulation Since A can ask both types of signature, we must also consider the case of a recovery signature. The core algorithm remains the same, so the results above still holds. Here we only need to change the setup phase during which the third player recovers its secret data. There are two scenarios: one in which A controls one of 𝑃1 or 𝑃2 and another where it controls 𝑃3 , which is easier, since the enrollment phase can be avoided. We will proceed in order. Trivially, if A asks for a recovery signature between the two honest parties, F can simply ask its oracle and output whatever it received from the oracle. So we can limit ourselves to deal with the case where A participates in the signing process. If A controls 𝑃2 the simulation works as follows: 1. 𝑃2 sends to 𝑃3 𝒜 , rec1,3 , rec2,3 . Note that some of them are random data sent by 𝑃1 ; 2. 𝑃3 cannot decrypt the values received in the previous step. It simulates the ZKP about 𝑥3 and extracts the secret values from 𝑃2 ; 3. 𝑃2 computes 𝜔2̃ = −3𝜔2 . Note that 𝑃3 does not have the right shards so it cannot compute its secret key; 4. They perform the signing algorithm using the simulation above. Here F does not know its secret key, but it can use the signing oracle to get the signature. If A controls 𝑃1 the only difference is in the computation of 𝜔̃ 1 = 34 𝜔1 . The last case is the one where A controls 𝑃3 . The enrollment phase is done all by F so it can easily generate random shards that will be sent to 𝑃3 during the recovery signature phase and output the public key given by the oracle. Then with the same simulation as before it can simulate the signature. 4.4. Proof of the unforgeability property Now that we have dealt with all the possible cases we need to prove Theorem 4.1: 72 Proof. Let 𝑄 < 𝜆𝑐 be the maximum number of signature queries that the adversary makes. In a real instance of the protocol the adversary outputs a forgery after 𝑙 < 𝑄 queries, either because it stops submitting queries or because the protocol aborts. As we previously proved, our simulator produces a view of the protocol that the adversary cannot distinguish from the real one, therefore A will produce a forgery with the same 3 probability as in a real execution. Then the probability of success of our forger F is 𝜖8 which is the product of the probability of the following independent events: 1. choosing a good random tape for A, whose probability is at least 2𝜖 as per Lemma 4.1; 2. getting a good public key, whose probability is at least 2𝜖 as shown in Lemma 4.2 and 4.3; 3. A successfully produces a forgery, whose probability is again 2𝜖 (2). Under the assumption on the security of the Schnorr signature scheme, the probability of success of F must be negligible, which implies that 𝜖 must be negligible too, contradicting the hypothesis that A has a non-negligible probability of forging a signature for the scheme. 4.5. Resilience of the recovery In our security analysis we focused on the unforgeability of the signature, however with an offline party another security aspect is worthy of consideration: the resiliency of recovery in the presence of a malicious adversary. Of course if the offline party is malicious and unwilling to cooperate there is nothing we can do about it, however the security can be strengthened if we consider that one of the online parties may corrupt the recovery material. In this case a generic CPA asymmetric encryption scheme is not sufficient to prevent malicious behaviour, because we need a verifiable encryption scheme that allows the parties to prove that the recovery material is consistent, just like they prove that they computed the shards correctly. In particular we need an encryption scheme that supports DLOG verification as explained in point 2d of the Key-Generation algorithm. A suitable candidate could be a variant of the CramerShoup cryptosystem presented in [6]. This algorithm is equipped with a ZKP that allows the sender to prove that the plaintext encrypted is the discrete logarithm of a public value. In particular, since the protocol is a three step ZKP with special soundness, completeness, and honest-verifier zero knowledge, it is possible to build a non-interactive ZKP using the Fiat-Shamir heuristic. 5. Conclusions In this paper, we presented a Schnorr threshold signature with the goal of providing a reliable and efficient solution for the custody of crypto-assets, both from possible attackers and from loss due to accidents of various nature. In this sense, threshold signatures 73 without a trusted dealer offer a perfect solution, since the private key is never created, and they overcome the limitations of blockchains that do not have native multi-signature support. Although decentralized signature algorithms have been known for a while, we are aware of only few proposals for algorithms that are able to produce signatures indistinguishable from a standard one. The protocol described in this work is, as far as we know, the first example of Schnorr threshold multi-signature allowing the presence of an offline participant during key-generation and whose signatures are indistinguishable from Schnorr ones. The focus of this work was to shift away from DSA-like protocols, further motivated by the recent adoption of Schnorr signatures in Bitcoin4 . Moreover, Schnorr signatures are quite a multi-party-friendly algorithm, unlike EdDSA, since we can avoid expensive tricks to generate a deterministic nonce. Similarly to its ECDSA and EdDSA counterparts, in order to guarantee the security of the signature itself against black-box adversaries, the protocol involves a large utilization of ZKPs, that are the main bottleneck in terms of efficiency. Future research steps could be the generalization to (𝑡, 𝑛)-threshold schemes with more than one offline party and the extension of our notion of security. Although our protocol is susceptible to DOS attacks on the offline party, there are many ways to overcome this apparent weakness, such as the distribution of the role of the Recovery party to multiple servers or the generalization of our scheme to more than three parties. Acknowledgments The core results of this paper are contained in the Master’s Thesis of the second author, supervised by the first and fourth authors. The third and the fourth authors are members of the INdAM Research group GNSAGA. The first author acknowledges support from TIM S.p.A. through the PhD scholarship. References [1] Michele Battagliola, Riccardo Longo, Alessio Meneghetti, and Massimiliano Sala. A provably-unforgeable threshold eddsa with an offline recovery party. CoRR, abs/2009.01631, 2020. [2] Michele Battagliola, Riccardo Longo, Alessio Meneghetti, and Massimiliano Sala. Threshold ecdsa with an offline recovery party. Mediterranean Journal of Mathe- matics, 19(1):1–29, 2022. [3] Mihir Bellare and Phillip Rogaway. Introduction to modern cryptography, 2005. https://web.cs.ucdavis.edu/~rogaway/classes/227/spring05/book/main.pdf. [4] Dan Boneh, Rosario Gennaro, and Steven Goldfeder. Using level-1 homomorphic encryption to improve threshold dsa signatures for bitcoin wallet security, 2017. [5] Gilles Brassard, David Chaum, and Claude Crépeau. Minimum disclosure proofs of knowledge. Journal of computer and system sciences, 37(2):156–189, 1988. 4 See https://github.com/taprootactivation/Taproot-Activation, accessed 29th April 2022 74 [6] Jan Camenisch and Victor Shoup. Practical verifiable encryption and decryption of discrete logarithms. In Dan Boneh, editor, Advances in Cryptology - CRYPTO 2003, pages 126–144, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg. [7] Ran Canetti, Rosario Gennaro, Steven Goldfeder, Nikolaos Makriyannis, and Udi Peled. Uc non-interactive, proactive, threshold ecdsa with identifiable aborts. In Pro- ceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 1769–1787, 2020. [8] Vincenzo Di Nicola. Custody at conio-part 3, 2020. https://medium.com/conio/ custody-at-conio-part-3-623292bc9222. [9] Jack Doerner, Yashvanth Kondi, Eysa Lee, and Abhi Shelat. Secure two-party threshold ecdsa from ecdsa assumptions. In 2018 IEEE Symposium on Security and Privacy (SP), pages 980–997. IEEE, 2018. [10] Jack Doerner, Yashvanth Kondi, Eysa Lee, and Abhi Shelat. Threshold ecdsa from ecdsa assumptions: The multiparty case. In 2019 IEEE Symposium on Security and Privacy (SP), pages 1051–1066. IEEE, 2019. [11] P. Feldman. A practical scheme for non-interactive verifiable secret sharing. In 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), pages 427–438, 1987. [12] Rosario Gennaro and Steven Goldfeder. Fast multiparty threshold ecdsa with fast trustless setup. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 1179–1194. ACM, 2018. [13] Rosario Gennaro, Steven Goldfeder, and Arvind Narayanan. Threshold-optimal dsa/ecdsa signatures and an application to bitcoin wallet security. In International Conference on Applied Cryptography and Network Security, pages 156–174. Springer, 2016. [14] Rosario Gennaro, Stanisław Jarecki, Hugo Krawczyk, and Tal Rabin. Robust threshold dss signatures. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 354–371. Springer, 1996. [15] Rosario Gennaro, Stanisław Jarecki, Hugo Krawczyk, and Tal Rabin. Secure distributed key generation for discrete-log based cryptosystems. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 295–310. Springer, 1999. [16] Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pages 174–187, 1986. [17] Yashvanth Kondi, Bernardo Magri, Claudio Orlandi, and Omer Shlomovits. Refresh when you wake up: Proactive threshold wallets with offline devices. IACR Cryptol. ePrint Arch., 2019:1328, 2019. [18] Yehuda Lindell. Fast secure two-party ecdsa signing. In Annual International Cryptology Conference, pages 613–644. Springer, 2017. [19] Yehuda Lindell and Ariel Nof. Fast secure multiparty ecdsa with practical distributed key generation and applications to cryptocurrency custody. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 75 1837–1854. ACM, 2018. [20] Philip MacKenzie and Michael K Reiter. Two-party generation of dsa signatures. In Annual International Cryptology Conference, pages 137–154. Springer, 2001. [21] Philip MacKenzie and Michael K Reiter. Two-party generation of dsa signatures. International Journal of Information Security, 2(3-4):218–239, 2004. [22] Antonio Marcedone and Claudio Orlandi. Obfuscation → (ind-cpa security ↛ circular security). In International Conference on Security and Cryptography for Networks, pages 77–90. Springer, 2014. [23] Gregory Neven, Nigel P Smart, and Bogdan Warinschi. Hash function requirements for schnorr signatures. Journal of Mathematical Cryptology, 3(1):69–87, 2009. [24] Claus-Peter Schnorr. Efficient identification and signatures for smart cards. In Conference on the Theory and Application of Cryptology, pages 239–252. Springer, 1989. [25] Berry Schoenmakers. A simple publicly verifiable secret sharing scheme and its application to electronic voting. In Annual International Cryptology Conference, pages 148–164. Springer, 1999. [26] Adi Shamir. How to share a secret. Commun. ACM, 22(11):612613, November 1979. [27] Victor Shoup and Joel Alwen. Σ-Protocols Continued and Introduction to Zero Knowledge, 2007. https://cs.nyu.edu/courses/spring07/G22.3220-001/lec3.pdf. 76