FORM 2
THE PATENTS ACT, 1970 (39 of 1970)
&
THE PATENTS RULES, 2003
COMPLETE SPECIFICATION
(See section 10, rule 13)
1. Title of the invention: IDENTITY BASED ENCRYPTION SYSTEM
2. Applicant(s)
NAME NATIONALITY ADDRESS
TATA CONSULTANCY Indian Nirmal Building, 9th Floor, Nariman Point. SERVICES LIMITED Mumbai Maharashtra 400021, India
3. Preamble to the description

COMPLETE SPECIFICATION
The following specification particularly describes the invention and the manner in which it is to be performed.

FIELD OF INVENTION
The present subject matter, in general, relates to encryption systems and, in
particular, relates to identity based encryption and signature generation systems.
BACKGROUND
Encryption is a commonly known process of transforming information using an
algorithm, called cipher, to make it unreadable to anyone except those possessing a passphrase,
usually referred to as a key. In today's world, a lot of information gets transmitted between a
sender and a receiver over communication networks. Encryption is usually done to ensure
authenticity, integrity and confidentiality of information between the sender and the receiver.
Authenticity means to confirm that the information actually originated from the
sender claiming to have sent such information. This is usually done to prevent fraud claims, impersonation, etc. Integrity is to ensure that the information has not been modified or tampered by a third party during the transmission of the information from the sender to the receiver. Confidentiality is to ensure that the information transmitted between the sender and the receiver is not read by a third party i.e. the information is available to only those people entitled to be in possession of it.
Various encryption schemes have been proposed to ensure authenticity, integrity
and confidentiality of data between the sender and the receiver. One of the commonly used encryption scheme is based on Public Key Infrastructure (PKI). PKI is an arrangement that binds public keys with respective user identities of the sender and the receiver by means of a certificate authority (CA). A user identity must be unique within each CA domain. The binding of the user identity and its public key is established through a registration and issuance process, which may be carried out by software at the CA, or under human supervision. The binding of the user identity and its public keys are maintained and assured by a Registration Authority (RA). For each user, the user identity, the public key, their binding, validity conditions and other attributes are made maintained in public key certificates issued by the CA.
Identity-based cryptography is an implementation of PKI in which a publicly
known string or the user identifier representing an individual or an organization is used as a public key. The publicly known string or the user identifier may be an email address, domain name, or a physical IP address, etc. Identity-based systems allow any party to generate the public key from a known identity value such as an ASCII string. A trusted third party, called the Private

Key Generator (PKG), generates corresponding priPvate keys. A private key is available only to the authentic user to decrypt the messages encrypted with the public key.
In operation, the PKG first publishes a master public key, retaining the
corresponding master private key. Given the master public key, any party can compute a public key corresponding to an individual or an organization by combining the master public key with an identity value of the individual or the organization. To obtain a corresponding private key, the party authorized to use the identity of the organization or the individual contacts the PKG, which uses the master private key to generate the private key for identity of the organization or the individual.
As a result, parties may encrypt messages (or verify signatures) with no prior
distribution of keys between individual participants. This is usually used in cases where pre-distribution of authenticated keys is inconvenient or infeasible due to technical restraints. However, to decrypt or sign messages, the authorized user must obtain the appropriate private key from the PKG. A basic assumption of this approach is that the PKG must be highly trusted, as it is capable of generating any user's private key and may therefore decrypt (or sign) messages without authorization.
SUMMARY
The subject matter described herein relates to a method and a system for identity
based encryption, which are further described below in the detailed description. This summary is not intended to identify essential features of the subject matter nor is it intended to be used in determining or limiting the scope of the subject matter.
The present subject matter discloses a method and a system for identity based
encryption. In one implementation, the method for identity based encryption comprises generating a user public-private key pair comprising a user public key and a user private key based in part on a system parameter, wherein the user private key is associated with at least one user identifier. The method further comprises generating an identity based signature based in part on the user public key and the at least one user identifier.
BRIEF DESCRIPTION OF THE DRAWINGS
The above features and aspects and other features and aspects of the subject
matter will be better understood with regard to the following description, appended claims, and accompanying figures. In the figures, the left-most digit(s) of a reference number identifies the

