METHOD AND SYSTEM FOR A VERIFIABLE IDENTITY BASED ENCRYPTION (VIBE) USING CERTIFICATE-LESS AUTHENTICATION ENCRYPTION (CLAE)

Abstract

Solutions of verifying a plurality of public parameters from a Trusted Centre (TC) in an identity-based encryption and signature system prior to encrypting a plaintext message by a sender having a sender identity string. The method may include identification of the Trusted Centre by a TC identity string, the Trusted Centre having a master public encryption key based on the TC identity string; determination if the sender has a sender private key and the public parameters for the Trusted Centre including the master public key of the Trusted Centre and a bilinear map; and verification of the public parameters using the TC identity string prior to encrypting the plaintext message into a ciphertext by comparing values of the bilinear map calculated with variables comprising the sender private key and the master public key. The ciphertext may include an authentication component for authenticating the sender once the ciphertext is received and decrypted by the recipient using the identity string of the sender and the private key of the recipient. Enables a signature scheme from the same parameters and private keys, the signature is forged using the private key of the signer, the message and the public parameters, the verification is done using the public parameters, the identity of the signer, the signature and the message.

Claims

1-21. (canceled)

22. A method of sending an encrypted message, by a sender having a sender identity string, to a recipient over a network using Identity-Based Encryption, the method comprising: identifying a Trusted Centre (TC) by a TC identity string (Id.sub.TC), the Trusted Centre having a master public key of the Trusted Centre (g.sub.Pub) based on the TC identity string (Id.sub.TC); determining if the sender has a sender private key Prv.sub.Sender and a plurality of public parameters (PK) for the Trusted Centre (TC), the public parameters (PK) including the master public key of the Trusted Centre (g.sub.Pub) and a bilinear map (e); verifying the public parameters (PK) of the Trusted Centre (TC) using the TC identity string (Id.sub.TC) prior to encrypting a plaintext message (M); identifying the recipient by a recipient identity string (Id.sub.Recipient); hashing the identity string of the recipient (Id.sub.Recipient) using cryptographic hash functions (H.sub.1,H.sub.2,H.sub.3,H.sub.T) lying in the public parameters (PK), encrypting the plaintext message (M) as ciphertext (C) using the public parameters (PK), a random symmetric key (Σ) and the hash of the identity string of the recipient (Id.sub.Recipient), and transmitting the ciphertext (C) to the recipient over the network, wherein a plaintext or a ciphertext is signed for any user attesting the origin of the message using the public parameters (PK) of the Identity-Based Encryption, which can be verified by any user.

23. The method of claim 22, wherein verifying the public parameters (PK) comprises comparing values of the bilinear map (e) calculated with variables comprising the sender private key (Prv.sub.Sender) and the master public key of the Trusted Centre (g.sub.Pub).

24. The method of claim 22, wherein the public parameters (PK) are verified if: e(g.sub.Pub,Prv.sub.(Sender,2))=e(H.sub.1(Id.sub.TC),H.sub.2(Id.sub.Sender)).

25. The method of claim 22, wherein the sender private key Prv.sub.Sender and master public key of the Trusted Centre (g.sub.Pub) are provided by the Trusted Centre (TC).

26. The method of claim 22, wherein the Trusted Centre (TC) is separated in a plurality of Trusted Centers avoiding any key escrow.

27. The method of claim 22, wherein the Trusted Centre (TC) is separated in two Trusted Centre (TC.sub.1) and (TC.sub.(−1)) with master secret key (s.sub.1) and (s.sub.(−1)) and the private keys (Prv.sub.Id) are computed through a protocol between the Trusted Centre (TC.sub.1,TC.sub.(−1)) and the user with identity (Id) as followed: at each Trusted Centre (TC.sub.i): computing A.sub.i=H.sub.1(Id.sub.TC).sup.s.sup.i, B.sub.i=H.sub.2(Id.sub.TC).sup.s.sup.i.sup.−1; transmitting privately A.sub.i, B.sub.i to TC.sub.−i; publishing A.sub.i; receiving A.sub.−i, B.sub.−i; verifying if e(A.sub.−i, B.sub.−i)=e(H.sub.1(Id.sub.TC), H.sub.2(Id.sub.TC)) and A.sub.−i≠H.sub.1(Id.sub.TC); computing the master public key of (TC) as g.sub.Pub=A.sub.−i.sup.s.sup.i; and new request of private key, at a Trusted Centre (TC.sub.i): if the request from the requestor contains an identifier (Id) identifying the requestor, verifying that this identifier has not been requested, generating a private key (Prv.sub.Id) based on the identifier (Id) and the secret master key (s.sub.i) and transmitting securely the private key (Prv.sub.Id) to the requestor over the network system; whereby all next transmissions preferably does not need to be secured; and at requestor with identity string (Id): receiving the private key (Prv.sub.Id,1, Prv.sub.Id,2); picking a random number (a) in Z; computing (HPK.sub.1, HPK.sub.2)=(Prv.sub.Id,1.sup.a.sup.−1, Prv.sub.Id,2.sup.a.sup.−1) and T=H.sub.2(Id).sup.a.sup.−1; transmitting (Id, HPK.sub.1, HPK.sub.2, T) to the second Trusted Centre (TC.sub.−i); and at the second Trusted Centre (TC.sub.−i): identifying the requestor with the identity string (Id); verifying that this identifier has not been requested; verifying that e(H.sub.1(Id), HPK.sub.2)=e(HPK.sub.1, H.sub.2(Id)) and e(A.sub.i, HPK.sub.2)=e(H.sub.1(Id.sub.TC), T); computing (HK.sub.1, HK.sub.2)=(HPK.sub.1.sup.s.sup.−1.sup.−1, HPK.sub.2.sup.s.sup.−1.sup.−1); transmitting (HK.sub.1, HK.sub.2) to the requestor over the network; and at the requestor: receiving (HK.sub.1, HK.sub.2); computing Prv.sub.Id=(HK.sub.1.sup.α, HK.sub.2.sup.α).

28. The method of claim 22, wherein the public parameters (PK) further include a description of the groups (G.sub.1,G.sub.2,G.sub.T), a description of the cryptographic hash functions (H.sub.1,H.sub.2,H.sub.3,H.sub.T), a symmetric key encryption function (E), and a description of the bilinear map (also called pairing) (e) which takes as input one element from (G.sub.1) and one element of (G.sub.2) and output an element from (G.sub.T) and that verifies the properties of a non-degenerated bilinear map.

29. The method of claim 22, wherein the ciphertext (C) includes an authentication component (Y) for authenticating the sender once the ciphertext (C) is received by the recipient.

30. The method of claim 29, wherein the authentication component (Y) is based on the sender private key (Prv.sub.Sender) and the identity string of the recipient (Id.sub.Recipient), and wherein preferably the recipient is operable to verify the sender using the public parameters (PK), the sender identity string (Id.sub.Sender) and a recipient private key (Prv.sub.Recipient) obtained from the Trusted Centre (TC).

31. The method of claim 22, wherein the signature σ is computed using the sender private key (Prv.sub.Sender), the identity of the sender (Id.sub.Sender) and wherein preferably the verifier is operable to verify the signature using the public parameters (PK), the sender identity string (Id.sub.Sender) and the Trusted Centre identity (Id.sub.TC).

32. The method of claim 22, wherein the sender can specify an expiry date for the master public key of the Trusted Centre (g.sub.Pub), whereby after the expiry date, the recipient is forced to authenticate with the Trusted Centre (TC) to obtain a new recipient private key (Prv.sub.Recipient).

33. The method of claim 22, wherein the sender can specify a descriptive string to append to the TC identity string (Id.sub.TC), whereby the descriptive string is used by the Trusted Centre (TC) to require additional levels of authentication from the recipient in order for the Trusted Centre (TC) to provide a recipient private key (Prv.sub.Recipient) to the recipient.

34. The method of claim 33, wherein the descriptive string is selected from the group consisting of: a revocation number, a role of the recipient, an age of the recipient, a location of the recipient and/or an expiry date.

