# Is it meaningful to consider the leakage of master key of KGC?

In the Identity-based cryptography, the user's private key in the systems is delivered by the key generation center(KGC). My question is : Is it meaningful to consider the leakage of master key of KGC? And further, if this happens, then can I think that all the user's private keys disclose?

supplementary part (below)

Actually, in the papers(ID-based key-exchange) that I've read, I rarely encounter the scenarios where the leakage of master key is considered. Maybe(I'm not sure) it's because that since the adversary has the competence to get the master key, then what keys(including user's private keys) it cannot get?

But if we consider from another aspect, if the master key of KGC compromises, then it depends.If the KGC generates the user's private key only as a function of master key and user's identity without adding some additional ephemeral information(e.g. $sk_A=H(ID_A)^{msk}$), then the compromise of master key means the leakage of user's private key. But, if the KGC generates the user's private key also adding some additional ephemeral information(e.g.$sk_A=k+msk*H(ID_A,r)$, where $r=g^k$ is the ephemeral information ), then it's the other way around.Unless the adversary obtains the master key and the ephemeral value, then it can get a user's private key.

So many times, I don't know if the leakage of master key should be considered.

There are plenty of papers on forward-secure IBE, one could just google that term.
Here, I will focus on IBE with a property that I would call "key forgetting",
and work toward a candidate construction for depth-O(1) HIBE with that property.

One could apply either of the sections "Random Oracles, depth-O(1) adaptive-ID security,
and (lack of) Completeness" and "Hashing and Recovery" without applying the other,
but if one applies both then one should apply them in that order.

Discussion and Inherent Limitations:

