Description:FORM 2

THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003

COMPLETE SPECIFICATION
(See Section 10 and Rule 13)

Title of invention:

METHOD AND SYSTEM FOR TWO-PARTY THRESHOLD DIGITAL SIGNATURE GENERATION

Applicant

Tata Consultancy Services Limited
A company Incorporated in India under the Companies Act, 1956
Having address:
Nirmal Building, 9th floor,
Nariman point, Mumbai 400021,
Maharashtra, India

Preamble to the description:
The following specification particularly describes the invention and the manner in which it is to be performed.
TECHNICAL FIELD

The disclosure herein generally relates to the field of cryptography and digital signatures, and, more particularly, to a method and a system for two-party threshold digital signature generation.

BACKGROUND

With the advancement of digital technology, digital communication has exponentially increased, however the biggest challenge with digital communication is to ensure secure transformation of the confidential information. Cryptography provides for a secure transmission of confidential information. In the field of cryptography, threshold signature is one of the most remarkable landmark schemes for secure transmission of confidential information.
A threshold signature scheme enables a group of n parties to jointly generate a digital signature using a single signing key, wherein a private key is split into partial keys and distributed among n parties, unlike regular signature schemes. There are several applications of threshold signatures for several scenarios that require signing only when a certain threshold of the parties/owners agrees, such as government agencies, banks, certifying authorities, wherein dividing the signing power from single to multiple entities provides increased protection against forgery by an adversary, as well as increases the availability of the signing entities thereby eliminating the single point of failure attack.
Digital Cryptographic techniques store keys (private keys) in online system for long term, thus making the keys vulnerable to the single-point of failure attack. To overcome the challenge, several techniques have been proposed and deployed in different cryptocurrencies. However, most of the existing threshold signature scheme such as Hardware Security Modules (HSMs) fail to provide security against malware attacks.
Further, another state-of-art for the threshold signature scheme is a fast threshold signatures such as RSA, Elliptical Curve Digital Signature Algorithm (ECDSA) and Schnorr signatures. However, despite several efforts towards the fast threshold signature schemes most of the protocols involve heavy-weight computations leading to delayed signing and verification time, which can be attributed to the difficulty involved in designing a threshold signature protocol for ECDSA, thus making the fast threshold signature schemes unfit for applications with limited computation power. Further the other challenge with the existing schemes includes identification of ways for secure storage of signing keys without relying on HSMs. Hence there is a requirement to overcome the above-mentioned shortcomings and design new solutions towards building a lightweight threshold signature scheme in the two-party setting with a trustless setup.

SUMMARY

Embodiments of the present disclosure present technological improvements as solutions to one or more of the above-mentioned technical problems recognized by the inventors in conventional systems. For example, in one embodiment, a method for two-party threshold digital signature generation is provided.
The system includes a memory storing instructions, one or more communication interfaces, and one or more hardware processors coupled to the memory via the one or more communication interfaces, wherein the one or more hardware processors are configured by the instructions to sharing a plurality of input parameters and a message with the first party and the second party, wherein the plurality of input parameters comprises an elliptic curve defined by an elliptic curve equation over a finite field, a base point in the elliptic curve, a pre-defined bit fixed prime number indicating an order of points in the elliptic curve , a field , a plurality of random numbers wherein each random number is an integer belonging to the field, and a set of hash functions. The system further includes generating a public key, via the one or more hardware processors, at the first party and the second party based on a public key generation technique, wherein the public key is generated at the first party and the second party using the plurality of input parameters, a first random number and a second random number from the plurality of random numbers. The system further includes generating a session key, via the one or more hardware processors, at the first party and the second party based on a session key generation technique, wherein the session key is generated at the first party and the second party using the plurality of input parameters, a third random number and a fourth random number from the plurality of random number. The system further includes generating a threshold digital signature at the first party and the second party , via the one or more hardware processors, based on a threshold digital signature generation technique, wherein the threshold digital signature generation technique comprises: generating a first set of signature components at the first party and the second party, wherein the first set of signature components comprises a hash element and a message digest, and the first set of signature components is generated using the plurality of input parameters, the message, the public key, and the session key, generating a second set of signature components at the first party, wherein the second set of signature components comprises a function value and a blinding element , generated using the plurality of input parameters and the first set of signature components, sharing the second set of signature components with the second party for a consistency verification; and generating the threshold digital signature based on the consistency verification using the plurality of input parameters, the first set of signature components, the second set of signature components and the first partial public key.
In another aspect, a method for two-party threshold digital signature generation is provided. The method includes sharing a plurality of input parameters and a message with the first party and the second party, wherein the plurality of input parameters comprises an elliptic curve defined by an elliptic curve equation over a finite field, a base point in the elliptic curve, a pre-defined bit fixed prime number indicating an order of points in the elliptic curve , a field , a plurality of random numbers wherein each random number is an integer belonging to the field, and a set of hash functions. The method further includes generating a public key at the first party and the second party based on a public key generation technique, wherein the public key is generated at the first party and the second party using the plurality of input parameters, a first random number and a second random number from the plurality of random numbers. The method further includes generating a session key at the first party and the second party based on a session key generation technique, wherein the session key is generated at the first party and the second party using the plurality of input parameters, a third random number and a fourth random number from the plurality of random number. The method further includes generating a threshold digital signature at the first party and the second party based on a threshold digital signature generation technique, wherein the threshold digital signature generation technique comprises: generating a first set of signature components at the first party and the second party, wherein the first set of signature components comprises a hash element and a message digest, and the first set of signature components is generated using the plurality of input parameters, the message, the public key, and the session key, generating a second set of signature components at the first party, wherein the second set of signature components comprises a function value and a blinding element , generated using the plurality of input parameters and the first set of signature components, sharing the second set of signature components with the second party for a consistency verification; and generating the threshold digital signature based on the consistency verification using the plurality of input parameters, the first set of signature components, the second set of signature components and the first partial public key.
In yet another aspect, a non-transitory computer readable medium for two-party threshold digital signature generation is provided. The program includes sharing a plurality of input parameters and a message with the first party and the second party, wherein the plurality of input parameters comprises an elliptic curve defined by an elliptic curve equation over a finite field, a base point in the elliptic curve, a pre-defined bit fixed prime number indicating an order of points in the elliptic curve , a field , a plurality of random numbers wherein each random number is an integer belonging to the field, and a set of hash functions. The program further includes generating a public key at the first party and the second party based on a public key generation technique, wherein the public key is generated at the first party and the second party using the plurality of input parameters, a first random number and a second random number from the plurality of random numbers. The program further includes generating a session key at the first party and the second party based on a session key generation technique, wherein the session key is generated at the first party and the second party using the plurality of input parameters, a third random number and a fourth random number from the plurality of random number. The program further includes generating a threshold digital signature at the first party and the second party based on a threshold digital signature generation technique, wherein the threshold digital signature generation technique comprises: generating a first set of signature components at the first party and the second party, wherein the first set of signature components comprises a hash element and a message digest, and the first set of signature components is generated using the plurality of input parameters, the message, the public key, and the session key, generating a second set of signature components at the first party, wherein the second set of signature components comprises a function value and a blinding element , generated using the plurality of input parameters and the first set of signature components, sharing the second set of signature components with the second party for a consistency verification; and generating the threshold digital signature based on the consistency verification using the plurality of input parameters, the first set of signature components, the second set of signature components and the first partial public key.
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed.

