PAIRING-BASED DIGITAL SIGNATURE WITH DESIGNATED VERIFIER

SCHEME BASED PROVIDING NON REPUDIATION

Technical Field

The present invention relates to digital signature verification.

Background

In a classic digital signature scheme, the whole wide world is capable of verifying a signature.

In a designated verifier scheme (DVS), only the designated verifier has this capability.

In a classic DVS scheme the signer themselves designates the entity that will have the capability of verifying their signature.

In a pure identity-based signature scheme, a Trusted Authority is introduced, and is responsible for issuing secret signing keys to all participants.

Summary of the Invention

In accordance with a first aspect of the invention, there is provided a method of verifying a digital signature. The method comprises: generating, by a trusted authority, a first secret key and communicating the first secret key to a verifier; generating, by the trusted authority, a second secret key and communicating the second secret key to a signer; generating, by the signer, a digital signature with the second secret key and communicating the digital signature to the verifier, and verifying, by the verifier, the digital signature using the first secret key. The first secret key is a point sQ on an elliptic curve of a group G2, the second secret key is a point sA on the elliptic curve of a group G1, and G1 and G2 are groups of a bilinear map e: G1 x G2 -> GT associated with the elliptic curve, s is a random secret generated by the trusted authority, Q is a fixed public generator generated by the trusted authority, and A is a public key of the signer.

Optionally, the method further comprises generating, by the signer, the digital signature as: (IDa,xA, -(x + h(m\U))sA), where A is calculated as H(IDa), where HQ is a first predefined hashing function, where h() is a second predefined hashing function, where x is a random secret generated by the signer, where U is xA, where IDa is an identifier associated with the signer and where m is a message.

Optionally, the method further comprises computing, by the verifier, g, where g = e(V, Q).e(U+h(m\U)A,sQ), and verifying, by the verifier, the digital signature from the signer if g=1 , where V is -(x + h(m\U))sA.

Optionally, the method further comprises generating, by the signer, a non-ID based public key Pa using a randomly generated secret z; generating, by the signer, a composite identity /Da|Pa comprising the non-identity based public key Pa and an identifier, IDa, associated with the signer and communicating the composite identity to the trusted authority and the verifier; modifying, by the signer, the second secret key from sA to zsA\ and generating, by the trusted authority, the public key A using the composite identity. Optionally, the method further comprises generating, by the trusted authority, the public key A using the composite identity /Da|Pa by calculating A = H(IDa\Pa), where H() is a first predefined hashing function.

Optionally, the method further comprises generating, by the signer, the digital signature as: IDa, Pa, xA, - (x+h(m\U)zsA), where h() is a second predefined hashing function and x is a random secret generated by the signer and U is xA.