35. The method of claim 22, wherein for encryption, the plaintext message (M) is a conventional encryption key for encryption.

36. A method for using verifiable identity-based encryption (VIBE) in a network system between a sender having a sender identity string (Id.sub.Sender) and a recipient having a recipient identity string (Id.sub.Recipient), the method comprising: at the sender: identifying a Trusted Centre (TC) by a TC identity string (Id.sub.TC), the Trusted Centre having a master public key of the Trusted Centre (g.sub.Pub) based on the Trusted Centre identity string (Id.sub.TC); determining if the sender has a sender private key (Prv.sub.Sender) and a plurality of public parameters (PK) for the Trusted Centre (TC), the public parameters (PK) including the master public key (g.sub.Pub) of the Trusted Centre (TC) and a bilinear map (e); verifying the public parameters (PK) of the Trusted Centre (TC) using the Trusted Centre identity string (Id.sub.TC) prior to encrypting a plaintext message (M); identifying the recipient by an identity string (Id.sub.Recipient); hashing the identity string of the recipient (Id.sub.Recipient) using cryptographic hash functions (H.sub.1,H.sub.2,H.sub.3,H.sub.T) lying in the public parameters (PK); encrypting the plaintext message (M) as ciphertext (C) using the public parameters (PK), a random symmetric key (Σ) and the hash of the identity string of the recipient (Id.sub.Recipient); transmitting (C) to the recipient over the network; and/or at the recipient: receiving the ciphertext (C) from the sender over the network system; determining if the recipient has a recipient private key (Prv.sub.Recipient) and the public parameters (PK) for the Trusted Centre (TC); decrypting the first part of the ciphertext (C) (e.g. U, V) to obtain the symmetric key (Σ) using the public parameters (PK) and the recipient private key (Prv.sub.Recipient); decrypting the second part of the ciphertext (C) (e.g. W the same as in the algorithm Auth-Decrypt) to obtain the plaintext message (M) using the decryption algorithm (ϵ) and the symmetric key (Σ), wherein a plaintext or a ciphertext is signed for any user attesting the origin of the message using the public parameters (PK) of the Identity-Based Encryption, which can be verified by any user.

37. The method of claim 36, wherein the method further comprises, at the recipient, verifying the identity of the sender using the ciphertext (C), the public parameters (PK), the sender identity string (Id.sub.Sender) and the recipient private key (Prv.sub.Recipient).

38. A method of verifying a plurality of public parameters (PK) from a Trusted Centre (TC) in an identity based encryption system prior to encrypting a plaintext message (M) by a sender having a sender identity string (Id.sub.Sender), the method comprising: identifying the Trusted Centre (TC) by a Trusted Centre identity string (Id.sub.TC), the Trusted Centre having a master public key (g.sub.Pub) based on the Trusted Centre identity string (Id.sub.TC); determining if the sender has a sender private key (Prv.sub.Sender) and the plurality of public parameters (PK) for the Trusted Centre (TC), the public parameters (PK) including the master public key of the Trusted Centre (g.sub.Pub) and a bilinear map (e); verifying the public parameters (PK) of the Trusted Centre (TC) using the Trusted Centre identity string (Id.sub.TC) prior to encrypting the plaintext message (M) by comparing values of the bilinear map (e) calculated with variables comprising the sender private key (Prv.sub.Sender) and the master public key of the Trusted Centre (g.sub.Pub), wherein a plaintext or a ciphertext is signed for any user attesting the origin of the message using the public parameters (PK) of the Identity-Based Encryption, which can be verified by any user.

39. A system for sending an encrypted message over a network using Identity-Based Encryption, the system comprising: a Trusted Centre (TC) having a Trusted Centre identity string (Id.sub.TC), a sender having a sender identity string (Id.sub.Sender), and a recipient having a recipient identity string (Id.sub.Recipient); wherein the Trusted Centre (TC) has a first memory and one or more configured for: generating a plurality of public parameters (PK) and a secret master key (s) from a security parameter (λ), the public parameters (PK) including a bilinear map (e) and a master public key of the Trusted Centre (g.sub.Pub) based on the Trusted Centre identity string (Id.sub.TC); receiving a request from a requestor; if the request from the requestor contains an identifier (Id) identifying the requestor, generating a private key (Prv.sub.Id) based on the identifier (Id) and the secret master key (s) and transmitting the private key (Prv.sub.Id) to the requestor over the network system; if the request from the requestor includes a request for the public parameters (PK), transmitting the public parameters (PK) to the requestor over the network system; wherein the sender has a second memory and one or more processors configured for: identifying the Trusted Centre (TC) by the Trusted Centre identity string (Id.sub.TC); determining if the sender has a sender private key (Prv.sub.Sender) and the public parameters (PK) for the Trusted Centre (TC); verifying the public parameters (PK) of the Trusted Centre (TC) using the Trusted Centre identity string (Id.sub.TC) prior to encrypting a plaintext message (M); identifying the recipient by the recipient identity string (Id.sub.Recipient); hashing the identity string of the recipient (Id.sub.Recipient) using cryptographic hash functions (H.sub.1,H.sub.2,H.sub.3,H.sub.T) lying in the public parameters (PK); encrypting the plaintext message (M) as ciphertext (C) using the public parameters (PK), a random symmetric key (λ) and the hash of the identity string of the recipient (Id.sub.Recipient); transmitting (C) to the recipient over the network; wherein the recipient has a third memory and one or more processors configured for: receiving the ciphertext (C) from the sender over the network system; determining if the recipient has a recipient private key Prv.sub.Recipient and the public parameters (PK) for the Trusted Centre (TC); decrypting the first part of the ciphertext (C) (e.g. U, V) to obtain the symmetric key (Σ) using the public parameters (PK) and the recipient private key (Prv.sub.Recipient); decrypting the second part of the ciphertext (C) (e.g. W) to obtain the plaintext message (M) using the decryption algorithm (ϵ) and the symmetric key (Σ), wherein a plaintext or a ciphertext is signed for any user attesting the origin of the message using the public parameters (PK) of the Identity-Based Encryption, which can be verified by any user.

40. The system of claim 39, wherein preferably the plurality of public parameters (PK) further include a description of the groups (G.sub.1, G.sub.2, G.sub.T), a description of the cryptographic hash functions (H.sub.1, H.sub.2, H.sub.3, H.sub.T), a symmetric key encryption function (ϵ), and a description of the bilinear map (also called pairing) (e) which takes as input one element from (G.sub.1) and one element of (G.sub.2) and output an element from (G.sub.T) and that verifies the properties of a non-degenerated bilinear map.

41. A computer program product comprising a computer readable memory storing computer executable instructions thereon that, when executed by a computer, perform the method steps of: identifying a Trusted Centre (TC) by a TC identity string (Id.sub.TC), the Trusted Centre having a master public (g.sub.Pub) based on the TC identity string (Id.sub.TC); determining if a sender has a sender private key (Prv.sub.Sender) and a plurality of public parameters (PK) for the Trusted Centre (TC), the public parameters (PK) including the master public key of the Trusted Centre (g.sub.Pub) and a bilinear map (e); verifying the public parameters (PK) of the Trusted Centre (TC) using the Trusted Centre identity string (Id.sub.TC) prior to encrypting a plaintext message (M); identifying a recipient by a recipient identity string (Id.sub.Recipient); hashing the identity of the recipient (Id.sub.Recipient); encrypting the plaintext message (M) as ciphertext (C) using the public parameters (PK) a random symmetric key (Σ) and the hash of the identity of the recipient; transmitting the ciphertext (C) to the recipient over a network, wherein a plaintext or a ciphertext is signed for any user attesting the origin of the message using the public parameters (PK) of the Identity-Based Encryption, which can be verified by any user.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0037] Reference may now be had to the following detailed description taken together with the accompanying drawings in which:

[0038] FIG. 1 shows a network system in accordance with an embodiment of the present invention;

