CLIAMS:1. A computer implemented method for encrypting data, the method comprising:
obtaining, by a computing device (104), a public key set and public parameters, from a central server (102), wherein the public parameters include a friendly prime (p), a torsion group prime order (q), a super-singular elliptic curve (E/GF(p)), a first torsion group (S[q]), a pre-computed Tate pairing value (Y), a first elliptic curve point (P), a second elliptic curve point (Q), and a distortion map (?), and wherein the pre-computed Tate pairing value (Y) is generated by the central server (102);
determining, by the computing device (104), a receiver key set of elliptic curve points based on a receiver identity (ID) of a receiver, wherein the receiver key set is a subset of the public key set;
computing, by the computing device (104), a receiver public key (Q_id) based on the receiver key set; and
encrypting, by the computing device (104), the data using the Tate pairing value (Y) and an encryption component (Eb) for obtaining encrypted data, wherein the encryption component (Eb) is computed based on the receiver public key set.
2. The method as claimed in claim 1, wherein the determining further comprises ascertaining, by the computing device (104), the receiver ID based on a public identity of the receiver, wherein the receiver ID is a 128 bit sequence.
3. The method as claimed in claim 1, wherein the public key set includes a plurality of elliptic curve points pertaining to the first torsion group (S[q).
4. The method as claimed in claim 3, wherein the public key set is computed using a master secret key set comprising a master secret key (s) and a set of distinct integers(T), wherein the master secret key (s) is an integer selected from the range of 1 to p-1, and wherein each integer in the set of distinct integers (T) is selected from the range of 1 to p-1.
5. The method as claimed in any of the previous claims, wherein the friendly prime (p) is based on a first variable (c) and Nth power of two, wherein N is an integer, and wherein base two logarithm of the first variable (c) has a minimum value greater than zero and a maximum value equal to half the value of the N given by the equation log2c = (1/2)N, and wherein the friendly prime (p) is congruent to 3 (mod 4), and wherein bit length of the friendly prime (p) is of at least 512 bits.
6. The method as claimed in claim 1, wherein the torsion group prime order (q) is a prime of bit length of at least 160 bits.
7. A computer implemented method for encrypting data, the method comprising:
computing, by a central server (102), a Tate pairing value (Y) based on a first elliptic curve point (P) and a second elliptic curve point (Q) using Tate pairing operation;
publishing a public key set and public parameters including at least the Tate pairing value (Y); and
encrypting, by a computing device (104), the data based on the Tate pairing value (Y) and an encryption component (Eb), wherein the encryption component (Eb) is determined based on a receiver public key and a random integer (x) in the range 1 to p-1.
8. The method as claimed in claim 7, wherein the method further comprises:
selecting, by the central server (102), the friendly prime (p) and the torsion group prime order (q);
ascertaining, by the central server (102), the first elliptic curve point (P) and the second elliptic curve point (Q) based on a first torsion group (S[q]), wherein the first torsion group (S[q]) is constructed based on a super-singular elliptic curve (E/GF(p)) determined based on the friendly prime (p);
9. The method as claimed in claim 8, wherein the method further comprises ascertaining a second torsion group (T[q]) based on the first torsion group (S[q]) using a distortion map (?), wherein the second torsion group (T[q]) is an isomorphic image of the first torsion group (S[q]).
10. The method as claimed in claim 9, wherein the method further comprises ascertaining, by the central server (102), the public key set based on a master secret key set and the first elliptic curve point (P), wherein the public key set comprises a plurality of elliptic curve points pertaining to the first torsion group (S[q]), and wherein the master secret key set comprises a plurality of distinct integers in the range 1 to p-1.
11. The method as claimed in any of the preceding claims, where the method further comprises publishing the public key set and the p, q, E/GF(p), S[q], Y, P, Q, and ? as public parameters for encrypting the data.
12. A computing device (104) comprising:
a processor (108-2);
a key generation module (132) coupled to the processor (108-2) to,
obtain public parameters and a public key set, from a central server (102), wherein the public parameters include a friendly prime (p), a torsion group prime order (q), an super-singular elliptic curve (E/GF(p)), a first torsion group (S[q]), a pre-computed Tate pairing value (Y), a first elliptic curve point (P) and a second elliptic curve point (Q), and a distortion map (?), and wherein the pre-computed Tate pairing value (Y) is generated by the central server (102);
determine a receiver key set of elliptic curve points based on a receiver identifier (ID) of a receiver, wherein the receiver key set is a subset of the public key set, wherein the receiver ID is based on a unique identity of the receiver, and wherein the receiver ID is a 128 bit sequence; and
compute a receiver pubic key of the receiver based on the receiver key set of elliptic curve points; and
an encryption module (134) coupled to the processor (108-2) to encrypt data using the Tate pairing value (Y) and an encryption component (Eb), wherein the encryption component (Eb) is computed based on the receiver public key set and a random integer (x) in the range of 1 to p-1.
.
13. A central server (102) comprising:
a processor (108-1);
a parameter generation module (118) coupled to the processor (108-1) to,
select a friendly prime (p) and a torsion group prime order (q);
determine a super-singular elliptic curve over a finite field, wherein the finite field is based on the friendly prime (p);
ascertain a first torsion group (S[q]) and a second torsion group (T[q]) having an order to equal to the value of the torsion group prime order (q) over the super-singular elliptic curve, wherein the second torsion group (T[q]) is an isomorphic image of the first torsion group (S[q]) obtained using a distortion map (?);
obtain a first elliptic curve point (P) and a second elliptic curve point (Q), belonging to the first torsion group (S[q]), wherein the second elliptic curve point (Q) is obtained as a product of a master secret key (s) and the first elliptic curve point (P);
compute a Tate pairing value (Y) based on the first elliptic curve point (P) and the second elliptic curve point (Q) using Tate pairing; and
a communication module (120) coupled to the processor (108-1) to,
publish the p, q, E/GF(p), S[q], Y, P, Q, and ?, as public parameters, and the public key set for encrypting data.
14. The central server (102) as claimed in claim 13, wherein the central server (102) further includes a user key module (122) coupled to the processor (108-1) to compute a private key based on the receiver ID and a private key set, wherein the private key set is generated based on the master secret key set and the receiver ID.
15. The central server (102) as claimed in claim 13, wherein the parameter generation module (118) further,
determines a master secret key set based on the friendly prime (p);
constructs a public key set based on the master secret key set and the first elliptic curve point (P).
16. The central server (102) as claimed in claim 13, wherein the parameter generation module (118) further,
computes the torsion group prime order using , where q is the torsion group prime order, and wherein is the bit length of the torsion group prime order and wherein bits, and wherein k is another integer; and
ascertains p based on the torsion group prime order using the equation , where p is the friendly prime, and q is the torsion group prime order, and t is an integer.
17. A computer implemented method for decrypting data, wherein the method comprises:
receiving, by a computing device (104), encrypted data, wherein the encrypted data is encrypted using a public key and an encryption component, wherein the public key is associated with a public identity of a user;
obtaining, by the computing device (104), a private key corresponding to the public key, wherein the private key is computed based on the public key and a master secret key set, wherein the master secret key set comprises a master secret key (s) and a set of distinct integers (T).
computing, by the computing device (104), a Tate pairing value based on the encryption component and the private key; and
decrypting, by the computing device (104), the encrypted data using the Tate pairing value for obtaining decrypted data.
18. The method as claimed in claim 17, wherein the master secret key (s) is an integer selected from the range of 1 to p-1, and wherein each integer in the set of distinct integers (T) is selected from the range of 1 to p-1, wherein p is a friendly prime based on a first variable (c) and Nth power of two, wherein N is an integer, and wherein base two logarithm of the first variable (c) has a minimum value greater than zero and a maximum value equal to half the value of the N given by the equation log2c = (1/2)N, and wherein the friendly prime (p) is congruent to 3 (mod 4), and wherein bit length of the friendly prime (p) is of at least 512 bits.
19. A computer-readable medium having embodied thereon a computer program for identity based encryption, the method comprising:
obtaining a public key set and public parameters, from a central server (102), wherein the public parameters include a friendly prime (p), a torsion group prime order (q), a super-singular elliptic curve (E/GF(p)), a first torsion group (S[q]), a pre-computed Tate pairing value (Y), a first elliptic curve point (P), a second elliptic curve point (Q), and a distortion map (?), and wherein the pre-computed Tate pairing value (Y) is generated by the central server (102);
determining a receiver key set of elliptic curve points based on a receiver identity (ID) of a receiver, wherein the receiver key set is a subset of the public key set;
computing a receiver public key (Q_id) based on the receiver key set; and
encrypting the data using the Tate pairing value (Y) and an encryption component (Eb), wherein the encryption component (Eb) is computed based on the receiver public key set and a random integer (x) in the range of 1 to p-1.
,TagSPECI:

FIELD OF INVENTION
[0001] The present subject matter relates to cryptography and, in particular, to
identity based encryption.
BACKGROUND
[0002] In today's world, with increasing exchange of information between various
entities, cryptography is being commonly implemented for ensuring safety of the
information being exchanged. Cryptography may be understood as a technique used for
converting the information into an inapprehensible form which may not be easily retraced
by a communicating party other than the intended recipient. Implementation of
cryptography helps in securing the information against malicious attacks, for example, by
hackers. Further, cryptography also preserves the security of the information in a case
where the information is wrongly transmitted to an undesired recipient.
BRIEF DESCRIPTION OF THE FIGURES
[0003] The detailed description is described with reference to the 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 same numbers are used throughout the
figures to reference like features and components. Some embodiments of systems and/or
methods in accordance with embodiments of the present subject matter are now
described, by way of example only, and with reference to the accompanying figures, in
which:
[0004] Figure 1 illustrates a network environment implementing identity based
encryption, according to an embodiment of the present subject matter;
[0005] Figure 2 illustrates a method for generating public parameters and a public
key set for identity based encryption, in accordance with an embodiment of the present
subject matter; and
3
[0006] Figure 3 illustrates a method for identity based encryption of data using
public parameters and public key set, in accordance with an embodiment of the present
subject matter.
DETAILED DESCRIPTION
[0007] With advancement in technology, a lot of information is exchanged
between parties communicating over communication networks, such as the Internet. The
advancement in technology has also led to an increase in threats to security of the
information being exchanged amongst the communicating parties. For instance, the
information may be wrongfully obtained by a malicious third party, say, a hacker, and
may be used in a manner detrimental to the communicating parties.
[0008] In the recent past, cryptography has been widely used for ensuring security
of information transmitted over a communication network. Cryptography is a
methodology of encrypting data, for example, before transmitting data over the
communication network, in such a manner that enables secure transmission of the data
even in the presence of malicious third parties. Thus, even in case the malicious third
parties gain access to the data, the malicious third parties may not be able to use the
encrypted data.
[0009] In one conventional technique involving identity based encryption and
decryption of data over an elliptic curve, i.e., identity based elliptic curve cryptography,
the data which is to be transmitted may be encrypted using a public key of a receiver of
the data. The public key of the receiver may be based on a public identity of the receiver.
The encryption of data, based on the elliptic curve, involves several complex
mathematical operations, for example, computationally intensive Tate pairing operation.
The Tate pairing operation involves several complex computations and thus results in
high consumption of battery, power, and processing resources. Further, such
computations typically involve high computational time. Thus, the encryption of data
may only be supported by devices having large processing capabilities, sufficient
memory, and sufficient battery backup. However, the intensive computations pertaining
to encryption of data may utilize a major portion of the processing resources of such
4
devices, thereby slowing down the other operations handled by the devices. Due to the
complexity involved in such computations and the corresponding intensive processing
requirements, implementation of identity based elliptic curve cryptography may not be
suitable in devices, such as mobile phones, smart phones, sensor nodes, and handheld
devices used for lightweight applications, having less processing power, less memory,
and limited battery backup.
[0010] The present subject matter describes method(s) and system(s) for identity
based elliptic curve cryptography. In one implementation, public parameters including a
Tate pairing value and a public key set generated by a central server may be utilized by a
computing device for encrypting data. As the computing device can encrypt the data
based on a pre-computed Tate pairing value, i.e., the Tate pairing value generated by the
central server, the computing device need not perform the intensive Tate pairing
computations during the encryption process, thereby resulting in an efficient identity
based elliptic curve cryptography scheme. Further, the public parameters and the public
key set generated in accordance with the present subject matter ensures quick
computation of the algorithms associated with identity based encryption in a secure
manner.
[0011] According to an embodiment of the present subject matter, the public
parameters and the public key may be generated by the central server. Initially, a friendly
prime and a torsion group prime order may be selected. The friendly prime and the
torsion group prime order may then be used for determining the other parameters, such as
a super singular elliptic curve, a first torsion group, a first elliptic curve point, a second
elliptic curve point, and a distortion map, included in the public parameters. In one
example, the friendly prime may be generated based on the torsion group prime order of
bit length 160 bits thereby ensuring that the cryptographic scheme based on the friendly
prime and the torsion group prime order is of high security standard. Further, the prime
number and the torsion group selected are of a manner such that which ensures quick
computation of the cryptographic operations.
[0012] Upon selection of the friendly prime and the torsion group prime order, a
super-singular elliptic curve may be generated over a finite field based on the friendly
5
prime. Thereafter, a first torsion group and a second torsion group may be ascertained
based on the super-singular elliptic curve. The first torsion group and the second torsion
group are generated in a form such that the number of points in the first torsion group and
the second torsion group, i.e., the torsion group prime order, is equal to the above
selected torsion group prime order. In one example, the first torsion group may comprise
of all points obtained by repetitive addition of a point lying on the super-singular elliptic
curve to itself until a point at infinity is obtained. Subsequently, a distortion map is used
for generating the second torsion group based on the first torsion group. The second
torsion group is an isomorphic image of the first torsion group.
[0013] Further, a first elliptic curve point and a second elliptic curve point,
hereinafter collectively referred to as elliptic curve points, are selected from amongst the
elements of the first torsion group based on one or more predetermined rules, for
example, no degeneracy. The no degeneracy may be defined as a criterion according to
which bilinear operation on the elliptic curve points should not result in integer value
one. In one implementation, the elliptic curve points may be used for computing the Tate
pairing value. In said implementation, the Tate pairing value may be computed by
performing Tate pairing operation between the first elliptic curve point and the second
elliptic curve point.
[0014] Thereafter, a master secret key set may be ascertained based on the
friendly prime. In one example, the master secret key set may include integers in the
range of one to one less than the friendly prime. Further, as will be understood, the
master secret key set is not shared publically as doing the same may compromise the
security of the encryption scheme. Based on the master secret key set, a public key set
may be determined. The public key set may include a plurality of points pertaining to the
first torsion group. In one implementation, the plurality of points are obtained as a result
of point multiplication of the integers included in the master secret key set with the first
elliptic curve point.
[0015] Subsequently, the friendly prime, the torsion group prime order, the supersingular
elliptic curve, the first torsion group, the elliptic curve points, the distortion map,
6
and the Tate pairing value are published, by the central server, as public parameters along
with the public key set for being used in encryption and decryption of the data.
[0016] As mentioned previously, the computing device may encrypt the data
using the public parameters and the public key set. For the purpose, initially a receiver
identity (ID) of a receiver may be computed. The receiver ID may be generated based on
a known public identity, for example, a mobile number, an email id, and the like, of the
receiver using known hashing techniques. In one example, the receiver ID may be a 128
bit sequence. Thereafter, a receiver public key may be generated by adding all the points
in a receiver key set obtained based on the receiver ID. The receiver public key is used to
encrypt the data which is to be transmitted to the receiver.
[0017] Further, in order to encrypt the data, an encryption component is generated
based on the receiver public key. The computing device may then encrypt the data based
on the encryption component and the Tate pairing value to obtain the data in an encrypted
form, hereinafter referred to as encrypted data. Thus, the encryption of data using the precomputed
Tate pairing value eliminates the need for computing Tate pairing operation by
the computing device, thereby reducing the utilization of resources, such as battery and
processors, required for performing the encryption operation. The encrypted data may
then be transmitted to the receiver over the communication network.
[0018] The system(s) and method(s) of the present subject matter thus reduces the
time required for implementing identity based cryptographic process and enables its use
in devices running lightweight applications by circumventing the computation of Tate
pairing operation while encrypting the data. The encryption scheme may thus be
implemented in devices, such as mobile phones, smart phones, and handheld devices
running lightweight applications, having less computational power, less memory, and
limited battery power. Further, the public parameter and the public key set generated in
accordance with the present subject matter are of a form which reduces the computation
time associated with complex mathematical operations pertaining to encryption and
decryption operations of cryptography.
7
[0019] These and other advantages of the present subject matter would be
described in greater detail in conjunction with the following figures. While aspects of
described system(s) and method(s) for identity based elliptic curve cryptography can be
implemented in any number of different computing systems, environments, and/or
configurations, the embodiments are described in the context of the following exemplary
system(s).
[0020] Figure. 1 illustrates a network environment 100 implementing identity
based encryption, according to an embodiment of the present subject matter. The network
environment 100 includes a central server 102 in communication with a plurality of
computing devices 104-1, 104-2...104-N, hereinafter collectively referred to as
computing devices 104 and individually referred to as a computing device 104, through a
network 106. Communication links between the computing devices 104 and central
server 102 are enabled through a desired form of communication, for example, via dialup
modem connections, cable links, digital subscriber lines (DSL), wireless or satellite
links, or any other suitable form of communication.
[0021] In one implementation, the central server 102 may be implemented as one
or more computing systems, such as a desktop computer, a cloud server, a mainframe
computer, a workstation, a multiprocessor system, a laptop computer, a network
computer, a minicomputer, and a gateway server. Further, the computing devices 104
may be implemented as, for example, personal computers, multiprocessor systems,
laptops, wireless devices, wireless sensors, M2M devices, and cellular communicating
devices, such as a personal digital assistant, a smart phone, and a mobile phone, and the
like.
[0022] The network 106 may be a wireless network, a wired network, or a
combination thereof. The network 106 can also be an individual network or a collection
of many such individual networks, interconnected with each other and functioning as a
single large network, e.g., the Internet or an intranet. The network 106 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. Further, the network
8
106 may include network devices that may interact with the central server 102 and the
computing devices 104 through communication links.
[0023] According to an embodiment of the present subject matter, the computing
device 104-1 may encrypt data using public parameters and a public key set published by
the central server 102. In said embodiment, amongst other parameters, the public
parameters may include a pre-computed Tate pairing value, generated by the central
server 102, which may be utilized by the computing device 104-1 for encrypting the data.
Use of the aforementioned public parameters including the Tate pairing value averts the
computation of Tate pairing value during encryption of the data, thus facilitating
encryption of data using lesser resources as compared to conventional encryption
techniques. The generation of the public parameters and the public key set to be used for
encryption may also be referred to as a setup operation.
[0024] For the purpose, the central server 102 and the computing device 104
include processors 108-1, 108-2, respectively, collectively referred to as processors 108
hereinafter. The processors 108 may be implemented as one or more microprocessors,
microcomputers, microcontrollers, digital signal processors, central processing units, Tate
machines, logic circuitries, and/or any devices that manipulate signals based on
operational instructions. Among other capabilities, the processor(s) is configured to fetch
and execute computer-readable instructions stored in the memory.
[0025] The functions of the various elements shown in the figure, including any
functional blocks labeled as processor(s), may be provided through the use of dedicated
hardware as well as hardware capable of executing software in association with
appropriate software. When provided by a processor, the functions may be provided by a
single dedicated processor, by a single shared processor, or by a plurality of individual
processors, some of which may be shared. Moreover, explicit use of the term processor
should not be construed to refer exclusively to hardware capable of executing software,
and may implicitly include, without limitation, digital signal processor (DSP) hardware,
network processor, application specific integrated circuit (ASIC), field programmable
gate array (FPGA), read only memory (ROM) for storing software, random access
9
memory (RAM), non-volatile storage. Other hardware, conventional and/or custom, may
also be included.
[0026] Also, the central server 102 and the computing device 104 include I/O
interface(s) 110-1 and 110-2, respectively, collectively referred to as I/O interfaces 110.
The I/O interfaces 110 may include a variety of software and hardware interfaces that
allow the central server 102 and the computing device 104 to interact with the network
106 and with each other. Further, the I/O interfaces 110 may enable the central server 102
and the computing device 104 to communicate with other communication and computing
devices, such as web servers and external repositories.
[0027] The central server 102 and the computing device 104 may include
memory 112-1 and 112-2, respectively, collectively referred to as memory 112. The
memory 112-1 and 112-2 may be coupled to the processor 108-1, and the processor 108-
2, respectively. The memory 112 may include any computer-readable medium known in
the art including, for example, volatile memory (e.g., RAM), and/or non-volatile memory
(e.g., EPROM, flash memory, etc.).
[0028] The central server 102 and the computing device 104 further include
modules 114-1, 114-2, and data 116-1, 116-2, collectively referred to as modules 114 and
data 116, respectively. The modules 114 include routines, programs, objects,
components, data structures, and the like, which perform particular tasks or implement
particular abstract data types. The modules 114 further include modules that supplement
applications on the central server 102 and the computing device 104, for example,
modules of an operating system.
[0029] Further, the modules 114 can be implemented in hardware, instructions
executed by a processing unit, or by a combination thereof. The processing unit can
comprise a computer, a processor, such as the processor 108, a state machine, a logic
array or any other suitable devices capable of processing instructions. The processing unit
can be a general-purpose processor which executes instructions to cause the generalpurpose
processor to perform the required tasks or, the processing unit can be dedicated
to perform the required functions.
10
[0030] In another aspect of the present subject matter, the modules 114 may be
machine-readable instructions (software) which, when executed by a
processor/processing unit, perform any of the described functionalities. The machinereadable
instructions may be stored on an electronic memory device, hard disk, optical
disk or other machine-readable storage medium or non-transitory medium. In one
implementation, the machine-readable instructions can be also be downloaded to the
storage medium via a network connection. The data 116 serves, amongst other things, as
a repository for storing data that may be fetched, processed, received, or generated by one
or more of the modules 114.
[0031] In an implementation, the modules 114-1 of the central server 102 include
a parameter generation module 118, a communication module 120, a user key module
122, and other module(s) 124. In said implementation, the data 116-1 of the central server
102 includes parameter data 126, communication data 128, and other data 130. The other
module(s) 124 may include programs or coded instructions that supplement applications
and functions, for example, programs in the operating system of the central server 102,
and the other data 130 comprise data corresponding to one or more other module(s) 124.
[0032] Similarly, in an implementation, the modules 114-2 of the computing
device 104 include a key generation module 132, an encryption module 134, and other
module(s) 136. In said implementation, the data 116-2 of the computing device 104
includes key data 138, encryption data 140, and other data 142. The other module(s) 136
may include programs or coded instructions that supplement applications and functions,
for example, programs in the operating system of the computing device 104, and the
other data 142 comprise data corresponding to one or more other module(s) 136.
[0033] In operation, the central server 102 may initially generate public
parameters and a public key set which may be subsequently published or provided to the
computing devices 104 for encrypting and decrypting data. Encryption of the data based
on the public parameters, as generated herein, averts the need for computing Tate pairing
operation while encryption, thereby resulting in an efficient identity based encryption
scheme. Further, the central server 102 may generate the public key set and the public
11
parameters in a secure manner, for instance, by using a master secret key set as will be
discussed in detail later.
[0034] For the purpose, a parameter generation module 118 may initially select a
friendly prime (p) and a torsion group prime order (q) based on a prime generation
technique. The friendly prime may be understood as a prime number of a special form, as
will be discussed later, determined such that the complex algorithms used in the identity
based elliptic curve cryptography may be computed in lesser time as compared to
conventional techniques of computing the complex algorithms. Further, as will be
understood, the torsion group prime order referenced herein is also a prime number
different than the friendly prime. In said prime generation technique, initially a value of
the torsion group prime order is ascertained based on the following relation:
q2  2 * k 1 (1)
where, q is the torsion group prime order,  is an integer having a bit value grater than
160 bits, i.e.,  160 , and k is another integer.
[0035] Based on the above relation, the parameter generation module 118 selects
a torsion group prime order with a minimum bit length of 160 bits. Subsequently, the
friendly prime is generated based on the following relation:
pq *4t 1 (2)
where p is the friendly prime, q is the torsion group prime order, and t is an integer.
[0036] Upon generation of the friendly prime, the parameter generation module
118 ascertains whether the generated friendly prime satisfies the following conditions:
p = 2N ± c (3)
log2c ≤ (1/2)N (4) and
p ≡ 3 mod 4 (5)
12
where N is the length of the friendly prime in bits and c is an integer, also known as a
first variable. In one example, the friendly prime may be of bit length 512 bits.
[0037] In a case where the friendly prime satisfies the aforementioned conditions,
the parameter generation module 118 selects the friendly prime as the desired friendly
prime p. In a case, where the friendly prime does not satisfy the above conditions, the
integer t is incremented by one and the new friendly prime is then analysed to obtain the
desired friendly prime p. The selection of the friendly prime based on the torsion group
order, as described above, ensures that the cryptographic scheme based on the
aforementioned friendly prime and the torsion group is of a secure standard. For example,
the parameter generation module 118 may generate a torsion group and a friendly prime
as given below:
Friendly prime (p):
109836762562089755439710412785302291476310964802292886550311415346968690
934362496833960954250583272879636740982263693728593951807995466301001184
452657841041367
Torsion group prime order (q):
137295953202612194299638015981627864345388706002866108187889269183710863
667953121042451192813229091099545926227829617160742439759994332876251480
56582230130171
[0038] Upon selection of the friendly prime and the torsion group prime order,
the parameter generation module 118 determines a super-singular elliptic curve (E/GF(p))
over a finite field based on the friendly prime. The super-singular elliptic curve may be
understood as a set of elliptic curve points satisfying a given elliptic curve equation. In
one example, the super-singular elliptic curve may include p+1 points and, as will be
understood, also includes a point at infinity. In one example, the parameter generation
module 118 may generate the super-singular elliptic curve having the following equation:
Equation of Super Singular Elliptic Curve:
13
y�� �� x�� �� x (6)
[0039] Thereafter, the parameter generation module 118 may ascertain a first
torsion group (S[q]) based on the super-singular elliptic curve. The elements of the first
torsion group lie on the super singular elliptic curve. In one example, the first torsion
group may be an additive subgroup of points lying on the super singular elliptic curve.
Further, the number of elements of the first torsion group is equal to the torsion group
prime order. The value of the torsion group prime order perfectly divides a value
obtained by adding one to the value of the prime. In one implementation, the friendly
prime and the torsion group prime order are related according to the relation given below:
q | (p+1 ) (7)
[0040] Subsequently, the parameter generation module 118 may ascertain a
second torsion group (T[q]) based on the first torsion group using a distortion map (ф). In
one example, the second torsion group may be an isomorphic image of the first torsion
group over the super singular elliptic curve. The isomorphic mapping between the first
and the second torsion groups simplifies the complex arithmetic operations. In one
implementation, the distortion map used for obtaining the second torsion group may be of
the following form:
Φ: [e, f] ε S[q]  Point [p-e, sqrt(-1)*f] ε T[q] (8)
Further, the order of the second torsion group is equal to the order of the first torsion
group, i.e., q.
[0041] Upon generation of the first torsion group and the second torsion group,
the parameter generation module 118 may ascertain a first elliptic curve point (P) and a
second elliptic curve point (Q), collectively hereinafter referred to as elliptic curve points,
from the first torsion group based on the friendly prime. In one example, the first elliptic
curve point may be generated based on known methods by selecting a random integer
from within the range 1 to p-1. Subsequently, another random integer, different from the
previous random integer, may be randomly selected from within the aforementioned
14
range and ascertained as a master secret key (s). The master secret key then may be used
for ascertaining the second elliptic curve point. In one implementation, the second elliptic
curve point may be obtained as a result of point multiplication between the master secret
key and the first elliptic curve point using the following equation:
Q=[s]P (9)
where Q is the second elliptic curve point, s is the master secret key, and P is the first
elliptic curve point.
[0042] In one example, the parameter generation module 118 may obtain the first
elliptic curve point, the master secret key s, and the second elliptic curve point of the
following form, expressed in Jacobian co-ordinates,:
Elliptic curve point (P):
[x]=84774320408723859608471128240189512513099352061376943592938266065763
853373714108766544098287424306905475017916174456532515183870665125513289
21926675082346
[y]=15223893830655100048486511306704881399342401222794478356575765909334
632261068308382179592627672068294267070303117177724020711813772432452182
844069643762457960
[z]= 1
Master secret key (s):
[x]=10948256399571592215005472071269646841570666741768560847743204087238
596084711282401895125130993520613769435929382660657638533737141087665440
9828742430690547501791617445653251518387066512551328921926675082346
[y]=15223893830655100048486511306704881399342401222794478356575765909334
632261068308382179592627672068294267070303117177724020711813772432452182
844069643762457960
[z]=1
Elliptic curve point (Q):
15
[x]=66915172303021824801945469853790102911679193945242404457300535394326
755718413293783652688630763735784682909588065604985206396398451912846497
620686434410899902
[y]=28675665280324633346560738478988883918913588249245674845568337679767
637774346021690446948577756346863358805296427657898044837668409061666371
04010129697363736
[z]=1
[0043] Further, in one implementation, the parameter generation module 118 may
construct a master secret key set ({s,T}) comprising of the master secret key and a set (T)
of distinct integers with each integer in the range of 1 to p-1. For example, the parameter
generation module 118 may construct the set of distinct integers as  1 2 255 T t ,t ,t ,....t o  ,
where each ti is a distinct integer in the range 1 to p-1. As would be understood, the
parameter generation module 118 may generate each master secret key randomly.
Thereafter, the parameter generation module 118 constructs a public key set ({P,  }),
based on the master secret key set. In one implementation, in order to construct the public
key set, point multiplication operation may be performed between the first elliptic curve
point and each of the element of the master secret key to obtain a corresponding point ( i

) pertaining to the first torsion group as shown below:
t P i i   (10)
[0044] As a result of the above point multiplication operation, the parameter
generation module 118 constructs the public key set comprising of all such points. For
instance, based on the master secret key set, the parameter generation module 118 may
ascertain the public key set   1 2 255   , , ,.... o  .
[0045] Thereafter, the parameter generation module 118 may compute a Tate
pairing value (Y) which may be published as a public parameter and may subsequently be
used for encrypting the data. In one implementation, the parameter generation module
118 may compute the Tate pairing value based on the first elliptic curve point and the
16
second elliptic curve point using the Tate pairing operation. For example, the Tate pairing
value may be computed using the following equation:
Y  eP,Q  eP,Ps (11)
where Q,PTq. Based on the values of the P and the Q as obtained in the
previous example, the parameter generation module 118 may compute a tate pairing
value as:
Tate pairing value (Y):
Y(real part)=
643836826761547683146003064734985052058726708825635652380438401529372630
516789002176974681417016951268622150943939805969427484414411648683914017
21007625367682
Y (Imaginary part)=
563352270459646292819758463349013808109730877729956704539618421213083888
515723619789608015329597330199452889081677288315903996532701318836466011
61910374057650
[0046] The parameter generation module 118 may subsequently store the friendly
prime, the torsion group prime order, the first elliptic curve point, the second elliptic
curve point, the first torsion group, the super-singular elliptic curve point, the distortion
map, and the Tate pairing value, interchangeably referred to as pre-computed Tate pairing
value, as public parameters, along with the public key set in the parameter data 126.
Thereafter, the communication module 120 may publish the public parameters and the
public key set for being used in encryption of the data. In one implementation, the public
parameters and the public key set may be obtained by the computing device 104-1 and
the same may be subsequently stored in the key data 138.
[0047] As mentioned previously, the public parameters and the public key set
may be used by the computing device 104-1 for encrypting the data. The encryption of
the data based on the public parameters and the public key set which averts the need for
performing the Tate pairing operation thereby resulting in less consumption of resources,
17
such as battery power. Further, use of a public key set separate from the master secret key
set ensures that the master secret key set is not published and thus security of the master
secret key set is maintained.
[0048] In order to encrypt the data, the computing device 104-1 may initially
compute a receiver public key of a receiver to which the data is to be transmitted over the
network 106. For the purpose, the key generation module 132 may initially ascertain a
receiver identity (ID) of the receiver based on any known public identity of the receiver
using known hashing techniques. For example, the key generation module 132 may
obtain the receiver ID based on any one of the e-mail id, mobile number, date of birth,
and the like, of the receiver. In one example, receiver IDb={b0, b1,b2,…b128} is a 128 bit
binary sequence representing the receiver ID.
[0049] Thereafter, the key generation module 132 may generate a receiver key set
comprising of elliptic curve points based on the receiver identity. In one example, the
receiver key set is a subset of the public key set. Based on the bits of the receiver ID, the
key generation module 132 generates a receiver key set  1 2 127 , , ,.... b bo b b b       using
on the following equation:
 

 


   
 

128 [ ] if the bit of 1
[ ] if the bit of 0
128
b
th
i
b
th
i
bi t P i ID i
i t P i ID



(12)
[0050] The key generation module 132 may then compute the receiver public key
(Q_id) based on the receiver key set. In one implementation, the key generation module
132 may perform addition of all points of the receiver key set for obtaining the receiver
public key using the following equation:
Q id t P t q P
i
bi
i
bi
i
bi 








 




 




   
  
_ mod
127
0
127
0
127
0

(13)
[0051] In one example, the key generation module 118 may generate the receiver
public key, represented in Jacobian co-ordinates, as:
18
Receiver public key (Q_id):
[x]=28292155308326101027944987840062930348162436083558260395287778218859
546238939411482190543027679870888215139371511216803536487199400370319122
033654884906100745
[y]=82403816506910205230965173110299320723533094711512809305530796352452
228648870390147260281758935873086053245801560950014694154515788265561496
985266603412027212
[z]=1
[0052] The receiver public key thus generated may be stored in the key data 138
along with the receiver public key data for being used in encryption of the data. In one
implementation, the encryption module 134 may encrypt the data based on an encryption
component (Eb) determined based on the receiver public key set and a random number x
in the range 1 to p-1. For the purpose, the encryption module 134 may obtain the receiver
public key set stored in the key data 138 and compute the encryption component using
the following equation:
E xQ id x t P x t q q P
i
bi
i
b bi 



 

 

 



   




   
 
_ mod mod
127
0
127
0
(14)
where, Eb is the encryption component, x is the random integer, and tb is a subset of the
master secret key set corresponding to the receiver ID and may be represented by a
mapping given below:
 

 


 


128 if the bit of 1
if the bit of 0
b
th
b
th
bi i ID ti
ti i ID
t
(15)
[0053] Upon computing the encryption component, the encryption module 134
may encrypt the data based on the encryption component, a random integer x, and the
Tate pairing value received as one of the public parameters. The random integer may be
19
selected from the range of one to one less than the value of the friendly prime. For
example, the encryption module 134 may encrypt data M in the following manner:
Mencrypt  MY x , Eb 
(16)
[0054] In one example, the encryption module 134 may encrypt a message, say
'world is beautiful' and may obtain the message in an encrypted form of the following
manner:
Encrypted form:
365276490196904582886715271720606538171588078181134035628015141233512729
440390060708428994305250678511155276576352250918153521307862575637269706
816560343097635485058397323582109011265522126600262421133710728051062260
079109287292143577737455179589680945357994588625445891246723303902295391
9192891929115589571462804054
104705537661624460092354600181160484440548215330198125212556160411712111
861700357253586136446780140362598091132614894140096057447827715928036481
056928329716140
504816936209227854699308806548783868574168625393644310285922953183070030
398241424251621964163678472307648309542600545316190866852773571524167556
49131830720882
[0055] Upon encryption of the data, the encryption module 134 may transmit the
encrypted data, i.e., data in the encrypted form, to the receiver over the network 106. The
Tate pairing value obtained from the public parameters averts the need for computing the
Tate pairing operation at the computing device 102 thereby reducing the resources, such
as battery and processor, being used in the encryption process.
[0056] Upon receiving the encrypted data, the receiver may send a private key
request to the central server 102 through a computing device, such as the computing
device 104-2 for obtaining a private key. The receiver may use the private key to decrypt
20
the encrypted data. In one implementation, the private key request may include the
receiver public key.
[0057] Upon receiving the private key request, the user key module 122 may
generate a private key set of the receiver based on the master secret key set and the
receiver ID identified based on the receiver public key. For the purpose, the user key
module 122 may use the mapping (15) and equation (12) mentioned above. For example,
based on the mapping (15) and the equation (12), the user key module 122 may generate
the private key set as  1 2 127 , , ,.... b bo b b b t  t t t t . Thereafter, the user key module 122
computes the private key of the receiver based on the following equation:
S id s t q q P
i
bi 



 


 


 








 
_ mod mod
127 1
0
(17)
where, S_id is the private key of the receiver, s is master secret key, and q is the torsion
group prime order, and P is the first elliptic curve point.
[0058] In one example, a recipient of the encrypted message say bob may request
for his private key. In said example, the user key module 122 may generate the private
key for bob using his public identity. In said example, for the public identity being 'bob',
the user key module 122 may obtain the private key, represented in Jacobian coordinates,
as:
Private key of bob:
[x]=28292155308326101027944987840062930348162436083558260395287778218859
546238939411482190543027679870888215139371511216803536487199400370319122
033654884906100745
[y]=82403816506910205230965173110299320723533094711512809305530796352452
228648870390147260281758935873086053245801560950014694154515788265561496
985266603412027212
21
[z]=1
[0059] Subsequently, the user key module 122 may transmit the private key of the
receiver to the computing device 104-2 over a secure communication channel over the
network 106.
[0060] The computing device 104-2, upon receiving the private key, may then
decrypt the encrypted data to obtain the data. In one example, decryption of data may
involve Tate pairing operation, the computational complexity of which is highly reduced
due to the public parameters being used for decryption process. For instance, the receiver
may perform the Tate pairing operation, using the computing device 104-2, based on the
private key and the encryption component in a manner as given below:
Tate Pairing Operation
   e S _ id, Eb
eP Ps t q x i t q Y x
bi
i
bi     


 




  



 





 



mod mod
127
0
127 1
, 0
[0061] Upon obtaining the Tate pairing value, the receiver may subsequently
decrypt the encrypted data to obtain the data in an apprehensible form. For instance, upon
obtaining Y x , the receiver may decrypt the encrypted data to obtain the data in a manner
as described below:
Decryption Operation
Y  p
M MY x
x  mod
where M is the data obtained upon decrypting the encrypted data MYx, Yx is the Tate
pairing value, and p is the friendly prime. In the example where the message ' world is
beautiful' is encrypted, the message received upon decryption of the received encrypted
data is 'world is beautiful'.
22
[0062] Figure 2 illustrates a method 200 for generating public parameters and a
public key set for identity based encryption, in accordance with an embodiment of the
present subject matter. Figure 3 illustrates a method 300 for identity based encryption of
data using public parameters and public key set, in accordance with an embodiment of
the present subject matter.
[0063] The order in which the methods 200 and 300 are 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 methods 200 and 300, or an alternative method.
Additionally, individual blocks may be deleted from the methods 200 and 300 without
departing from the spirit and scope of the subject matter described herein. Furthermore,
the methods 200 and 300 may be implemented in any suitable hardware, machine
readable instructions, firmware, or combination thereof.
[0064] A person skilled in the art will readily recognize that steps of the methods
200 and 300 can be performed by programmed computers. Herein, some examples are
also intended to cover program storage devices and non-transitory computer readable
medium, for example, digital data storage media, which are machine or computer
readable and encode machine-executable or computer-executable instructions, where said
instructions perform some or all of the steps of the described methods 200 and 300. The
program storage devices may be, for example, digital memories, magnetic storage media,
such as a magnetic disks and magnetic tapes, hard drives, or optically readable digital,
data storage media.
[0065] With reference to Figure 2, at block 202, a friendly prime and a torsion
group prime order are selected. In one implementation, the friendly prime and the torsion
group prime order selected are of a form which facilitates fast computation of
mathematical operations associated with an identity based elliptic curve cryptography
scheme. For instance, the friendly prime and the torsion group order are selected in
manner such that the friendly prime and the torsion group order satisfies the relations
illustrated using the equations (1 to 5) as described above. Further, the friendly prime and
the torsion group prime order may be used for determining other parameters used for
23
encryption and decryption of data. In one example, the parameter generation module 118
may select the friendly prime and the torsion group prime order.
[0066] At block 204, a super-singular elliptic curve may be determined. Upon
selection of the friendly prime, the super-singular elliptic curve may be determined. In
one implementation, the super-singular elliptic curve may be defined over a finite field of
points, where the finite field of points is based on the friendly prime. In one
implementation, the parameter generation module 118 may determine the super-singular
elliptic curve.
[0067] At block 206, a first torsion group and a second torsion group is
constructed based on the super-singular elliptic curve. In one implementation, a first
torsion group comprising of points lying on the super-singular elliptic curve is
ascertained. In said implementation, an order of the first torsion group, i.e., the number of
points in the first torsion group is equal to the torsion group prime order. Upon
constructing the first torsion group, a second torsion group may be constructed. In one
example, the second torsion group may be an isomorphic image of the first torsion group
obtained using a distortion map. Further, the second torsion group has an order equal to
the order of the first torsion group . In one implementation, the parameter generation
module 118 may construct the first torsion group and the second torsion group.
[0068] At block 208, a first elliptic curve point and a second elliptic curve point,
from the first torsion group, is ascertained based on the friendly prime. In example, a
random integer in the range of one to one less than the value of the friendly prime is
selected and subsequently a first elliptic curve point is ascertained using known methods.
Based on the first elliptic curve point, a second elliptic curve point is generated. For the
purpose, another random integer from the aforementioned range is selected as a master
secret key. Thereafter, point multiplication operation is performed between the first
elliptic curve point and the master secret key for obtaining the second elliptic curve point.
In one implementation, the parameter generation module 118 may ascertain the first
elliptic curve point and a second elliptic curve point.
24
[0069] At block 210, a public key set is determined based on a master secret key
set and the first elliptic curve point. In one implementation, initially, the master secret
key set comprising of distinct integers, which are generated randomly in the range one to
one less than the friendly prime, is ascertained. Thereafter, a public key set may be
determined based on the master secret key set and the first elliptic curve point. For the
purpose, point multiplication operation may be performed between each of the integers of
the master secret key set and the first elliptic curve point. As a result of the point
multiplication operations, a plurality of points is obtained and may be included in the
public key set. In one implementation, the parameter generation module 118 may
determined the public key set.
[0070] At block 212, a Tate pairing value based on the first elliptic curve point
and the second elliptic curve point may be generated. In one implementation, the Tate
pairing value may be generated as a result of the Tate pairing operation performed using
the first elliptic curve point and the second elliptic curve point. In one implementation,
the parameters generation module 118 may generate the Tate pairing value.
[0071] At block 214, the public key set and public parameters are published for
encrypting data. In one implementation, the friendly prime, the torsion group prime order,
the super-singular elliptic curve, the first torsion group, the first elliptic curve point, the
second elliptic curve point, the distortion map, and the Tate pairing value are published as
public parameters along with the public key set. The public key set and the public
parameters may then be used for encrypting the data.
[0072] With reference to Figure 3, at block 302, public parameters and a public
key set for encrypting data are obtained. In one implementation, a public key set and
public parameters, which includes at least a pre-computed Tate pairing value, are
obtained for encrypting data.. In one example, the computing device 104-1 may obtain
the public key set and the public parameters from the central server 102. In another
example, the public key set, generated by the central server 102, may be in a memory of
the computing device 104-1.
25
[0073] At block 304, a receiver identity (ID) of a receiver of the data is
ascertained based on a public identity of the receiver. In order to encrypt the data,
initially the receiver ID is ascertained based on the public identity of the receiver. The
public identity may be any known identity of the receiver, for example, an e-mail id, a
phone number, date of birth, and the like. In one example, hashing technique may be used
for obtaining the receiver ID and may be a 128 bit binary sequence.
[0074] At block 306, a receiver key set based on the receiver ID, the public
parameters, and the public key set is generated. In one example, the receiver key set may
be a subset of the public key set and may be obtained as a mapping using the equation as
illustrated in the equation (12) in Figure 1. The receiver key set thus generated includes a
point on the elliptic curve for each of the bits of the receiver ID.
[0075] At block 308, a receiver public key is computed based on the receiver key
set. In one example, all the points of the receiver key set are added as illustrated in
equation (13) for obtaining the receiver public key. In one implementation, the key
generation module 132 may compute the receiver public key.
[0076] At block 310, an encryption component based on the receiver public key,
the public parameters, and the public key set is determined. In one implementation, an
encryption component may be determined for being used in the encryption process. In
said implementation, the encryption component may be generated based on the receiver
public key, the public parameters, and the public key set in a manner as described earlier
in equation (14).
[0077] At block 312, the data is encrypted based on the encryption component
and the pre-computed Tate pairing value. In one implementation, the data may be
encrypted using the encryption component and the pre-computed Tate pairing value in a
manner as described earlier in equation (16).The use of pre-computed Tate pairing value
eliminates the need for performing the computationally extensive Tate pairing operations
thus reducing the resources utilized for encrypting the data.
[0078] Upon encrypting the data, the encrypted data, i.e., the data in an
inapprehensible form, may be transmitted to the receiver. The receiver, upon receiving
26
the encrypted data may decrypt the data through a computing device, such as the
computing device 104-2. For the purpose, a tate pairing operation may be performed by
the receiver in a manner as describer earlier in the Tate pairing operation. Further, the
receiver may then decrypt the data based on the Tate pairing value, obtained as result of
the Tate pairing operation, in a manner as described earlier in decryption operation.
[0079] Although implementations for identity based encryption have been
described in language specific to structural features and/or methods, it is to be understood
that the appended claims are not necessarily limited to the specific features or methods
described. Rather, the specific features and methods are disclosed as exemplary
implementations for identity based encryption.