CN101527629A - Hierarchical identity-based encryption and signature schemes - Google Patents

Abstract

The invention provides an identity-based hierarchical encryption and signature scheme. A method for encoding and decoding a digital message between a sender and a receiver in a system involving multiple private key generators ("PKGs"). The PKG includes at least one root PKG and n lower-level PKGs in the hierarchical structure between the root PKG and the recipient. A root key generating ciphertext is selected and known only to the root PKG (102). Generate a root key generation parameter (104) according to the root key generation ciphertext. A low-level key generation ciphertext is selected for each of the n low-level PKGs, wherein each low-level key generation ciphertext is known only to its associated low-level PKG (106). Also generate a low-level key generation parameter for each of the n low-level PKGs, at least using the low-level key corresponding to its associated low-level private key generator to generate ciphertext (108).

Description

Identity-based Hierarchical Encryption and Signature Scheme

This application is a divisional application of the invention patent application with the application number 03803910.9, the application date is March 18, 2003, and the invention title is "identity-based hierarchical encryption and signature scheme".

related application

Applicant hereby claims priority under 35 U.S.C § 119(e) to Provisional U.S. Patent Application 60/366,292, filed March 21, 2002, and Provisional U.S. Patent Application 60/366,196, filed March 21, 2002, the Both provisional patent applications are incorporated herein by reference.

technical field

The present invention relates generally to cryptography and secure communications with devices over computer networks or through other types of systems, and more particularly to identity-based hierarchical schemes for encrypting and decrypting communications.

Background technique

Broadly speaking, identity-based cryptosystems are public-key cryptosystems in which an entity's public key is derived from information related to the entity's identity. For example, the identity information may be personal information (ie name, address, email address, etc.) or computer information (ie IP address, etc.). However, identity information can include not only information strictly related to an entity's identity, but also widely available information, such as time or date. That said, the importance of the concept of identity information lies not in its strict relationship to an entity's identity, but in the ease with which anyone wishing to send an encrypted message to an entity can obtain that information.

An entity's private key is generated and distributed by a trusted party or logical process, commonly referred to as a private key generator ("PKG"). PKG uses a master ciphertext message to generate a private key. Since an entity's public key can be deduced from its identity, when Alice wants to send Bob a message, she does not have to retrieve Bob's public key from the database. Instead, Alice simply infers the key directly from Bob's identifying information. Public key databases are then redundant, and certificate authorities ("CAs") are unnecessary. There is no need to "bind" Bob's identity to his public key, because his identity is his public key.

The concept of identity-based systems is not new. It has been proposed in "Identity-Based Cryptosystems and Signatures Schemes (identity-based encryption system and signature scheme)" written by A.Shamir, which was published in ADVANCES INCRYPTOGRAPHY-CRYPTO'84, Lecture Notes in ComputerScience 196( 1984), Springer, 47-53. However, practically applicable identity-based encryption schemes have not been found so far. For example, identity-based schemes have been proposed in the following documents, "An Identity-Based Encryption Scheme Based on Quadratic Residues (an Identity-Based Encryption Scheme Based on Quadratic Residues)" by C. Cocks, which can be Available at http://www.cesg.gov.uk/technology/id-pkc/media/ciren.pdf ; "Identity Based Encryption from the Weil Pairing" by D. Boneh , M. Franklin Encryption of Identity)", which was published in ADVANCES IN CRYPTOGRAPHY-CRYPTO2001, Lecture Notes in Computer Science2139 (2001), Springer, 213-229; and "Identity Based Encryption from the Weil Pairing ( extended version) (identity-based encryption obtained by Weil pairing (extended version)), this paper is available at http://www.cs.stanford.edu/~dabo/papers/ibe.pdf . Cocks' scheme is based on the "squared residual problem", although encryption and decryption are quite fast (about the speed of RSA), but there will be significant message expansion (that is, the ciphertext bit length is many times the plaintext bit length) . The Boneh-Franklin scheme bases its security on the "bilinear Diffie-Hellman problem", which is quite fast and efficient when using Weil or Tate pairings on supersingular elliptic curves or Abelian variety curves.

However, known identity-based encryption schemes all have a significant flaw - none of them are hierarchical. In non-identity-based public-key cryptography, it is already possible to set up a hierarchy of CAs, in which a root CA can issue certificates for other CAs, which in turn can issue certificates for users within a particular domain. Doing this is well worth it, as it lightens the root CA's workload. A practical classification scheme that can be used with identity-based encryption has not yet been developed.

Ideally, an identity-based hierarchical encryption scheme would include a logical or actual PKG hierarchy. For example, a root PKG can issue private keys to other PKGs, which in turn can issue private keys to users within a specific domain. At the same time, as long as the sender obtains the public parameters of the root PKG, even if the sender is not in the system at all, it can send an encrypted message without going online to find the receiver's public key or low-level public parameters. Another advantage of identity-based hierarchical encryption schemes is damage control. For example, the leakage of the ciphertext of a domain PKG will not compromise the ciphertext of a higher-level PKG, nor will it compromise the ciphertext of any other PKG that is not a direct subordinate of the compromised domain PKG. The scheme advocated by Cocks and Boneh-Franklin does not have these properties.

A secure and practical identity-based hierarchical encryption scheme has not yet been developed. An identity-based hierarchical key sharing scheme with partial collusion resistance has been proposed in the following literature: "An Efficient Hierarchical Identity-Based Key by G. Hanaoka, T. Nishioka, Y. Zheng, H. Imai -Sharing Method ResistantAgainst Collusion Attacks (an efficient identity-based hierarchical key sharing method that can resist collusion attacks)", this article was published in ADVANCES INCRYPTOGRAPHY-ASIACRYPT 1999, Lecture Notes in ComputerScience 1716(1999), Springer, 348 -362; and "A Hierarchical Non-InteractiveKey-Sharing Scheme With Low Memory Size and High Resistance Against Collusion Attacks" by G.Hanaoka, T.Nishioka, Y.Zheng, H.Imai A Hierarchical Non-Interactive Key Sharing Scheme for Attack Resistance), which will be published in THE COMPUTERJOURNAL. In addition, an introduction to identity-based hierarchical encryption is also provided in the article "Toward Hierarchical Identity-Based Encryption" by J. Horwitz, B. Lynn, which will be published in ADVANCES IN CRYPTOGRAPHY - EUROCRYPT 2002, Lecture Notes in Computer Science, Springer. Horwitz and Lynn propose a two-level hierarchical scheme that is fully collusion-resistant at the first level and partially collusion-resistant at the second level (i.e., users can collude to obtain their The ciphertext of the domain PKG, and pretend to be the domain PKG accordingly). However, the complexity of the Horwitz-Lynn system increases with the collusion resistance at the second level, so this scheme cannot be both practical and safe.

Therefore, a safe and practical identity-based hierarchical encryption scheme is needed. One object of the present invention is to provide a safe and practical identity-based hierarchical encryption scheme. Another object of the present invention is to provide a secure and practical identity-based hierarchical signature scheme. Another object of the invention is that both encryption and signature schemes are fully scalable. Another object of the present invention is that the described encryption and signature schemes are completely collusion resistant on any number of levels and they have chosen ciphertext security in the random oracle model.

Contents of the invention

According to the present invention, it provides a method for implementing a secure, reliable and practical identity-based hierarchical encryption and signature scheme.

According to one aspect of the present invention, there is provided a method for encoding and decoding digital messages between a sender and a receiver in a system comprising a plurality of private key generators (" PKG"). These PKGs include at least one root PKG and n lower-level PKGs in the hierarchy between the root PKG and the recipient, where n≥1. A root key generating ciphertext is chosen and known only to the root PKG. Generate a root key generation parameter according to the root key generation ciphertext. Select a low-level key to generate ciphertext for each of the n low-level PKGs, where each low-level key generates ciphertext only known to its associated low-level PKG. A low-level key generation parameter is also generated for each of the n low-level PKGs, wherein at least the low-level key generation ciphertext corresponding to the relevant low-level private key generator is used. The message is encoded using at least root key generation parameters and recipient identity information to form a ciphertext. generate a recipient private key such that the recipient private key is in at least n lower-level key-generating ciphertexts associated with n lower-level PKGs in the hierarchy between the root key-generating ciphertext, the root PKG, and the recipient One or more of , and the recipient's identity information. Decrypting said ciphertext using at least the recipient's private key to recover said message.

According to another aspect of the present invention, there is provided a method for encoding and decoding digital messages between a sender and a receiver in a system comprising a plurality of private key generators ( "PKG", ). These PKGs include at least one root PKG, m lower-level PKGs in the hierarchical structure between the root PKG and the sender, where m≥1, and n lower-level PKGs in the hierarchical structure between the root PKG and the receiver, where n ≥1, and PKG _l , which is the predecessor PKG common to both sender and receiver. In this hierarchical structure, l of the m private key generators is the common predecessor PKG of the sender and the receiver, where l≥1.

According to the content of this aspect of the present invention, a low-level key is selected for each of the m low-level PKGs in the hierarchical structure between the root PKG and the sender to generate ciphertext. Generate a sender private key such that the sender private key is in at least m lower-level key-generating ciphertexts related to m lower-level PKGs in the hierarchy between the root key-generating ciphertext, the root PKG, and the sender One or more of , and sender identity information. Generate a recipient private key such that the recipient private key is in at least n lower-level key-generating ciphertexts related to n lower-level PKGs in the hierarchy between the root key-generating ciphertext, the root PKG, and the recipient One or more of , and the recipient's identity information. Utilizes _at least 0 or multiple, to encode the message in question, but cannot use any of the low-level key generation parameters associated with (1-1) PKGs higher than the common predecessor _PKG 1. _Utilizes at least 0 or multiple, to decode the message in question, but cannot use any of the low-level key generation parameters associated with (1-1) PKGs higher than the common predecessor _PKG 1.

According to another aspect of the present invention, there is provided a method for generating and verifying a digital signature of a message between a sender and a receiver in a system comprising a plurality of PKGs. These PKGs include at least one root PKG and n lower-level PKGs in the hierarchy between the root PKG and the sender, where n≧1. A root key generating ciphertext is chosen and known only to the root PKG. Generate a root key generation parameter according to the root key generation ciphertext. Select a low-level key to generate ciphertext for each of the n low-level PKGs, where each low-level key generates ciphertext only known to its associated low-level PKG. A low-level key generation parameter is also generated for each of the n low-level PKGs, wherein at least the low-level key generation ciphertext corresponding to the relevant low-level private key generator is used. A private key is generated for the sender, so that the private key is at least related to the ciphertext generated by the root key and the identity information of the sender. Said message is signed with at least the sender's private key to generate a digital signature. The digital message is authenticated using at least root key generation parameters and sender identity information.

Description of drawings

The following description of preferred embodiments of the invention refers to the accompanying drawings, in which:

Figure 1 shows a flow diagram illustrating a method of encoding and decoding a digital message in accordance with the presently preferred embodiment of the present invention;

Figure 2 shows a flow chart illustrating a method of encoding and decoding digital messages between a sender y and a receiver z according to another presently preferred embodiment of the present invention;

Figure 3 shows a block diagram illustrating a typical hierarchical structure in which the method shown in Figure 2 can be implemented;

