Optimal stateless deterministic threshold schnorr signatures from bi-homomorphic pseudo-random functions

A non-transitory computer-readable storage medium coupled to one or more processors and having instructions stored thereon which, when executed by the one or more processors, cause the one or more processors to perform operations for secure execution of transactions between computing devices, the operations comprising:

• receiving, by a second computing device and from a first computing device, a first set of nonce values, each nonce value in the first set of nonce values being generated using a first bi-homomorphic pseudo-random function (BH-PRF) of the first computing device and being deterministic with respect to a message;
• transmitting, by the second computing device and to the first computing device, a second set of nonce values, each nonce value in the second set of nonce values being generated using a second BH-PRF of the second computing device and being deterministic with respect to the message;
• and
• executing, by the second computing device, at least part of a threshold signature scheme (TSS) in response to:
• verifying, by the second computing device, correctness of a verification token based on the first set of nonce values and the second BH-PRF, and
• correctness of the verification token being verified by the first computing device based on the second set of nonce values and the first BH-PRF.

A system, comprising:

• one or more processors;
• and
• a non-transitory computer-readable storage device and having instructions stored thereon which, when executed by the computing device, cause the computing device to perform operations for secure execution of transactions between computing devices, the operations comprising:
• receiving, by a second computing device and from a first computing device, a first set of nonce values, each nonce value in the first set of nonce values being generated using a first bi-homomorphic pseudo-random function (BH-PRF) of the first computing device and being deterministic with respect to a message;
• transmitting, by the second computing device and to the first computing device, a second set of nonce values, each nonce value in the second set of nonce values being generated using a second BH-PRF of the second computing device and being deterministic with respect to the message;
• and
• executing, by the second computing device, at least part of a threshold signature scheme (TSS) in response to:
• verifying, by the second computing device, correctness of a verification token based on the first set of nonce values and the second BH-PRF, and
• correctness of the verification token being verified by the first computing device based on the second set of nonce values and the first BH-PRF.