Optionally, the method further comprises computing, by the verifier, the public key A using the composite identity /Da|Pa generated by the signer; computing, by the verifier, g, where g = e(V,Pa).e(U+h(m\U)A, sQ, where U is xA and V is -(x + h(m\U))zsA, and verifying, by the verifier, the digital signature from the signer if g=1, where m is a message.

Optionally, the trusted authority comprises a plurality of distributed trusted authorities, and the first secret key comprises a plurality of first secret keys, each of the first secret keys generated, and communicated to the verifier, by one of the distributed trusted authorities and the second secret key comprises a plurality of second secret keys, each of the second secret keys generated, and communicated to the signer, by one of the distributed trusted authorities, and the method further comprises: constructing, by the verifier, the first secret key by combining the plurality of first secret keys, and constructing, by the signer, the second secret key by combining the plurality of second secret keys.

Optionally, the method further comprises generating, by the signer, a token by combining the second secret key received from the trusted authority with at least one authentication factor, and generating, by the signer, the digital signature using a reconstructed version of the second secret key, said reconstructed version of the second secret key formed by combining the token with a subsequently received version of the at least one authentication factor. Optionally, the token is formed by subtracting from the second secret key sA a value aA, where a is value corresponding to an authentication factor and aA is a point aA of the group G1.

Optionally, the trusted authority is implemented on one or more first computing devices; the signer is implemented on a second computing device, and the verifier is implemented on a third computing device, said first, second and third computing devices connected via data communication means.

In accordance with a second aspect of the invention, there is provided a system for verifying a digital signature. The system comprises one or more first computing devices on which is running a computer program providing a trusted authority function, a second computing device on which is running a computer program providing a digital signature generation function and a third computing device on which is running a computer program providing a digital signature verification function. The trusted authority function is configured to control the first computing device to generate a first secret key and communicate the first secret key to the third computing device and to generate a second secret key and communicate the second secret key to the second computing device, and the digital signature generation function is configured to control the second computing device to generate a digital signature using the second secret key and communicate the digital signature to the third computing device, and the digital signature generation function is configured to control the third computing device to verify the digital signature using the first key, wherein the first secret key is a point sQ on an elliptic curve of a group G2, the second secret key is a point sA on the elliptic curve of a group G1, and G1 and G2 are groups of a bilinear map e: G1 x G2 -> GT associated with the elliptic curve, s is a random secret generated by the trusted authority function, Q is a fixed public generator generated by the trusted authority, and A is a public key associated with the second computing device on which is running the digital signature generation function.

In accordance with a third aspect of the invention, there is provided a trusted authority computing system for use in a system for verifying a digital signature according to the second aspect of the invention and on which is implemented a trusted authority function, wherein the trusted authority function is configured to control the computing device to generate a first secret key and a second secret key, the trusted authority function further configured to communicate the second secret key to a second computing device on which is running a digital signature generation function for generating a digital signature with second secret key and to communicate the first secret key to a third computing device on which is running a digital signature verification function for verifying the digital signature generated by the second computing device with the first secret key, wherein the first secret key is a point sQ on an elliptic curve of a group G2, the second secret key is a point sA on the elliptic curve of a group G1, and G1 and G2 are groups of a bilinear map e: G1 x G2 -> GT associated with the elliptic curve, s is a random secret generated by the trusted authority function, Q is a fixed public generator generated by the trusted authority function, and A is a public key of the second computing device on which is running a digital signature generation function.

Optionally, the system comprises a computing device on which is running the trusted authority function.

Optionally, the trusted authority function comprises a plurality of distributed trusted authorities, the plurality of distributed trusted authorities implemented across a plurality of computing devices, wherein the first secret key comprises a plurality of first secret keys, each of the first secret keys generated, and communicated to the third computing device, by one of the distributed trusted authorities and the second secret key comprises a plurality of second secret keys, each of the second secret keys generated, and communicated to the second computing device, by one of the distributed trusted authorities.

In accordance with a fourth aspect of the invention, there is provided computing device on which is running a computer program providing a digital signature generation function for use in a system for verifying a digital signature according to the second aspect of the invention, wherein the digital signature generation function is configured to control the computing device to generate a digital signature using a secret key received from a first further computing device on which is running a computer program providing a trusted authority function, and to communicate the digital signature to a second further computing device on which is running a computer program providing a digital signature verification function which is configured to control the second further computing device to verify the digital signature using a further secret key, wherein the secret key is a point sA on the elliptic curve of a group Gi, and the further secret key is a point sQ on an elliptic curve of a group G2, and G1 and G2 are groups of a bilinear map e: G1 x G2 -> GT associated with the elliptic curve, s is a random secret generated by the trusted authority, Q is a fixed public generator generated by the trusted authority function, and A is a public key associated with the computing device.

In accordance with a fifth aspect of the invention, there is provided a computing device on which is running a computer program providing a digital signature verification function for use in a system for verifying a digital signature according to the second aspect of the invention, wherein the digital signature verification function is configured to control the computing device to verify, using a first secret key received from a first further computing device on which is running a computer program providing a trusted authority function, a digital signature received from a second further computing device on which is running a computer program providing a digital signature generation function, said digital signature having been generated using a second secret key, wherein the second secret key is a point sA on the elliptic curve of a group G1, and the first secret key is a point sQ on an elliptic curve of a group G2, and G1 and G2 are groups of a bilinear map e: G1 x G2 -> GT associated with the elliptic curve, s is a random secret generated by the trusted authority function, Q is a fixed public generator generated by the trusted authority function, and A is a public key associated with the second further computing device.

In schemes in accordance with embodiments of the invention, a trusted authority (TA), rather than the signer of a digital signature, designates the verifier of the signature. To this end the trusted authority issues the designated verifier with its own secret. In certain embodiments, functionality is distributed across several distributed trusted authorities (D-TAs) each of which issue their own secret to the designated verifier, which is then reconstructed as a single secret at the verifier. In certain embodiments, a non-repudiation function is provided.

In certain embodiments, multi-factor authentication capability is provided.

Various further features and aspects of the invention are defined in the claims.

Brief Description of the Drawings

Embodiments of the present invention will now be described by way of example only with reference to the accompanying drawings where like parts are provided with corresponding reference numerals and in which:

Figure 1 provides a schematic diagram of a system arranged in accordance with certain embodiments of the invention;

Figure 2 provides a schematic diagram of a process for generating and verifying digital signatures in accordance with certain embodiments of the invention;

Figure 3 provides a schematic diagram of a process for generating and verifying digital signatures in accordance with further embodiments of the invention, and Figure 4 provides a schematic diagram of a further system arranged in accordance with certain embodiments of the invention.

Detailed Description

The following describes the principles of the invention and considerations relating to particular embodiments of the invention.

Consider a scenario where a Bank wishes to have the capability of verifying customer signatures on important transactions. It is not important or indeed desired that the general public can verify these signatures - it is sufficient that the Bank is convinced of their validity, and that disputes can be legally resolved if necessary.

In accordance with certain embodiments of the invention, a solution is provided in which a Distributed Trusted Authority (D-TA) infrastructure is required which confirms identities and issues shares of the secret keys.

The Bank itself would naturally control one component of this infrastructure, but one or more external identity provisioners should be involved as well.

In one embodiment a simple system is provided. In further embodiments, a non- repudiation feature (not normally possible with Identity-Based signature) is added. In a further embodiment, a signature method is provided that can be made“multi-factor”, so for example a customer can sign using a software token and a memorised PIN number. This is a better solution than currently deployed alternatives, which typically require the bank to issue an expensive hardware device to each customer.

Basic Scheme

The basic scheme is based on an Identity-Based signature suggested by Cha and Cheon [2], shifted from a type-1 pairing to a type-3 pairing context [3]

- Setup. A Trusted Authority chooses a type-3 pairing friendly elliptic curve and publishes its parameters. The associated bilinear map is e ; G G2 GT,

where all groups are of prime order q. The TA generates a random secret s for use with a particular designated verifier and a fixed public generator Q e G2.

A hash function H(.) is provided which hashes and maps identity strings to a point in G1.

A second hash function h(.) hashes messages of arbitrary length into a short digest of size less than q.

- Key Extract - verifier. The secret key issued to the designated verifier by the TA is the point sQ EG2.

- Key Extract - signer. For an identity IDa, the associated ID-based public key is

A = H(IDa).

The secret key issued by the TA to IDa is the point sAeG1.

- Sign. To sign a message m, IDa generates a random x, calculates A = H(IDa) and the signature as

(IDa.U. V) = (IDa,xA,-(x+h(m)\U)sA))