figure in which the reference number first appears. The use of the same reference number in
different figures indicates similar or identical items.
Fig. 1 illustrates an exemplary cryptosystem in accordance with one embodiment
of the present subject matter.
Fig. 2 illustrates an exemplary method for identity based encryption, according to
an embodiment of the present subject matter.
DETAILED DESCRIPTION
The present subject matter discloses a method and a system for identity based
encryption for ensuring authenticity, integrity and confidentiality of information shared between a sender and a receiver.
In conventional identity based encryption systems, an assumption is made
regarding the absolute trustworthiness of the PKG. This is because the PKG is capable of generating any user's private key and therefore may decrypt or sign messages without authorization. Thus, in a situation where a PKG is compromised, all information protected over the entire time period of the public-private key pair used by that PKG is also compromised. To limit the damage due to a compromised or a malicious PKG, the master private-public key pair can be updated with a new independent key pair. However, this introduces a key-management problem where all users must have the most recent public key of the PKG. Further, the PKG may decrypt and/or authenticate any information on behalf on an individual or an organization without authorization. These are serious security limitations which limit the reliability of these conventional identity based encryption systems.
To this end an identity based encryption system, henceforth referred to as the
cryptosystem, which implements a method of identity based encryption is disclosed herein. The cryptosystem achieves Level 3 trust with the Private Key Generator (PKG), which is the highest standard defined in the encryption industry. In Level 3 trust, the PKG can neither compute a secret key nor can impersonate any user or organization without being detected. Additionally, the cryptosystem being an identity-based system does not involve the use of a public key thus increasing the efficiency of the cryptosystem. Further, the cryptosystem uses only the identity of the user or organization to verify a signature making it possible for the signature to be anonymous with respect to the public key leading to more security.

In one embodiment, the cryptosystem involves interaction with four entities, the
users, the PKG, a Trusted Third Party (TTP) and a judge. As apparent, users, like individuals or
organizations, are the ones who use the proposed method of identity based encryption. PKG is
the aforementioned private key generator that generates the master public and private key pair
represented by mpk and msk, respectively, hereinafter. Additionally, the user also generates its
own pair of public and private key represented by upk and usk, respectively, hereinafter. The
TTP is an entity which verifies the association of the user with its upk, while, the judge is a
system which verifies the interaction between the users, the PKG and the TTP.
The method implemented by the cryptosystem uses a security parameter 1 as
input to a global key generator module of the cryptosystem to generate a system parameter
param, the msk and the mpk. In one embodiment, the security parameter 1k may be any k bit long
string of 0's and 1 's. For example, in one embodiment, the security parameter 1 may be of 128
bits. The system parameter param, msk and mpk may be generated from the security parameter
1k using conventional key generation algorithms, such as Advanced Encryption Standard (AES)
algorithm or R.SA algorithm, or a combination of such algorithms. Further, multiple iterations of
a conventional encryption algorithm or multiple iterations of a combination of conventional
encryption algorithms may be used for generation of system parameter param, msk and mpk.
The system parameter param is used as an input to a user key generator module,
by the user to generate its own pair of public and private keys upk and usk. The cryptosystem implements an interactive information exchange between the PKG and the user. The user uses the system parameter param, the upk, the usk and the publicly known string or the user identifier representing the user to interact with the PKG. The publicly known string of the user or the user identifier representing the user, henceforth referred to as the user ID, might be an email address or a domain name, or a physical IP address associated with the user. Similarly, the PKG uses the param, the upk, the ID and the msk to interact with the user. The interaction between the user and the PKG involves the user giving a joining proof Pf to the PKG which shows the association of the user with its public key upk. Usually the TTP certifies the joining proof. In one example, the joining proof may be a digital certificate issued by the TTP with respect to the upk. The issuing of the digital certificate signifies that the TTP acknowledges that the user is associated with the upk. Based on the interaction, the PKG issues the user an identity based key sKid,upk, which is a function of the user ID and the upk.