In such a scheme, the KGC is able to update the main private key (that is, the KGC's secret) in order to "forget" the private key corresponding to a specific ID. $\:$ After it does so, the main private key should
be sufficient to compute the private keys corresponding to other IDs, but should not be sufficient to
violate confidentiality on that particular ID. $\;\;\;\;$ For n such that $\: 2\hspace{-0.04 in}\cdot \hspace{-0.04 in}n \leq 2^L \:$, $\:$ one can consider an
arbitrary set B of $\:2\hspace{-0.04 in}\cdot \hspace{-0.04 in}n\:$ identities whose lengths are each $L$, and imagine having the KGC forget the provide keys corresponding to an $n$-element subset S of B. $\:$ Confidentiality implies that encrypting a
long random plaintext for an ID in B, having the KGC run extract on that ID, and applying decryption
with its output to the ciphertext, should have a negligible probability of resulting in the original plaintext.
On the other hand, functionality implies that doing the same for an ID in B-S
should have an overwhelming probability of resulting in the original plaintext.
Thus, doing that for each ID in B should have an overwhelming probability of recovering the set S.
Since there are at least 2^n such subsets of B, it follows that the probability of the main
private key being shorter than $\:\lfloor n/2\rfloor\:$ bits long is at most negligibly more than $\:1/2^{\lfloor n/2\rfloor}\;$.
Thus the size of the main private key must grow at least
linearly with the number of secret keys forgotten so far.

Now, suppose additionally that the scheme has sufficient completeness to make the next sentence true.
The not-necessarily-feasible procedure that takes as input (the public key and) the main private
key and outputs the set of IDs for which the extract procedure has a probability greater than
half of neither giving a valid private key nor successfully blaming anyone else for that failure,
always outputs a subset of the set of IDs for which the KGC has run the "forget" procedure.
Furthermore, confidentiality and computational soundness of the blame testing implies that
the procedure I just described should have an overwhelming probability of outputting all of
the IDs for which the KGC has run the forget procedure, which means the main private key is
overwhelmingly likely to uniquely determine that set of IDs. $\:$ Thus, that completeness condition
essentially requires the KGC to store a list of all IDs for which it has run the forget procedure.

Those limitations apply even to IBE schemes that only need confidentiality to hold for random IDs.

Positive Results from BTE:

Binary Tree Encryption directly allows for the construction of
selective-ID HIBE for fixed-depth-and-fixed-piece-length IDs with key-forgetting at each level, by just concatenating the parts of the IDs together to determine the relevant node, and to forget a key, store the keys corresponding to the nodes that differ from the relevant node in their last bit but nowhere else, and then erase the keys corresponding to the nodes that are prefixes of the relevant node.

Although potential encryptors would have to be informed somehow,
any KGC at any level could otherwise independently, by putting the time period before the ID, implement forward-security and revocation at the additional cost of requiring decryptors
to get a private key during each time period, which would also make it so that the KGC's
storage requirements only depend on the keys forgotten during the current time period.

By, for example, putting a 1 before each "real" part of IDs and appending an
all-zero ID-piece, one can use IDs of bounded depth, rather than just fixed depth.
By using a prefix-free code, one can also handle IDs whose pieces have bounded length,
although the next part of this answer will assume the ID-pieces are still fixed-length.

Random Oracles, depth-O(1) adaptive-ID security, and (lack of) Completeness

In order to go from selective-ID security to adaptive-ID security in the Random Oracle Model, one picks a Random Oracle whose inputs are interpreted as having two parts, the main one of which will be IDs, and whose outputs are much longer than its inputs, and an XOR-almost-universal family of hash functions whose domains are the space of IDs and whose codomains are the set of
bit strings whose lengths are each the same unit fraction of the oracle's output length.
(Multiplication in a binary field is an example of such a hash family.) $\:$ The master private key is has ident_set and func_set both initialized as empty sets, along with what the master private key would
be for the selective-ID scheme with ID-piece lengths equal to the length of the oracle's outputs.
The public key contains a list of [that fraction's denominator] claimed samples from that hash family, one of which was generated by the master KGC and the others of which weren't, the public key for
the selective-ID scheme, and a random string that will be used as the minor part of the oracle's input.
As long as the hashes chosen all do not depend on that random string (in particular, if they are all chosen before the random string), confidentiality will hold even if the hashes are all chosen maliciously.

For any real ID, let F(ID) denote the list that is [[the random oracle applied to the random string and the real ID-piece] xor [the concatenation of the hashes of the real ID-piece]] for each piece of the real ID. $\:$ To encrypt and decrypt, use F(ID) in the selective-ID scheme. $\:$ To forget a user's private key, the KGC puts ID and F(ID) into the sets ident_set and func_set respectively, and then runs the selective-ID scheme's forgetting procedure on F(ID). $\:$ To extract, a KGC does as follows: if F(ID) is not in func_set then run the selective-ID scheme's extract algorithm on F(ID) and return that algorithm's output,
else if ID is in ident_set then reject, else [indicate a completeness failure, find the value ID' ident_set such that F(ID') = F(ID), and give the pair ID,ID' as a publicly-verifiable proof that all of the hashes in the public key came from a particular subset of their values that, unconditionally, is exponentially unlikely].
The last part is somewhat unsatisfying, since I don't see any
reason why one shouldn't hope for perfect completeness.

Although potential users would have to be informed somehow, any KGC at
any level could otherwise independently use a different list of such hashes.

The resulting bounded-depth-and-fixed-piece-width HIBE scheme is such that attacking an ID
that differs in at most $\Delta$ pieces from a pre-selected ID of depth at most d, by making at most
q Random Oracle queries, corresponds to attacking the selective-ID scheme on one of a list of
of at most $\:((\Delta \hspace{-0.04 in}+\hspace{-0.04 in}d\hspace{.03 in})\hspace{-0.02 in}\cdot \hspace{-0.02 in}(1\hspace{-0.04 in}+\hspace{-0.04 in}q))^{\Delta}\:$ randomly chosen IDs. $\;\;$ In particular, the resulting scheme is
adaptive-ID secure for IDs of depth O(1), where the constant does not need to be chosen a-priori.

Hashing and Recovery

In order to remove the fixed-ID-length restriction, one can try hashing IDs.
However, the issue is that completeness when IDs collide.
That can be dealt with by using a collision-resistant (cryptographic) hash family such that each
hash is associated with a unique and computationally-indistinguishable-from-uniform secret,
one can efficiently sample pairs consisting of one of those hashes and the secret for that hash,
and one can efficiently recover that secret from a hash collision.
(I will give a candidate construction of such families at the bottom of this answer.)

I'm getting really bored with typing this up, so for now I'll just say that
the KGC encrypts its original key with the hash, so that it will be able to
decrypt that and preserve completeness whenever it sees a collision.
Hopefully I'll finish this sometime soon.

The hash families I'm talking about are given by a (strongly) hard-core function and
concatenation of Pedersen commitments, for groups of known prime order p such that
there is an efficiently-computable, but not necessarily efficiently invertible, injective map
from the group to {0,1,2,3,...,n-2,n-1} for a known n such that (p^2)/((p^2)-n) is noticeable,
and the secret is the concatenation of values of the hard-core function on the discrete logs.

• how to understand the notion of "securely forget"? – T.B Mar 1 '14 at 9:28
• sorry I still don't understand what you are talking about, I think your answer needs improving. – T.B Mar 2 '14 at 3:11

Disclaimer: I am not familiar with Identity-Based Key Exchange, know only the most basic Identity-Based Encryption setup, and restrict to that. For other than trivialities, I refer to Ricky Demer's answer.

The defining property of Identity-Based Encryption is: a user's ID and the KGC's public key is all it takes to encipher; and a user gets from a Key Generation Center what it takes to decipher (in other words, a user's private key) only after demonstrating that he or she is entitled to the ID. If the master key of the KGC leaks to an adversary (at least, in the state that it had when the KGC was originally setup), then, for any ID, this adversary can perform whatever the legitimate KGC would have done on request of a user's private key from a user pretending to be entitled to the ID, only skipping the demonstration of being entitled to the ID; then the adversary can perform whatever the user legitimately entitled to the ID would have done, including deciphering anything enciphered with the intention to be deciphered only by a user entitled to the ID.

Thus yes, it is meaningful to consider the leakage of a KGC's master key. The consequence in a basic Identity-Based Encryption scheme is that confidentiality of all messages (past and future) is lost. This disastrous consequence of KGC master key leakage is bound to apply to any IBE system where communication of enciphered messages to enrolled users is unidirectional, and the secret information held by the KGC remains unchanged over use, regardless of if ephemeral information is involved in generating a user's private key. Update: If the secret information held by the KGC is allowed to change at each use, it can be arranged that it looses the ability to generate a user private-key that already was distributed; that preserves the confidentiality of messages (past and future) enciphered with the intention to be deciphered by those users who obtained their private key before the leakage. That's covered in more depth in Ricky Demer's answer.

Note: The confidentiality of user private keys (or whatever users entitled to some IDs actually get from the KGC) is not necessarily lost, if after a randomized user key generation the KGC zeroized the user's key, any randomness used in this process, and other ephemeral information; but I do not see that it makes any difference with respect to the confidentiality of messages in the basic IBE setup.

• I think zeroizing the master secret of the KGC renders the role of the KCG quite useless, i.e., the KCG can no longer issue private keys to users. However, this strategy could be used in some specific scenarios, e.g., if all user keys are generated at some specific point in time and no new keys w.r.t. the same public parameters of the KCG are requested at some later point in time. – DrLecter Mar 1 '14 at 23:19
• – user991 Mar 2 '14 at 21:36
• Also, Binary Tree Encryption is trivially sufficient for bounded-id-length, selective-id IBE which has the property sought, where the total storage required grows linearly with the number of user keys forgotten so far. $\:$ (By information-theoretic arguments, that growth must be at least linear, although one could hope for better dependence on the security parameter.) $\:$ If one uses a KDF $\:$ (continued ...) $\hspace{1.47 in}$ – user991 Mar 3 '14 at 0:14
• (... continued) $\:$ and a collision-resistant hash family that can be sampled along with a unique secret that can be recomputed from any collision, then one can remove the bounded-id-length condition. $\:$ If one additionally has a fixed-input-length random oracle, then one can replace selective-id security with full security at the cost of there being a special setup string such that completeness (but not confidentiality) will fail for an exponentially small fraction of those setup strings. $\;\;\;$ – user991 Mar 3 '14 at 0:15
• (Most prime-order groups allow the conversion of an arbitrary discrete logarithm instance into such a hash family for which the secret is the solution to the discrete logarithm instance.) $\:$ – user991 Mar 3 '14 at 1:13

For ordinary key exchange, leaking Alice's private key obviously allows the adversary to impersonate Alice to other people, but should not allow the adversary to (e.g.) impersonate Bob to Alice, or compromise sessions from the past.

I am not familiar with identity-based key exchange, but I would expect something similar to apply. After the key has leaked, the adversary will be able to impersonate anyone to anyone, but he should not be able to compromise sessions from the past, nor compromise future sessions that the adversary observes passively.

If you consider the obvious identity-based analogue of Needham-Schroeder-Lowe using identity-based encryption instead of public key encryption, it fails badly under master key compromise.

If you consider the obvious identity-based analogue of Signed Diffie-Hellman using identity-based signatures instead of digital signatures, it does not fail under master key compromise.

So yes, compromise of the master key should be interesting for identity-based key exchange.

• yes, it's interesting, so you mean that it has meaning to consider the leakage of master key of KGC. But, the truth is I rarely encounter the paper in which it's considered. In general, maybe people don't consider this problem. – T.B Mar 3 '14 at 23:40