- Verify. To verify the signature on m calculate

A = H(IDa) and g = e(V, Q).e(U+h(m)\U)A,sQ), and if g = 1 accept the signature, otherwise reject it.

This simple system has a number of short-comings. Clearly the TA is in a position to create a signature on any message.

In some embodiments, the TA functionality can be distributed to mitigate the risk that the a rogue or compromised TA can create a signature on any message. To this end a D-TA is established.

For example a pair of D-TAs can generate their own independent secrets si and S2, and separately issue siA and S2A to a client IDa, and siQ and S2Q to the designated verifier. Both clients and verifier simply add these components together to form their full secrets.

In some embodiments, ideas from Certificateless Cryptography [1 ] can be used to mitigate the risk that a conspiracy of D-TAs could in theory still forge signatures.

A scheme with non-repudiation

The setup and Verifier key extraction is as above.

- Key Extract - signer. The client IDa generates a random z, and calculates a non-ID- based public key

Pa = z ^~1 Q, and presents the composite identity /Da|Pa to the trusted authority, which constructs the ID-based public key as

A = H(IDa\Pa), and returns the secret key

SA E G1.

The client then modifies its secret key to be zsA, and deletes z and sA.

- Sign. To sign a message m, IDa generates a random x, calculates A = H(IDa\Pa) and the signature as