The user then uses a signing module of the cryptosystem to sign its messages. The
signing module uses the usk the identity based secret key sKid,upk, a message m and the user ID to generate a signature a. The signature a is verified by a verification module of the cryptosystem. The verification module uses system parameter, the mpk, the user ID, the message m and the signature o to verify the authenticity of the signature a. In one embodiment, the verification module is configured to return 1 if the signature σ is authentic and 0 if the signature σ could not be verified as authentic.
In case of failure of authentication of the signature σ, there is an interactive
communication between the PKG, the user and the judge. The judge points out if the failure to authenticate the signature a was due to a malicious PKG trying to forge the user or a malicious user trying to frame the PKG.
Thus, it is seen that though the signature a is generated using usk and a secret key
sKid,upk which is a function of the ID and the upk, the verification of the signature c does not need the upk. This provides anonymity of the signature a with respect to the user public key upk. Further, the cryptosystem achieves Level 3 trust with the PKG, wherein the PKG cannot generate the user's secret key usk or impersonate a user without being detected. Additionally, the cryptosystem is also prevented from being able to disclose the user's secret key usk, sign messages or decrypt messages on behalf of the user fraudulently without being detected. These and other advantages and aspects of the cryptosystem are further discussed in detail in conjunction with the following figures.
Fig. 1 illustrates an exemplary cryptosystem 100 in accordance with one
embodiment of the present subject matter. The cryptosystem 100 can be implemented as any of a variety of computing devices, including, for example, servers, a desktop personal computer, a notebook or portable computer, a workstation, a mainframe computer, a mobile computing device and an internet appliance.
In said embodiment, the cryptosystem 100 includes one or more processor(s) 102,
a memory 104 coupled to the one or more processor(s) 102, input/output interfaces 106, henceforth referred to as interfaces 106, to facilitate user interaction and communication with external network(s), peripheral(s), device(s), system(s), etc.

The processor 102 can be implemented as one or more microprocessors,
microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, or any devices that manipulate signals based on operational instructions. Among other capabilities, the processor 102 can be configured to fetch and execute computer-readable instructions and data stored in the memory 104.
The memory 104 can include any computer-readable medium known in the art
including, for example, volatile memory (e.g., RAM) and/or non-volatile memory (e.g., flash, etc.). The memory 104 includes module(s) 108 and data 110. The module(s) 108 usually includes routines, programs, objects, components, data structure, etc., that perform particular task or implement particular abstract data types.
In one embodiment of the cryptosystem 100, the module(s) 108 include a global
key generator 112, a user key generator 114, a signing module 116 and a verification module
118. Further, the cryptosystem 100 may include other module(s) 120 to provide additional
functionalities and utilities. The data 110 includes an encryption scheme data 122. Further, the
cryptosystem 100 may have other data 124 for performing other functions, etc.
The encryption scheme data 122 stores one or more modes of encryption such as
Digital Signature Algorithm (DSA), RSA, Pretty Good Privacy (PGP), Blowfish, Twofish, Data
Encryption Standard (DES), Advanced Encryption Standard (AES), Carlisle Adams and Stafford
Tavares (CAST), International Data Encryption Algorithm (IDEA), Serpent, etc.
The cryptosystem 100 may interact with four entities, one or more users, a PK.G, a
Trusted Third Party (TTP) and a judge either directly or over a network. The network may be a wireless network, wired network or a combination thereof. The network can be implemented as one of the different types of networks, such as intranet, local area network (LAN), wide area network (WAN), the internet, and such. The network may either be a dedicated network or a shared network, which represents an association of the different types of networks that use a variety of protocols, for example, Hypertext Transfer Protocol (HTTP), Transmission Control Protocol/Internet Protocol (TCP/IP), User Datagram Protocol (UDP), Wireless Application Protocol (WAP), etc., to communicate with each other.
In operation, a security parameter 1k is used as an input to the global key generator
module 112 to generate a system parameter and a master public-private key pair mpk, msk. The security parameter 1 is usually an ASCII string of user specified length. For example, in one