Figure 4 shows a flow chart illustrating a method of encoding and decoding a digital message M between a sender y and a receiver z according to another presently preferred embodiment of the present invention transfer between

Fig. 5 shows a flow diagram illustrating a method of encoding and decoding a digital message M between a sender y and a receiver z according to another presently preferred embodiment of the present invention transfer between

Figure 6 shows a flow diagram illustrating a method of encoding and decoding a digital message M between a sender y and a receiver z according to another presently preferred embodiment of the present invention transfer between

FIG. 7 shows a flowchart illustrating a method of generating and verifying a digital signature according to another presently preferred embodiment of the present invention;

Fig. 8 shows a flow chart illustrating a method of generating and verifying a digital signature Sig of a digital message M between sender y and transfer between receiver z; and

Fig. 9 shows a flow chart illustrating a method of generating and verifying a digital signature Sig of a digital message M between sender y and Transfer between receiver z.

Detailed ways

The presently preferred method of the present invention provides a secure and practical Hierarchical Identity-Based Encryption ("HIDE") and Signature ("HIDS") scheme. The described hierarchical scheme is fully adjustable, fully collusion-resistant at any number of levels, and has chosen-ciphertext security in a random oracle model. These goals are achieved in part by introducing additional random information in each low-level PKG. One intuitively surprising aspect of these schemes is that even if the low-level PKG produces additional random information, it does not force the addition of common parameters below the root level of the hierarchy. In addition, the random information generated by the low-level PKG does not negatively affect the ability of users not below the low-level PKG to send encrypted messages to users below the low-level PKG.

Each of the HIDE and HIDS schemes of the present invention requires a hierarchical structure of PKGs, which includes at least one root PKG and multiple lower-level PKGs. Hierarchies and low-level PKGs can be logical or physical. For example, a single entity can generate root key-generating ciphertexts and low-level key-generating ciphertexts from which the encryption or signing keys of low-level users are generated. In this case, the lower-level PKGs are not independent entities, but just processes or information organized in a logical hierarchy and used to generate keys for descendant PKGs and users in the hierarchy. Alternatively, each low-level PKG may also be a separate entity. Another alternative involves a mixed form of actual and logical low-level PKG. For the purposes of this disclosure, the phrase "lower PKG" is used generally to refer to any of these alternatives.

In the context of the identity-based hierarchical cryptosystem disclosed herein, the identity-based public key may be time-period-based. For example, the identity of a particular recipient may change with each subsequent time period. Alternatively, the receiver can schedule the time periods as descendants or subordinates of itself in the hierarchy, and the sender will use the identity on the correct time period when encoding the message. Regardless of the method used, each key is only valid for the relevant time period to sign the message to Bob.

The HIDE scheme of the present invention generally includes five randomized algorithms: root set, low level set, decimation, encryption, and decryption. Three of these algorithms rely on the identity of related entities in a hierarchy. Each user preferably has a place in the hierarchy, which can be defined by its ID tuple (ID ₁ , . . . , ID _t ). The predecessor of the user in the hierarchical structure is the root PKG and the user or PKG whose ID tuple is {(ID ₁ , . . . , ID _i ): 1≤i≤(t−1)}. For computational purposes, ID tuples are best represented as binary strings.

In the root setting algorithm, the root PKG uses a secret parameter k to generate the public system parameter params and a root key to generate ciphertext. The system parameters include descriptions of the message space M and the ciphertext space X. The system parameters described are for public use, but only the root PKG knows the root key to generate the ciphertext.

In the low-level set algorithm, each low-level PKG preferably generates its own low-level key-generating ciphertext for extraction purposes. Alternatively, a low-level PKG can also generate a one-time ciphertext for each draw.

In the extraction algorithm, a PKG (root PKG or lower-level PKG) generates a private key for any of its descendants. The private key is generated using system parameters, the private key of the producer PKG, and any other preferred ciphertext information.

In the encryption algorithm, the sender receives system parameters from the root PKG, preferably through some secure means outside the system. The sender does not have to accept any low-level key generation parameters. The sender encodes a message M∈M using params and the ID tuple of the intended recipient to generate an encrypted text C∈X. Conversely, in the decoding algorithm, the recipient decodes the encrypted text C using params and the recipient's private key d to recover the message M. Encryption and decryption preferably both satisfy the standard consistency constraints:

$\∀m\∈m:$ Decryption(params, d, C) = M

Where C = Encryption (params, ID tuple, M).

Like the HIDE scheme, the HIDS scheme of the present invention also generally includes 5 randomized algorithms: root setting, low-level setting, extraction, signing and verification. In root settings, system parameters are supplemented to include a specification of the signature space Σ. The low-level setup and decimation is preferably the same algorithm as in HIDE above.

In the signing algorithm, the sender of the digital message uses params and the sender's private key d to sign the message M∈M to generate a signature S∈∑. In the verification algorithm, the recipient of the signed message uses params and the ID tuple of the sender to verify the signature S. The verification algorithm preferably outputs "valid" or "invalid". Signing and verification preferably also satisfy the consistency constraints:

$\∀m\∈m:$ Verification(params, ID tuple, S) = "Valid"

where S = Signing (params, d, M).

Security of HIDE and HIDS schemes

The security of the solution of the present invention will be described below for HIDE and HIDS respectively. In the context of identity-based non-hierarchical cryptography, it has been noted that standard definitions for the security of selected ciphertexts must be enforced for identity-based systems. This is because, for the purposes of security analysis, it should be assumed that an adversary has access to private keys associated with any identity of its choosing (except for the specific identity under attack). The same applies to identity-based hierarchical encryption. Therefore, in order to ensure that the HIDE scheme of the present invention is safe with selected ciphertexts, a simulated attacker can be allowed to perform key extraction queries. At the same time, the simulated hostile party should be allowed to choose the identity it wishes to challenge.

It should also be noted that an adversary can choose its object's identity adaptively or non-adaptively. An adversary that adaptively selects its objects will first conduct out-of-order and extraction queries, and then select its targets based on the results of these queries. Such an adversary would not have a specific target in mind when initiating an attack. Rather, as long as it can crack someone, the adversary is successful. On the other hand, a non-adaptive adversary does not select its targets based on the results of out-of-order queries and extracted queries. For example, such an adversary would target a personal enemy. The adversary still performs out-of-order queries and extraction queries, but its target selection is strictly based on target identity rather than query results. Obviously, the security of the adversary selected against the adaptive target is stronger, and therefore a more superior and desirable security concept. However, the security analysis of the HIDE scheme in the present invention mentions two types of security.

If there is no polynomial-limited adversary A that has a non-negligible advantage over the challenger in the following competition, then the HIDE scheme is said to be semantically secure against adaptively selected ciphertext and adaptively selected targets.

Setup: The challenger gets a secret parameter k and runs the root setup algorithm. It provides the obtained system parameter params to the adversary. It leaves the root key generation ciphertext to itself.

Phase 1: The adversary proposes queries q ₁ ,...,q _m , where q _i is one of the following queries:

1. Public key query (ID tuple _i ): The challenger runs an out-of-order algorithm on ID tuple _i to obtain the public key H(ID tuple _{i )} corresponding to ID tuple i.

2. Extraction query (ID tuple _i ): The challenger runs the extraction algorithm to generate a private key d _i corresponding to ID tuple _i , and sends d _i to the adversary.

3. Decrypt query (ID tuple _i , C _i ): the challenger runs the extraction algorithm to generate the private key d _i corresponding to ID tuple _i , uses d _i to run the decryption algorithm to decrypt C _i , and converts the resulting The plaintext is sent to the adversary.

These queries can be asked adaptively. In addition, the queried ID tuple _i can correspond to a position on any level of the hierarchy.

Challenge: Once the adversary decides that Phase 1 is over, it outputs two plaintexts M ₀ , M ₁ ∈ M of equal length, and an ID tuple it wishes to challenge. The only restriction is that neither this ID tuple nor its predecessors can appear in any private key extraction queries in phase 1. The challenger randomly selects a random bit b∈{0, 1}, and sets C=Encryption(params, ID tuple, M _b ). It sends C as a challenge to the adversary.

Phase 2: The adversary proposes more queries q _m+1 , ..., q _n , where q _i is one of the following queries:

1. Public key query (ID tuple _i ): The challenger responds as in phase 1.

2. Extract query (ID tuple _i ): the challenger responds as in phase 1.

3. Decrypt query(C, ID tuple _i ): The challenger responds as in phase 1.

The query in phase 2 is restricted in that the challenger cannot perform an extraction query on the ID tuple associated with the challenge ciphertext C, or use that ID tuple and ciphertext C to perform a decryption query. This restriction applies equally to all predecessors of this ID tuple.

Guess: The opponent outputs a guess value b′∈{0, 1}. If b=b', the opponent wins the game. The advantage possessed by the enemy in attacking this scheme is defined as |Pr[b=b′]-1/2|.

In the race described below, a HIDE scheme is called a one-way encryption scheme if there is no polynomial-time adversary with a non-negligible advantage. In this competition, the opponent A is given a random public key K _pub and an encrypted text C, and outputs a guess value of the plaintext. The encrypted text C is obtained by encrypting a random message M with K _pub . If ε is the probability of A outputting M, then the hostile party is said to have an advantage ε in this scheme. Said competition is run as follows:

Setup: The challenger gets a secret parameter k and runs the root setup algorithm. It provides the obtained system parameter params to the adversary. It leaves the root key generation ciphertext to itself.

Phase 1: The adversary performs a public key and/or extraction query just as in Phase 1 of the selected ciphertext security analysis above.

Challenge: Once the adversary decides that Phase 1 is over, it outputs a new ID tuple ID that it wishes to challenge. The challenger randomly selects a random M∈M, and sets C=Encryption(params, ID tuple, M). It sends C as a challenge to the adversary.

Phase 2: The adversary makes more public key queries and more extraction queries for identities other than the ID and its predecessors, and the challenger responds as in phase 1.

Guess: The opponent outputs a guess value M′∈M. If M=M', the opponent wins the game. The advantage possessed by the enemy in attacking this scheme is defined as Pr[M=M'].

The solution of the present invention is safe and reliable for the above-mentioned challenges. In addition, the HIDS scheme of the present invention is also safe and reliable for the existing forgery of self-adaptive selection messages. Even after (adaptively) acquiring the target's signature on a message chosen by the adversary, the adversary cannot forge its target's signature on other messages it has not previously signed. A HIDS adversary will also have the ability to conduct public key lookups and private key extraction lookups to entities other than its target and its predecessors, as well as the ability to select its targets. For HIDE, the target selection of the adversary can be adaptive or non-adaptive.

pair

The presently preferred HIDE and HIDS schemes of the present invention are both based on pairings, such as Weil or Tate pairings related to elliptic curves or Abelian cluster curves. The method described can also be based on the bilinear Diffie-Hellman problem. They use two cyclic groups Γ ₁ and Γ ₂ , which preferably have prime order q of the same size. The first group Γ ₁ is preferably a group of points on elliptic curves or Abelian variety curves, and the group rules on Γ ₁ can be written as additive. The second group Γ ₂ is preferably a multiplicative subgroup of finite fields, and the group rules on Γ ₂ can be written multiplicatively. However, other types of groups can also be used as Γ ₁ and Γ ₂ according to the invention.