(IDa, Pa, U, V ) = (IDa,Pa,xA,-(x + h(m\U))zsA)

- Verify. To verify the signature on m, independently calculate A = H(IDa\Pa).

Next calculate g = e(V,Pa).e(U + h(m\U)A,sQ).

If g = 1 accept the signature, otherwise reject it.

Certificateless cryptography [1 ] does not increase the number of secrets to be protected compared with pure Identity-Based cryptography, but it does introduce a new individualised public key Pa. It is assumed that the TA (or equivalently at least one component of a D-TA) will not get involved in an attack involving replacement of these public keys. The authors of [1 ] argue that this is essentially the same level of trust we have in a PKI Certificate Authority (CA) not to issue false certificates. Hence their schemes are “certificateless”, as public keys gain no extra security from being embedded into a certificate. For digital signatures to have the non-repudiation property, an assumption of this kind is regarded as acceptable, and does not invalidate the legality of PKI signatures. Therefore it is reasonable to assume that at least one of independent D- TA has the same level of integrity as a CA.

A multi-factor variation

Multi-factor methods of signature are often required by organisations like Banks, and normally require that customers be provisioned with an expensive hardware token. A cheaper software-only solution can be provided in certain embodiments.

A private key used for digital signature can be split into two parts, say a PIN number and a software token. Both components would need to be recombined in order to form a signature. In a normal digital signature scheme clearly this will not work - an attacker who captures the software token simply has to try every possible PIN number until the private key formed by combining token and PIN matches the user’s public verification key.

But in an ID-based designated verifier scheme of the type described above, the single verification key is in fact now a secret known only to the designated verifier. So a software-only 2-factor signature becomes a possibility.

If an attacker has access to the token and a valid signature this is not sufficient to find the PIN via an off-line attack. Implementing a basic scheme as described above in which a PIN a is used and the secret s is divided into the token sA-aA and the PIN derived component a A.

An attacker who has access to sA-aA and signature components xA and xsA , can try adding guesses of aA to the token, hoping to detect the triplet sA, xA and xsA. But this is the Decisional Diffie-Hellman problem in G1. It is the XDH assumption that this is still a hard problem, despite the computability of a pairing.

The skilled person will understand that this concept can be extended to the scheme that supports nonrepudiation. The extension of the idea from 2-factor to multi-factor is also straightforward.

In theory a conspiracy of D-TAs can re-create sQ, and therefore can verify signatures. Also, such a conspiracy that gains access to client tokens, can calculate the associated PINs. However it considered that these do not constitute realistic attacks.

While a conspiracy of D-TAs can forge individual signatures, the security risk is equivalent to the capabilities of the single corrupt Certificate Authority in the equivalent PKI signature context. In that situation the existence of a pair of digital signatures on the same message associated with the same identity, but with different public keys, suffices to expose such a conspiracy.

Revocation can be supported either as described in [1 ], or using the concept of“time permits”, which are publicly issued by the D-TAs on, for example, a daily basis which will be understood by the skilled person.