[0039] FIG. 2 shows a flowchart illustrating a method for sending an encrypted message in accordance with an embodiment of the present invention;

[0040] FIG. 3 shows a plurality of users in a network registering with the Trusted Centre in accordance with an embodiment of the present invention;

[0041] FIG. 4 shows a flowchart for a user labeled “Identity String” registering with the Trusted Centre in accordance with an embodiment of the present invention;

[0042] FIG. 5 shows a user labeled “User A” transmitting an encrypted message to a user labeled “User B” in a network with certificate-less authenticated encryption using identity-based encryption in accordance with an embodiment of the present invention;

[0043] FIG. 6 shows a flowchart for a user labeled “User A” encrypting a message to a user labeled “User B” in accordance with an embodiment of the present invention;

[0044] FIG. 7 shows a flowchart for a user labeled “User A” determining whether to get the public key for the Trusted Centre in accordance with an embodiment of the present invention;

[0045] FIG. 8 shows a flowchart for a user labeled “User B” decrypting the message from a user labeled “User A” in accordance with an embodiment of the present invention;

[0046] FIG. 9 shows a flowchart for a user labeled “User B” determining whether to get its private key from the Trusted Centre in accordance with an embodiment of the present invention; and

[0047] FIG. 10 shows a flowchart for a user labeled “User A” determining whether to get its private key from two different Trusted Centers disabling key escrow in accordance with an embodiment of the present invention.

DETAILED DESCRIPTION

[0048] A network system 10 in accordance with an embodiment of the present invention is shown in FIG. 1. The network system 10 includes a Trusted Centre 20, a user 30 labeled as “Sender” and a user 30 labeled as “Recipient” connected over a network 2, such as an intranet, the internet, and/or the like. While the two users 30 may be labeled differently, it should be understood that the labels are arbitrary and may change based on the direction an encrypted message is being sent. A “Sender” is a user 30 operable to package a plaintext message as an encrypted message for transmission and a “Recipient” is a user 30 operable to receive the encrypted message from the “Sender”. Upon a response to an encrypted message, the “Recipient” may become the “Sender”, and vice versa.

[0049] Each of the users 30 labeled “Sender” respectively “Recipient” are configured with a memory 32 and one or more processors 34. It should be understood that any additional hardware as known to those skilled in the art may be included, such as dedicated circuits, a field programmable gate array (FPGA), and/or the like. Each of the users 30 may exist on separate computers and/or mobile devices incorporating the necessary operating system, software and/or browsers as known to those skilled in the art.

[0050] Similarly, the Trusted Centre 20 may exist as a dedicated server or as part of a distributed network having memory 22 and one or more processors 24. The Trusted Centre 20 may also include additional hardware and/or software components as known the art, such as firewalls and/or associated security mechanisms. The Trusted Centre 20 is connected to the “Sender” and “Recipient” over network 2.

[0051] In operation, the network system 10 in accordance with the present invention is operable to transmit information from the “Sender” to the “Recipient” using verifiable identity based encryption (VIBE) scheme. Each of the users 30 is operable to communicate with the Trusted Centre 20 to obtain a respective private key (Prv) and a plurality of public parameters (PK). The public parameters (PK) are specific to the Trusted Centre, which includes a master public key of the Trusted Centre (g.sub.Pub) Once these parameters (i.e. Prv and PK) have been obtained by the respective “Sender” and “Recipient”, the sender and recipient are operable to communicate independent of the Trusted Centre 20 over a secure channel by encrypting the message using the identity string (Id.sub.Recipient) associated with the recipient. Furthermore, prior to encrypting a message, the sender is operable to verify the public parameters (PK) of the Trusted Centre (TC) using the Trusted Centre identity string (Id.sub.TC), which is known to the sender, to ensure that the public parameters (PK) have not been modified.

[0052] The VIBE scheme according to the present invention is based on identity-based encryption (IBE) and, as shown in the flowchart 100 of a preferred embodiment as seen in FIG. 2, generally operates as follows: [0053] a) In step 110, the user 30 (i.e. “Sender”) identifies a Trusted Centre (TC) by a TC identity string ((Id.sub.TC) i.e. “xyz.com” or “name of TC”). [0054] b) In step 120, the “Sender” determines if it has a sender private key (Prv.sub.Sender) and a plurality of public parameters (PK) associated with or generated by the Trusted Centre (TC). [0055] c) In step 130, the “Sender” verifies the public parameters (PK) of the Trusted Centre (TC) prior to encrypting a plaintext message (M). The verification process relies on the properties of the public parameters (PK) and sender private key (Prv.sub.Sender), both generated by the Trusted Centre (TC), and the known TC identity string (Id.sub.TC) and the sender identity string (Id.sub.Sender), the verification process relies on the mathematical properties of the bilinear map (e), which forms part of the public parameters, as further discussed below. [0056] d) In step 140, the “Sender” identifies the user 30 (i.e. “Recipient”) to receive the plaintext message (M) by a recipient identity string (Id.sub.Recipient). The recipient identity string may be an email address, a phone number, a name, and/or the like. [0057] e) In step 150, the “Sender” encrypts the plaintext message (M) as ciphertext (C) using the identity of the recipient (Id.sub.Recipient) and the public parameters (PK). The ciphertext (C) includes the encrypted message, as well as ancillary information necessary for decrypting the message. Additional authentication information may also be appended to the ciphertext (C); this additional piece is computed using the identity of the recipient (Id.sub.Recipient) and the private key of the sender (Prv.sub.Sender). [0058] f) In step 160, the “Sender” transmits the ciphertext (C) to the “Recipient” over the network. As the message is encrypted, the message may be sent over an unsecured channel. A user will require the recipient private key (Prv.sub.Recipient) and the public parameters for the Trusted Centre (PK) to decrypt and be able to read the plaintext message (M).

[0059] In this manner, the “Sender” is able to send a plaintext message (M) as an encrypted message to the “Recipient” without accessing the Trusted Centre (TC), as long as the “Sender” has the required public parameters (PK) and its own sender private key (Prv.sub.Sender). Furthermore, with the public parameters (PK) and its own sender private key (Prv.sub.Sender), the “Sender” is able to verify that the public parameters (PK) have not been compromised. In this manner, the “Sender” is operable to ensure that only the “Recipient” having the recipient private key (Prv.sub.Recipient) will be able to decrypt the ciphertext (C).

[0060] To implement the VIBE scheme according to the present invention, and the method of the preferred embodiment of the present invention discussed above, four major algorithms are utilized. It should be understood that additional algorithms, application programming interfaces (APIs), methods, and/or functions will be known and/or implemented by those skilled in the art to provide common functions and operations necessary to implement the network system according to the present invention. The four major algorithms in accordance with a preferred embodiment include: [0061] Setup(λ): This algorithm is run by the Trusted Centre 20 (i.e. system administrator) which provides the encryption/decryption services. It takes as inputs the security parameter (λ) and outputs the public parameters (PK) and the secret master key (s) of the Trusted Centre (TC). [0062] KeyGen(Id,s): This algorithm is also run by the Trusted Centre 20 (i.e. administrator) which distributes the private keys (Prv) throughout the system. It takes as inputs an identity string (Id), which may be received from a user 30, and the secret master key (s) from the administrator. It outputs a private key (Prv.sub.Id) that will be used for decryption in the Auth-Decrypt( ) algorithm, but which may also be incorporated into the Verifi-Encrypt( ) algorithm to allow for the authentication of a sent message. While the KeyGen( ) algorithm is run by the Trusted Centre 20, it may be run on behalf of a user 30 which has provided its identity string (Id) to the Trusted Centre (TC). [0063] Verifi-Encrypt(Id,PK,M,Prv.sub.Sender): This algorithm is run independently by individual users 30 who wish to encrypt sensitive data (i.e. the “Sender”). It takes as inputs the identity string of the recipient ((Id), or more specifically, (Id.sub.Recipient)), the set of public parameters (PK), the plaintext message (M) and the private key of the sender (Prv.sub.Sender) The algorithm first verifies whether the public parameters (PK) are genuine under the given administrative network for the specific Trusted Centre 20 and then outputs the ciphertext message (C) where C=(V,U,W,Y) and where V, U, and W are parameters that are necessary to decrypt and recover the plaintext message (M), and Y is a parameter which may be used by the recipient to authenticate the sender. [0064] Auth-Decrypt(Prv.sub.Id,PK,Id.sub.Sender,C): This algorithm is run independently by individual users 30 who are recipients of the ciphertext (C) and wish to decrypt and access the plaintext message (M) from the ciphertext (C). The algorithm takes as inputs the private key of the recipient ((Prv.sub.Id), or more specifically, (Prv.sub.Recipient)), the public parameters (PK), the identity of the Sender (Id.sub.Sender) and the ciphertext message (C). If the recipient has the proper private key (Prv.sub.Id) under the same administrative network associated with identity string of the recipient (Id), the algorithm outputs the plaintext message (M).