最好是双线性的，如果Q和R都在Γ₁中，且a和b都是整数，那么 $\hat{e}(\mathrm{aQ},\mathrm{bR})=\hat{e}{(Q,R)}^{\mathrm{ab}}.$ 第二，函数

最好是非退化的，从而使得该映射不会将Γ₁×Γ₁中的所有配对转变为Γ₂中的身份。第三，函数

最好是可以高效计算的。满足这三个条件的函数被认为是可行的。The described method also utilizes the generator P ₀ of the first group Γ ₁ . Additionally, a paired or function is provided $\hat{e}:{\mathrm{\Γ}}_1\×{\mathrm{\Γ}}_1\&Right\; Arrow;{\mathrm{\Γ}}_2,$ Used to map two elements of the first group Γ ₁ to one element of the second group Γ ₂ . function It is best to meet three conditions. First, the function

Preferably bilinear, if both Q and R are in Γ ₁ , and both a and b are integers, then $\hat{e}(Q,b)=\hat{e}{(Q,R)}^{\mathrm{ab}}.$ Second, the function

Preferably non-degenerate so that the mapping does not convert all pairs in Γ ₁ × Γ ₁ to identities in Γ ₂ . Third, the function

Preferably one that can be computed efficiently. A function that satisfies these three conditions considered feasible.

最好还是对称的，从而对所有的Q，R∈Γ₁都有 $\hat{e}(Q,R)=\hat{e}(R,Q).$ 然而，对称性直接来自于双线性以及Γ₁是循环群这样一个事实。可根据现有技术中已知的方法来修改与超奇异椭圆曲线以及阿贝尔簇曲线相关的Weil和Tate配对，以创建这样的双线性映射。但是，即使将第一循环群Γ₁的元素称为“点”会暗示函数

是一种经过修改的Weil或Tate配对，但应该注意的是，任何可行的配对

都能够发挥作用。function

Preferably symmetric, so that for all Q, R ∈ Γ ₁ has $\hat{e}(Q,R)=\hat{e}(R,Q).$ However, the symmetry comes directly from bilinearity and the fact that Γ ₁ is a cyclic group. The Weil and Tate pairings associated with supersingular elliptic curves and Abelian variety curves can be modified according to methods known in the art to create such bilinear maps. But even calling the elements of the first cyclic group _Γ1 "points" would imply that the function

is a modified Weil or Tate pairing, but it should be noted that any feasible pairing

can work.

The security of the HIDE and HIDS schemes in the present invention is mainly based on the bilinear Diffie-Hellman problem. The bilinear Diffie-Hellman problem is given a randomly selected P∈Γ ₁ , and aP, bP and cP (for unknown randomly selected a, b, c∈Z/qZ), find The problem. Solving the Diffie-Hellman problem in Γ ₁ solves the bilinear Diffie-Hellman problem because $\hat{e}{(P,P)}^{\mathrm{abc}}=\hat{e}(\mathrm{abP},\mathrm{CP}).$ Similarly, solving the Diffie-Hellman problem in Γ ₂ also solves the bilinear Diffie-Hellman problem, because if $g=\hat{e}(P,P),$ Then g ^abc = (g ^ab ) ^c , where $g^{\mathrm{ab}}=\hat{e}(\mathrm{aP},b)$ and $g^c=\hat{e}(P,\mathrm{CP}).$ In order to make the bilinear Diffie-Hellman problem difficult, Γ ₁ and Γ ₂ should be chosen such that there is no known algorithm in Γ ₁ or Γ ₂ that can efficiently solve the Diffie-Hellman problem.

的概率，其中是IΓ针对足够大的保密系数k的输出，P是Γ₁的随机生成器，a、b和c则是Z/qZ的随机元素。双线性Diffie-Hellman问题下的假设是，Adv_IΓ(B)对于所有的有效算法B都是可忽略的。If a randomization algorithm IΓ takes a secrecy parameter k > 0, runs in polynomial time of k, and outputs a description of the two groups Γ ₁ and Γ ₂ and a feasible pairing $\hat{e}:{\mathrm{\Γ}}_1\×{\mathrm{\Γ}}_1\&Right\; Arrow;{\mathrm{\Γ}}_2$ , where the two groups preferably have the same prime order q, then the algorithm IΓ is a bilinear Diffie-Hellman generator. If IΓ is a bilinear Diffie-Hellman parameter generator, then the advantage Adv _IΓ (B) of an algorithm B in solving the bilinear Diffie-Hellman problem is defined as, when the input to the algorithm is Γ ₁ , Γ ₂ , When P, aP, bP and cP, algorithm B outputs

probability, where is the output of IΓ for a sufficiently large confidentiality coefficient k, P is the random generator of Γ ₁ , and a, b, and c are the random elements of Z/qZ. The assumption under the bilinear Diffie-Hellman problem is that Adv _IΓ (B) is negligible for all efficient algorithms B.

HIDE program

Referring now to the drawings, FIG. 1 is a flowchart illustrating a method of encoding and decoding digital messages in accordance with a presently preferred embodiment of the present invention. The method is performed in a HIDE system comprising multiple PKGs. The PKG includes at least one root PKG and n lower-level PKGs in the hierarchical structure between the root PKG and the recipient, where n≥1.

In module 102, the root PKG selects a root key known only by the root PKG to generate ciphertext. The root key generation ciphertext may be used to generate private keys for PKGs and/or users below the root PKG in the hierarchy. Then, in module 104, the root PKG generates a root key generation parameter according to the root key generation ciphertext. The root key generation parameters are used to mask the root key generation ciphertext. The root key generation parameters can be revealed to the lower level PKG without compromising the root key generation ciphertext. In module 106, the low-level PKG selects the low-level key to generate ciphertext. The lower-level key generation ciphertext associated with a given lower-level PKG can be used to generate private keys for PKGs and/or users below the associated lower-level PKG in the hierarchy. Similar to the root key-generating ciphertext, each lower-level key-generating ciphertext is known only to its associated lower-level PKG.

In module 108, low-level key generation parameters are generated for each of the n low-level PKGs. The generation of each low-level key generation parameter shall at least utilize the low-level key of its associated low-level PKG to generate ciphertext. Similar to the root keygen parameters, each low-level keygen parameter masks the low-level keygen ciphertext associated with it.

In block 110, the sender encodes the message using at least root key generation parameters and identity information associated with the recipient to form a ciphertext. For example, the message may be encoded using only root key generation parameters and the identity of the recipient. Alternatively, one of the low-level key generation parameters can also be utilized, as will be explained in more detail below in terms of the double HIDE scheme. In module 112, a lower-level PKG generates a private key for the receiver such that the private key is at least n related to the root key-generating ciphertext, and n lower-level PKGs in the hierarchy between the root PKG and the receiver. One or more of the low-level key generation ciphertexts are associated with the recipient's identity information. For example, in addition to the root key generation ciphertext and the recipient's identity information, the recipient's private key is preferably at least related to the low-level key generation ciphertext of the PKG that issues the private key to the recipient. Alternatively, the receiver's private key can also be related to the lower-level key-generating ciphertexts of all n predecessors PKG as well as the root-key-generating ciphertext. In module 114, the recipient uses at least its private key to decode the ciphertext and recover the message. In addition to decoding using its private key, the receiver preferably also uses n lower-level key generation parameters associated with the n lower-level PKGs between the root PKG and the receiver in the hierarchy.

Each low-level PKG has a key generating ciphertext, just like the root PKG. As mentioned above, the low-level PKG preferably uses this ciphertext to generate private keys for its various descendants, just as the root PKG does. In this way, the private key of the descendant is related to the key-generating ciphertext of the lower-level PKG. This is true even if the lower-level PKG uses a modified version of its key-generating ciphertext to hide that ciphertext for the purpose of restricting key escrow, as will be explained more fully below. At the same time, instead of always using the same ciphertext for each private key extraction, the low-level PKG can randomly generate a new key generation ciphertext for each descendant of the PKG, thus obtaining a different key for each descendant. key generation parameters.

Since a lower-level PKG is able to generate a private key for the recipient (block 112), the root PKG does not have to generate all private keys itself. Also, since lower-level PKGs use their own key-generating ciphertexts to generate private keys for their descendants, exposing a lower-level key-generating ciphertext causes only limited security damage to the hierarchy. Rather than exposing all private keys in the hierarchy, it is better to have a single breach of a low-level PKG expose only that PKG's private keys and those produced by generating ciphertexts using that PKG's keys (i.e., as the exposed The private keys of those users who are direct descendants of the PKG in the hierarchy).

Another advantage of this embodiment is that the sender does not have to be in a hierarchy to send an encoded message to the receiver. The sender only needs to know the identity information related to the receiver and the system parameters generated by the root PKG. However, when the sender is in a hierarchical structure, the HIDE scheme of the present invention has some additional advantages. For example, when both the sender and receiver are in a hierarchical structure, the efficiency of message encryption can be improved by utilizing the identities of both parties. This type of HIDE scheme can be called double HIDE because the identity of both the sender and receiver are used as input to the encryption and decryption algorithms. An encoding and decoding method using the double HIDE scheme will now be described with reference to FIGS. 2 and 3 .

Double HIDE

The flowchart shown in FIG. 2 illustrates a method of encoding and decoding a digital message between a sender y and a receiver z according to another presently preferred embodiment of the present invention. The block diagram shown in Figure 3 illustrates a typical hierarchical structure in which this approach can be implemented. Similar to the previous embodiments, the method can be implemented in a HIDE system comprising at least one root PKG 302, and n lower-level PKGs in the hierarchy between the root PKG 302 and recipient z 308 304a, b, d, where n≥1. The sender y 306 in this embodiment must also be in the hierarchy, and the hierarchy also includes m lower-level PKGs 304a,b,c between the root PKG 302 and the sender y 306, where m≧1. Of the m PKGs 304a, b, c between the root PKG 302 and the sender y 306, and the n PKGs 304a, b, d between the root PKG 302 and the receiver z 308, l PKGs 304a, b are The common predecessor of sender y 306 and receiver z 308, where 1≤l≤m,n. For example, two of these 1 common predecessor PKGs (PKG _y1 /PKG _z1 304a and PKG _y1 /PKG _z1 304b) are shown in FIG. 3 .

The method of this embodiment begins in block 202, where the root PKG 302 selects a root key known only to the root PKG 302 to generate a ciphertext. Then, in module 204, the root PKG 302 generates a root key generation parameter according to the root key generation ciphertext. In block 206, the low-level PKG 304a-d selects the low-level key to generate ciphertext. Similar to the root key-generating ciphertext, each lower-level key-generating ciphertext is known only to its associated lower-level PKG 304a-d. In block 208, low-level key generation parameters are generated for each of the n low-level PKGs 304a-d. Each low-level keygen parameter is generated using at least the low-level keygen ciphertext corresponding to its associated low-level PKG 304a-d.