Using the principles described above, in accordance with certain embodiments of the invention, a technique is provided for undertaking a verification process in which a digital signature provided by a computing device or system (a“signer”) is verified. The verification is performed by a further computing device or system (a“verifier”). Before the verification process is performed, another computing device or system (a“trusted authority”) establishes a secret key for the verifier and a secret key for the signer which enable the verification process (and subsequent verification processes) to be performed. Figure 1 provides a schematic diagram of a system arranged in accordance with certain embodiments of the invention.

A first computing device 101 (a trusted authority), for example an application server, has running thereon software providing a trusted authority function. The first computing device 101 is connected, via a suitable data connection, to a data network 102 (for example the internet).

A second computing device 103 (a signer), for example a user device such as a smartphone, personal computer, tablet and so on, is also connected via a suitable data connection to the network 102. The second computing device 103 has running thereon software providing a digital signature generation function.

A third computing device 104 (a verifier), again, for example an application server, has running thereon on software providing a digital signature verification function. The third computing device 104 is also connected, via a suitable data connection, to the network 102.

The network enables data to be communicated between the first, second and third computing devices 101 , 103, 104 using data communication techniques well known in the art.

In accordance with a first configuration, the trusted authority function running on the first computing device 101 establishes a type-3 pairing friendly elliptic curve and publishes its parameters, i.e. communicates the parameters to at least the second computing device 103 on which is running the digital signature generation function and the third computing device 104 on which is running the digital signature verification function.

A bilinear map associated with the elliptic curve is e : G1 x G2 GT, where all groups are of prime order q.

The trusted authority function running on the first computing device 101 generates a random secret s and a fixed public generator

Q e G2.

The trusted authority function running on the first computing device 101 communicates to the second computing device 103 and the third computing device 104 a first hash function H(.) which hashes and maps identity strings to a point in G1 and a second hash function h(.) which hashes messages of arbitrary length into a short digest of size less than q.

The trusted authority function running on the first computing device 101 generates a first secret key and communicates this to the third computing device 104 and generates a second secret key and communicates this to the second computing device 103.

The first secret key is the elliptic curve point sQ E G2.

The second secret key is the elliptic curve point sA E G1.

A is the ID based public key of the signer. A is calculated as A = H(IDa), where IDa is an identity string associated with the signer. To sign a message (generate a digital signature) a message m is signed. The digital signature generation function running on the second computing device 103 undertakes a signature generation process in which a secret random value x is generated; A = H(IDa) is calculated and then the signature is calculated as

(IDa, U, V ) = (IDa,xA, -(x + h(m\U))sA), where

U is xA.

The signature, thus generated, is communicated from the signature generation function running on the second computing device 103 to the third computing device 104 on which is running the digital signature verification function.

On receipt of the signature, the digital signature verification function running on the third computing device 104 undertakes a digital signature verification process in which the signature applied to message m is verified, that is, it is confirmed that it was the second computing device 103 that generated the digital signature.

During the digital signature verification process, the digital signature verification function running on the third computing device 104 calculates

A = H(IDa) then g = e(V, Q).e(U+h(m\U)A,sQ), where

V is -(x + h(m\U))sA. If g = 1 , the digital signature verification function running on the third computing device 104 verifies the signature. Otherwise the digital signature verification function running on the third computing device 104 rejects the signature, that is, does not verify the signature.

Figure 2 provides a diagram depicting this digital signature generation and verification process.

In certain embodiments, the digital signature generation and verification process described above and depicted in Figure 2 can be modified to include a time permit function.

A modified ID based public key of the signer (e.g. the second computing device 103 described with reference to Figure 1 ) is formed by the signer as A = H(IDa) + H2(D| IDa) where H2() is a hash function distinct from, but with the same range as, Fl().

The trusted authority function generates a time permit of the form T = sFI2(D|IDa) which is added to the secret key sA and communicated to the signer.

The signature applied to the message m by the digital signature generation function is the tuple {Da;D;U; V}, where U = xA, and V = -(x + h{m\U)){sA + T). The verifier uses the claimed date from the signature and the identity string IDa to construct the signer’s modified public key.

