Cocks IBE scheme

Setup

The PKG chooses:

1. a public RSA-modulus n = p q , where p , q , p ≡ q ≡ 3 mod 4 are prime and kept secret,
2. the message and the cipher space M = { − 1 , 1 } , C = Z n and
3. a secure public hash function f : { 0 , 1 } ∗ → Z n .

Extract

When user I D wants to obtain his private key, he contacts the PKG through a secure channel. The PKG

1. derives a with ( a n ) = 1 by a determistic process from I D (e.g. multiple application of f ),
2. computes r = a ( n + 5 − p − q ) / 8 mod n (which fulfils either r 2 = a mod n or r 2 = − a mod n , see below) and
3. transmits r to the user.

Encrypt

To encrypt a bit (coded as 1 / − 1 ) m ∈ M for I D , the user

1. chooses random t 1 with m = ( t 1 n ) ,
2. chooses random t 2 with m = ( t 2 n ) , different from t 1 ,
3. computes c 1 = t 1 + a t 1 − 1 mod n and c 2 = t 2 − a t 2 − 1 and
4. sends s = ( c 1 , c 2 ) to the user.

Decrypt

To decrypt a ciphertext s = ( c 1 , c 2 ) for user I D , he

1. computes α = c 1 + 2 r if r 2 = a or α = c 2 + 2 r otherwise, and
2. computes m = ( α n ) .

Note that here we are assuming that the encrypting entity does not know whether I D has the square root r of a or − a . In this case we have to send a ciphertext for both cases. As soon as this information is known to the encrypting entity, only one element needs to be sent.

Correctness

First note that since p ≡ q ≡ 3 mod 4 (i.e. ( − 1 p ) = ( − 1 q ) = − 1 ) and ( a n ) ⇒ ( a p ) = ( a q ) , either a or − a is a quadratic residue modulo n .

Therefore, r is a square root of a or − a :

Moreover (for the case that a is a quadratic residue, same idea holds for − a ):

Security

It can be shown that breaking the scheme is equivalent to solving the quadratic residuosity problem, which is suspected to be very hard. The common rules for choosing a RSA modulus hold: Use a secure n , make the choice of t uniform and random and moreover include some authenticity checks for t (otherwise, an adaptive chosen ciphertext attack can be mounted by altering packets that transmit a single bit and using the oracle to observe the effect on the decrypted bit).

Problems

A major disadavantage of this scheme is that it can encrypt messages only bit per bit - therefore, it is only suitable for small data packets like a session key. To illustrate, consider a 128 bit key that is transmitted using a 1024 bit modulus. Then, one has to send 2 × 128 × 1024 bit = 32 KByte (when it is not known whether r is the square of a or −a), which is only acceptable for environments in which session keys change infrequently.

This scheme does not preserve key-privacy, i.e. a passive adversary can recover meaningful information about the identity of the recipient observing the ciphertext.