In module 210, the parent PKG _ym 304c of the sender generates a private key for the sender y 306, so that the private key is at least the same as the root key to generate the ciphertext, and the m number between the root PKG 302 and the sender y 306 One or more of the m low-level key generation ciphertexts related to the low-level PKG 304a, b, c are related to the sender's identity information. For example, in addition to the root key generation ciphertext and the sender's identity information, the sender's private key is preferably at least related to the low-level key generation ciphertext of the sender's previous generation PKG _ym 304c. Alternatively, the sender's private key can also be related to the low-level keygenerating ciphertexts of all its m immediate predecessors PKG as well as the root keygenerating ciphertext. In block 212, the recipient's parent PKG _zn 304d generates a private key for recipient z in a manner similar to that used by the sender's parent PKG _ym 304c to generate the sender's private key.

In block 214, sender y encodes the message to form a ciphertext using at least the sender's private key and (m-l+1) PKGs between root PKG 302 and sender y 306 (i.e., PKG _yl 304b and PKG _ym 304c) one or more of the relevant low-level key generation parameters, and said PKG is located at the lowest level common predecessor PKG of sender y 306 and receiver z 308 (PKG _yl /PKG _zl 304b) or below. When _encoding the message, sender y 306 _{preferably does} not use any lower-level Key generation parameters.

Then, in block 216, recipient z 308 decodes the ciphertext to recover said message using at least the recipient's private key and the (n- One or more of the low-level key generation parameters associated with 1+1) PKGs (i.e., PKG _zl 304b and PKG _zn 304c), and said PKG is located at the lowest level common to sender y 306 and receiver z 308 Senior PKG (PKG _yl /PKG _zl 304b) level or lower. When decoding _{the message} , receiver z 308 _preferably does not use any lower-level Key generation parameters.

This double HIDE embodiment of the present invention provides a more efficient scheme for encoding and decoding messages, since fewer key generation parameters need to be used. For example, decoding in a normal HIDE scheme requires approximately all n key generation parameters, but decoding in a double HIDE scheme requires only (n-l+1) key generation parameters. The double HIDE scheme requires sender y 306 to obtain its private key before sending an encoded message to receiver z 308, as opposed to only obtaining the public system parameter of the root PKG. The double HIDE scheme also enables sender y 306 and receiver z 308 to limit the scope of key escrow, as will be explained more fully below. This shared ciphertext is unknown to third parties other than their lowest public predecessor, PKG _yl /PKG _zl 304b.

Basic HIDE

使得该函数

能够由第一循环群Γ₁的两个元素生成第二循环群Γ₂的一个元素。函数最好是一种可行的配对，如上所述。在模块406中选取第一循环群Γ₁的一个根生成器P₀。在模块408中，选取一个随机根密钥生成密文s₀，该密文与根PKG 302相关且只有根PKG 302知道。s₀最好是循环群Z/qZ的一个元素。在模块410中产生一个根密钥生成参数Q₀＝s₀P₀。Q₀最好是第一循环群Γ₁的一个元素。在模块412中，选取一个第一函数H₁，使得H₁能够由第一串二进制数生成第一循环群Γ₁的一个元素。在模块414中选取一个第二函数H₂，使得H₂能够由第二循环群Γ₂的一个元素生成第二串二进制数。模块402至414的功能都是上述HIDE根设置算法的组成部分，并且最好都在大致相同的时刻完成。作为示例，比如那些在Boneh-Franklin中公开的函数就可以被用作H₁和H₂。The flowchart shown in FIG. 4 illustrates a method of encoding and decoding a digital message M communicated between a sender y and a receiver z, according to another presently preferred embodiment of the present invention. As shown in FIG. 3, recipient z 308 is n+1 levels below the root PKG in the hierarchy and is associated with ID tuples (ID _z1 , . . . , ID _z(n+1) ). The receiver's ID tuple includes identity information ID _z(n+1) related to the receiver, and identity information ID _zi related to its n predecessors and low-level PKGs in the hierarchical structure. The method starts in block 402 where first and second cyclic groups Γ ₁ and Γ ₂ of elements are generated. In block 404, select a function

makes the function

One element of the second cyclic group Γ ₂ can be generated from two elements of the first cyclic group Γ ₁ . function Preferably a viable pairing, as described above. In block 406 a root generator P ₀ of the first cyclic group Γ ₁ is selected. In block 408, a random root key is chosen to generate a ciphertext s ₀ , which is associated with the root PKG 302 and known only to the root PKG 302 . s ₀ is preferably an element of the cyclic group Z/qZ. In block 410 a root key generation parameter Q ₀ =s ₀ P ₀ is generated. Q ₀ is preferably an element of the first cyclic group Γ ₁ . In module 412, a first function H ₁ is selected such that H ₁ can generate an element of the first cyclic group Γ ₁ from the first string of binary numbers. In module 414, a second function H ₂ is selected such that H ₂ can generate a second string of binary numbers from an element of the second cyclic group Γ ₂ . The functions of blocks 402 through 414 are all integral to the HIDE root setup algorithm described above, and preferably all complete at approximately the same time. As an example, functions such as those disclosed in Boneh-Franklin can be used as _H1 and _H2 .

The next series of blocks (blocks 416 to 424) illustrate the functions performed as part of the low-level setup algorithm. In module 416, a common element P _zi is generated for each of the n predecessor low-level PKGs of the receiver. Each common element P _zi =H ₁ (ID ₁ , . . . , ID _zi ) is preferably an element of the first cyclic group Γ ₁ , where 1≤i≤n. Although represented by a single module, the generation of all common elements P _zi needs to be performed for a period of time instead of being completed all at once.

Select a low-level key for each of the n predecessors low-level PKG 304a, b, d of the receiver to generate ciphertext s _zi (block 418). The lower-level key-generating ciphertexts _szi are preferably elements of the cyclic group Z/qZ, where 1≤i≤n, and each lower-level key-generating ciphertext _szi is preferably known only to its associated lower-level PKG. Similarly, although it is represented by a single module, the selection of all low-level key generation ciphertexts _zi needs to be performed for a period of time instead of being completed all at once.

One low-level secret element S _zi is generated for each of the sender's n predecessor low-level PKGs (block 420 ). Each low-level secret element S _zi = S _z(i-1) + s _z(i-1) P _zi is preferably an element of the first cyclic group Γ ₁ , where 1≤i≤n. Although it is represented by a single module like the public element P _zi and the ciphertext s _zi , the generation of all the secret elements S _zi also needs to be done for a period of time instead of being completed all at once. For the sake of these repeated key generation processes, S ₀ may be defined as the identity element of Γ ₁ .

A low-level key generation parameter Q _zi is also generated for each of the receiver's n predecessors low-level PKGs (block 422 ). Each key generation parameter Q _zi =s _zi P ₀ is preferably an element of the first cyclic group Γ ₁ , where 1≤i≤n. Similarly, although represented by a single module, the generation of all key generation parameters Q _zi also needs to be performed for a period of time instead of being completed all at once.

The functions of the next two blocks (blocks 424 and 426) are performed as part of the decimation algorithm described above. In block 424 a receiver common element P _z(n+1) related to receiver z is generated. The recipient common element, P _z(n+1) =H ₁ (ID _z1 , . . . ID _z(n+1) ), is preferably an element of the first cyclic group Γ ₁ . Then in block 426 a recipient secret element S _z(n+1) related to recipient z is generated. the recipient secret element, $S_{z(\mathrm{no}+1)}=S_{\mathrm{zn}}+{\mathrm{the\; s}}_{\mathrm{zn}}{P}_{z(\mathrm{no}+1)}={\mathrm{\Σ}}_{i=1}^{\mathrm{no}+1}{\mathrm{the\; s}}_{z(i-1)}{P}_{\mathrm{the\; zi}},$ Preferably also an element of the first cyclic group _Γ1 .

For convenience, the first function H ₁ can be chosen as an iterative function, so that for example H ₁ (P _z(i-1) , ID _zi ) instead of H ₁ (ID ₁ , . . . ID _zi ) to calculate the common point P _i .

The last two blocks shown in Figure 4 (blocks 428 and 430) represent the encryption and decryption algorithms described above. In block 428, the message M is encoded to generate a ciphertext C. The encoding process preferably uses at least root key generation parameter Q ₀ and ID tuples (ID _z1 , . . . ID _z(n+1) ). The encrypted text C is then decoded to recover the message M in block 430 . The decoding process preferably uses at least the low-level key generation parameters Q _zi and the receiver secret element S _z(n+1) , where 1≤i≤n.

The modules shown in Figure 4 do not have to appear in exact sequence. For example, a sender who knows the identity of the receiver can encrypt the communication before the receiver has the private key.

Now, referring to FIG. 5 and FIG. 6, the specific application of the parameters and elements mentioned in the encoding and decoding of the message M and the ciphertext C will be described in detail. The flowchart shown in FIG. 5 illustrates a method of encoding and decoding a digital message M communicated between a sender y and a receiver z, according to another presently preferred embodiment of the present invention. In this scheme, called Basic HIDE, the root setup, low-level setup, and decimation algorithm are all the same as in the embodiment shown in blocks 402 to 426 in FIG. 4 . The flow diagram shown in Figure 5 illustrates the encryption and decryption algorithm, which begins in block 528a with the selection of a random encryption parameter r. r is preferably an integer in the cyclic group Z/qZ. Then in module 528b, the encrypted text C is generated by using the formula C=[U ₀ , U ₂ , . . . , U _n+1 , V]. The encrypted text C includes elements U _i =rP _zi , where i=0 and 2≤i≤n+1, and these elements are related to the position of the receiver in the hierarchical structure. The other components of the ciphertext C are the actual message in encrypted form, $V=m\⊕h_2\left(g^r\right),$ in $g=\hat{e}(Q_0,P_{z1}).$ Element g is preferably a member of the second cyclic group _Γ2 . After the message is encoded, it can be decrypted according to the basic HIDE decryption algorithm in which the formula $m=V\⊕h_2\left(\frac{\hat{e}(u_0,S_{\mathrm{no}+1})}{{\mathrm{\Π}}_{i=2}^{\mathrm{no}+1}\hat{e}(Q_{i-1},u_i)}\right),$ The message M is recovered from the encrypted text C (block 530).

Full HIDE

Using known methods to make one-way encryption schemes secure against chosen ciphertext attacks, the basic HIDE scheme can be transformed into a full HIDE scheme with chosen ciphertext security in the random oracle model. A full HIDE scheme with selected ciphertext security will now be described with reference to FIG. 6 .

The flowchart shown in FIG. 6 illustrates a method of encoding and decoding a digital message M communicated between a sender y and a receiver z, according to another presently preferred embodiment of the present invention. In this embodiment of the invention, the root setup, low-level setup, and decimation algorithm are the same as the embodiment described with reference to FIG. 4, except that the root setup algorithm of this embodiment requires two additional functions. Thus, the flowchart shown in Figure 6 begins with the selection of additional functions (blocks 615a and 615b) and continues with the encryption and decryption algorithms (blocks 628a to 630d).

The root setting algorithm is completed by selecting a third function _H3 (block 615a) and a fourth function _H4 (block 615b). The third function _H3 is preferably capable of generating an integer of the cyclic group Z/qZ from two strings of binary numbers. The fourth function _H4 is preferably capable of generating a binary string from another binary string.

