AUTHENTICATED ENCRYPTION FOR DIGITAL SIGNATURES WITH MESSAGE RECOVERY

1 . A method of applying a signature to an original message [M] to generate a signed message signed by a signer, the original message [M] consisting of a first portion [N] and a second portion [V], the method comprising:

selecting a first integer value [k] and computing a second value [Q] from the first integer value [k] and from a base point [G] of an elliptic curve such that the second value [Q] is included in a set of points on the elliptic curve;

constructing a derived key [k 1 ] by applying a key derivation function [KDF] to input that comprises the second value [Q];

applying an authenticated encryption function, keyed by the derived key [k 1 ] to the first portion [N] of the message [M] to obtain an encrypted value [c 1 ] and to obtain a message authentication code [mac];

reversibly combining the encrypted value [c 1 ] and the message authentication code [mac] to form a first signature component [c];

computing a second signature component [s] using

(i) the first integer value [k];

(ii) a private key [d A ] of the signer; and

(iii) a second integer value dependent on the first signature component [c] and the second portion [V] of the message [M]; and

reversibly combining the first signature component [c], the second signature component [s] and the second portion [V] of the message [M] to form the signed message,

wherein verification of the signed message and recovery of the first portion [N] of the message [M] from the signed message involves a public key [G A ] of the signer.

2 . The method as claimed in claim 1 , wherein the public key [G A ] of the signer is included in the set of points on the elliptic curve and is computable from the private key [d A ] and the base point [G].

3 . The method as claimed in claim 1 , the method further comprising:

transmitting the signed message to a verifier.

4 . The method as claimed in claim 1 , the method further comprising:

applying a hash function to a reversible combination of the first signature component [c] and the second portion [V] of the message [M] to obtain a hash result; and

calculating the second integer value equivalent to the hash result.

5 . The method as claimed in claim 4 , wherein the reversible combination further comprises an identity of the signer.

6 . A method of verifying a signed message, the signed message having been generated by applying a signature to an original message [M] that consists of a first portion [N] and a second portion [V], the method comprising:

receiving the signed message purported to be signed by a signer, the signed message having been prepared in a reversible manner from a first signature component [c], a second signature component [s], and the second portion [V] of the original message [M];

extracting the first signature component [c], the second signature component [s], and the second portion [V] from the signed message;

extracting a message authentication code [mac′] and an encrypted value [c 1 ′] from the first signature component [c];

receiving a public key [G A ] of the signer;

computing a first value [Q′] using the second signature component [s], a base point [G] of an elliptic curve, the public key [G A ], and an intermediate value dependent on the first signature component [c] and the second portion [V] of the message [M];

constructing a derived key [k 1 ′] by applying a key derivation function [KDF] to input that comprises the first value [Q′];

applying an authenticated decryption function, keyed by the derived key [k 1 ′], to the encrypted value [c 1 ′] and to the message authentication code [mac′] to determine whether the signed message is valid and, where the signed message is valid, to recover the first portion [N] of the original message [M].

7 . The method as claimed in claim 6 , wherein the public key [G A ] of the signer is included in the set of points on the elliptic curve and is computable from a private key [d A ] of the signer and the base point [G].

8 . A signer device able to apply a signature to an original message [M] to generate a signed message, the original message [M] consisting of a first portion [N] and a second portion [V], the signer device comprising:

a processor;

a communication interface coupled to the processor;

a memory coupled to the processor, the memory storing code which, when executed by the processor, is arranged to:

select a first integer value [k] and compute a second value [Q] from the first integer value [k] and from a base point [G] of an elliptic curve such that the second value [Q] is included in a set of points on the elliptic curve;

construct a derived key [k 1 ] by applying a key derivation function [KDF] to input that comprises the second value [Q];

apply an authenticated encryption function, keyed by the derived key [k 1 ] to the first portion [N] of the message [M] to obtain an encrypted value [c 1 ] and to obtain a message authentication code [mac];

reversibly combine the encrypted value [c 1 ] and the message authentication code [mac] to form a first signature component [c];

compute a second signature component [s] using

(i) the first integer value [k];

(ii) a private key [d A ] of the signer device; and

(iii) a second integer value dependent on the first signature component [c] and the second portion [V] of the message [M]; and

reversibly combine the first signature component [c], the second signature component [s] and the second portion [V] of the message [M] to form the signed message,

wherein verification of the signed message and recovery of the first portion [N] of the message [M] from the signed message involves a public key [G A ] of the signer device.

9 . The signed device as claimed in claim 8 , wherein the public key [G A ] of the signer device is included in the set of points on the elliptic curve and is computable from the private key [d A ] and the base point [G].

10 . The signer device as claimed in claim 8 , wherein the code, when executed by the processor, is further arranged to:

transmit the signed message to a verifier device via the communication interface.

11 . The signer device as claimed in claim 8 , wherein the code, when executed by the processor, is further arranged to:

apply a hash function to a reversible combination of the first signature component [c] and the second portion [V] of the message [M] to obtain a hash result; and

calculate the second integer value equivalent to the hash result.

12 . The signer device as claimed in claim 11 , wherein the reversible combination further comprises an identity of the signer device.

13 . A verifier device able to verify a signed message, the signed message having been generated by applying a signature to an original message [M] that consists of a first portion [N] and a second portion [V], the verifier device comprising:

a processor;

a communication interface coupled to the processor;

a memory coupled to the processor, the memory storing code which, when executed by the processor, is arranged to:

receive via the communication interface the signed message which is purported to be signed by a signer device, the signed message having been prepared in a reversible manner from a first signature component [c], a second signature component [s], and the second portion [V] of the original message [M];

extract the first signature component [c], the second signature component [s], and the second portion [V] from the signed message;

extract a message authentication code [mac′] and an encrypted value [c 1 ′] from the first signature component [c];

receive via the communication interface a public key [G A ] of the signer device;

compute a first value [Q′] using the second signature component [s], a base point [G] of an elliptic curve, the public key [G A ], and an intermediate value dependent on the first signature component [c] and the second portion [V] of the message [M];

construct a derived key [k 1 ′] by applying a key derivation function [KDF] to input that comprises the first value [Q′];

apply an authenticated decryption function, keyed by the derived key [k 1 ′] to the encrypted value [c 1 ′] and to the message authentication code [mac′] to determine whether the signed message is valid and, where the signed message is valid, to recover the first portion [N] of the original message [M].

14 . The verifier device as claimed in claim 13 , wherein the public key [G A ] of the signer device is included in the set of points on the elliptic curve and is computable from a private key [d A ] of the signer device and the base point [G].