Identity-based ElGamal

These are the notes for my talk at toorcon: Seattle 2008.

Mathematical background

We begin with a refresher on the ElGamal cryptosystem. To do so, we need to define an alarmingly valuable mathematical object:

Definition (Group)

A group is a set $G$ together with a binary operation $\cdot : G \times G \rightarrow G$ (whose action is typically denoted by juxtaposition, ie $ab$ denotes $a \cdot b$) satisfying the following:

1. Associativity: $a(bc) = (ab)c$
2. Identity: There exists an element $e \in G$ (called the identity element) such that, for all $a \in G$, we have $ae = ea = a$.
3. Inverses: For all $a \in G$ there exists an element $b \in G$ (called the inverse of $a$) such that $ab = ba = e$.

If, in addition we have that $ab = ba$ for all $a,b \in G$, we say that the group $G$ is commutative.

Throughout the rest of the article, we will let $G$ be a commutative group with identity $e \in G$. If $n$ is a positive integer, and $a \in G$, we define $a^n = \underbrace{a\cdot a \cdots a}_{n\text{ times}}$. We take $a^0 = e$, and take $a^{-1}$ to be the inverse of $a$. Lastly, if $n$ is a negative integer, we take $a^n = (a^{-1})^n$.

Groups are easy to come by in mathematics. Here are some common examples of groups:

1. The real numbers under addition. The identity is 0, and the inverse of a number is just its negative.
2. The set of complex invertible $n\times n$ matrices under multiplication form an important group called the general linear group.
3. If $p$ is a prime number, the non-zero elements of the finite field $\mathbb{Z}/\mathbb{Z}_{p}$ is a group under multiplication. These groups are very popular because they are both easy to come by and also finite in size. The calculations in this group are easy to perform: the elements of the group are simply $1,2,3,...,p-1$, and the operation is just multiplication modulo $p$.
4. If $n$ is a positive integer, then the numbers $0,1,2,...,n-1$ form a group under addition.
5. Elliptic curves are algebraic curves that can be given a group structure in a manner that is inspired by their geometry. When taken as curves over finite fields, their groups are very popular in cryptography — largely because they can be used with the ElGamal cryptosystem.

Some groups have special elements that are capable of representing any other element in the group. We should introduce a definition to capture this behavior:

Definition (Primitive element of a group)

Let $G$ be a commutative finite group. We say that an element $r \in G$ is a primitive element if, for all $a \in G$ there exists an integer $n_a$ such that $r^{n_a} = a$.

Not all finite groups have a primitive element, but many do. For instance, all of the groups from Example 3 above have primitive elements. This fact makes these groups very appealing to users of the ElGamal cryptosystem.

Okay, that’s enough background to introduce ElGamal. So let’s get on with it!

Let $G$ be a finite group, and let $r$ be a primitive element of $G$. Production of a private key is easy: the user selects a random integer $a$. That’s it. Private key created.

The corresponding public key is easy to produce: the user simply publishes $r$ as well as the value $b=r^a$ (which, you’ll recall, is just another element of the group). That’s it. Public key created.

So at this point we should pause and ask a math question: given the knowledge that $r$ is a primitive root of $G$, and given an element $b \in G$, can we always find an integer $a$ such that $r^a = b$? The answer is yes, although it’s not necessarily true that we have an efficient means for doing so. In fact, at present there is no known general purpose algorithm for solving this problem efficiently. This problem is called the Discrete Logarithm Problem, and its difficulty is ultimately what keeps our private key secure.

Okay, so back to the algorithm. We have our public key, so now it’s time to describe the encryption process.

Let $P$ be some plaintext, encoded as an element of our group. To encrypt $P$, we first pick a random integer $k$ and then compute two values: $\gamma = r^k$ and $\delta = b^k\,P$. The pair $(\gamma,\delta)$ is the cipher text.

Decryption is fairly easy. When we receive $(\gamma,\delta)$, we simply compute $\gamma^{-a}\,\delta$, which happens to be equal to $P$. Why is this true? If we look at the algebra, we get the following:

$\gamma^{-a}\,\delta = (r^k)^{-a}(b^k\,P) = r^{-ak}\,r^{ak}\, P = P$.

And that’s ElGamal!

Identity-based ElGamal

Before we can describe Identity-based ElGamal, we should first describe what we mean by identity-based.

Definition (Identity-based cyrptosystem)

We say that a public key cryptosystem is identity-based if a user’s public and private key are functions of their “identity” (typically understood to mean a string associated with a user, such as an email address).

People who are comfortable with public key cryptosystems may already be dubious about whether or not identity-based systems are a good idea. After all, typically we prefer that it be difficult to compute a user’s private key as a function of any public data — but here we are asking that the public key be a function of the user’s identity (which is assumed to be public data)! Overriding this apparent contradiction is the primary task of the identity-based cryptosystem designer.