The encryption algorithm begins at block 628a, which shows the selection of a random binary string σ. Then, the random binary string σ is used to generate a random integer r=H ₃ (σ, M, W), as shown in block 628b. where W is the symmetric encryption of the actual message M. The encryption is preferably generated using a symmetric encryption algorithm E with H ₄ (σ) as the encryption key. corresponding, $W={\mathrm{E.}}_{h_4\left(\mathrm{the\; s}\right)}\left(m\right).$ In block 628c, the encrypted text C=[U ₀ , U ₂ , . . . , U _n+1 , V, W] is generated. The ciphertext C includes elements U _i =rP _zi , where i=0 and 2≤i≤n+1, which are related to the receiver's position in the hierarchical structure. The second component of the ciphertext C is the encrypted form of the random binary string σ, $V=\mathrm{\σ}\⊕h_2\left(g^r\right),$ in $g=\hat{e}(Q_0,P_{z1}).$ Element g is preferably a member of the second cyclic group _Γ2 . The third component of the ciphertext C is W, which, as mentioned above, is the actual message in symmetric encrypted form.

The decryption algorithm starts at block 630a, which shows the recovery of the random binary string σ. The random binary string σ is obtained using the formula $\mathrm{the\; s}=V\⊕h_2\left(\frac{\hat{e}(u_0,S_{\mathrm{no}+1})}{{\mathrm{\Π}}_{i=2}^{\mathrm{no}+1}\hat{e}(Q_{i-1},u_i)}\right)$ restored. Then use the formula $m={\mathrm{E.}}_{h_4\left(\mathrm{the\; s}\right)}^{-1}\left(W\right)$ Message M is recovered from ciphertext C (block 630b). Encrypted text can be checked to verify internal consistency. For example, an experimental random integer r'= _H3 (σ, M, W) may be generated, as shown in block 630c. Then, U ₀ =r'P ₀ and U _i =r'P _zi can be checked using the experimental random integer r' in block 630d, where 2≤i≤n+1. If established, the encrypted text C can be considered as authentic.

Dual Basic HIDE and Dual Full HIDE

The dual HIDE concept described with reference to FIGS. 2 and 3 can be applied to basic HIDE and full HIDE schemes. When both the sender and the receiver are in a hierarchical structure, as shown in Figure 3, double HIDE enables them to improve the efficiency and security of their encrypted communication. Applying double HIDE to basic HIDE and full HIDE schemes requires determining additional information, mostly through the low-level setup algorithm described above. For example, a common element P _yi , a low-level key generation ciphertext s _yi , a low-level secret element S _yi , and a low-level key generation parameter Q _yi must be decided for m predecessors low-level PKGs of the sender. Note, however, that these parameters are preferably the same for the low-level PKG that is the common predecessor of sender y and receiver z, so that the analysis is performed on sender y and receiver z (that is, for all i ≤ l Preferably there are: P _yi =P _zi , s _yi =s _zi , S _yi =S _zi and Q _yi =Q _zi ). Double HIDE also requires determining a sender public element P _y(m+1) and a sender secret element S _y(m+1) for the sender, using the same method as described above for determining these parameters for the receiver .

With these additional parameters, the message M can be encoded according to the double-HIDE principle to generate an encrypted text C. The encoding process uses the low-level key generation parameters Q _yi (where i≥l) and the sender’s secret element S _{y ( m+1)} , but the low-level key generation parameter Q _yi with i<l will not be used. Similarly, low-level key generation parameters Q _yi (where i ≥ l) and receiver secret element S _z(n+1) are used when decoding the encrypted text C to recover the message M, but i<l is not used. Low-level key generation parameters Q _zi .

For example, in the basic HIDE scheme (Fig. 4 and Fig. 5), the application of double HIDE changes the encoding of the message M to generate a ciphertext C=[U ₀ , U _l+1 , . . . , U _n+1 , V], where for i=0 and l+1≤i≤n+1, U _i =rP _zi , where $V=m\&CirclePlus;h_2\left(g_{\mathrm{yl}}^r\right),$ and among them $g_{\mathrm{yl}}=\frac{\hat{e}(P_0,S_{\mathrm{the\; y}(m+1)})}{{\mathrm{\&Pi;}}_{i=l+1}^{m+1}\hat{e}(Q_{\mathrm{the\; y}(i-1)},P_{\mathrm{yi}})}.$ The calculation of the U _i factor is the same as before, but only a small part of it needs to be calculated. However, double basic HIDE requires sender y to generate _g yl using more key generation parameters Q _yi than are necessary to generate g as described above. This is because the identity of the sender is included in the encryption algorithm.

The efficiency improvement of the decryption algorithm is even more astonishing. Message M is exploited

$m=V\&CirclePlus;h_2\left(\frac{\hat{e}(u_0,S_{z(\mathrm{no}+1)})}{{\mathrm{\&Pi;}}_{i=l+1}^{\mathrm{no}+1}\hat{e}(Q_{z(i-1)},u_{\mathrm{the\; zi}})}\right)$ restored. Again, fewer U _i parameters are required. Similarly, the receiver needs fewer key generation parameters Q _zi for double HIDE than would otherwise be necessary.

Full HIDE can also be modified to create a dual full HIDE scheme. The generation of encrypted text C in the encryption algorithm is modified as C=[U ₀ , U _l+1 ,..., U _n+1 , V, W], where for i=0 and l+1≤i≤n+ 1. There is U _i =rP _zi . The parameters W and r are still generated in the same way, $W={\mathrm{E.}}_{h_4\left(\mathrm{the\; s}\right)}\left(m\right),$ and $V=\mathrm{\&sigma;}\&CirclePlus;h_2\left(g_{\mathrm{yl}}^r\right)$ parameters in $g_{\mathrm{yl}}=\frac{\hat{e}(P_0,S_{\mathrm{the\; y}(m+1)})}{{\mathrm{\&Pi;}}_{i=l+1}^{m+1}\hat{e}(Q_{\mathrm{the\; y}(i-1)},P_{\mathrm{yi}})}.$

In the double full HIDE scheme, the decryption algorithm is also modified. The random binary string σ is exploited $\mathrm{\&sigma;}=V\&CirclePlus;h_2\left(\frac{\hat{e}(u_0,S_{z(\mathrm{no}+1)})}{{\mathrm{\&Pi;}}_{i=l+1}^{\mathrm{no}+1}\hat{e}(Q_{z(i-1)},u_{\mathrm{the\; zi}})}\right)$ restored. In addition, the recovery of message M is unchanged.

Although these dual HIDE schemes have been illustrated with PKG ₁ 304b as the lowest common predecessor PKG of sender y and receiver z, PKG ₁ 304b can be any common predecessor PKG. Encryption and decryption algorithms are the same. But for highest efficiency, PKG _l 304b is preferably the lowest common predecessor PKG.

In addition to the increased efficiency, the double HIDE scheme of the present invention provides greater security by limiting key escrow. In the Basic HIDE and Full HIDE schemes described above, all PKGs of the receiver's immediate predecessors are able to decrypt messages addressed to the receiver. However, since the double HIDE scheme adds the key generation ciphertext of PKG _1-1 (the direct predecessor of _PKG 1), the ciphertext is unknown to the public predecessor PKG above PKG _1-1 , so those public predecessor PKGs cannot Decrypt messages between sender y and receiver z.

Key escrow can be further restricted so that even PKG ₁ 's immediate ancestors cannot decrypt messages between sender y and receiver z. This can be done by hiding PKG _l in the process of generating private keys for sender y and receiver z (or for a PKG that is a descendant of PKG _l and is also a predecessor of sender y and receiver z) of the private key. For example, for some random b∈Z/qZ _{, PKG l 304b can} easily _{change its} private key. The new private key _S'l is also valid, but not known to the immediate parent of _PKGl . Therefore, no PKG above PKG _l can decode an encrypted message sent to receiver z. More specifically, only recipient z's predecessors within the domain of PKG ₁ are able to decrypt messages sent to recipient z.

When PKG ₁ 304b changes its private key by setting S' ₁ := S ₁ + bP ₁ and Q' _1-1 := Q _1-1 + bP ₀ , the new private key is still the same as PKG _1-1 The key generation ciphertext s _l-1 is related because the new private key is derived from a private key generated by PKG _l-1 using s _l-1 . In general, in all the schemes discussed in this paper, a user or PKG can be selected by choosing the value of b _i (where 1≤i≤n) and setting ${S^{\&prime;}}_{z(\mathrm{no}+1)}:=S_{z(\mathrm{no}+1)}+{\mathrm{\&Sigma;}}_{i=1}^{\mathrm{no}}{b}_i{P}_{z(i+1)}$ and Q′ _zi :=Q _zi +b _i P ₀ (where 1≤i≤n), to change its own secret element S _z(n+1) and key generation parameter Q _zi (where 1≤i≤n ). However, for the purposes of the present invention, this new private key is still considered to be related to the original private key and thus also to the initial value of the key generating ciphertext s _zi .

Double HIDE scheme with more efficient encryption and decryption technology

In the double HIDE scheme described above, it is possible to reduce the number of pairing values that the encryptor has to compute by one without increasing the number of pairing values that the decryptor has to compute. For example, the double base HIDE encryption algorithm described above can be modified so that the ciphertext

$C=[P_0,r(P_{\mathrm{the\; y}(l+1)}-P_{z(l+1)}),r{P}_{z(l+2)},K,r{P}_{z(\mathrm{no}+1)},m\&CirclePlus;h_2\left(g_{\mathrm{the\; y}(l+1)}^r\right)],$ in

$g_{\mathrm{the\; y}(l+1)}=\frac{\hat{e}(P_0,S_{\mathrm{the\; y}(\mathrm{no}+1)})}{{\mathrm{\&Pi;}}_{i=l+2}^m\hat{e}(Q_{\mathrm{the\; y}(i-1)},P_{\mathrm{yi}})}=\hat{e}(P_0,S_{\mathrm{the\; y}(l+1)}).$ If the ciphertext is expressed as

C=[U ₀ , U _l+1 , K, U _n+1 , V], then you can use $m=V\&CirclePlus;h_2\left[\frac{\hat{e}(u_0,S_{z(\mathrm{no}+1)})\hat{e}(u_{l+1},Q_{\mathrm{zl}})}{{\mathrm{\&Pi;}}_{i=l+2}^{\mathrm{no}}\hat{e}(Q_{z(i-1)},u_i)}\right]$ to decrypt it.

Likewise, it is also possible to reduce the number of paired values the decryptor must compute by one without increasing the number of values the encryptor must compute. For example, the double base HIDE encryption algorithm can be modified so that the ciphertext $C=[P_0,r{P}_{\mathrm{the\; y}(l+2)},K,r{P}_{\mathrm{the\; y}\left(\mathrm{no}\right)},m\&CirclePlus;h_2\left(g_{z(l+1)}^r\right)],$ in

$g_{z(l+1)}=\frac{\hat{e}(P_0,S_{\mathrm{the\; y}(m+1)})\hat{e}(Q_{\mathrm{yl}},(P_{z(l+1)}-P_{\mathrm{the\; y}(l+1)}))}{{\mathrm{\&Pi;}}_{i=l+2}^m\hat{e}(Q_{\mathrm{the\; y}(i-1)},P_{\mathrm{yi}})}=\hat{e}(P_0,S_{z(l+1)}).$ If the ciphertext is expressed as