[0065] The internal structure of each of the four-mentioned algorithms in accordance with a preferred embodiment of the present invention will be further discussed below, including the mathematical basis which may provide the functionality of the mentioned algorithms

Bilinear Pairings

[0066] The VIBE scheme according to the present invention is based on bilinear pairings. A bilinear pairing is formally defined as follows:

[0067] Let (G.sub.1,.Math.), (G.sub.2,.Math.) and (G.sub.T,.Math.) be groups, with G.sub.1 and G.sub.2 prime order groups, let g.sub.1 be a generator of G.sub.1 and g.sub.2 be a generator of G.sub.2. A bilinear map is an efficiently computable application from (G.sub.1×G.sub.2) to (G.sub.T), that verifies the two following properties:

[0068] 1. Bilinearity: [0069] for all (g.sub.1, g.sub.2)∈(G.sub.1×G.sub.2) and all [0070] (a, b)∈(×), [0071] e: G.sub.1×G.sub.2-»G.sub.T, [0072] e(g.sub.1.sup.a,g.sub.2.sup.b)=e(g.sub.1.sup.b, g.sub.2.sup.a)=e(g.sub.1, g.sub.2).sup.ab

[0073] 2. Non-Degeneracy: [0074] GT is not trivial and if g.sub.1 is a generator of G.sub.1 and g.sub.2 is a generator of G.sub.2 then e(g.sub.1, g.sub.2) is a generator of G.sub.T

[0075] Weil pairing and Tate pairing are two implementations of an efficient bilinear map over elliptic curve groups useful for cryptography, such as described in Ian F. Blake, Gadiel Seroussi, and Nigel P. Smart, editors, Advances in Elliptic Curve Cryptography, Cambridge University Press, 2005, the contents of which are herein incorporated by reference in its entirety. Cryptographic bilinear maps must have certain complexity properties that are explained in the following section.

Complexity Assumptions

[0076] In general, cryptographic bilinear maps need to be one-way functions, i.e. computing the bilinear pairing should be efficient, but the inverse has to be difficult. The Bilinear Diffie-Hellman (BDH) complexity assumption is related to the difficulty of solving Discrete Logarithm Problem (DLP) over large algebraic groups.

[0077] The Diffie Hellman Problem guarantee the security of many schemes in elliptic curves cryptography. The problem is, in a group G of order p, to compute the element (g.sup.ab), knowing the group elements g, g.sup.a and g.sup.b (with a and b random elements in .sub.p). Precisely, this problem is known as the computational Diffie Hellman Problem.

[0078] The Decisional DH Problem is to recognize if an element h is equal to the unknown element gab, knowing the group elements g, g.sup.a and g.sup.b (with a and b random elements in .sub.p). It is trivial to see that the Decisional DH problem is easier to solve than the Computational one. Indeed, if an adversary can construct g.sup.ab then solving the Decisional problem is straightforward: it computes g.sup.ab and compare it to h. Thus, any scheme based on the hardness of the Decisional problem is stronger than one based on the Computational problem.

[0079] The Trilinear Computational DH Problem is to compute the element e(g.sub.1, g.sub.2).sup.abc knowing the group elements (g.sub.1, g.sub.2, g.sub.1.sup.a, g.sub.2.sup.a, g.sub.1.sup.b, g.sub.2.sup.e) (with a, b, c random elements in .sub.p). This Problem is harder than the Computational DH problem and is advantageously ensuring the security of the present invention.

Verifiable Identity Based Encryption (VIBE)

[0080] The details of the main algorithms in the VIBE scheme in a preferred embodiment of the present invention, using the bilinear mapping and assumptions provided above, are given as follows: [0081] Setup(λ): It takes as inputs the security parameter λ and then generates the groups G.sub.1, G.sub.2 and G.sub.T and a bilinear map e. The size of the groups is determined by λ. Let's denote the identity string of the Trusted Centre by “admin”—note that any other string representing the Trusted Centre, e.g. “abc.com” or “xyz.com” could be used. Select a symmetric key encryption function E in which the shared key is n-bit long. We denote the decryption function corresponding to E by D, and it should be clear that by knowing E it would be easy to find D. Choose four cryptographic hash functions H.sub.1, H.sub.2, H.sub.3, H.sub.T such that [0082] H.sub.1{0,1}*.fwdarw.G.sub.1, [0083] H.sub.2: {0,1}*.fwdarw.G.sub.2, [0084] H.sub.3: {0,1}*.fwdarw.*, [0085] H.sub.T: G.sub.T>{0,1}* [0086] Notations: {0,1}* means a bit string of an arbitrary length, * means the set of the non-zero elements of Z (which is the set of relative integers).

[0087] Pick at random s∈.sub.p* and set g.sub.admin=H.sub.1(“admin”)∈G.sub.1. Compute g.sub.Pub=g.sub.admin.sup.s as the Trusted Centre's master public key. Let's denote the public parameters of the VIBE by public parameters (PK) that includes a description of (G.sub.1, G.sub.2, G.sub.T, H.sub.1, H.sub.2, H.sub.3, H.sub.T, g.sub.Pub, ϵ). Set s as the master secret key, which is only known to the Trusted Centre. Output (PK) and s. [0088] Keygen(Id,s): It takes as inputs an identity string of a user (Id) and the secret master key (s) of the administrator. It computes g.sub.Id=(H.sub.1(Id),H.sub.2(Id)) and sets the private key of the user as the couple Prv.sub.Id=g.sub.Id.sup.s.sup.−1(H.sub.1(Id).sup.s.sup.−1, H.sub.2(Id).sup.s.sup.−1) (Prv.sub.Id,1 will be the first element and Prv.sub.Id,2 the second). It then outputs Prv.sub.Id, and privately shares it with the user, for example, over a secure channel. The private key of the user Prv.sub.Id, may be shared by any highly secure means, however the VIBE deployment key protocol should be preferred in any cases. Although the private key Prv.sub.Id must be kept secure, the public parameters (PK) are very resilient to attacks and can even be sent over an insecure channel and/or be publicly broadcast.

[0089] Verifi—Encrypt(Id, PK, M, Prv.sub.Id): It takes as inputs the identity string (Id) of the recipient (Id.sub.Recipient), the set of public parameters (PK), the plaintext message (M) and the private key of the sender (Prv.sub.Sender). The plaintext message (M) is encrypted as follows: The method first verifies the public parameters (PK) are genuine under the chosen Trusted Centre by comparing e (g.sub.Pub, Prv.sub.Sender,2) with e(H.sub.1(“admin”), H.sub.2(Id.sub.Sender)). If these values are equal then the public parameters have not been altered and are related to the private keys of the user. If the verification passes, it picks a random symmetric key (Σ) and outputs the encrypted ciphertext (C), where C=(V, U, W, Y) and where V, U, W, Y are computed as follow:

r=H.sub.3(Σ),

i V=g.sub.Pub.sup.r

U=Σ⊕H.sub.T(e(H.sub.1(“admin”),H.sub.2(Id.sub.Recipient).sup.r))