embodiment, the security parameter 1k may be of 128 bits whereas in another embodiment the
security parameter 1k may be an ASCII string of 256 bits. The global key generator module 112
generates the system parameter, the msk and the mpk from the security parameter 1k using
encryption algorithms like Data Encryption Standard (DES) algorithm or RSA algorithm, or a
combination of algorithms retrieved from the encryption scheme data 122. Further multiple
iterations of a conventional encryption algorithm or multiple iterations of a combination of
conventional encryption algorithms may be used for the generation of the system parameter, the
msk and the mpk. Yet in another implementation, a randomized polynomial time complexity
algorithm may be used to generate the system parameter, the msk and the mpk.
The user key generator module 114 generates a pair of public and private key,
represented by upk and usk, for the user. The user generator module 114 uses the system parameter as an input to generate the upk and the usk. However, in one embodiment the user key generator module 114 may use the security parameter 1k to generate the usk and the upk. In another embodiment, the usk and the upk may be generated using a randomized polynomial time complexity algorithm. Further, the usk may also be associated with the identity of the user. In said implementation, the association of the usk and the identity of the user is a one to one association. The association of the usk and the identity of the user vary in each session due to randomization of the identity of the user used in every session making the cryptosystem 100 resistant to any identity spoofing attacks.
The cryptosystem 100 implements an interactive information exchange between
the PKG and the user. The user uses the system parameter, the upk, the usk and the publicly known string representing the user, i.e. the user identifier, to interact with the PKG. In one example, the publicly known string or the user identifier representing the user, henceforth referred to as the user ID, might be an email address or a domain name, or a physical IP address associated with the user.
The PKG uses the system parameter, the upk, the user ID and the msk to interact
with the user. The interaction between the user and the PKG involves the user giving a joining
proof Pf to the PKG which shows the association of the user with its public key upk.
Usually the TTP certifies the joining proof. In one embodiment, the joining proof
may be a digital certificate issued by the TTP with respect to the upk. The issuing of the digital certificate signifies that the TTP has proof of knowledge that the user is associated with the upk.

Based on the interaction, the PKG issues the user an identity based key sKid,upk, which is a function of the user ID and the upk. The joining proof is important to protect the interests of both the users and the PKG.
As stated earlier, the user ID is derived from the usk from a randomized
algorithm, the user ID will vary in every session. However, the usk may remain constant over different sessions. Thus in said implementation, the usk is changed more frequently than its upk making the cryptosystem secure and robust. Since user ID changes in every session, launching of identity spoofing attacks are extremely difficult to execute.
Thereafter the signing module 116 signs the messages to be transmitted by the
user. The signing module 116 uses the usk, the identity based key sKid,upk, the message m and
the ID to generate a signature σ. As mentioned before, since the user ID is different in different
sessions, the signature σ is also different for the same message m in different sessions. This
makes cipher-text or cipher-text only attacks very difficult to execute on the cryptosystem 100.
Further in one embodiment, the signature σ is generated using a probabilistic polynomial time
complexity algorithm which makes guessing of the user ID by an attacker very difficult.
The signature σ is verified by the verification module 118 of the cryptosystem
100. The verification module 118 uses system parameter, the mpk, the user ID, the message m to verify the authenticity of the signature a. In one embodiment, if the signature σ is authenticated by the verification module 118, the verification module 118 returns 1. Likewise, in case the signature σ is not authenticated, a value a 0 is returned. In one embodiment, the verification is done using a deterministic algorithm. In said embodiment, the verification module 118 also accounts for the variation of user ID in every session into consideration.
In case the signature σ is not authenticated, there is an interactive communication
between the PKG, the user and the judge. The judge points out if a malicious PKG trying to forge the user or a malicious user trying to frame the PKG was the cause of the failure in authenticating the signature a. In one implementation, the judge runs a blame algorithm. In said implementation, the blame algorithm is a deterministic algorithm which has the usk as the input and sends a blame request φ to the judge. Since the user ID is different in every session, the input for blame algorithm may be different for each blame request that the user may make. This eliminates a scenario in which a malicious attacker may launch a cipher-text attack and make a false blame request on behalf of the user and hence wrongly implicating the PKG.