C=[U ₀ , U _l+2 , K, U _n , V], then you can use $m=V\&CirclePlus;h_2\left[\frac{\hat{e}(u_0,S_{z(\mathrm{no}+1)})}{{\mathrm{\&Pi;}}_{i=l+2}^{\mathrm{no}}\hat{e}(Q_{z(i-1)},u_i)}\right]$ to decrypt it.

Certified Low Level Root PKG

The efficiency of the above double HIDE scheme can be extended to message senders located outside the hierarchy by creating an authenticated low-level root PKG. To "authenticate", the lower-level PKG, the root PKG can propose an additional parameter, such as a random message M'. Then, the lower-level PKG "signs"M', generating a signature Sig = S _zl + s _zl P _M' , where S _l is The private key of the low-level PKG, s _l is the ciphertext generated by its low-level key. The low-level PKG will also publish Q _i corresponding to 1≤i≤t.

With an authenticated lower-level root PKG, a sender located outside the hierarchy can send an encrypted message to a receiver z without computing the common element P _zi of all n predecessor PKGs of the receiver. The sender can more efficiently encrypt messages using parameters corresponding to the low-level authentication root PKG. Specifically, the sender calculates P _zi =H ₁ (ID ₁ , . . . , ID _zi )∈Γ ₁ , where l+1≤i≤n+1. Then the sender picks a random r∈Z/qZ and generates encrypted text $C=[P_0,r{P}_{z(l+1)},...,r{P}_{z(\mathrm{no}+1)},m\&CirclePlus;h_2\left(g_{\mathrm{zl}}^r\right)],$ in

$g_{\mathrm{zl}}=\frac{\hat{e}(P_0,\mathrm{Sig})}{\hat{e}({\mathrm{the\; s}}_{\mathrm{zl}}{P}_0,P_{m^{\&prime;}})}=\hat{e}(P_0,S_{\mathrm{zl}}).$ Assuming the received ciphertext C=[U ₀ , U _l+1 ,..., U _n+1 , V], the receiver can decrypt the ciphertext to recover the message $m=V\&CirclePlus;h_2\left[\frac{\hat{e}(u_0,S_{z(\mathrm{no}+1)})}{{\mathrm{\&Pi;}}_{i=l+1}^{\mathrm{no}+1}\hat{e}(Q_{z(i-1)},u_i)}\right],$ where S _z(n+1) is the recipient's private key.

Distributed PKG

To further protect the key generation ciphertext of the above HIDE schemes and make these schemes robust against dishonest PKGs, the key generation ciphertext and the private key can be distributed using known threshold encryption techniques.

More Efficient Encryption Technology

By merging the top two levels in the hierarchy into a single root PKG, the efficiency of the encryption techniques used for the HIDE scheme described above can be increased. In that case, $g=\hat{e}(Q_0,P_1)$ is included in the system parameters. This saves the encryptor from the task of computing this pairing value. However, the decryptor has to compute an additional pairing (which is its result at the next level of the tree).

HIDS program

Considering now the signature scheme or HIDS scheme of the present invention, the flowchart shown in FIG. 7 shows a method of generating and verifying a digital signature according to another presently preferred embodiment of the present invention. The method is implemented in a HIDS system containing multiple PKGs. The PKG includes at least one root PKG and n lower-level PKGs in the hierarchical structure between the root PKG and the sender or signer, where n≥1. In module 702, the root PKG selects a root key known only by the root PKG to generate ciphertext. This root key generating ciphertext can be used to generate private keys for PKGs or users below the root PKG in the hierarchy. Then in module 704, the root PKG generates a root key generation parameter according to the root key generation ciphertext. In block 706, the low-level PKG selects the low-level key to generate ciphertext. The lower-level key generation ciphertext associated with a given lower-level PKG can be used to generate private keys for PKGs or users lower in the hierarchy than the associated lower-level PKG. Similar to the root key-generating ciphertext, each lower-level key-generating ciphertext is known only to its associated lower-level PKG. In block 708, low-level key generation parameters are generated for each of the n low-level PKGs. The generation of each low-level key generation parameter requires at least the low-level key generation ciphertext of its associated low-level PKG.

In block 710, a low-level PKG generates a private key for the recipient such that the private key is associated with at least one of the n low-level key-generating ciphertexts. For example, the sender's private key may at least be associated with the low-level key-generating ciphertext of the PKG that issued the private key to the recipient. However, the recipient's private key is preferably related to the lower key-generating ciphertexts of all its n predecessors PKG as well as the root key-generating ciphertext. In block 712, the sender signs the message using at least its private key and generates a digital signature. Then in block 714, the recipient or verifier verifies the digital signature using at least one of the low-level key generation parameters. For example, the signature can be verified using only the root key generation parameters. Alternatively, one or more of the low-level key generation parameters may also be utilized.

使得该函数能够由第一循环群Γ₁的两个元素生成第二循环群Γ₂的一个元素。函数

最好是一种可行的配对，如上所述。在模块806中选取第一循环群Γ₁的一个根生成器P₀。在模块808中，选取一个随机根密钥生成密文s₀，该密文与根PKG 302相关且只有根PKG 302知道。s₀最好是循环群Z/qZ的一个元素。在模块810中产生一个根密钥生成参数Q₀＝s₀P₀。Q₀最好是第一循环群Γ₁的一个元素。在模块812中，选取一个第一函数H₁，使得H₁能够由第一串二进制数生成第一循环群Γ₁的一个元素。在模块814中选取一个第二函数H₃，使得H₃能够由第二循环群Γ₂的一个元素生成第二串二进制数。模块802至814的功能都是上述HIDS根设置算法的组成部分，并且最好都在大致相同的时刻完成。作为示例，比如那些在Boneh-Franklin中公开的函数就可以被用作H₁和H₃。实际上，函数H₁和H₃可以是完全相同的函数。但是会有一个潜在的隐患。一名攻击者可能尝试让签署人签署M＝ID_t，其中ID_t代表了一个实际身份。在这种情况下，签署人的签名实际上会是一个私有密钥，此后该密钥可被用来解密消息及伪造签名。但是，通过采用某些能够区分签名与私有密钥提取的手段——比如一个比特前缀或为H₃采用不同的函数，该隐患是可以避免的。The flowchart shown in FIG. 8 shows a method of generating and verifying a digital signature Sig of a digital message M between a sender y and a receiver z according to another presently preferred embodiment of the present invention transfer. As shown in FIG. 3 , sender y 306 is m+1 levels below the root PKG in the hierarchy and is associated with ID tuples (ID _y1 , . . . , ID _y(m+1) ). The sender's ID tuple includes identity information ID _y(m+1) related to the sender, and identity information ID _yi related to each of its m predecessors and lower-level PKGs in the hierarchical structure. The method begins at block 802 by generating first and second cyclic groups Γ ₁ and Γ ₂ of elements. In block 804, select a function

makes the function One element of the second cyclic group Γ ₂ can be generated from two elements of the first cyclic group Γ ₁ . function

Preferably a viable pairing, as described above. In block 806 a root generator P ₀ of the first cyclic group Γ ₁ is selected. In block 808, a random root key is chosen to generate a ciphertext s ₀ , which is associated with the root PKG 302 and known only to the root PKG 302 . s ₀ is preferably an element of the cyclic group Z/qZ. In block 810 a root key generation parameter Q ₀ =s ₀ P ₀ is generated. Q ₀ is preferably an element of the first cyclic group Γ ₁ . In module 812, a first function H ₁ is selected such that H ₁ can generate an element of the first cyclic group Γ ₁ from the first string of binary numbers. In module 814, a second function H ₃ is selected such that H ₃ can generate a second string of binary numbers from an element of the second cyclic group Γ ₂ . The functions of blocks 802 through 814 are all integral to the HIDS root setup algorithm described above, and are preferably all performed at approximately the same time. As an example, functions such as those disclosed in Boneh-Franklin can be used as _H1 and _H3 . In fact, functions H ₁ and H ₃ can be exactly the same function. But there will be a potential hidden danger. An attacker may try to get the signer to sign M=ID _t , where ID _t represents an actual identity. In this case, the signer's signature would actually be a private key, which could then be used to decrypt the message and forge the signature. However, this hidden danger can be avoided by adopting some means that can distinguish the signature from the extraction of the private key—such as a bit prefix or a different function for _H3 .

The next series of blocks (blocks 816 to 824) illustrate the functions performed as part of the low-level setup algorithm. In module 816, a common element P _yi is generated for each of the m predecessor low-level PKGs of the sender. Each common element P _yi =H ₁ (ID ₁ , . . . , ID _yi ) is preferably an element of the first cyclic group Γ ₁ , where 1≤i≤m. Although represented by a single module, the generation of all common elements P _yi needs to be performed for a period of time instead of being completed all at once.

Select a low-level key for each of the sender's m predecessors low-level PKG 304a, b, d to generate ciphertext s _yi (block 818). The low-level key-generating ciphertexts s _yi are preferably elements of the cyclic group Z/qZ, where 1≤i≤m, and each low-level key-generating ciphertext _syi is preferably known only by its associated low-level PKG. Similarly, although it is represented by a single module, the selection of all low-level key generation ciphertexts _yi needs to be performed for a period of time instead of being completed all at once.

One low-level secret element S _yi is generated for each of the sender's m predecessor low-level PKGs (block 820 ). Each low-level secret element S _yi =S _y(i-1) +s _y(i-1) P _yi is preferably an element of the first cyclic group Γ ₁ , where 1≤i≤m. Although the same as the public element P _yi and the ciphertext s _yi are represented by a single module, the generation of all the secret elements S _yi also needs to be performed for a period of time instead of being completed all at once. For the sake of these repeated key generation processes, S ₀ may be defined as the identity element of Γ ₁ .

A low-level key generation parameter Q _yi is also generated for each of the sender's m predecessor low-level PKGs (block 822 ). Each key generation parameter Q _yi =s _yi P ₀ is preferably an element of the first cyclic group Γ ₁ , where 1≤i≤m. Similarly, although represented by a single module, the generation of all key generation parameters Q _yi also needs to be performed for a period of time, rather than being completed all at once.

The functions of the next two blocks (blocks 824 and 826) are performed as part of the decimation algorithm described above. In block 824 a sender public element P _y(m+1) related to sender y is generated. The sender common element, P _y(m+1) =H ₁ (ID _y1 , ... ID _y(m+1) ), is preferably an element of the first cyclic group Γ ₁ . A sender secret element Sy _(m+1) related to sender y is then generated in block 826 . the sender secret element, $S_{\mathrm{the\; y}(m+1)}=S_{\mathrm{ym}}+{\mathrm{the\; s}}_{\mathrm{ym}}{P}_{\mathrm{the\; y}(m+1)}={\mathrm{\&Sigma;}}_{i=1}^{m+1}{\mathrm{the\; s}}_{\mathrm{the\; y}(i-1)}{P}_{\mathrm{yi}},$ Preferably also an element of the first cyclic group _Γ1 .

For convenience, the first function H ₁ can be chosen as an iterative function, so that for example H ₁ (P _y(i-1) , ID _yi ) instead of H ₁ (ID ₁ , ... ID _yi ) to calculate the common point P _i .