In a further configuration, the process for generating and verifying digital signatures described above and depicted in Figure 2 is modified to introduce non-repudiation functionality. The non-repudiation functionality is such that the digital signature verification function running on the third computing device 104 can confirm with improved confidence that the digital signature generation function running on the second computing device 103 generated the digital signature, rather, than, for example, the trusted authority function running on the first computing device 101 . The trusted authority function running on the first computing device 101 generates the first secret key and communicates this to the verification running on the third computing device 104 in the same way as described above and as depicted in Figure 2.

However, a modified process is used to generate the second secret key.

The digital signature generation function running on the second computing device 103 generates a random value z and calculates a non-ID-based public key

Pa = z ^~1 Q.

The digital signature generation function running on the second computing device 103 then generates a composite identity IDa|Pa and communicates this to the trusted authority function running on the first computing device 101 and the digital signature verification function running on the third computing device.

The trusted authority function running on the first computing device 101 then generates an ID-based public key for the second computing device 103 as

A = H(IDa\Pa), generates the second secret key as sA e G1 and communicates this to the second computing device 103.

The digital signature generation function running on the second computing device 103 then modifies its secret key to zsA, and deletes previously generated z and sA received from the trusted authority function running on the first computing device 101 .

To generate a digital signature, the digital signature generation function running on the second computing device 103 generates a random value x, calculates

A = H(IDa\Pa) and the signature as

(IDa,Pa, U, V ) = (IDa,Pa,xA, ^~ (x + h(m\U))zsA), where

U is xA.

The signature, thus generated, is communicated from the signature generating function running on the second computing device 103 to the third computing device 104 on which is running the digital signature verification function.

On receipt of the signature, the digital signature verification function running on the third computing device 104 undertakes a digital signature verification process in which the signature applied to message m is verified.

During the digital signature verification process, the digital signature verification function running on the third computing device 104 calculates

A = H(IDa\Pa) then g = e(V,Pa).e(U + h(m\U) A,sQ), where V is ~(x + h(m\U))zsA.

If g = 1, the digital signature verification function running on the third computing device 104 verifies the signature. Otherwise the digital signature verification function running on the third computing device 104 rejects the signature, that is, does not verify the signature.

Figure 3 provides a diagram depicting this modified digital signature generation and verification process.

In certain embodiments, the trusted authority function is distributed across a plurality of distributed trusted authority functions, each distributed trusted authority function running, for example, on a different computing device or system.

In such systems, each distributed trusted authority function generates their own independent secrets and separately issue first secret keys to the computing device on which is running the verifier function and second secret keys to the device on which is running the digital signature generation function.

A simple example of this is depicted in Figure 4 which shows a pair of distributed trusted authority functions, a first distributed trusted authority function running on a first computing device 401 and a second distributed trusted authority function running on a second computing device 402.

The first distributed trusted authority function running on the first computing device 401 generates a first secret si and generates a first secret key component siQ and a second secret key component siA. Via a data network 405, the first distributed trusted authority function running on the first computing device 401 then communicates the first secret key component SiQ to the designated verifier function running on a third computing device 404 and the second secret key component SiA to the digital signature generation function running on a fourth computing device 403. The second distributed trusted authority function running on the second computing device 402 generates a second secret S2 and generates a first secret key component S2Q and a second secret key component S2A. The second distributed trusted authority function running on the second computing device 402 then communicates the second secret key component S2Q to the designated verifier function running on a third computing device 404 and the second secret key component S2A to the digital signature generation function running on a fourth computing device 403.

On receipt of the two first secret key components, siQ and S2Q, the verifier function running on a third computing device 404 adds these key components to generate the composite first secret key sQ.

On receipt of the two second secret key components, siA and S2A, the digital signature generation function running on the fourth computing device 403 adds these key components to generate the composite second secret key sA.

