An Identity based Encryption Scheme based on Quadratic

An Identity based Encryption Scheme
based on Quadratic Residues



In Public Key
Crypto system, it is required to know the Public Key of Receiver to encrypt the
messages. So that receiver can decrypt the message using his/her own private
key.  This system needs to maintain
directories which holds Public Keys of each user. To eliminate the need of
maintaining such directories, this paper suggests computing the public key
using receiver’s identity such as Email address. However, implementation of
such system which is secure and practical, is difficult. The system uses Quadratic
Residues modulo a large composite integer. 2


What is Quadratic Residues?

“If m and a are coprime integers, then a
is called a quadratic residue modulo m
if the congruence   has a solution. “1


Congruent Meaning:

” if
m divides (a – b). Also,  if and only if a mod m = b mod m. For Example, 15 mod 4 = 3 mod 4 = 3.” 3


Jacobi symbol:

“The Jacobi
symbol, written (n/m) is defined for positive odd m as


Where  ” 4



The system has an
authority that generates public modulus M, which is universally available (Publicly

M = PQ

P and Q are kept
Private (Secret) by Authority, also they are congruent to 3 mod 4. System also
uses secure hash function, which is publicly available.

If Alice wants to
receive a message from Bob, she gets Private Key from authority by presenting
her own identity. On the other end, Bob uses Alice’s public identity (key) to
encrypt the data for Alice. Here, Public key Dictionary is not Required.


Description of System:

Hash function is
applied to the string representing Alice’s identity and a value  has been calculated by authority, such that
Jacobi Symbol  for all values of a. This is universally known process, anyone knowing Alice’s
identity can calculate .  One who does not know the factorization of M,
can calculate Jacobi Symbol easily.

As  then,

will be square modulo of both P and Q. Hence,
a is square modulo of M.

Also, P and Q are
congruent to 3 mod 4,

Thus, a or
-a will be Quadratic Residues modulo
P and Q.


Only authority
can determine the square root of modulo M
and provide it to Alice. Here, we call it r


If Bob wants to
send data to Alice, he will generate a Transport key and perform Symmetric Key
Encryption using that key. Then, he sends it to Alice bit by bit.

Let’s say,  is
the single bit of transport key, coded as +1
or -1. Bob will choose a value t at a random modulo M, such that Jacobi Symbol

Then, he sends  to Alice

recovers the bit  as follows,

it follows Jacobi Symbol  

 Here, Alice knows the value of r, using that she will calculate value

Bob need to
double up the Key data as he is not aware whether Alice uses root of a or -a. He will select random t to send
 bits, and send There
is no way to avoid sending this extra amount of data. 2


Implementation Aspects:

System is not
very much expensive in terms of computation. If transport key is K bits long,
then Alice need to compute K Jacobi Symbols and Bob will need to compute K
divisions mod M and K Jacobi Symbols.



Each bit of
Transport key requires size up to M for bandwidth.

Bob Does not know
whether Alice uses square root of a or -a, hence, he must double key data.  



It can be used in
offline applications such as Email.


Security Analysis:

Factorization of
M can be used to break the system. Also, M and r values need to compute in
shared fashion, so that master secret can’t be on single location.

This scheme is
vulnerable against Chosen Ciphertext Attack. Attacker can modify each bit of
transport key at a time while transmission and by observing the decryption,
attacker can compute transport key bit. It has been suggested to add some
redundancy to transport key, so that a small part of randomly chosen message
will be decrypted correctly. If the entire decrypted message is not correct,
then system will give an error of invalid message output.