BRIEF DESCRIPTION OF THE DRAWINGS

The accompanying drawings, which are incorporated in and constitute a part of this disclosure, illustrate exemplary embodiments and, together with the description, serve to explain the disclosed principles:
FIG.1 illustrates an exemplary system for two-party threshold digital signature generation according to some embodiments of the present disclosure,
FIG.2A and FIG.2B is a flow diagram illustrating a method (200) for two-party threshold digital signature generation in accordance with some embodiments of the present disclosure.
FIG.3 is a flow diagram illustrating a method (300) for public key generation technique during for two-party threshold digital signature generation in accordance with some embodiments of the present disclosure,
FIG.4A and FIG.4B is a flow diagram illustrating a method (400) for session key generation technique during for two-party threshold digital signature generation in accordance with some embodiments of the present disclosure, and
FIG.5 is a flow diagram illustrating a method (500) for threshold digital signature verification technique after generating the two-party threshold digital signature in accordance with some embodiments of the present disclosure.

DETAILED DESCRIPTION OF EMBODIMENTS

Exemplary embodiments are described with reference to the accompanying drawings. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. Wherever convenient, the same reference numbers are used throughout the drawings to refer to the same or like parts. While examples and features of disclosed principles are described herein, modifications, adaptations, and other implementations are possible without departing from the scope of the disclosed embodiments.
The embodiments disclosed herein are directed to a two-party threshold digital signature generation scheme that utilizes a set of lightweight operations in two party setting, wherein two parties refer to one of two computing devices such as two PCs, two servers, two mobile devices, etc., or a combination of above devices, for example one PC and one mobile. The disclosure for a two-party threshold digital signature generation eliminates the need for trusting any third-party storage for signature generation, maintaining a trustless setup model. A threshold digital signature scheme is introduced in an elliptic curve setting, and the security is verified against existential forgery in the random oracle model from the Decisional Diffie-Hellman assumption.
The method and system disclosed herein generate a valid publicly verifiable threshold digital signature in a two-party setting. The generation of the threshold digital signature is based on a key-splitting technique, where a private key is split into two shares and shared between two parties in a distributed fashion, such that, the first party is not aware of the private share value of second party and vice versa. Further the disclosed method further secures the communication by aborting the threshold digital signature generation process in case one of the parties is compromised by an adversary by performing verification process. The two-parties can be any two computing devices, such as two servers, laptops or mobile phones or a combination of the above, where the shares of the private key is stored.
Referring now to the drawings, and more particularly to FIG. 1 through FIG.5, where similar reference characters denote corresponding features consistently throughout the figures, there are shown preferred embodiments and these embodiments are described in the context of the following exemplary system and/or method.
FIG.1 is an exemplary block diagram of a system 100 for two-party threshold digital signature generation in accordance with some embodiments of the present disclosure. The system 100 enables communication between the two parties that require to generate the threshold digital signature.
In an embodiment, the system 100 includes a processor(s) 104, communication interface device(s), alternatively referred as input/output (I/O) interface(s) 106, and one or more data storage devices or a memory 102 operatively coupled to the processor(s) 104. The system 100 with one or more hardware processors is configured to execute functions of one or more functional blocks of the system 100.
Referring to the components of the system 100, in an embodiment, the processor(s) 104, can be one or more hardware processors 104. In an embodiment, the one or more hardware processors 104 can be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the one or more hardware processors 104 is configured to fetch and execute computer-readable instructions stored in the memory 102. In an embodiment, the system 100 can be implemented in a variety of computing systems including laptop computers, notebooks, hand-held devices such as mobile phones, workstations, mainframe computers, servers, a network cloud and the like.
The I/O interface(s) 106 can include a variety of software and hardware interfaces, for example, a web interface, a graphical user interface, a touch user interface (TUI) and the like and can facilitate multiple communications within a wide variety of networks N/W and protocol types, including wired networks, for example, LAN, cable, etc., and wireless networks, such as WLAN, cellular, or satellite. In an embodiment, the I/O interface (s) 106 can include one or more ports for connecting a number of devices (nodes) of the system 100 to one another or to another server.
The memory 102 may include any computer-readable medium known in the art including, for example, volatile memory, such as static random-access memory (SRAM) and dynamic random-access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes.
Further, the memory 102 may include a database 108 configured to include information regarding two-party threshold digital signature generation. The memory 102 may comprise information pertaining to input(s)/output(s) of each step performed by the processor(s) 104 of the system 100 and methods of the present disclosure. In an embodiment, the database 108 may be external (not shown) to the system 100 and coupled to the system via the I/O interface 106.
The system 100 supports various connectivity options such as BLUETOOTH®, USB, ZigBee and other cellular services. The network environment enables connection of various components of the system 100 using any communication link including Internet, WAN, MAN, and so on. In an exemplary embodiment, the system 100 is implemented to operate as a stand-alone device. In another embodiment, the system 100 may be implemented to work as a loosely coupled device to a smart computing environment. The components and functionalities of the system 100 are described further in detail.
The various modules of the system 100 are configured for two-party threshold digital signature generation are implemented as at least one of a logically self-contained part of a software program, a self-contained hardware component, and/or, a self-contained hardware component with a logically self-contained part of a software program embedded into each of the hardware component that when executed perform the above method described herein.
Functions of the components of the system 100 are explained in conjunction with flow diagram of FIG.2A and FIG.2B. The FIG.2A and FIG.2B with reference to FIG.1, is an exemplary flow diagram illustrating a method 200 for two-party threshold digital signature generation using the system 100 of FIG.1 according to an embodiment of the present disclosure.
The steps of the method 200 of the present disclosure will now be explained with reference to the components of the system (100) for two-party threshold digital signature generation as depicted the flow diagrams as depicted in FIG.2A and FIG.2B. Although process steps, method steps, techniques or the like may be described in a sequential order, such processes, methods and techniques may be configured to work in alternate orders. In other words, any sequence or order of steps that may be described does not necessarily indicate a requirement that the steps to be performed in that order. The steps of processes described herein may be performed in any order practical. Further, some steps may be performed simultaneously.
At step 202 of the method (200) a plurality of input parameters and a message digest (m) is shared with the first party and the second party, via one or more hardware processors 104.
The plurality of input parameters comprises an elliptic curve (E) defined by an elliptic curve equation over a finite field, a base point (P) in the elliptic curve, a pre-defined bit fixed prime number (q) indicating an order of points in the elliptic curve , a field (Z_p), a plurality of random numbers wherein each random number is an integer belonging to Z_p, and a set of hash functions ( H_1 and H_2). Further, for the set of hash functions - H_1 is a hash function mapping two elliptic curve points to an integer and H_2 is a hash function mapping a string of arbitrary length to an integer.
The disclosure for two-party threshold digital signature generation is a key-splitting technique, where a private key (a) is generated by the two parties as secret shares in a distributed fashion, such that, the first party is not aware of the private share value of second party and vice versa. In an embodiment, the first party and the second party refer to one of two computing devices such as two PCs, two servers, two mobile devices, etc., or a combination of above devices, for example one PC and one mobile.
The plurality of random numbers comprises several random numbers wherein each random number is an integer belonging to Z_q. The random are defined by the rule as shown below:
a_1 + a_2 = a (mod q) ---- (1)
The disclosed technique ensures secure generation of the digital signature by splitting the secret key and distributing one part each to the participating parties, thus increasing safety and making the technique more secure.
At step 204 of the method (200), a public key (PK) is generated by the first party and the second party based on a public key generation technique, via one or more hardware processors 104. The public key is generated at the first party and the second party using the plurality of input parameters, a first random number (a_1) and a second random number (a_2) from the plurality of random numbers, such that the equation (1) for private key for first random number (a_1) and the second random number (a_2) is satisfied.
The two parties - party A and the party B, independently generate their public key (PK) / key shares and then together obtain the public key in several steps as discussed below – using the public key generation technique.
In an embodiment, the method for public key generation technique is explained using flowchart of method 300 as depicted in FIG.3. The public key generation technique comprises the following steps.
At step 302 of the method 300, a first partial public key (?PPK?_A) is computed at the first party. The first partial public key is computed as an exponentiation of the base point in the elliptic curve (P) with the first random number (a_1) .
In an embodiment, the first party identifies a first random number (a_1), wherein the first random number (a_1) belongs to the plurality of random numbers. The first random number (a_1) is the first share of the private key. Further the first partial public key (?PPK?_A) is computed as an exponentiation of the base point in the elliptic curve (P) with the first random number (a_1), expressed as shown below:
?PPK?_A= a_1 P --- (2)
At step 304 of the method 300, a zero-knowledge proof (p_1) of the first partial public key is computed at the first party.
In an embodiment, the zero-knowledge proof (p_1) of the first partial public key is computed at the first party to prove that the first partial public key is valid, wherein the zero-knowledge proof (ZKP) is a cryptographic construct used to prove integrity of a class of computations. The class of computation refers to providing a correctness of discrete logarithm operation. If the ZKP is valid, the process of generation of the digital key is continued, whereas if the ZKP is invalid, then the process of the generation of the digital key is aborted.
At step 306 of the method 300, a second partial public key (?PPK?_B) is computed at the second party. The second partial public key is computed as an as exponentiation of the base point in the elliptic curve (P) with the second random number (a_2).
In an embodiment, the second party identifies a second random number (a_2), wherein the second random number (a_2) belongs to the plurality of random numbers. The second random number (a_2) is the second share of the private key. Further the second partial public key (?PPK?_B) is computed as an exponentiation of the base point in the elliptic curve (P) with the second random number (a_2), expressed as shown below:
?PPK?_B= a_2 P --- (3)
At step 308 of the method 300, a zero-knowledge proof (p_2) of the second partial public key is computed by the second party.
In an embodiment, the zero-knowledge proof (p_2) of the first partial public key is computed at the second party to prove that the second partial public key is valid, wherein the zero-knowledge proof (ZKP) is a cryptographic construct used to prove integrity of a class of computations. The class of computation refers to providing a correctness of discrete logarithm operation. If the ZKP is valid, the process of generation of the digital key is continued whereas if the ZKP is invalid, then the process of the generation of the digital key is aborted.
At step 310 of the method 300, the first partial public key and the zero-knowledge proof of the first partial public key (p_1) are exchanged with the second party and the second partial public key and the zero-knowledge proof of the second partial public key (p_2) with is shared the first party for a zero-knowledge proof verification.
In an embodiment, the first partial public key and the second partial public key along with the ZKP s generated at the first party and the second party are exchanged with each other. In an example scenario, a non-interactive ZKP of discrete logarithm is utilized, wherein the proof of discrete log proceeds without revealing the logarithmic value. A ZKP (p_1) is computed at the first party as a tuple, which is verified at the second party if a pre-defined discrete log function is verified. The first party verifies that the zero-knowledge proof (ZKP) received (from the second party), based on the verification the process is continued for a valid ZKP however in case of invalid ZKP, the generation of the digital signature is aborted. Similarly, the second party verifies that the zero-knowledge proof received (from the first party), based on the verification the process is continued for a valid ZKP however in case of invalid ZKP, the generation of the digital signature is aborted. If none of the parties call abort, the public key is generated simultaneously at the first party and the second party.
At step 312 of the method 300, the public key (PK) is generated at the first party and the second party. The public key is generated as a point addition of the first partial public key and the second partial public key.
In an embodiment, generation of public key (PK) is expressed as shown below:
PK= ?PPK?_A+?PPK?_B ---(4)
Referring to FIG.2, at step 206 of the method (200), a session key is generated by the first party and the second party based on a session key generation technique, via one or more hardware processors 104. The session key is generated at the first party and the second party using the plurality of input parameters, a third random number (k_1) and a fourth random number (k_2) respectively from the plurality of random number.
In an embodiment, the method for session key generation technique is explained using flowchart of 400 as depicted in FIG.4. The session key generation technique comprises the following steps.
At step 402 of the method 400, a first local session key (T_1) is computed at the first party.
In an embodiment, the first local session key (T_1) is computed as an exponentiation of the base point in the elliptic curve (P) with a third random number (k_1) as shown below:
T_1= k_1 P --- (5)
At step 404 of the method (400), a zero-knowledge proof of the first local session key (p_3) is computed by the first party.
In an embodiment, a non-interactive ZKP of discrete logarithm is utilized, wherein the proof of discrete log proceeds without revealing the logarithmic value. A ZKP (p_3) is computed at the first party as a tuple, which is verified at the second party if a pre-defined discrete log function is verified. The first party verifies that the zero-knowledge proof (ZKP) received (from the second party), based on the verification the process is continued for a valid ZKP however in case of invalid ZKP, the generation of the digital signature is aborted. Similarly, the second party verifies that the zero-knowledge proof received (from the first party), based on the verification the process is continued for a valid ZKP however in case of invalid ZKP, the generation of the digital signature is aborted. If none of the parties call abort, the public key is generated simultaneously at the first party and the second party.
At step 406 of the method 400, a second local session key (T_2) is computed at the second party.
In an embodiment, the second local session key is computed as an exponentiation of the base point in the elliptic curve (P) with a fourth random number (k_2) , expressed as shown below:
T_2= k_2 P --- (6)
At step 408 of the method 400, a zero-knowledge proof of the second local session key (p_4) is computed at the second party.
In an embodiment, a non-interactive ZKP of discrete logarithm is utilized, wherein the proof of discrete log proceeds without revealing the logarithmic value. A ZKP (p_4) is computed at the second party as a tuple, which is verified at the first party if a pre-defined discrete log function is verified. The second party verifies that the zero-knowledge proof (ZKP) received (from the first party), based on the verification the process is continued for a valid ZKP however in case of invalid ZKP, the generation of the digital signature is aborted. Similarly, the first party verifies that the zero-knowledge proof received (from the first party), based on the verification the process is continued for a valid ZKP however in case of invalid ZKP, the generation of the digital signature is aborted. If none of the parties call abort, the public key is generated simultaneously at the first party and the second party.
At step 410 of the method 400 the first local session key and the zero-knowledge proof of the first local session key are exchanged with the second party and the second local session key and the zero-knowledge proof of the second local session key is exchanged with the first party for a zero-knowledge proof verification.
In an embodiment, the first party verifies that the zero-knowledge proof (ZKP) received (from the second party), based on the verification the process is continued for a valid ZKP however in case of invalid ZKP, the generation of the digital signature is aborted. Similarly, the second party verifies that the zero-knowledge proof received (from the first party), based on the verification the process is continued for a valid ZKP however in case of invalid ZKP, the generation of the digital signature is aborted. If none of the parties call abort, the public key is generated simultaneously at the first party and the second party.
At step 410 of the method 400, a first full local session key and the zero-knowledge proof of the first local session key at the second party is compared with a second full local session key and the zero-knowledge proof of the second local session key at the first party.
Based on the comparison, either step 412A or 412B is performed.
At step 412A of the method 400, a session key (R) is generated at the first party and the second party if the first full local session key and the second full local session key are equal.
The session key (R) is generated at the first party as a multiplication of the first local session key and the third random number is expressed as shown below:
R= k_1 T_2 --- (7)
The session key (R) is generated at the second party as a multiplication of the second local session key and the fourth random number is expressed as shown below:
R= k_2 T_1 ---(8)
At step 412B of the method 400, the process of generation of the session key is aborted if the first full local session key and the second full local session key are unequal.
Referring to FIG.2B, at step 208 of the method 200, a threshold digital signature (S) is generated by the first party and the second party, via one or more hardware processors 104. The threshold digital signature (s) is generated based on a threshold digital signature generation technique. The threshold digital signature generation technique comprises the following sub-steps.
At step 208A, a first set of signature components is generated at the first party and the second party.
The first set of signature components comprises a hash element (r) and a message digest (h), and the first set of signature components is generated using the plurality of input parameters, the message, the public key, and the session key. The set of signature components is generated at the first party and the second party as explained in the below sections.
In an embodiment, the hash element (r) is a hash of the public key, the session key and is expressed as shown below:
r= H_1 (PK,R) (9)
wherein,
H_1 is one of the set of hash functions (H_1,H_2),
R is the session key, and
PK is the public key.
In an embodiment, the message digest (h) is a hash of the message is expressed as:
h= H_2 (m) (10)
wherein,
H_2 is one of the set of hash functions (H_1,H_2)
h is the message digest, and
m is the message.
At step 208B, a second set of signature components is generated at the first party.
The second set of signature components comprises a function value (S_A) and a blinding element (k^'), generated using the plurality of input parameters and the first set of signature components.
In an embodiment, the function value (S_A) is generated based on the message digest (h), the fifth random number (r^' ), k_1 is the third random number, the first random number (a_1), and the pre-defined bit fixed prime number (q) and is expressed as:
S_A=hr^' k_1+ra_1 mod q (11)
wherein,
S_A is the function value,
r^' is a fifth random number,
h is the message digest,
r is the hash element,
k_1 is the third random number,
a_1is the first random number, and
q is the pre-defined bit fixed prime number.
Further the blinding element (k^') is generated based on the fifth random number (r^'), the third random number (k_1) and the pre-defined bit fixed prime number (q) and is expressed as:
k^'= k_1.r^' mod q (12)
Wherein,
k^' is the blinding element,
r is the hash element,
k_1 is the third random number,
q is the pre-defined bit fixed prime number.
At step 208C, the second set of signature components is shared with the second party for a consistency verification. The second set of signature components generated at the first party is shared with the second party for the consistency verification.
In an embodiment, the consistency verification is performed at the second party to check for the consistency of the second set of signature components generated by first party. The consistency verification is performed based on the plurality of input parameters, the first set of signature components and the second set of signature components and is expressed as:
S_A.P=k^'.h.P+r.?PPK?_A (13)
wherein,
S_A is the function value,
P is the base point,
k^' is the blinding element,
h is the message digest,
r is the hash element, and
?PPK?_A is the first partial public key.
The generation of the threshold digital signature is aborted if the consistency verification is failed, wherein the consistency verification is failed when the left-hand side of the equation (S_A.P) is unequal to the right-hand side of the equation (k^'.h.P+r.?PPK?_A).
At step 208D of the method 200, the threshold digital signature is generated based on the consistency verification using the plurality of input parameters, the first set of signature components, the second set of signature components and the first partial public key.
In an embodiment, the generation of the threshold digital signature (s) is expressed as:
s=(s,r,k^' P,T_2) (14)
where,
s= k_2^(-1) (S_A+r.a_2 )mod q
wherein,
k_2 is the fourth random number,
r is the hash element
k^' is the blinding element,
P is the base point,
T_2 is the second local session key,
S_A is the function value,
a_2 is the second random number, and
q is the pre-defined bit fixed prime number.
The generation of the threshold digital signature (s) is verified based on a threshold digital signature verification technique. The threshold digital signature verification technique is illustrated in FIG.5 and comprises of several steps as explained below.
At step 502 of the method 500, the threshold digital signature verification technique includes parsing the threshold digital signature (s) into a pre-defined set of components based on a pre-defined size associated with the pre-defined set of components.
In an embodiment, the threshold digital signature is parsed into its four components based on a size associated with the threshold digital signature. For example, given the size of first component "s" is x bits, then the first x bits of the threshold digital signature is parsed as the value of s
s=(s,r,T^',T_2) --- (15)
wherein
T^'=k^' P
At step 504 of method 500, a modular inverse of the first component is computed from the pre-defined set of components of the parsed threshold digital signature. The modular inverse of the first component (?) is computed as shown below:
?= s^(-1) mod q --- (16)
At step 506 of method 500, a pair of verification component is computed based on the parsed threshold digital signature, the public key and the message digest.
In an embodiment, the pair of verification component is represented by U and V and is computed as shown below :
U= ?.r.PK, --- (17)
V= H_2 (m).w.T' (18)
At step 508 of method 500, the validity of the threshold digital signature is verified using the pair of verification component.
T_2=U+V --- (19)
The validity of the threshold digital signature is verified using the pair of verification component as shown above in equation (19) wherein the threshold digital signature is valid is the equation (19) returns “1” else the threshold digital signature is invalid.
The threshold digital signature generation scheme shared above remains same as described in the above sections for a variety of schemes wherein, the key generation method is tweaked to include a (2,n) as follows: The n parties agree on using some verifiable linear secret sharing scheme ( In an example scenario : Feldman's Verifiable Secret Sharing Scheme). Using such a (pre decided) scheme each party distributes its key share among the remaining (n-1) parties in such a way that any 2 (of the n-1) parties can reconstruct the key share.
Further, the threshold signature scheme has been designed from a novel one-party digital signature scheme. The two-party threshold signature scheme can be converted to a single-party digital signature scheme with the assumption that only one party exists. Thus, there is no requirement of any zero-knowledge proofs p_1,p_2,p_3 or p_4 in this case, as the party itself does the key and signature generation. The two shared secret keys (a_1 and a_2) , partial public keys (?PPK?_A and ?PPK?_B) and local session key share entities (T_1 and T_2) are no longer generated, and are computed by the party as a single private key (a), public key (PK) and session key (R) during the key generation and signature generation method respectively.

EXPERIMENTS:
An experiment has been simulated based on the disclosed technique. The experiment has been compared with state-of-art techniques to measure the performance time taken for threshold digital signature generation. The experimental setup includes two parties - Party1 and Party2 on two different endpoints. The Party1 and Party2 follow the method disclosed and jointly compute the shared secret key – public key and signature in the key generation and threshold digital signature generation protocols respectively.
A 1024 bits as key size and the standard Bitcoin curve SECP256k1 is used for elliptic curve-based operation. The entire code base is built in C language using openssl based ECC library for the elliptic curve operations and MPZ library for all the number theoretic operations. The experiments were run on machine with Intel I5 pro processor with 8 cores each with processor speed of 1.7 Ghz. The Random Access Memory (RAM) of the machine is 16 GB and it is running on Ubuntu 18.0 operating system.
For experimentation purpose, the disclosed technique is compared against the existing threshold signature schemes in the literature for the two-party setting. For the case of ECDSA-based threshold signature schemes, the most efficient scheme is due to "Doerner et al".
The following table (Table 1) illustrates the comparison of timings taken by the disclosed technique and the two other known methods, where te is used to denote the time taken by one modular exponentiation operation.

Protocol KeyGen Sign
Threshold ECDSA by Doerner et al. 10t_e 17t_e
Threshold Schnorr by Komlo et al. 14t_e 13t_e
Threshold RSA by Shoup (involves Dealer for KeyGen ) 2t_e 18t_e
Disclosed method
8t_e 11t_e
Table 1: Comparison with exiting state-of-art

Protocol KeyGen Sign Verify
Doerner et al 43.41 3.26 1.6
Disclosed method
2.1 4.1 1.22
Table 2: Time Comparison in milliseconds
The disclosed threshold signature technique has two components, threshold key generation and threshold digital signature computation. In case of multi-party protocols, the efficiency is indicated by the time required to run these protocols. The lesser the requirement, the better is the protocol. The following table (Table 2) illustrates the comparison of timings taken by the disclosed technique and the three other known methods. The known methods used for comparison are as follows:
J. Doerner, Y. Kondi, E. Lee and A. Shelat, "Secure Two-party Threshold ECDSA from ECDSA Assumptions," 2018 IEEE Symposium on Security and Privacy (SP), 2018, pp. 980-997, doi: 10.1109/SP.2018.00036 - represented as Method B in table.1
C. Komlo and I. Goldberg, “FROST: flexible round-optimized schnorr threshold signatures," in Selected Areas in Cryptography - SAC 2020 - 27th International Conference, 2020, pp. 34-65, doi: 10.1007/978-3-030-81652-0_2
V. Shoup, Practical threshold signatures," in Advances in Cryptology - EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Technique, 2000, pp. 207-220, doi: 10.1007/3-540-45539-6_15
The scheme by Doerner is the most efficient scheme till date, in terms of the time taken for the threshold key generation and the signature generation, however based on the experimentation it can be inferred that the disclosed method is more efficient compared to Doerner. The Table 2 illustrates the total time taken in milliseconds by the scheme of Doerner and our scheme, which demonstrates that our scheme is more efficient than the scheme by Doerner.
The disclosed technique has several advantages compared to the mentioned/ cited prior art items which includes no requirement of any participation in any kind of key exchange or generation method if any two parties want to combine [or aggregate] their signature. In case of a signature exchange, the parties can simply run the disclosed digital signature computation technique, which results in a single [known as aggregated] signature, wherein the digital signature (single) guarantees that both parties have participated in the signature computation and requires a public key that is aggregation of the two individual public keys. On the other hand if the two parties use the methods proposed in the three cited prior arts, then they first have to run in a joint key generation method, which is not required in the disclosed technique, hence resulting in faster and efficient generation of the digital signature.
Another advantage of the disclosed technique is the total computations required is much less compared to other cited prior arts. For example, Doerner's key generation method takes about 10 number of Elliptic curve exponentiation operations while the disclosed technique takes only 4 Elliptic curve exponentiations. Similarly, Doerner’s signature generation method takes about 17 number of Elliptic curve exponentiations, while the disclosed technique two party signature method requires only 12 Elliptic curve exponentiations. Additionally, Doerner’s method needs 16 rounds of interactions between first party and second party for a signature generation, whereas, the present method is faster and requires only 5 rounds of communications between the two parties for signature generation.
The written description describes the subject matter herein to enable any person skilled in the art to make and use the embodiments. The scope of the subject matter embodiments is defined by the claims and may include other modifications that occur to those skilled in the art. Such other modifications are intended to be within the scope of the claims if they have similar elements that do not differ from the literal language of the claims or if they include equivalent elements with insubstantial differences from the literal language of the claims.
The embodiments of present disclosure herein provide a solution to secure threshold digital signature generation. One of the major challenges with threshold digital signature scheme is increased vulnerability during long-term storage of keys in an online system and usage of heavy-weight computations leading to delayed signing and verification time. The disclosure is a lightweight threshold digital signature scheme in the two-party setting with a trustless setup.
It is to be understood that the scope of the protection is extended to such a program and in addition to a computer-readable means having a message therein; such computer-readable storage means contain program-code means for implementation of one or more steps of the method, when the program runs on a server or mobile device or any suitable programmable device. The hardware device can be any kind of device which can be programmed including e.g., any kind of computer like a server or a personal computer, or the like, or any combination thereof. The device may also include means which could be e.g., hardware means like e.g., an application-specific integrated circuit (ASIC), a field-programmable gate array (FPGA), or a combination of hardware and software means, e.g., an ASIC and an FPGA, or at least one microprocessor and at least one memory with software processing components located therein. Thus, the means can include both hardware means and software means. The method embodiments described herein could be implemented in hardware and software. The device may also include software means. Alternatively, the embodiments may be implemented on different hardware devices, e.g., using a plurality of CPUs.
The embodiments herein can comprise hardware and software elements. The embodiments that are implemented in software include but are not limited to, firmware, resident software, microcode, etc. The functions performed by various components described herein may be implemented in other components or combinations of other components. For the purposes of this description, a computer-usable or computer readable medium can be any apparatus that can comprise, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device.
The illustrated steps are set out to explain the exemplary embodiments shown, and it should be anticipated that ongoing technological development will change the manner in which particular functions are performed. These examples are presented herein for purposes of illustration, and not limitation. Further, the boundaries of the functional building blocks have been arbitrarily defined herein for the convenience of the description. Alternative boundaries can be defined so long as the specified functions and relationships thereof are appropriately performed. Alternatives (including equivalents, extensions, variations, deviations, etc., of those described herein) will be apparent to persons skilled in the relevant art(s) based on the teachings contained herein. Such alternatives fall within the scope of the disclosed embodiments. Also, the words “comprising,” “having,” “containing,” and “including,” and other similar forms are intended to be equivalent in meaning and be open ended in that an item or items following any one of these words is not meant to be an exhaustive listing of such item or items, or meant to be limited to only the listed item or items. It must also be noted that as used herein and in the appended claims, the singular forms “a,” “an,” and “the” include plural references unless the context clearly dictates otherwise.
Furthermore, one or more computer-readable storage media may be utilized in implementing embodiments consistent with the present disclosure. A computer-readable storage medium refers to any type of physical memory on which information or data readable by a processor may be stored. Thus, a computer-readable storage medium may store instructions for execution by one or more processors, including instructions for causing the processor(s) to perform steps or stages consistent with the embodiments described herein. The term “computer-readable medium” should be understood to include tangible items and exclude carrier waves and transient signals, i.e., be non-transitory. Examples include random access memory (RAM), read-only memory (ROM), volatile memory, nonvolatile memory, hard drives, CD ROMs, DVDs, flash drives, disks, and any other known physical storage media.
It is intended that the disclosure and examples be considered as exemplary only, with a true scope of disclosed embodiments being indicated by the following claims. , C , Claims:We Claim:

A processor-implemented method (200) for a two-party threshold digital signature generation in a distributed fashion by a first party and a second party, comprising:
sharing, via one or more hardware processors, a plurality of input parameters and a message (m) with the first party and the second party, wherein the plurality of input parameters comprises an elliptic curve (E) defined by an elliptic curve equation over a finite field, a base point (P) in the elliptic curve, a pre-defined bit fixed prime number (q) indicating an order of points in the elliptic curve , a field (Z_p), a plurality of random numbers wherein each random number is an integer belonging to Z_p, and a set of hash functions ( H_1 and H_2) (202);
generating a public key (PK), via the one or more hardware processors, at the first party and the second party based on a public key generation technique, wherein the public key is generated at the first party and the second party using the plurality of input parameters, a first random number (a_1) and a second random number (a_2) from the plurality of random numbers (204);
generating a session key (R), via the one or more hardware processors, at the first party and the second party based on a session key generation technique, wherein the session key is generated at the first party and the second party using the plurality of input parameters, a third random number (k_1) and a fourth random number (k_2) from the plurality of random number (206); and
generating a threshold digital signature (s) at the first party and the second party (208), via the one or more hardware processors, based on a threshold digital signature generation technique, wherein the threshold digital signature generation technique comprises:
generating a first set of signature components at the first party and the second party, wherein the first set of signature components comprises a hash element (r) and a message digest (h), and the first set of signature components is generated using the plurality of input parameters, the message, the public key, and the session key (208A);
generating a second set of signature components at the first party, wherein the second set of signature components comprises a function value (S_A) and a blinding element (k^'), generated using the plurality of input parameters and the first set of signature components (208B);
sharing the second set of signature components with the second party for a consistency verification (208C); and
generating the threshold digital signature based on the consistency verification using the plurality of input parameters, the first set of signature components, the second set of signature components and the first partial public key (208D).

The method of claim 1, wherein the public key generation technique (300) comprises:
computing a first partial public key (?PPK?_A) at the first party, wherein the first partial public key is computed as an exponentiation of the base point in the elliptic curve (P) with the first random number (a_1) (302);
computing a zero-knowledge proof (p_1) of the first partial public key at the first party (304);
computing a second partial public key (?PPK?_B) at the second party, wherein the second partial public key is computed as an as exponentiation of the base point in the elliptic curve (P) with the second random number (a_2) (306);
computing a zero-knowledge proof (p_2) of the second partial public key by the second party (308);
exchanging the first partial public key and the zero-knowledge proof of the first partial public key (p_1) with the second party and the second partial public key and the zero-knowledge proof of the second partial public key (p_2) with the first party for a zero-knowledge proof verification (310); and
generating the public key (PK) at the first party and the second party, wherein the public key is generated as a point addition of the first partial public key and the second partial public key (312).

The method of claim 1, wherein the session key generation technique (400) comprises:
computing a first local session key (T_1) at the first party, wherein the first local session key is computed as an exponentiation of the base point in the elliptic curve (P) with a third random number (k_1) (402);
computing a zero-knowledge proof of the first local session key (p_3) by the first party (404);
computing a second local session key (T_2) at the second party, wherein the second local session key is computed as an exponentiation of the base point in the elliptic curve (P) with a fourth random number (k_2) (406);
computing a zero-knowledge proof of the second local session key (p_4) at the second party (408);
exchanging the first local session key and the zero-knowledge proof of the first local session key with the second party and exchanging the second local session key and the zero-knowledge proof of the second local session key with the first party for a zero-knowledge proof verification (410); and
comparing (412) a first full local session key and the zero-knowledge proof of the first local session key at the second party with a second full local session key and the zero-knowledge proof of the second local session key at the first party, wherein,
a session key (R) is generated at the first party and the second party if the first full local session key and the second full local session key are equal, wherein the session key (R) is generated at the first party as a multiplication of the first local session key and the third random number and the session key (R) is generated at the second party as a multiplication of the second local session key and the fourth random number (412A), or
the process of generation of the session key is aborted if the first full local session key and the second full local session key are unequal (412B).

The method of claim 1, wherein generation of the threshold digital signature is aborted if at least one of the zero-knowledge proof verification and the consistency verification is failed.

The method of claim 1, wherein the hash element (r) is a hash of the public key and the session key, and the message digest (h) is a hash of the message and the generation the set of signature components at the first party and the second party is expressed as:
r= H_1 (PK,R),
h= H_2 (m)
wherein,
H_1 and H_2 are the set of hash functions,
R is the session key
PK is the public key,
h is the message digest, and
m is the message.

The method of claim 1, wherein the generation of the second set of signature components is expressed as:
S_A=hr^' k_1+ra_1 mod q
k^'= k_1.r^' mod q,
wherein,
S_A is the function value,
r^' is a fifth random number,
k^' is the blinding element,
h is the message digest,
r is the hash element,
k_1 is the third random number,
a_1is the first random number, and
q is the pre-defined bit fixed prime number.

The method of claim 1, wherein the consistency verification is performed based on the plurality of input parameters, the first set of signature components and the second set of signature components and is expressed as:
S_A.P=k^'.h.P+r.?PPK?_A
wherein,
S_A is the function value,
P is the base point,
k^' is the blinding element,
h is the message digest,
r is the hash element, and
?PPK?_A is the first partial public key.

The method of claim 1, wherein the generation of the threshold digital signature (s) is expressed as:
s=(s,r,k^' P,T_2)
where,
s= k_2^(-1) (S_A+r.a_2 )mod q
wherein,
k_2 is the fourth random number,
r is the hash element
k^' is the blinding element,
P is the base point,
T_2 is the second local session key,
S_A is the function value,
a_2 is the second random number, and
q is the pre-defined bit fixed prime number.

The method of claim 1, wherein the generation of the threshold digital signature (s) is verified based on a threshold digital signature verification technique, wherein the threshold digital signature verification technique (500) comprises:
parsing the threshold digital signature into a pre-defined set of components based on a pre-defined size associated with the pre-defined set of components (502);
computing a modular inverse of the first component from the pre-defined set of components of the parsed threshold digital signature (504);
computing a pair of verification component based on the parsed threshold digital signature, the public key and the message digest (506); and
verifying the validity of the threshold digital signature using the pair of verification component (508).

A system (100), comprising:
a memory (102) storing instructions;
one or more communication interfaces (106); and
one or more hardware processors (104) coupled to the memory (102) via the one or more communication interfaces (106), wherein the one or more hardware processors (104) are configured by the instructions to:
share, via one or more hardware processors, a plurality of input parameters and a message (m) with the first party and the second party, wherein the plurality of input parameters comprises an elliptic curve (E) defined by an elliptic curve equation over a finite field, a base point (P) in the elliptic curve, a pre-defined bit fixed prime number (q) indicating an order of points in the elliptic curve , a field (Z_p), a plurality of random numbers wherein each random number is an integer belonging to Z_p, and a set of hash functions ( H_1 and H_2);
generate a public key (PK), via the one or more hardware processors, at the first party and the second party based on a public key generation technique, wherein the public key is generated at the first party and the second party using the plurality of input parameters, a first random number (a_1) and a second random number (a_2) from the plurality of random numbers ;
generate a session key (R), via the one or more hardware processors, at the first party and the second party based on a session key generation technique, wherein the session key is generated at the first party and the second party using the plurality of input parameters, a third random number (k_1) and a fourth random number (k_2) from the plurality of random number; and
generate a threshold digital signature (s) at the first party and the second party, via the one or more hardware processors, based on a threshold digital signature generation technique, wherein the threshold digital signature generation technique comprises:
generating a first set of signature components at the first party and the second party, wherein the first set of signature components comprises a hash element (r) and a message digest (h), and the first set of signature components is generated using the plurality of input parameters, the message, the public key, and the session key;
generating a second set of signature components at the first party, wherein the second set of signature components comprises a function value (S_A) and a blinding element (k^'), generated using the plurality of input parameters and the first set of signature components;
sharing the second set of signature components with the second party for a consistency verification; and
generating the threshold digital signature based on the consistency verification using the plurality of input parameters, the first set of signature components, the second set of signature components and the first partial public key.

The system of claim 10, wherein the one or more hardware processors are configured by the instructions to perform the public key generation technique wherein:
compute a first partial public key (?PPK?_A) at the first party, wherein the first partial public key is computed as an exponentiation of the base point in the elliptic curve (P) with the first random number (a_1);
compute a zero-knowledge proof of the first partial public key (p_1) at the first party;
compute a second partial public key (?PPK?_B) at the second party, wherein the second partial public key is computed as an as exponentiation of the base point in the elliptic curve (P) with the second random number (a_2);
compute a zero-knowledge proof of the second partial public key (p_2) by the second party;
exchange the first partial public key and the zero-knowledge proof of the first partial public key (p_1) with the second party and the second partial public key and the zero-knowledge proof of the second partial public key (p_2) with the first party for a zero-knowledge proof verification; and
generate the public key (PK) at the first party and the second party, wherein the public key is generated as a point addition of the first partial public key and the second partial public key.

The system of claim 10, wherein the one or more hardware processors are configured by the instructions to perform session key generation technique wherein:
compute computing a first local session key (T_1) at the first party, wherein the first local session key is computed as an exponentiation of the base point in the elliptic curve (P) with a third random number (k_1);
compute a zero-knowledge proof of the first local session key (p_3) by the first party;
compute a second local session key (T_2) at the second party, wherein the second local session key is computed as an exponentiation of the base point in the elliptic curve (P) with a fourth random number (k_2);
compute a zero-knowledge proof of the second local session key (p_4) at the second party;
exchange the first local session key and the p_3 with the second party and exchanging the second local session key and the p_4 with the first party for a zero-knowledge proof verification; and
compare a first full local session key and the zero-knowledge proof of the first local session key (p_3) at the second party with a second full local session key and the zero-knowledge proof of the second local session key (p_4) at the first party, wherein,
a session key (R) is generated at the first party and the second party if the first full local session key and the second full local session key are equal, wherein the session key (R) is generated at the first party as a multiplication of the first local session key and the third random number and the session key (R) is generated at the second party as a multiplication of the second local session key and the fourth random number, or
the process of generation of the session key is aborted if the first full local session key and the second full local session key are unequal.

The system of claim 10, wherein the one or more hardware processors are configured by the instructions to perform the generation the set of signature components at the first party and the second party (r,h), to perform the generation of the second set of signature components (S_A,k^') and to perform the generation of the threshold digital signature (s), expressed as:
r= H_1 (PK,R),
h= H_2 (m),
S_A=hr^' k_1+ra_1 mod q ,
k^'= k_1.r^' mod q,
s=(s,r,k^' P,T_2),
where,
s= k_2^(-1) (S_A+r.a_2 )mod q.

The system of claim 10, wherein the one or more hardware processors are configured by the instructions to perform the consistency verification based on the plurality of input parameters, the first set of signature components and the second set of signature components and is expressed as:
S_A.P=k^'.h.P+r.?PPK?_A.

The system of claim 10, wherein the one or more hardware processors are configured by the instructions to perform the verification of the generated of the threshold digital signature (s) based on a threshold digital signature verification technique, wherein the threshold digital signature verification technique, comprises:
parsing the threshold digital signature into a pre-defined set of components based on a pre-defined size associated with the pre-defined set of components;
computing a modular inverse of the first component from the pre-defined set of components of the parsed threshold digital signature;
computing a pair of verification component based on the parsed threshold digital signature, the public key and the message digest; and
verifying the validity of the threshold digital signature using the pair of verification component.

Dated this 19th day of May 2022
Tata Consultancy Services Limited
By their Agent & Attorney

(Adheesh Nargolkar)
of Khaitan & Co
Reg No IN-PA-1086