W=ϵ.sub.σ(M)

Y=H.sub.T(e(H.sub.1(Id.sub.Recipient).sup.r, Prv.sub.Sender,2))

[0090] Auth—Decrypt(Prv.sub.Recipient, PK, Id.sub.Sender, C): it takes as inputs the private key of the recipient (Prv.sub.Recipeint) the public parameters (PK), the identity of the Sender (Id.sub.Sender) and the ciphertext (C=(V,U,W,Y)). If the message has been encrypted for the identity (Id.sub.Recipient) then the recipient will be able to recover the symmetric key: [0091] Σ=U⊕H.sub.T(e(V, Prv.sub.Recipient,2)).

[0092] The plaintext message is recovered by computing M=D.sub.Σ(W). Note that (Y) is used to authenticate the sender as follows: The recipient computes r=H.sub.3(Z) and verifies if Y=H.sub.T(e(Prv.sub.Recipient,1.sup.r, H.sub.2(Id.sub.Sender))). If it is true the sender is authenticated and the recipient can be sure of who sent the message, if not the sender is rejected.

[0093] Verifying the correctness of the scheme: It is easy to check that decryption correctly recovers M. Since ϵ.sub.Σ and D.sub.Σ have the exact opposite action, thus the recovering of M is equivalent to the recovering of Σ. This is done correctly:

U⊕H.sub.T(e(V,Prv.sub.Recipient,2))

=U⊕H.sub.T(e(g.sub.Pub.sup.r, g.sub.Recipient,2.sup.s.sup.−1))

=U⊕H.sub.T(e(g.sub.admin.sup.s.Math.r,g.sub.Recipient,2.sup.s.sup.−1))