The last two blocks shown in Figure 8 (blocks 828 and 830) represent the signing and verification algorithm described above. In block 828, the message M is signed to generate a digital signature Sig. This signing process preferably uses at least the sender secret element S _y(m+1) . The digital signature Sig is then verified in block 830 . The verification process preferably uses at least the root key generation parameter Q ₀ and the low level key generation parameter Q _yi . The specific usage of these parameters and elements when signing the message M and verifying the digital signature Sig will now be explained with reference to FIG. 9 .

The flowchart shown in FIG. 9 shows a method of generating and verifying a digital signature Sig of a digital message M between a sender y and a receiver z according to another presently preferred embodiment of the present invention transfer. In this scheme, the root settings, low-level settings, and decimation algorithms are all the same as in the embodiment shown in blocks 802 to 826 in FIG. 8 . Therefore, the flowchart shown in FIG. 9 starts in block 927a by selecting a sender's key to generate a ciphertext _sy(m+1) , which is known only to the sender y. In block 927b, a sender key generation parameter Q _y(m+1) associated with the sender is generated using the formula Q y(m+1) =s _{y(m+1) P 0} . The signing algorithm then generates a message element P _M =H ₃ (ID _y1 , . . . , ID _y(m+1) , M) from the sender in block 928a. The message element _PM is preferably a member of the first cyclic group _Γ1 . The digital signature Sig itself is generated in block 928b using the equation Sig= _Sy(m+1) + _{sy(m+1) PM} . The receiver passes the verification equation $\frac{\hat{e}(P_0,\mathrm{Sig})}{\hat{e}(Q_{\mathrm{the\; y}(m+1)},P_m){\mathrm{\&Pi;}}_{i=2}^{m+1}\hat{e}(Q_{\mathrm{the\; y}(i-1)},P_{\mathrm{yi}})}=\hat{e}(Q_0,P_1)$ Whether it is satisfied to verify the digital signature Sig.

Herein, the present invention has been described in detail with reference to the preferred embodiments and illustrated examples of the present invention, but it should be understood that various changes and improvements can be realized within the spirit and scope of the present invention.

Claims (48)