The first composite secret key sQ and the second composite secret key sA thus generated, the verifier function running on a third computing device 404 and the digital signature generation function running on the fourth computing device 403 can undertake the digital signature generation and verification processes as described above.

In certain embodiments, multi-factor authentication can be used. In such embodiments the second secret key sA used by the digital signature generation function is a version of the second secret key constructed by combining a token (e.g. a software token) with one or more previously provided authentication factors.

In such embodiments, one or more authentication factors are initially established by, or provided to, the digital signature generation function. The one or more authentication factors are used in combination with the second secret key sA to form a token. The token is such that the second secret key is reproduced when the token is correctly combined with the authentication factors. The token is stored by the digital signature generation function Subsequently, when the digital signature generation function is performed, the one or more authentication factors are provided to the digital signature generation function, for example by a user. These authentication factors are combined with the token to form a version of the second secret key which is used in the digital signature genertation function.

The digital signature will only be verified by the digital signature verification function if the version of the second secret key is the same as that provided by the trusted authority function. This requires the correct authentication factors to be provided when the digital signature is being generated.

In one such example, using known techniques, an authentication factor such as a PIN (personal identity number) a is established by the digital signature generation function.

On receipt of the second secret key sA, the digital signature generation function generates a software token which comprises the second secret key absent an authentication component, where the authentication component is aA, aA being a point aA of the group Gi. Thus, the software token is

S/A- a A.

To apply the digital signature, a signature generation process of one of the types described above is undertaken, except that the digital signature function requires a PIN a _u to be provided by a user. The digital signature generation function then generates the authentication component a _u A and constructs a version of the second secret key sA by adding the authentication component a _u A to the previously created software token sA- aA. If

S/A- aA + OuA = S/A (i.e. a = cui) then the digital signature will be verified by the digital signature verification function (i.e. g = 1 ). If a is different to a _u (e.g. a user has provided an incorrect PIN), then the digital signature verification function will not verify the signature.

