An Identity based Encryption Scheme

based on Quadratic Residues

Introduction:

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

Functionality:

The system has an

authority that generates public modulus M, which is universally available (Publicly

known).

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,

a

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

Where,

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

Alice

recovers the bit as follows,

Also,

it follows Jacobi Symbol

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

of

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

Practical

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.

Issue:

·

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.

Use:

·

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.