Thus, the cryptosystem 100 removes the possibility of a malicious PKG
impersonating a user or a malicious user trying to frame a PKG. Moreover, the cryptosystem 100 prevents a malicious attacker from launching an identity-spoofing attack on a legitimate user or from launching a cipher-text only attack on the valid signature σ on message m of a user. The cryptosystem 100 also ensures that the malicious attacker does not launch an identity-spoofing attack on the PKG. Additionally, the cryptosystem 100 keeps the upk anonymous with respect to the signature o, thus leading to added confidentiality and security.
Fig. 2 illustrates an exemplary method 200 for identity based encryption,
according to an embodiment of the present subject matter. The method 200 may be described in the general context of computer executable instructions. Generally, computer executable instructions can include routines, programs, objects, components, data structures, procedures, modules, functions, etc., that perform particular functions or implement particular abstract data types. The method 200 may also be practiced in a distributed computing environment where functions are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, computer executable instructions may be located in both local and remote computer storage media, including memory storage devices.
The order in which the method 200 is described is not intended to be construed as
a limitation, and any number of the described method blocks can be combined in any order to
implement the method 200, or an alternative method. Additionally, individual blocks may be
deleted from the method 200 without departing from the spirit and scope of the subject matter
described herein. Furthermore, the method 200 can be implemented in any suitable hardware,
software, firmware, or combination thereof. The method 200 is presently provided for identity
based encryption. Although, the method 200 has been described in context of the cryptosystem
100, the same should not be construed as a limitation. It will be apparent that the method 200
may be implemented for identity based encryption in various other similar system and devices.
At block 202, on input of a security parameter lk, the system parameter, the mpk
and the msk are generated. In one implementation, the system parameter, the mpk and the msk may be generated by the global key generator module 112. In said implementation, a randomized polynomial time complexity algorithm may be used to generate the system parameter, the mpk and the msk.

At block 204, the system parameter is used to generate the upk and the usk. For
example, the system parameter may serve as an input to the user key generator module 114
which in turn may generate the upk and the usk. As mentioned previously, various algorithms
like Data Encryption Standard (DES) algorithm or RSA algorithm, or a combination thereof may
be used for the generation of the system parameter, the mpk, the msk, the upk, and the usk. In
one embodiment, the algorithms may be retrieved from the encryption scheme data 122. In one
implementation, a randomized polynomial time complexity algorithm is used to generate the upk
and the usk. In said implementation, the usk is associated with the user ID. As mentioned before,
the user ID may be any string associated with the user such as an e-mail address, domain name,
IP address, etc. The randomized polynomial time complexity algorithm ensures that the usk and
the user ID have a one to one association. Moreover, the association of the usk and the user ID is
different for every session due to randomization of the user ID used in each of the every session.
At step 206 the joining proof of the user is validated. In one embodiment, joining
proof is a certification by the TTP which confirms the user's association with the upk. The
joining proof may be a digital certificate, a physically signed document, etc. The joining proof is
an important parameter when determining whether a malicious PKG is impersonating a user or
whether a malicious user trying to frame a PKG. For example, a malicious PKG can generate an
identity based sKid,upk using any upk generated by the malicious PKG and an honest user cannot
show that upk used is not its public key. On the other hand, a malicious user can claim that upk
used in the identity based key sKid,upk is not its public key and frame an honest PKG.
At block 208, an identity based key sKid,upk is generated based on the user ID and
the upk. In one embodiment, the identity based key sKid,upk is generated by the PKG. As illustrated in block 210, the signature of the user is generated. In one implementation, the signing module 116 uses the usk, the identity based key sKid,upk, the message m and the user ID to generate a signature a.
The signature o is verified at block 212. In the said implementation, the
verification module 118 authenticates the signature σ based on various parameters like system parameter, the mpk, the ID, the message m.
In case the signature Σ is found not to be authentic, at block 214, the verification
module 118 determines if the failure to authenticate the signature σ was due to a malicious PKG impersonating a user or a malicious user attempting to falsify a PKG. In case of failure to