Conventionally, to solve the challenge of secure multi-factor authentication, a hardware vault of some form, like a Trusted Platform Module (TPM) is required on the client side. Typical solutions, such as that proposed by the FIDO alliance (https://fidoalliance.org/) require the protection of a PKI (public key infrastructure)-like signing key on the client device, which is used to sign a random challenge issued by the server every time the client wishes to authenticate. Ideally for an optimal user experience this signing key should be activated from the hardware vault by the entry of a low entropy secret like a PIN number, or a biometric which matches a template stored inside the vault. An attacker who can gain access to the TPM, either by successful hacking, or by way of a manufacturer's back-door, can gain immediate access to the secret, with no need of a PIN or a biometric. As a bonus they might capture the biometric template as well. As is well known, the cryptographic protection of a PKI private key in software requires the use of a very user-unfriendly high-entropy pass-phrase, a process made famous by PGP, which makes implementation of this conventional technique in software on the client side very difficult.

In contrast, advantageously, the technique of multi-factor authentication described above can be implemented entirely in software with the software token stored in an unencrypted on the device on which the digital signature generation function is running and the PIN memorised by a user. This reduces cost because specific hardware is not required and overcomes the requirement to trust a hardware manufacturer.

As will be appreciated, embodiments can be provided in which multiple authentication factors can be used 01,02... a _n. The software token is then generated using multiple authentication components: sA- aiA - aåA - ... a _n A. For the successful verification of the signature, the second secret key sA must be reconstructed with the correct provision of the relevant authentication factors.

Whilst the embodiments described above have been described in terms of a system in which the trusted authority is implemented on one or more application servers running suitable software, the verifier is implemented on an application server running suitable software, and the signer is implemented on a user device running suitable software, it will be understood that digital signature generation and verification techniques in accordance with examples of the invention can be implemented in any suitable system.

For example the computing devices on which the functionality associated with the trusted authority, the verifier and signer are implemented can be provided by any suitable computing devices such as servers, personal computers, “smart devices” (smart phones, smart televisions and so on), “embedded” computing systems and such that are well known in the art.

The computing devices on which the functionality associated each of the trusted authority or distributed trusted authorities, the verifier and signer are implemented can be on a single physical device or can each be implemented across two or more different physical devices using well known distributed computing (e.g. “cloud computing”) techniques.

The means by which the computing devices communicate data with each other can be by any suitable means for communicating data, for example via conventional data packet (e.g. internet protocol) based networks using any suitable data transmission techniques, for example using wired or wireless connections.

The functionality associated with the trusted authority, the verifier and signer is typically provided by software, stored in memory and running on suitably programmed processing devices. In certain examples some or all of the functionality the trusted authority, the verifier and signer may be implemented in hardware (rather than software) using, for example, hardware configurable computing devices employing programmable logic blocks such as FPGAs (field programmable gate arrays) and so on.

All of the features disclosed in this specification (including any accompanying claims, abstract and drawings), and/or all of the steps of any method or process so disclosed, may be combined in any combination, except combinations where at least some of such features and/or steps are mutually exclusive. Each feature disclosed in this specification (including any accompanying claims, abstract and drawings) may be replaced by alternative features serving the same, equivalent or similar purpose, unless expressly stated otherwise. Thus, unless expressly stated otherwise, each feature disclosed is one example only of a generic series of equivalent or similar features. The invention is not restricted to the details of the foregoing embodiment(s). The invention extends to any novel one, or any novel combination, of the features disclosed in this specification (including any accompanying claims, abstract and drawings), or to any novel one, or any novel combination, of the steps of any method or process so disclosed.

With respect to the use of substantially any plural and/or singular terms herein, those having skill in the art can translate from the plural to the singular and/or from the singular to the plural as is appropriate to the context and/or application. The various singular/plural permutations may be expressly set forth herein for sake of clarity.

It will be understood by those within the art that, in general, terms used herein, and especially in the appended claims are generally intended as“open” terms (e.g., the term “including” should be interpreted as “including but not limited to,” the term “having” should be interpreted as“having at least,” the term “includes” should be interpreted as“includes but is not limited to,” etc.). It will be further understood by those within the art that if a specific number of an introduced claim recitation is intended, such an intent will be explicitly recited in the claim, and in the absence of such recitation no such intent is present. For example, as an aid to understanding, the following appended claims may contain usage of the introductory phrases "at least one" and "one or more" to introduce claim recitations. Flowever, the use of such phrases should not be construed to imply that the introduction of a claim recitation by the indefinite articles "a" or "an" limits any particular claim containing such introduced claim recitation to embodiments containing only one such recitation, even when the same claim includes the introductory phrases "one or more" or "at least one" and indefinite articles such as "a" or "an" (e.g.,“a” and/or“an” should be interpreted to mean“at least one” or“one or more”); the same holds true for the use of definite articles used to introduce claim recitations. In addition, even if a specific number of an introduced claim recitation is explicitly recited, those skilled in the art will recognize that such recitation should be interpreted to mean at least the recited number (e.g., the bare recitation of "two recitations," without other modifiers, means at least two recitations, or two or more recitations).

It will be appreciated that various embodiments of the present disclosure have been described herein for purposes of illustration, and that various modifications may be made without departing from the scope of the present disclosure. Accordingly, the various embodiments disclosed herein are not intended to be limiting, with the true scope being indicated by the following claims.

References

[1 ] S. Al-Riyami and K. Paterson. Certificateless public key cryptography. Cryptology ePrint Archive, Report 2003/126, 2003. http://eprint.iacr.org/2003/126.

[2] J. Cha and J. Cheon. An identity-based signature from gap diffie-hellman groups.

In PKC 2003, volume 2567 of Lecture Notes in Computer Science, pages 18-30. Springer-Verlag, 2003.

[3] S. Galbraith, K. Paterson, and N. Smart. Pairings for cryptographers. Discrete Applied Mathematics, 156:3113-3121 , 2008.