Provably Unforgeable Threshold EdDSA with an Offline Participant and Trustless Setup

We present an EdDSA-compatible multi-party digital signature scheme that supports an offline participant during the key-generation phase, without relying on a trusted third party. Under standard assumptions, we prove our scheme secure against adaptive malicious adversaries. Using a classical game-based argument, we prove that if there is an adversary capable of forging the scheme with non-negligible probability, then we can build a forger for the original EdDSA scheme with non-negligible probability. The scheme requires only two communication rounds in the signature generation phase and avoids expensive multi-party evaluation of cryptographic hash functions. We present our solution in a setting where two parties generate the keys and compute signatures, with a third party which can be brought online after the key generation when one of the other parties becomes unavailable. This setting is a perfect fit for custodial solutions where partially trusted services are employed by a user to increase resiliency. We provide also a possible solution to retain the resiliency of the recovery in the presence of a malicious party.