In order to overcome this difficulty, we will introduce a new player into the cryptosystem. This player will serve as a type of “secret keeper,” in that they will privately posses some kernel of information that is at the heart of the key generation process. In practice, this person may be chosen to be a mail administrator.

Let’s introduce some notation. First, let $I$ denote the set of all identities (in a practical implementation, we can choose this to be the set of email addresses on our mail server). The space of identities probably has more structure to it than a cryptographer would prefer, for reasons that we will discuss shortly. Consequently, in order to mix it up a bit, we’ll also introduce a hash function. Let $T$ be a (finite) set of tokens (for instance, the set of numbers between 0 and 255) and let $h : I \rightarrow T^n$ be a hash function, where $n$ is some fixed integer.

While this may seem notationally heavy, it’s really nothing new to most programmers. For instance, MD5 is a hash function that maps strings into the space $\lbrace 0,1,2,...,255 \rbrace^{16}$.

For each $t \in T$, the Secret Keeper picks an integer $k_t$ that they will keep secret. As in standard ElGamal, they pick a primitive element $r$ of their group. They publish $r$, as well as the values $(t, r^{k_t})$ for all $t \in T$.

To produce a user’s public key, we first take their identity and hash it into $(t_1,t_2,...,t_n)$. We then use the values published by the Secret Keeper. We construct the private key for the user by computing the value

$(r^{k_{t_1}})^1(r^{k_{t_2}})^2\cdots (r^{k_{t_n}})^n$,

which (performing some algebra) is equal to

$(r^{1k_{t_1}})(r^{2k_{t_2}})\cdots (nr^{k_{t_n}}) = r^{1k_{t_1} + 2k_{t_2} + \cdots + nk_{t_n}}.$

This value can then be treated as a public key in standard ElGamal, where the corresponding private key is the value

$1k_{t_1} + 2k_{t_2} + \cdots + nk_{t_n}$.

In order to obtain their private key, a user authenticates himself to the Secret Keeper, who then carries out this computation on their behalf and gives them the final result. This authentication takes place in whatever manner one usually prefers for authenticating to a certificate authority.

So why do we ask that the identities be hashed before we perform key generation? In short, it’s an effort to make it more difficult for users of the system to collaborate to discover some of the $k_t$. In particular, if two users have identities that differ by a single character, and we were not doing any hashing, they could compare their private keys to learn one of the $k_t$. Since identities often do have substrings in common, this is a fairly real concern (this is what I meant when I said that identities have too much structure for cryptographic purposes). By hashing, we distribute identities uniformly across the token space, making these types of overlaps less likely to occur (unless, of course, users selected identities specifically crafted to game the system, although defenses against this type of attack can be implemented in policy rather than math).

Conclusions

So at this point we’ve introduced a modification to the key generation process for ElGamal that enables it as an identity-based encryption system.

Now, the dependence on the Secret Keeper is arguably not desirable in many instances. For instance, in places where absolute secrecy of communications is necessary, we would not wish to trust the Secret Keeper to resist the temptation to use our private key. In this case, we are better off resorting to other cryptosystems.

However, there are many potential users for this system. In corporate mail systems, for instance, it is often sufficient (for most users) to simply have encryption on the wire, with the assumption that a Secret Keeper can be selected who is not properly motivated to betray the trust placed in them.

In situations where the legitimacy of this assumption is not clear, we may choose to adopt a slightly different key generation process that relies on several Secret Keepers in such a manner that no subset of them has enough information to produce a user’s private key. In particular, we can pick $k$ Secret Keepers, each of which performs their part as usual. Each of them has a public and a private key for each user. To produce a user’s public key, simply take the product of each of the Secret Keeper’s public keys for the user. Similarly, a user’s private key is the sum of the Secret Keeper’s private keys for the user. In this scheme, a user would simply authenticate to each of the Secret Keepers and do the final summation themselves. In this way, the cooperation of all of the Secret Keepers is necessary to discover a user’s private key.

Identity based systems such as this offer many benefits:

• Users do not need to have their private key before someone can send them encrypted messaged. Since the public keys are all published, a person can encrypt and send a message, and let the user obtain their private key only after they have already received the message.
• If we like, we can introduce time dependence into the encryption. In particular, we could take a person’s identity to be a combination of their usual identity together with a time stamp. In this way, a user’s key pair changes over time. If we have time stamps with granularity of one month, this allows us to have keys that expire every month! This is particularly desirable for people who need to carry key data on laptops, since were the laptop to be stolen, the keys on it would only be valuable for a short period of time.