1. A computer-implemented encryption method for encrypting a message M for decrypting ciphertext information of an intended recipient entity E in a hierarchical encryption scheme, the method comprising: (1) Obtain variable value r; (2) Obtain a first encryption of said message M, which can be decrypted using the value g ^r , where g is the value of a predefined function at the value ê(p0,p1); ê: G ₁ ×G ₁ →G ₂ is a non-degenerate bilinear map, where G ₁ and G ₂ are groups, and ê, G ₁ and G ₂ will be used for decryption; p0, p1 are elements of _G1 , at least one of which depends on the ID of the previous generation of E in the hierarchical encryption system; (3) Obtain the first ciphertext part, including a plurality of values, each value is an element of the group _G1 and is a linear expression of a value of the form rF, where each F is the ID of E and/or at least one previous generation of E A predefined function of where at least one value F depends on the ID of at least one ancestor of E; and (4) Generate a ciphertext formed using the first encryption of the first ciphertext portion and the message M. 2. A method according to claim 1, wherein said first ciphertext part does not depend on M. 3. A method according to claim 1 or 2, wherein said hierarchical encryption scheme is such that: The root entity E ₀ generates its ciphertext integer s ₀ ; Each entity E _i of the previous generation of E with hierarchical level i>0 generates its own ciphertext integer s _i ; For each integer i∈[1,t], where t > 1 is the hierarchical level of E and where E _t = E, each entity E _i gets a value equal to S _i-1 + s _i-1 P _i , and Set the ciphertext S _i of E _i to the value equal to S _i-1 + s _i-1 P _i or a value obtained by modifying the value equal to S _i-1 + s _i-1 P _i , where each P _i is a function of one or more IDs including the ID of E _i , and S ₀ is the identity element of G ₁ , P _i can be used for said decryption; Each entity E _i (i∈[1, t-1]) generates element Q _i , and Q _i =s _i P ₀ , each entity E _i (i∈[2, t-11]) is all k∈[ 1,i-1] obtains a set of elements Q _k , and modifies one or more Q _k or keeps them unmodified to correspond to S _i , and entity E _t receives elements Q ₁ ,...,Q _t-1 . 4. The method according to claim 3, wherein for at least one value i ∈ [2, t-1], E _i sets S _i equal to S _i-1 + s _i-1 P _i , and element Q _k is not replaced by E _i Revise. 5. The method according to claim 3, wherein for at least one value i∈[2,t−1]: E _i generates one or more variable integer values b _c for one or more integer values c ∈ [1, i-1], and uses said values equal to S _i-1 + s _i-1 P _i to generate S _i as the sum of the values b _c P _{c + 1} ; and E _i modifies the element Q _k by replacing the element Q _c with Q _c +b _c P ₀ for each said c. 6. A method according to claim 3, wherein each F is a linear expression of one or more elements _P0 , ..., _Pt such that the values F together define all P0 _, ... except _Pj , the value of _Pt ; For some j∈[1,t-1], g=ê(Q ₀ ,P _j ), and g ^r can be calculated as follows ${\mathrm{<span\; class="notranslate">\; g</span>}}^{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; =</span>\frac{\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&NotEqual;</span>\mathrm{<span\; class="notranslate">\; j</span>}}\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}$ where U ₀ =rP _{0 ,} each U _i =rP _i . 7. The method according to claim 6, wherein said value F is a value _Pi for all i∈[0,t] such that i≠1 and j=1. 8. The method of claim 3, wherein obtaining the first encryption comprises: Obtaining the value Sig=S _l +s _l P _M' from another entity, l is a chosen integer, l<t, where S _l is not used to encrypt said message M, and PM _' is available for encryption, and the product s _l P ₀ is used as Q ₁ for encrypting said message M; Calculate g: $\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; =</span>\frac{\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; Sig</span>}<span\; class="notranslate">\; )</span>}{\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; the\; s</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; P</span>}}_{{\mathrm{<span\; class="notranslate">\; m</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}<span\; class="notranslate">\; )</span>}$ where g ^r can be calculated as follows ${\mathrm{<span\; class="notranslate">\; g</span>}}^{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; =</span>\frac{\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}$ where U _i =rP _i for each i∈[l+1,t]; and The value F together defines P ₀ and all P _l+1, . . . , P _t . 9. The method according to claim 8, wherein g=ê(P ₀ , S _l ). 10. The method according to claim 3, wherein: performing the method on behalf of an entity E _ym at level m in a hierarchical encryption scheme and a descendant of some E _l for which l<t; For each entity E _yi of the previous generation of E _ym with grade i>0, generate the corresponding ciphertext integer s _yi ; For each integer i ∈ [1, m], each entity E _yi obtains the ciphertext S yi of E _yi from a value equal to S _{y (i-1)} + s _y(i-1) P _yi , where each P _yi is a function of one or more IDs including the ID of E _yi and can be used for decryption, and S _y0 is the identity element of G ₁ ; Each entity E _yi (i∈[1,m-1]) generates an element Q _yi , Q _yi =s _yi P _0, obtains a set of elements Q _yk for all k∈[1,i-1], and provides The modified or unmodified elements Q _yk and Q _yi give E _y(i+1) . 11. The method according to claim 10, wherein: $\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; =</span>\frac{\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; ym</span>}}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; m</span>}}\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; yi</span>}}<span\; class="notranslate">\; )</span>}$ and g ^r can be calculated as follows ${\mathrm{<span\; class="notranslate">\; g</span>}}^{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; =</span>\frac{\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}$ where U _i =rP _i for each i∈[l+1,t]; and The value F together defines P ₀ and all P _l+1, . . . , P _t . 12. The method according to claim 11, wherein from s _l and s _yl are generated separately as variable values. 13. The method according to claim 10, wherein s _yl =s _l , and $\mathrm{<span\; class="notranslate">\; g</span>}<span\; class="notranslate">\; =</span>\frac{\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; ym</span>}}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; m</span>}}\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{{\mathrm{<span\; class="notranslate">\; Q</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}_{\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; yi</span>}}<span\; class="notranslate">\; )</span>}$ and g ^r can be calculated as follows ${\mathrm{<span\; class="notranslate">\; g</span>}}^{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; =</span>\frac{\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; )</span>\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span>{{\mathrm{<span\; class="notranslate">\; Q</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}_{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{{\mathrm{<span\; class="notranslate">\; Q</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}$ where U _l+1 = r(P _y(l+1) -P _l+1 ), and for i=0 and for each i∈[l+2,t], U _i =rP _i , and The values F together define P ₀ , P _y(l+1) −P _l+1 , and all of P _l+2, . . . , P _t . 14. The method according to claim 3, wherein P _i is a function of (ID _{1 ,} . . . , ID _i ) for each i>1. 15. A computer-implemented decryption method for recovering a message M from a ciphertext C representing a ciphertext possessing E obtained using one or more values obtained from one or more previous generations of E in a hierarchical encryption scheme An entity E of information, the ciphertext information of E comprises elements S(E) of group _G1 , where S(E) is a linear combination of the first members of group _G1 , in which each first member is associated with A corresponding integer coefficient is associated, the first member comprising one or more first elements of the group _G1 , each depending on the ID of E, the first member comprising one or more second elements of the group _G1 , each independent of the ID of E, the method includes: (1) Calculate the value g _r according to the following: ciphertext C; element S(E); and a set of one or more elements Q of group _G1 ; where each element Q is independent of the ciphertext C, but depends on the coefficients of one or more first and second elements, where the value g _r does not depend on the ID of E but depends on the coefficients of one or more second elements, The value g _r is calculated as a function of the ratio A/B, where: (i) A is the first product of one or more elements of the group _G2 , the one or more elements of the first product include an element that is a bilinear nondegenerate map ε on two elements: G ₁ ×G ₁ →G ₂ , of which at least one element depends on S(E) and at least one element depends on ciphertext C; and (ii) B is a second product of one or more elements of the group _G , the one or more elements of said second product comprising one or more elements each equal to the value of the map ε over the two elements, At least one of the two elements depends on one or more elements Q and at least one depends on the ciphertext C; (2) Use the value g _r to recover the message M from C. 16. A method according to claim 15, wherein operation (2) does not use any information of the coefficients of said first element other than that present in A and/or B and/or ciphertext C 17. A method according to claim 15, wherein operation (2) does not use any information on E's ID other than that present in A and/or B and/or ciphertext C. 18. A method according to claim 17, wherein the value _gr depends on the ID of one or more previous generations of E. 19. The method of claim 15, wherein the coefficients of the first elements are each a ciphertext of a previous generation of E and cannot be used to decrypt E. 20. The method of claim 19, wherein the coefficients of the second elements are each a ciphertext of a previous generation of E and cannot be used to decrypt E. 21. The method of claim 15, wherein one or more of said second elements are dependent on the ID of one or more ancestors of E. 22. The method according to claim 15, wherein $\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; E.</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}{\mathrm{<span\; class="notranslate">\; the\; s</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}$ in: t>1 is the grade of E; {P _i } is the first member and {s _i-1 } is the coefficient; For each i ∈ [1, t-1], E _t = E and E _i is the parent of hierarchical level i of E, and where for each i < t, P _i is a function of ID _i , which ID _i is the ID of the corresponding entity E _i , but P _i is independent of any ID _k for any k >i; and For one or more integers i∈[1,t], said one or more elements Q are one or more elements Q _i =s _i−1 P _{0 ,} where P ₀ is a predefined element of group G ₁ . 23. The method according to claim 22, wherein ${\mathrm{<span\; class="notranslate">\; g</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; =</span>\frac{\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; E.</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&NotEqual;</span>\mathrm{<span\; class="notranslate">\; j</span>}}\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}$ in j is an integer selected in [1,t-1]; The elements U _0, U _i (1≤i≤t}, i≠j) are obtained from the ciphertext C. 24. The method of claim 23, wherein each U _i = rP _i , where r is an integer for which E is not available. 25. The method according to claim 22, wherein one of the following conditions (a) or (b) holds: $<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; g</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; =</span>\frac{\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; E.</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}$ in: l is an integer selected in [2,t-1]; Obtain said elements U _0, U _i (i=l+1,...,t) from said ciphertext C; $<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; b</span>}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; g</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; =</span>\frac{\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; )</span>\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}$ in: l is an integer selected in [2,t-2]; Obtain said elements U _0, U _i (i=l+2, . . . , t) from said ciphertext C 26. The method of claim 22, wherein said hierarchical encryption scheme is such that: Each entity E _i (0≤i<t) generates its own ciphertext integer s _i ; For each integer i ∈ [1, t], each entity E _i obtains E _i 's ciphertext S _i from a value equal to S _i-1 + s _i-1 P _i , where S(E) = S _t and where S ₀ is the identity element of G ₁ ; Each entity E _i (i∈[1,t-1]) generates Q _i and Q _i =s _i P ₀ , for all k∈[1,i-1], each entity E _i (i∈[2 , t−1]) obtain a set of elements Q _k and modify one or more Q _k or leave it unmodified to correspond to S _i . 27. A computer-implemented key extraction method for a hierarchical encryption scheme comprising a plurality of entities, each entity being associated with an encrypted ciphertext value S ("S value"), the encrypted ciphertext value S being a group _G1 An element of , the method includes, representing one of said entities _{, an entity E t-1} with hierarchical level t-1, where t > 1 and where the root entity E ₀ has hierarchical level 0: (1) Obtain the first ciphertext value corresponding to E _t-1 from the data received by the immediate predecessor of E _t-1 ; (2) Obtain the S value S _{t-1 of E t-1} from the first ciphertext value corresponding to E _{t- 1} ; (3) For each of one or more direct descendants E _t of E _t-1 : Obtain a value P _t that is a function of the ID of E _t and is an element of the group G ₁ ; generating data comprising the value S _t-1 + s _t-1 P _t as a first ciphertext value corresponding to E _t , where st _t-1 is the ciphertext value generated by E _t-1 ; and Providing said data comprising said first ciphertext value S _t-1 + st _-1 P _t to E _t such that E _t generates a ciphertext S value of E _t . 28. The method according to claim 27, wherein t>2, wherein operation (2) comprises setting S _t-1 equal to said first ciphertext value corresponding to E _t-1 , and the method further comprises, representing E _{t -1,} : For each level i of 1≤i≤t-2, obtain the elements Q _i of group G ₁ , each element Q _i is associated with the parent E _t-1 of level i; For each direct descendant E _t of E _t-1 , provide elements Q _i (1≤i≤t-2) and Q _t-1 to E _t , where Q _t-1 is generated by E _t-1 as Q _{t- 1} = s _t-1 P ₀ , where P ₀ is a predefined common element of group G ₁ , where P ₀ is independent of descendant E _t and entity E _t-1 . 29. The method according to claim 27, wherein t > 2, wherein operation (2) comprises generating one or more variable integer values b _c for one or more selected values c ∈ [1, t-2], and setting S _t-1 is equal to the sum of the value b _c P _c+1 and said first ciphertext value corresponding to E _t-1 ; Wherein the method further comprises, representing E _t-1 : For each level i of 1≤i≤t-2, obtain the elements Q _i of group G ₁ , each element Q _i is associated with the parent E _t-1 of level i; for each said value c, replace _Qc with _Qc + _bcP0 ; _and then For each direct descendant E _t of E _t-1 : For each direct descendant E _t of E _t-1 , provide elements Q _i (1≤i≤t-2) and Q _t-1 to E _t , where Q _t-1 is generated by E _t-1 as Q _{t- 1} = s _t-1 P ₀ , where P ₀ is a predefined common element of group G ₁ , where P ₀ is independent of descendant E _t and entity E _t-1 . 30. The method of claim 27, wherein Et _-1 has more than one direct descendant _Et , and st _-1 is produced as a single value for all descendants _Et . 31. The method of claim 27, wherein Et _-1 has more than one direct descendant _Et , and a separate value st _-1 is generated for each descendant _Et . 32. A _computer -implemented method of generating a digital signature on a message M for a signatory E _t that is a hierarchy comprising at least entities E _{0 ,} E _{1 ,} ... , E _t , t ≥ 2 Entities of rank t lower than entity E ₀ in a system in which each entity E _i (i=1, . . . , t) is a descendant of entity E _i−1 in the hierarchical system, the method comprising: (1) Obtain the key S _t of the signer, which is a member of the group G ₁ ; (2) Obtain the integer ciphertext s _t of the signer; (3) Generate signature component Sig on message M as value Sig=S _t +s _t P _M in: "+" is the group operation of group _G1 ; and P _M is a value that depends on message M and is a member of group _G1 . 33. A computer-implemented method of verifying a digital _signature on a message M to verify that the digital signature is the correct signature of a signer E _t that includes at least entities E _{0 ,} E _{1 ,} ..., E _t , entities of rank t lower than entity E ₀ in a hierarchical system with t ≥ 2, where each entity E _i (i=1,...,t) is a descendant of entity E _i-1 in the hierarchical system , the method includes: (1) Obtain the signature component Sig, which is an element of the predefined group _G1 ; (2) obtaining one or more values Q _i associated with the respective one or more entities E _i , said one or more values Q _i including the value Q _t ; (3) confirmation $\frac{\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; Sig</span>}<span\; class="notranslate">\; )</span>}{\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; V</span>}$ in: P ₀ is a predefined element of group G ₁ ; Said product ∏ _i ê(Q _i-1 , P _i ) is performed on all integers i in the appropriate subset of integers comprising 1 to t; Each Q _i-1 = s _i-1 P _0, where s _i-1 is the integer ciphertext of entity E _i-1 ; Q _t = s ₀ P _0, where s _i is the integer ciphertext of entity E _t ; ê is the bilinear non-degenerate mapping from G ₁ ×G ₁ to the predefined group G ₂ ; _PM is a value that depends on message M and is a member of group _G1 ; Each P _i depends on the identity of the entity E _i ; V is an element of group _G2 . 34. The method according to claim 32 or 33, wherein: Each entity E _i (i > 0) receives its key S _i from entity E _i-1 ; Each entity E _i (i<t) generates its ciphertext s _i and also generates a key S _i+1 as follows: S _i+1 ＝S _i +s _i P _i+1 and providing the key S _i+1 to said entity E _i+1 ; Each entity E _i (0≤i≤t) generates a value Q _i =s _i P _{0 ,} where P ₀ is a predefined element of group G ₁ . 35. The method of claim 34, wherein said signature component Sig is to be provided to a verifier, wherein for a value i in a subset comprising integers from 0 to t, said verifier accesses a value {Q _i }. 36. The method of claim 35, wherein the subset comprising integers from 0 to t is the set comprising all integers from 1 to t-1. 37. An apparatus for performing a method according to any preceding claim. 38. A device for generating a digital signature according to claim 32. 39. A method according to claim 32 or an apparatus according to claim 38, wherein ${\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}{\mathrm{<span\; class="notranslate">\; the\; s</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}$ where each P _i is a public function of the identity of entity E _i and each s _i-1 is the integer ciphertext of entity E _i-1 . 40. A method or apparatus according to claim 39, wherein in operation (1) the signer obtains S _t from the entity E _t-1 , and in operation (2) the signer generates _st . 41. A method or apparatus according to claim 39, wherein each _Pi is dependent on the identity of each entity _Ej such that 1≤j≤i. 42. A method or apparatus according to claim 39, wherein: Each entity E _i (i>0) receives its key S _i from said entity E _i-1 ; Each entity E _i (i<t) generates its key _si and also generates key S _i+1 as follows: S _i+1 ＝S _i +s _i P _i+1 and providing said key S _i+1 to said entity E _i+1 ; Each entity E _i (0≤i≤t) generates a value Q _i =s _i P _{0 ,} where P ₀ is a predefined element of group G ₁ . 43. A method or apparatus according to claim 42, wherein said signature component Sig is to be provided to a verifier, wherein for a value i in the subset comprising integers from 0 to t, said verifier accesses the value { _Qi }. 44. A method or apparatus according to claim 43, wherein said subset of integers comprising from 0 to t is the set comprising all integers from 1 to t-1. 45. An apparatus operable to verify a digital signature on a message _{M to determine that said digital signature is the correct signature of a signatory E t comprising} at least entities E _{0 ,} E _{1 ,} ... , E _t , an entity of rank t lower than entity E ₀ in a hierarchical system with t≥2, where each entity E _i (i=1,...,t) is a member of entity E _i−1 in the hierarchical system For posterity, this device operation can be used to: (1) Obtain the signature component Sig, which is an element of the predefined group _G1 ; (2) obtaining one or more values Q _i associated with the respective one or more entities E _i , said one or more values Q _i including the value Q _t ; (3) confirmation $\frac{\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; Sig</span>}<span\; class="notranslate">\; )</span>}{\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}\stackrel{<span\; class="notranslate">\; ^</span>}{\mathrm{<span\; class="notranslate">\; e</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; V</span>}$ in: P ₀ is a predefined common element of group G ₁ ; ê is the bilinear non-degenerate mapping from G ₁ ×G ₁ to the predefined group G ₂ ; _PM is a value that depends on message M and is a member of group _G1 ; Each P _i depends on the identity of the entity E _i ; V is an element of group _G2 . 46. The method according to claim 43 or the apparatus of claim 45, wherein said product ∏ _i ê (Q _i−1 , P _i ) is performed on all integers i including from 1 to t except the integer i ₀ , And V=ê(Q ₀ , P _i0 ). 47. A method or apparatus according to claim 46, wherein said product ∏ _i ê(Q _i-1 , P _i ) is performed over all integers i including from 2 to t, and V=ê(Q ₀ , P ₁ ). 48. A method according to claim 33 or an apparatus according to claim 45, wherein: Each entity E _i (i > 0) receives its key S _i from entity E _i-1 ; Each entity E _i (i<t) generates its ciphertext s _i and also generates a key S _i+1 as follows: S _i+1 ＝S _i +s _i P _i+1 and providing the key S _i+1 to said entity E _i+1 ; Each entity E _i (0≤i≤t) generates a value Q _i =s _i P _{0 ,} where P ₀ is a predefined element of group G ₁ .

Images