Most CS/Math undergrads run into the well-known RSA cryptosystem at some point. But about 10 years ago Boneh and Franklin introduced a practical Identity-Based Encryption system (IBE) that has excited much of the research community and produced a huge flood of follow-up work.

What is IBE exactly and in what way does it improve over conventional public-key systems like RSA?


Conventional public-key cryptosystems require key distribution: in order to encrypt a message destined to Bob, you must know Bob's public key with enough certainty (an attacker could try to substitute his own key there). Various systems have been designed for that, e.g. certificates. In practice, key distribution proves complex.

With IBE, the name (email address) of Bob is his public key, so it is already distributed. To understand it, imagine the following model: there is a trusted central service, to which you send the email; the central service forwards it to Bob, and all communications are encrypted. This is how encrypted communications worked before the invention of RSA, so it is an old model. It has two drawbacks:

  • the central service must be trusted (it has the power to read all emails);
  • the central service must have oversized optic fibers and thousands of processors because every message goes through it.

IBE uses high-level mathematics to remove the second issue. With IBE, the "central service" must exist, but it needs not be "online"; its real-time action is replaced with a mathematical pairing.

Another, more mathematical way to say it, is that with IBE, a central authority has a key pair. The central authority can compute the private key corresponding to a given "public key", where public keys can be just any sequence of bits, e.g. email addresses. You cannot do that with RSA: RSA public keys have a strong internal mathematical structure. With IBE users key pairs, not so. The counterpart of that property is that the central authority public key must be involved in the encryption and decryption processes. In a full-fledged IBE system, users obtain their own private key from the central authority; afterwards, no need to talk to the central authority.

Voltage Security sells IBE-based products (Dan Boneh is one of the founders of that company). The practical point of IBE is to "avoid" certificates. See Voltages pages to get some descriptions of IBE; also, the Boneh-Franklin article is a good source of information. Details on the actual computation of Weil and Tate pairings are intricate; Ben Lynn's thesis is a good starting point.

| improve this answer | |
  • $\begingroup$ There are fairly trivial IBE's done using RSA-style prime number crypto aka "certificate authorities". They work as well as some of the newer pairing based schemes, albeit less efficiently, since they require the generation of new large primes for each public (and private) identity... derived from the master public/private keys. See: ics.uci.edu/~gts/paps/bdt03.pdf $\endgroup$ – Erik Aronesty Mar 23 '18 at 20:00

(An addendum to the answers by Thomas and Poncho:)

One disadvantage of IBE (or advantage, depending on the point of view) is that the central authority knows (or can generate) all private keys, i.e. it allows a global key escrow.

For example, if an email address changes the owner (i.e. there is a new person in a company which now should read the mails addressed to an address), the central agency can give this new person the same private key as the previous one had. (Though there is no way to make sure the previous owner has to forget his key.)

A government could force the central authority either to give the central private key, or selected private keys of individual users, enabling decryption of those messages. This is nice for an intelligence agency which wants to read our mail, but less nice for the users who want their mails to be secret.

If the central private key is stolen, all previously sent messages encrypted using the corresponding public key as a component are now decrypt-able (for anyone who captured them before), not just future ones are affected (which could be solved by key revocation).

Thus, this requires even more trust to the central authority than to the certification authorities in certificate-based systems: not only that the authority (or its current private key) was never compromised in the past (thus creating wrong certificates), but also that it never will be compromised in the future.

An analogue to having multiple certificates (by different certification agencies) for one key would be to use multiple (more or less) trusted central (or now actually decentralized) authorities: split a message in parts such that all ones are needed, and encrypt each one for a different authority's public key (and the receiver's identity, of course). The receiver than would have to obtain his private keys from each authority, decrypt all the parts and combine them again to obtain the message. To read a sent message, an attacker now would have to compromise all the authorities, not just one.

(I'm not sure if this was proposed somewhere already, I just thought about it.) Of course, each authority has to check the receiver's identity before handing them the key, which might make this inpractical in practice. One could use some k-out-of-n secret sharing scheme to make not all authorities needed.

Edit: I just found something similar in the last chapter of Advances in Elliptic Curve Cryptography (page 244): Here Alice (with identity $Q_A$) gets secret keys $[s_1]Q_A$ and $[s_2]Q_A$, where $s_i$ are the private keys of two trusted agencies with public keys $Q_1 = [s_1]P$, $Q_2 = [s_2]P$. Bob then creates $$([t]P, M \oplus H_2(\hat e(Q_A, Q_1 + Q_2)^t)),$$ where $M$ is the message, $t$ a random number, $H_2$ a hash function, $\hat e$ a modified pairing. For decryption of a message $(U,V)$, Alice uses the sum $S_A = [s_1]Q_A + [s_2]Q_A = [s_1 + s_2]Q_A$ of her private keys, by calculating $$ M' = V \oplus H_2(\hat e(S_A, U)).$$ This uses the basic scheme of Boneh and Franklin, published in Identity based encryption from the Weil pairing, 2003.

Of course, this is easily generalizable to any number of trusted agencies, who then must collaborate in order to escrow Alice's key $S_A$.

| improve this answer | |
  • $\begingroup$ global key escrow. That is the simple defintion! $\endgroup$ – kelalaka Oct 19 '19 at 16:36

Well, the quick answer to what is IBE is "it's public key encryption except that someone's public key can be an arbitrary string, rather than something picked by a key generation process".

The first obvious question to above would be "if John Smith can get the private key corresponding to "JohnSmith@company.com", why can't anyone else? The answer is that there's a central authority with the magic formula for converting public keys into private ones; the real John Smith asks for his private key, the central authority authenticates that that's the real John Smith, and then hands him the private key. This magic formula uses its own public/private key pair, where the central authority holds the private key, and the public key is used as a part of the public key encryption method (in addition to the public key of the person you're encrypting to).

Now, as why it is better, well, it does simplify one aspect compared to traditional public key encryption. If you need this one aspect simplified, it's a great help; if you don't need that simplification, there's no benefit.

When you compare the enrollment process between public keys and certificates, it's (at a high level) the same; a node asks a central authority for authentication material, the central authority validates the person being asking, and then hands the node some authentication data (be it a certificate or an IBE private key).

Here's where IBE makes things simpler than public keys and certificates: when it comes time for someone to send an encrypted message to the node, he needs the public key. For IBE, that's easy; he can get it directly from the identity he wants to send the message to. For public key/certificates, he needs to get the certificate. If he can just ask the node he wants to talk to and the node can reply with it, it's easy (and so IBE doesn't have any great benefit). If there is no such back channel (say, for encrypted mail), IBE is a definite improvement.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.