authenticate the signature a, the user generates a blame request φ as a function of the usk. The
blame request φ is sent to the judge. The judge determines whether the blame request φ is related
to the upk. If the blame request φ is determined to be related to the upk, the PKG is requested to
provide a public key upk such that the public key upk is related to the signature σ, the joining
proof showing the user's association with the public key upk and the transcript of the interactive
information exchange between the user and the PKG. In failure to provide any of the above
parameters the PKG is determined to be malicious or else the user is determined to be malicious.
Thus, the cryptosystem 100 implements an identity based encryption scheme. In
this encryption scheme a malicious PKG cannot sign messages or decrypt messages on behalf of
a user. Further, the PKG cannot compute the usk and hence cannot impersonate the user. Since
the signing and verification of the message does not require the use of the upk, the user public
key is kept anonymous with respect to the signature σ and the user ID of the user leading to
added security levels. Additionally, the cryptosystem 100 may be implemented in any client-
server or peer to peer communication system involving various types of communication devices
like computers, laptops, notebooks, mobile phones, pagers, personal digital assistants, etc.
Although embodiments the cryptosystem have been described in language
specific to structural features and/or methods, it is to be understood that the invention is not necessarily limited to the specific features or methods described. Rather, the specific features and methods are disclosed as exemplary implementations for the cryptosystem and method.

We claim:
1. A computer implemented method for encryption, the method comprising:
generating, based in part on a system parameter, a user public-private key pair comprising a user public key and a user private key, wherein the user private key is associated with at least one user identifier;
generating an identity based signature based in part on the user public key and the at least one user identifier.
2. The computer implemented method as claimed in claim 1 further comprising signing a message using the identity based signature.
3. The computer implemented method as claimed in claim 1, wherein the at least one identifier associated with the user private key is different for every session.
4. The computer implemented method as claimed in claim 1, wherein the identity based signature is unique for every session.
5. The computer implemented method as claimed in claim 1 further comprising generating at least one of the system parameter and a master public-private key pair.
6. The computer implemented method as claimed in claim 1 further comprising verifying at least one of the identity based signature and an identity of an user based in part on the user public-private key pair.
7. A cryptosystem (100) comprising:
a processor (102); and
a memory (104) coupled to the processor (102), the memory (104) comprising,
a global key generator module (112) configured to generate at least one of a system parameter and a master public-private key pair; and
a user key generator module (114) configured to generate a user public-private key pair based in part on the system parameter based in part on the system parameter, wherein a user private key of the public-private key pair is associated with at least one identifier of the user.
8. The cryptosystem (100) as claimed in claim 7, wherein the key generator module (114) is
further configured to generate an identity based signature based on the user public key and the at least one identifier of the user.

9. The cryptosystem (100) as claimed in claim 8, further comprising a signing module (116) configured to sign a message using the identity based signature.
10. The cryptosystem (100) as claimed in claim 1, further comprising a verification module (118) to verify at least one of an identity based signature and the identifier of the user based in part of the user public-private key pair.
11. A computer-readable medium having embodied thereon a computer program for executing a method comprising:
generating based in part' on a system parameter, a User public-private key pair comprising a user public key and a user private key, wherein the user private key is associated with at least one user identifier;
generating an identity based signature based in part on the user public key and the at least one user identifier.