=U⊕H.sub.T(e(g.sub.admin,g.sub.Recipient,2.sup.r.Math.s.Math.s.sup.−1)

=U⊕H.sub.T(e(g.sub.admin,g.sub.Recipient,2).sup.r)

=Σ⊕H.sub.T(e(H.sub.1(“admin”),H.sub.2(Id.sub.Recipient).sup.r))⊕H.sub.T(e(g.sub.admin,g.sub.Recipient,2).sup.r)

=Σ

[0094] It is also easy to verify that a correctly computed Y will be accepted by the recipient:

Y=H.sub.T(e(H.sub.1(Id.sub.Recipient).sup.r, Prv.sub.Sender,2))

Y=H.sub.T(e(H.sub.1(Id.sub.Recipient).sup.r,g.sub.Sender,2.sup.s.sup.−1))

Y=H.sub.T(e(H.sub.1(Id.sub.Recipient),H.sub.2(Id.sub.Sender)).sup.r.Math.s.sup.−1)

Y=H.sub.T(e(H.sub.1(Id.sub.Recipient).sup.s.sup.−1,H.sub.2(Id.sub.Sender)).sup.r)

Y=H.sub.T(e(Prv.sub.Recipient,1,H.sub.2(Id.sub.Sender)).sup.r)

Y=H.sub.T(e(Prv.sub.Recipient,1.sup.r,H.sub.2(Id.sub.Sender)))

[0095] As discussed above, the Trusted Centre 20 is configured to initiate the setup of the Verifiable Identity Based Encryption (VIBE) system by running the Setup(λ) algorithm and manage the distribution of private keys (Prv) and public parameters (PK) by Keygen(Id,s) function calls from different users 30 in the network system 10. The Trusted Centre 20 may itself initiate the Setup(λ) algorithm upon startup or when the Trusted Centre 20 determines that it is necessary to renew or reset the security of the network system 10. It can do so by generating a new secret master key (s) and new public parameters (PK). Potential reasons for self-initiation of Setup(λ) are: [0096] security requirements; [0097] policy or regulatory requirements; [0098] application requirements;
and may be run according to renewal schedules and the like.

[0099] Using the mathematical foundation, described above in the preferred embodiments, users 30 in the network system 10 are able to encrypt and decrypt messages using the VIBE scheme.

[0100] Turning now to FIG. 3, the different users 30 in the network system 10 are operable to register with the Trusted Centre 20 and obtain the public parameters (PK) and their respective private keys (Prv). For example, the users 30 may call the Keygen function 28 made available by the Trusted Centre 20.

[0101] The Trusted Centre 20 may also provide a Setup function 26 for a user to call. When called, the Setup function 26 may initiate the Setup(λ) algorithm to renew and/or reset the security of the network system 10 by generating a new secret master key (s) and new public parameters (PK).

[0102] Referring now to FIG. 4, a user 30 is operable to register itself with the Trusted Centre 20 by first authenticating itself with the Trusted Centre 20. Different means for authentication may be used to authenticate a user 30 with the Trusted Centre 20, as known in the art. For example, password-based authentication, a challenge-response protocol such as the Kerberos protocol from the Massachusetts Institute of Technology, biometric authentication (i.e. fingerprint, retinal), and the like may be used. Once the user 30 has authenticated itself, the user 30 is operable to call the Keygen function 28 provided by the Trusted Centre 20 and submitting its identity string (Id) to the Trusted Centre (TC). In FIG. 4, the user 30 is labeled as “Identity String” (e.g. “Id”). The Trusted Centre (TC) then calls the Keygen(Id,$) algorithm using the identity string (Id) provided by the user 30 and its own secret master key (s). In return, the Trusted Centre 20 receives the private key for the user 30 (Prv.sub.Id) which the Trusted Centre 20 then passes on to the user 30. The Trusted Centre 20 may also pass on to the user 30, as part of the Keygen function 28, the public parameters (PK).

[0103] Another advantageously example would be a registration at the manufacturing process when dealing with connected objects: [0104] inside a chip representing a user 30 with identity (Id), a private key (Prv.sub.Id) would be printed. This private key would have been computed using the identity of the chip (Id) and the secret master key (s.sub.M) of the manufacturer (M) playing the role of a Trusted Centre; [0105] any real life Trusted Centre (TC) will contact the manufacturer and get a private key (Prv.sub.TC) computed using the identity of the Trusted Centre (TC) and the secret master key (s.sub.M); [0106] user 30 request a private key to the Trusted Centre 20 by sending an authenticated encryption of a request to the Trusted Centre 20 computed using the private key of user 30 (Prv.sub.Id), the master public key of the manufacturer (g.sub.(Pub,M)) and the identity of the Trusted Centre 20 (TC); [0107] the Trusted Centre 20 computes the private key of the user 30 (Prv.sub.Id) using the identity of user 30 (Id) and the secret master key (s.sub.TC); [0108] the Trusted Centre 20 sends the private key (Prv.sub.Id) to user 30 over the secure channel created by the user on his request.

[0109] Once the user 30 has its respective private key (Prv) and the public parameters (PK), which includes the master public key of the Trusted Centre (g.sub.Pub), a sender is able to send an encrypted message to a recipient without contacting the Trusted Centre 20. No certificate authority is necessary, only the public parameters (PK) and the identity string of the recipient (Id.sub.Recipient) is required and guarantee the identity of the recipient.

[0110] Referring now to FIG. 5, a transmission from a user 30A labeled “User A” to a user 30B labeled “User B” is shown in a preferred embodiment. The transmission of an encrypted message may be completed without contacting the Trusted Centre 20.

[0111] In some preferred embodiments, the VIBE scheme of the present invention may not be efficient for encrypting very small messages. In this case (message length less than an AES key length) then the message can be directly encrypted, playing the role of Σ in the encryption algorithm. Note that there will be no W in this ciphertext.

[0112] Referring now to FIG. 6, a flowchart 600 is shown illustrating the encryption method of VIBE described before in the algorithm Verifi-Encrypt, used by a user 30A, labeled “User A”, for encrypting a message for a user labeled “User B. In step 610, the sender (i.e. user 30A or “User A”) identifies or chooses a Trusted Centre (TC) to associate the encrypted message with. The sender identifies the Trusted Centre (TC) by its (TC) identity string (Id.sub.TC), e.g. label “TC”.

[0113] Next, in step 612 the sender determines whether it has the plurality of public parameters (PK) for the Trusted Centre (TC), including the master public key of the Trusted Centre (g.sub.Pub) or whether the sender must get the TC's master public key prior to proceeding. Referring briefly to FIG. 7, the sender determines whether or not it needs to get the TC's master public key by comparing whether any of the (g.sub.Pub) the sender may have stored in memory is associated with the identity string of the Trusted Centre (Id.sub.TC). If not, user 30A authenticates itself with the Trusted Centre 20 and calls the Keygen function to receive its own private key Prv.sub.UserA and the Trusted Centre's public parameters (PK), as previously described when registering a new user 30 in FIG. 4.

[0114] Returning to FIG. 6, once the sender believes it has the proper master public key (g.sub.Pub), the sender in step 614 verifies the TC's public key (g.sub.Pub) using the senders private key (Prv.sub.Sender) as described above with respect to Verifi-Encrypt(Id,PK,M,Prv.sub.Sender) algorithm using the different parameters in the public parameters (PK) associated with the Trusted Centre 20 and the private key of the sender (Prv.sub.Sender). As noted above, the TC's master public key (g.sub.Pub) and the sender private key (Prv.sub.Sender) are fixed values received and stored by the sender from the Trusted Centre (TC). The sender can be assured that the public parameters (PK) have not been tampered with if [0115] e(g.sub.Pub,Prv.sub.(Sender,2)=e(H.sub.1(“admin”) ,H.sub.2(Id.sub.Sender))
is satisfied, as described in the algorithm Verifi-Encrypt(Id,PK,M,Prv.sub.Sender).

[0116] Once the sender has verified the public parameters (PK), the sender can begin by picking a conventional encryption key (Σ) that is used to encrypt the actual confidential data, such as large documents or video/audio files, using the conventional symmetric encryption scheme (i.e. AES, 3DES and the like). The plaintext message (M) is then set to include the conventional encryption key (Σ) of the conventional symmetric encryption scheme to be protected by the VIBE Verifi-Encrypt( ) algorithm, as shown in step 616. Next, as shown in step 618, the confidential data is symmetrically encrypted using the conventional symmetric encryption scheme and the conventional encryption key (Σ) is stored as (or as a part of) the plaintext message (M).

[0117] Next, in step 620, the sender computes each component of the ciphertext (C), as described above with respect to the Verifi-Encrypt(Id,PK,M,Prv.sub.Sender) algorithm to symmetrically-encrypt the plaintext message (M) using the symmetric key encryption function (EE), found within the public parameters (PK), and using a random symmetric key (Σ), generated locally by the sender. In particular, each of V, U and W are computed for the particular Trusted Centre (TC) using the recipient identity string (Id.sub.Recipient i.e. “User B”) associated with the recipient, the random symmetric key (Σ), which is randomly generated every time Verifi-Encrypt(Id,PK,M,Prv.sub.Sender) is run, and the master public key of the Trusted Centre (g.sub.Pub), as well as the other public parameters in the public parameters (PK).

[0118] In step 622, the encrypted message is signed by returning the ciphertext component Y for the recipient using the sender private key (Prv.sub.Sender), or more specifically (Prv.sub.UserA). The recipient may be operable to use this ciphertext component Y to authenticate the received message.

[0119] Finally, the ciphertext (C) is packaged together in step 624 and is ready to be attached to the transmission to be sent to the recipient. The components of the ciphertext (C) may be packaged as a file (i.e. “cip.key”) or within other methods and/or structures known in the art. The symmetrically-encrypted data using the conventional symmetric encryption scheme along with the file, “cip.key”, containing the conventional encryption key (Σ) stored in the plaintext message (M) is then ready for transmission to the recipient and may be sent over an unsecured channel as a properly encrypted message.

[0120] Upon receipt of the ciphertext (C), i.e. as stored in the file “cip.key”, the recipient is operable to decrypt the ciphertext (C) to retrieve the plaintext message (M) that contains the conventional encryption key (Σ) used to encrypt the actual data.

[0121] Referring now to FIG. 8, a flowchart 800 is shown illustrating a user 30B, labeled “User B”, decrypting a message from a user labeled “User A. In step 810, the recipient (i.e. user 30B or “User B”) retrieves the ciphertext (C) from the received transmission. For example, the ciphertext (C) may be packaged as the file, “cip.key”.

[0122] Next, the recipient determines, at step 812, whether it needs to get the recipient private key Prv.sub.Recipient (or more specifically Prv.sub.UserB) from the Trusted Centre (TC). Referring briefly to FIG. 9, the recipient determines whether or not it needs to get the recipient private key (Prv.sub.Recipient) of the particular Trusted Centre (TC) by comparing whether any of the Prv.sub.UserB the recipient may have stored in memory is associated with the identity string of the Trusted Centre (Id.sub.TC, i-e. “admin”). If not, user 30B authenticates itself with the Trusted Centre 20 and calls the Keygen( ) function to receive its own private key (Prv.sub.UserB) and the Trusted Centre's public key (g.sub.Pub), as previously described when registering a new user 30 in FIG. 4. At this time, the recipient may also receive an updated set of public parameters (PK) from the Trusted Centre (TC).

[0123] Referring now to FIG. 10, a flowchart is illustrating a method wherein the Trusted Centre (TC) is separated in two Trusted Centre (TC.sub.1) and (TC.sub.(−1)) with master secret key (s.sub.1) and (s.sub.(−1)) and the private keys (Prv.sub.Id) are computed through a protocol between the Trusted Centre (TC.sub.1,TC.sub.(−1)) and the user with identity (Id): [0124] at each Trusted Centre (TC.sub.i): [0125] computing A.sub.i=H.sub.1(Id.sub.TC).sup.s.sup.i, B.sub.i=H.sub.2(Id.sub.TC).sup.s.sup.−1.sup.i; [0126] transmitting privately A.sub.i, B.sub.i to TC.sub.(−i); [0127] publishing A.sub.i; [0128] receiving A.sub.−i, B.sub.−i; [0129] verifying if e(A.sub.−i, B.sub.−i)=e(H.sub.1(Id.sub.TC), H.sub.2(Id.sub.TC)) and A.sub.−i≠H.sub.1(Id.sub.TC); [0130] computing the master public key of (TC) as g.sub.Pub=A.sub.−i.sup.s.sup.i. [0131] new request of private key, at a Trusted Centre (TC.sub.i): if the request from the requestor contains an identifier (Id) identifying the requestor, verifying that this identifier has not been requested, generating a private key (Prv.sub.Id) based on the identifier (Id) and the secret master key (s.sub.i) and transmitting securely the private key (Prv.sub.Id) to the requestor over the network system; All next transmissions do not need to be secured. [0132] at requestor with identity string (Id): [0133] receiving the private key (Prv.sub.Id,1, Prv.sub.Id,2); [0134] picking a random number (a) in ; [0135] computing (HPK.sub.1,HPK.sub.2)=(Prv.sub.Id,1.sup.a.sup.−1, Prv.sub.Id,2.sup.a.sup.−1) and T=H.sub.2(Id).sup.a.sup.−1; [0136] transmitting (Id,HPK.sub.1,HPK.sub.2,T) to the second Trusted Centre (TC.sub.−i). [0137] at the second Trusted Centre (TC.sub.−i): [0138] identifying the requestor with the identity string (Id); [0139] verifying that this identifier has not been requested; [0140] verifying that e(H.sub.1(Id),HPK.sub.2)=e(HPK.sub.1,H.sub.2(Id)) and e(A.sub.i,HPK.sub.2)=e(H.sub.1 (Id.sub.TC),T); [0141] computing (HK.sub.1,HK.sub.2)=(HPK.sub.1.sup.s.sup.−1.sup.−1, HPK.sub.2.sup.s.sup.−1.sup.−1); [0142] transmitting (HK.sub.1,HK.sub.2) to the requestor over the network. [0143] at the requestor: [0144] receiving (HK.sub.1,HK.sub.2); [0145] computing Prv.sub.Id=(HK.sub.1.sup.a,HK.sub.2.sup.a).

[0146] Returning to FIG. 8, the recipient is now able to decrypt the different components V, U and W of the ciphertext (C) using the recipient private key (Prv.sub.Recipient) and the public parameters (PK) in step 814. From these components, the recipient is able to retrieve the conventional encryption key (Σ), as described in the Auth-Decrypt(Prv.sub.Recipient,PK,Id.sub.Sender,C) algorithm. Furthermore, in step 816, the recipient is operable to verify the sender of the message by inspecting the ciphertext (C) component Y. As described in the Auth-Decrypt(Prv.sub.Recipient,PK,Id.sub.Sender,C) algorithm, the sender may be authenticated by calculating H.sub.T(e(Prv.sub.Recipient,1.sup.r, H.sub.2(Id.sub.Sender))); User A is authenticated if this value is equal to the received Y.

[0147] Finally, once the sender has been verified, the recipient is operable to recover the conventional encryption key (Σ) used by the conventional symmetric encryption scheme to encrypt the confidential data. The plaintext message (M) is recovered using the random symmetric key (Σ) and the symmetric key encryption function (ϵ) to easily determine (D), as described above in the Auth-Decrypt(Prv.sub.Recipient,PK,Id.sub.Sender,C) algorithm. Using the conventional encryption key (Σ), the recipient is operable to decrypt the transmitted message using the conventional symmetric encryption scheme. The decryption process is now complete.

[0148] The VIBE scheme as described above in a preferred embodiment of the present invention allows for the intended recipient to verify the sender's identity without storing or referring to any public key certificates. If the recipient successfully decrypts the ciphertext (C), the recipient can authenticate the sender based on the properties of the bilinear map (e) using the public parameters (PK) and the sender identity string (Id.sub.Sender). The authentication is an integral part of the VIBE scheme and it is more efficient to verify the sender in this manner than separately adding additional authentication components to the encryption process. The VIBE scheme according to the preferred embodiment of the present invention will ensure that not only is the sensitive data kept confidential, but also the sender of the confidential data is authentic. It should be noted that the authentication can be made optional by removing Y from the ciphertext (C) in an application where other authentication/digital signature schemes exist.

Verifiable Identity-Based Signature (VIBS)

[0149] The details of the main algorithms in the signature scheme VIBS in a preferred embodiment of the present invention, using the bilinear mapping and assumptions provided above, are given as follows:

[0150] Setup(λ): It takes as inputs the security parameter λ and then generates the groups G.sub.1, G.sub.2 and G.sub.T and a bilinear map e. The size of the groups is determined by λ. Denote the identity string of the Trusted Centre by a string, for example “admin”—note that any other string representing the Trusted Centre, e.g. “abc.com” or “xyz.com” could be used. Select a symmetric key encryption function E in which the shared key is n-bit long. Denote the decryption function corresponding to E by D, and it should be clear that by knowing ϵ it would be easy to find D. Choose four cryptographic hash functions H.sub.1, H.sub.2, H.sub.3, H.sub.T such that [0151] H.sub.1{0,1}*>G.sub.1, [0152] H.sub.2: {0,1}*>G.sub.2, [0153] H.sub.3: {0,1}*>*, [0154] H.sub.T: G.sub.T>{0,1}* [0155] Notations: {0,1}* means a bit string of an arbitrary length, * means the set of the non-zero elements of (which is the set of relative integers).

[0156] Pick at random s∈.sub.p* and set g.sub.admin=H.sub.1(“admin”)∈G.sub.1. Compute G.sub.Pub=g.sub.admin.sup.s as the Trusted Centre's master public key. Denote the public parameters of the VIBE by public parameters (PK) that includes a description of (G.sub.1, G.sub.2, G.sub.T, H.sub.1, H.sub.2, H.sub.3, H.sub.T, g.sub.Pub, ϵ). Set s as the master secret key, which is only known to the Trusted Centre. Output (PK) and s.

[0157] Keygen(Id,s): It takes as inputs an identity string of a user (Id) and the secret master key (s) of the administrator. It computes g.sub.Id=(H.sub.1(Id),H.sub.2(Id)) and sets the private key of the user as the couple Prv.sub.Id=g.sub.Id.sup.s.sup.−1=(H.sub.1(Id).sup.s.sup.−1, H.sub.2(Id).sup.s.sup.−1) (Prv.sub.Id,1 will be the first element and Prv.sub.Id,2 the second). It then outputs Prv.sub.Id, and privately shares it with the user, for example, over a secure channel The private key of the user Prv.sub.Id may be shared by any highly secure means, however the VIBE deployment key protocol should be preferred in any cases. Although the private key Prv.sub.Id must be kept secure, the public parameters (PK) are very resilient to attacks and can even be sent over an insecure channel and/or be publicly broadcast.

[0158] Sign(Id.sub.Sender), PK, m, Prv.sub.Id.sub.Sender): It takes as inputs the identity string of the sender (Id.sub.Sender), the set of public parameters (PK), the plaintext message (M) (or a ciphertext message) and the private key of the sender (Prv.sub.Sender). It picks a random big number a different from 0 and 1 and outputs the signature σ. Where σ=(σ.sub.1, σ.sub.2, σ.sub.3) and where σ.sub.1, σ.sub.2, σ.sub.3 are computed as follow:

[00001]${\sigma }_1={\mathrm{Prv}}_{\mathrm{Sender},2}^{\frac{1}{H_3\left(m\right)+\alpha }},{\sigma }_2=g_{Pub}^{\alpha },{\sigma }_3=Pr{v}_{Sen\mathrm{der},2}^{{\alpha }^{-1}}.$

[0159] Verify(Id.sub.Sender, PK, σ): It takes as inputs the identity string of the sender (Id.sub.Sender), the set of public parameters (PK), the signature on the message (σ) and the plaintext (or ciphertext) message (m). The verification of the signature is achieved by verifying the validity of the two following equalities (3 pairings needed only):

e(σ.sub.2,σ.sub.3)=e(H.sub.1(Id.sub.TC),H.sub.2(Id.sub.Sender)),

e(g.sub.Pub.sup.H.sup.3.sup.(m).Math.σ.sub.2,σ.sub.1)=e(H.sub.1(Id.sub.TC), H.sub.2(Id.sub.Sender))

[0160] Verifying the correctness of the scheme: It is easy to check that the verification of a correctly computed signature verifies:

[00002]$e\left({\sigma }_2,{\sigma }_3\right)=e\left(g_{\mathrm{Pub}}^{\alpha },{\mathrm{Prv}}_{Sen\mathrm{der},2}^{{\alpha }^{-1}}\right)={e\left(g_{\mathrm{Pub}},{\mathrm{Prv}}_{\mathrm{Sender},2}\right)}^{{\alpha }^{-1}.Math.\alpha }=e\left(g_{\mathrm{Pub}},{\mathrm{Prv}}_{\mathrm{Sender},2}\right)=e\left({H_1\left(I{d}_{TC}\right)}^s,{H_2\left(I{d}_{Sender}\right)}^{s^{-1}}\right)={e\left(H_1\left(I{d}_{TC}\right),H_2\left(I{d}_{Sender}\right)\right)}^{s.Math.s^{-1}}=e\left(H_1\left(I{d}_{TC}\right),H_2\left(I{d}_{Sender}\right)\right)$

And:

[0161] [00003]$e\left(g_{\mathrm{Pub}}^{H_3\left(m\right)}.Math.{\sigma }_2,{\sigma }_1\right)=e\left(g_{\mathrm{Pub}}^{H_3\left(m\right)}.Math.g_{\mathrm{Pub}}^{\alpha },{\mathrm{Prv}}_{\mathrm{Sender},2}^{\frac{1}{H_3\left(m\right)+\alpha }}\right)={e\left(g_{\mathrm{Pub}}^{H_3\left(m\right)+\alpha },H_2\left(I{d}_{Sender}\right)\right)}^{\frac{s-1}{H_3\left(m\right)+\alpha }}={e\left({H_1\left(I{d}_{TC}\right)}^{s\left(H_3\left(m\right)+\alpha \right)},H_2\left(I{d}_{Sender}\right)\right)}^{\frac{s-1}{H_3\left(m\right)+\alpha }}={e\left(H_1\left(I{d}_{TC}\right),H_2\left(I{d}_{Sender}\right)\right)}^{\frac{s.Math.s^{-1}\left(H_3\left(m\right)+\alpha \right)}{H_3\left(m\right)+\alpha }}=e\left(H_1\left(I{d}_{TC}\right),H_2\left(I{d}_{Sender}\right)\right)$

[0162] The algorithms Setup and Keygen are the same in VIBE and VIBS enabling the use of both with the same public parameters and private keys.

Dynamic Authority

[0163] The encryption key in VIBE scheme according to the preferred embodiment of the present invention is derived from dynamic parameters that are calculated from the Trusted Centre's identifier, e.g. domain name, phone number, etc.

[0164] This new design yields greater flexibility in working with multiple authorities. The sender of encrypted data can enforce elaborate access conditions on the recipient before the recipient can decrypt and retrieve sensitive data. The sender can select not only who the recipient is but also how the recipient receives its private key (Prv.sub.Recipient). For example, a descriptive string may be combined or appended with the TC identity string (Id.sub.TCc) to increase the level of authentication required by the Trusted Centre (TC) necessary for the recipient to obtain its private key (Prv.sub.Recipient) from the Trusted Centre (TC). The recipient may be forced by the Trusted Centre (TC) to further authenticate itself by satisfying this additional condition, provided by the descriptive string. The additional descriptive string may include the recipient's role, the recipient's revocation number, the recipient's age, the recipient's location, an expiry date and the like.

[0165] As an example, the sender can choose “bob@ abc.com” as the recipient's identity of the encrypted message and can set “abc.com-date” as the Trusted Centre's public identity string (TC.sub.Id) with an expiry date “date”. The sender's description of the TC identity string (TC.sub.Id) is then enforced in the ciphertext (C) by locally computing a new g.sub.(Admin-New) where g.sub.(Admin-New)=H.sub.1(“abc.com-date”). If the sender possesses the master public key of the Trusted Centre (TC) g.sub.Pub=g.sub.Admin-New.sup.s it can proceed with Verifi-Encrypt( ) as described above. Otherwise, the sender is forced to obtain a new g.sub.Pub, as shown with respect to FIG. 7.

[0166] Beyond this date, the encryption algorithm would receive a new public key from the Trusted Centre (TC) and would use it to generate new encryption keys. The recipient would then be forced to renew its private key from Trusted Centre. This is very useful in conditions where the identity of users in the system will remain the same for an extended period, but it is beneficial for security reasons to have the private keys update periodically and/or frequently. On the receiver's side, if the same secret master key (s) is used to compute the new master public key of the Trusted Centre (TC) no change has to be made to the private key of the recipient (Prv.sub.Recipient) or the decryption algorithm. If, however, a different secret master key (s) is used, the recipient will be forced to receive a new private key corresponding to the secret master key of the Trusted Centre (TC) with the new TC identity string (Id.sub.TC), as shown in FIG. 9.

[0167] It should be noted that the same encryption algorithm can be used if the sender decides to use a different server (trusted authority) such as “xyz.com” instead of “abc.com”. The only difference in the encryption algorithm would be in using the master public key of the new Trusted Centre (g(Pub-New)) everything else remains the same.

Revocation and Rekeying

[0168] This design using identity string can also be used on the user side allowing for example rekeying: an arbitrary sized revocation number (RevNum) can be appended on identity string (Id) representing the identity of the user: (Id∥RevNum). This method advantageously allows any user to renew his key as followed: [0169] Any private key (Prv) that is requested for the new identity (Id) is computed using the hash of the identity (Id∥0). [0170] When a user with identity string (Id) request a rekeying to the Trusted Centre (TC), the Trusted Centre search for this identity string (Id) in the revocation list (RL) and extract the revocation number attached to it (RevNum.sub.Id). [0171] The Trusted Centre (TC) securely transmit the new private key (Prv.sub.(Id|RevNumId+2)) computed using the secret master key (s), the identity string of the requestor (Id) and the revocation number increased by 2 (RevNum.sub.Id+2). [0172] The Trusted Centre (TC) register the new revocation number (RevNum.sub.Id+1) along with the identity of the requestor (Id) in the revocation list (RL). [0173] The Trusted Centre publish the new revocation list (RL).

[0174] The same method can advantageously be used to do simple revocation: a revocation number is appended on identity string representing the identity of the user: (Id∥RevNum). This method advantageously allows any user to be revoked through the following method: [0175] When a user with identity string (Id) request a revocation to the Trusted Centre (TC), the Trusted Centre search for this identity string (Id) in the revocation list (RL) and extract the revocation number attached to it (RevNum.sub.Id). [0176] The Trusted Centre (TC) register the new revocation number (RevNum.sub.Id+1) along with the identity of the requestor (Id) in the revocation list (RL). [0177] The Trusted Centre publish the new revocation list (RL).

Exchange of Trust

[0178] As discussed above, the VIBE scheme according to the present invention allows the sender to communicate privately with any recipient under various trusted authorities. For example, the sender can send an encrypted message from the “abc.com” domain (with secret master key s) to someone in the “xyz.com” domain (with secret master key s′). As long as any new Trusted Centre (TC″) register to the first Trusted Centre (TC) and owns a private key (Prv.sub.TC), any user can get a private key (Prv′) for the domain of (TC″) advantageously as follow: [0179] The user with identity (Id) sends an encrypted and authenticated message to (TC′) using the private key (Prv.sub.Id), the identity of the second Trusted Centre (Id.sub.TC), and a private key request as plaintext message (M). [0180] Once this request received and the validity of the user's identity is verified the second Trusted Centre (TC″) compute a private key (Prv'.sub.Id) using the secret master key (s′), and the identity string of the user (Id). [0181] The second Trusted Centre (TC′) sends an authenticated ciphertext (C) encrypted using the master public key of the first Trusted Centre (TC), the identity of the user (Id), the sender's private key (Pr.sub.TC′) and the freshly computed private key (Prv′) as plaintext message (M). [0182] At reception of the ciphertext (C), the user decrypts and verify the identity of the sender using the receiver private key (Prv.sub.Id) and the identity string of the sender (Id.sub.TC).

[0183] In this manner, the sender has control of which Trusted Centre (TC) to associate with and can force the recipient to authenticate to a Trusted Centre (TC) of its choosing. Accordingly, the sender can rely on the additional security of choosing its preferred Trusted Centre to generate and supply the private key (Prv) to the recipient. The onus can then be placed on the recipient to associate with reliable Trusted Centers and authenticate itself to the Trusted Centre (TC), selected by the sender, to receive the private key for the recipient (Prv.sub.Recipient)

[0184] Although this disclosure has described and illustrated certain preferred embodiments of the invention, it is also to be understood that the invention is not restricted to these particular embodiments rather, the invention includes all embodiments which are functional, or mechanical equivalents of the specific embodiments and features that have been described and illustrated herein. The scope of the claims should not be limited to the preferred embodiments set forth in the examples, but should be given the broadest interpretation consistent with the description as a whole.

[0185] It will be understood that, although various features of the invention have been described with respect to one or another of the embodiments of the invention, the various features and embodiments of the invention may be combined or used in conjunction with other features and embodiments of the invention as described and illustrated herein. Furthermore, while the various methods described herein may refer to a specific order and number of steps, it should be understood that the order and/or number of method steps described herein should not be construed as limiting, as other orders and/or number of steps would be understood by persons skilled in the art.

[0186] The embodiments of the invention in which an exclusive property or privilege is claimed is defined as stated in the claims.