**Executive Summary**
This document proposes a homomorphic encryption (HE) scheme based on Carmichael's theorem over integers, which supports both addition and multiplication on encrypted data. The scheme is probabilistic, using a randomized integer for encryption, and is designed for positive integers. It aims to address privacy concerns in cloud and distributed computing.
**Key Points / Main Content**
* **Homomorphic Encryption (HE) Overview**
* HE allows computations on encrypted data without prior knowledge of the original message or decryption.
* The proposed scheme is both additive and multiplicative.
* **Proposed HE Scheme based on Carmichael's Theorem**
* Uses two large prime integers, p and q, and Carmichael's function is calculated as λ(n) = lcm((p-1),(q-1)), where n = p x q.
* 'An' and n are used for encryption, and n is used for decryption.
* **Encryption:** c = m + rλmod n2
* **Decryption:** m = cλ mod n
* **Delegation Computation**
* Details how users can outsource computation to service providers or the cloud while maintaining data privacy.
* The user encrypts data using the HE scheme and sends it to the service provider, along with the function to be performed.
* The service provider performs the operation on the encrypted data and sends the encrypted result back to the user, who then decrypts it.
**Impact Analysis**
**Stakeholder: Users**
* **Impact:** Can perform computations on data outsourced to cloud or distributed computing without decrypting the data.
* **Action Required:** Need to implement the HE algorithm to encrypt data before sending it to service providers and decrypt the results.
**Stakeholder: Service Providers (Cloud)**
* **Impact:** Can perform computations on encrypted data without having access to the original, unencrypted data.
* **Action Required:** Implement algorithms to operate on encrypted data according to user-defined functions and return encrypted results to the user.
Key Entities Referenced
Homomorphic Encryption : The primary focus of the paper, involving encryption schemes that allow computations on encrypted data without decryption.
Carmichael's Theorem : The mathematical foundation upon which the proposed homomorphic encryption scheme is based.
Rivest, Adleman and Dertouzos : Pioneers in the field of homomorphic encryption, whose work inspired the present research.
See Full Document Text
2016 International Conference on Electrical, Electronics, Communication, Computer and Optimization Techniques (ICEECCOT)
A Homomorphic Encryption Scheme Over
Integers Based on Carmichael’s Theorem
Pramod Kumar Siddharth Om Pal
JamiaMilliaIslamia University,New Delhi Ministry of Electronics and IT, Govt. of India
siddharthpramodkr@gmail.com ompal.cdac@gmail.com
Bashir Alam
Department of Computer Engineering,
JamiaMilliaIslamia New Delhi
babashiralam@gmail.com
Abstract— The homomorphic properties of the cryptographic term homomorphic from the algebraic term
techniques take the attention of the scholars and makes it open homomorphism, which refers to a mapping between two
research problem. The traditional encryption schemes don’t groups and .
support the operations to be computed on the encrypted data, Let and are two groups over some
which may compromise the privacy of the sensitive data. The
algebraic operation. A function is called
homomorphic encryption supports the algebraic operations to be
computed on the encrypted data. This property of the homomorphism. If for all
homomorphic encryption scheme have a wide application areas , that is, if commutes with the group
such as secure electronic voting, multiparty computation, private
operations of and . A group homomorphism
searching, delegation of computation and many more. In this
is called isomorphism, if there exists a group
paper we proposed a homomorphic encryption scheme based on
the Carmichael’s theorem over integers. The operations in the homomorphism , such that
scheme are modular arithmetic. The paper also discuss the a. and
security scheme and further optimization are pointed out.
b.
Keywords: probabilistic, homomorphism, homomorphic
encryption, Charmichael. for all and
This notion can then be extended to rings or similar
I. INTRODUCTION algebraic objects in the same category with multiple
operations. In[1], Rivest presented the privacy
When the data is outsourced to the cloud computing or
homomorphism system in the form of algebraic system,
distributed computing the privacy of the sensitive data can be
which can be explained as: An algebraic system consists
compromised and the possible issues and attacks which can
of a set ,
compromise the privacy are: untrusted third party
a. some operations
computation, side channel attacks and the implementation
b. some predicates and
bugs in the system. Due to these issues an encryption scheme
is required to allow the algebraic operations to be computed c. some distinguished constants
on the encrypted data without prior knowledge of the original The system is denoted as
message and disables the decryption at the untrusted third . For example,
party site. The traditional encryption systems do not allow the system consisting of the integers under the usual set of
such computation without decryption of the data and can’t be operations, denoted , where is the
no longer used in the cloud computing or distributed
set of integers. Let’s have two algebraic systems and
computing.
given as:
Then the concept of the privacy homomorphism[1]
and
(homomorphic encryption) is introduced by the Rivest,
Adleman and Dertouzos, which supports the computations on
the encrypted data.
The encoding and decoding map elements from to
To understand homomorphic encryption, it is essential to
understand the algebraic meaning of the phrase. We get the and vice versa. The decoding function is and
978-1-5090-4697-3/16/$31.00 ©2016 IEEE 17encoding function is . The user’s database is Definition: An encryption scheme is said to
denoted as the sequence each is element of . The homomorphic with respect to some operation on if
user encodes each datum before giving to the system: the we have:
encoded database is ,
To operate on the encrypted data, the decoding function
must be homomorphism from to , such that
An additive homomorphic encryption is the encryption
function in which the decryption of a sum of ciphertexts is
and
the sum of the corresponding messages. That is
And . The decoding function caries each
operation in into the corresponding operation in . If user
A multiplicative homomorphic encryption is the
wants to know the value of , then the system
encryption function in which the decryption of a product
computes . Since this is
of ciphertexts is the product of the corresponding
homomorphism messages. That is
The requirements on the choice of the and functions and
are:
III. PROPOSED SCHEME
a. The and should be easy to compute.
We proposed a Homomorphic Encryption scheme, which
b. The and in should be efficiently computable.
supports addition and multiplication on the encrypted
c. The expansion should be minimum.
data. The proposed algorithm is probabilistic encryption
d. Knowledge of for many data should not be
scheme in which a single message is encrypted into
sufficient to reveal .
different ciphertext each time the message is encrypted
e. Knowledge of and for several values of
with the same encryption key. A random integer is used
should not be sufficient to reveal .
to randomize the encryption function. Our proposed
f. The operations and predicates in should not be
algorithm is developed for positive integers. Our
sufficient to yield an efficient computation of .
algorithm is based on the large prime numbers and the
In this paper we represent the algebraic homomorphic
Carmichael’s[5] theorem. The Carmichael’s theorem.
encryption system over the integers, which is based on the
Carmichael’s[5] theorem. The scheme is probabilistic scheme
in which the encryption of the same message depends on some A. OVERVIEW OF THE SCHEME
randomized integer and produces the different ciphertexts each Let we have two large prime numbers and , and
time encrypted. product of these numbers is calculated as and
the Carmichael’s function
II. HOMOMORPHISM
. Now for any
the following equations holds:
The idea of homomorphism was first proposed in 1978 by
and
Rivest, Adleman and Dertouzos in their paper ―On Data
Banks and Privacy Homomorphisms[1]. Homomorphic
We use both of this theorems for enciphering and
encryption is the encryption function which allows the
deciphering and the cyclic property of Carmichael’s
encrypted data to be operated without knowledge of the function used, which is stated as:
decryption function (original data). For plaintexts and
and corresponding ciphertext and , a homomorphic The proposed HE algorithm is given as:
1. Select two large prime integers and and
encryption scheme permits meaningful computation of
compute , and Carmichael’s function λ
from and without revealing .The
is evaluated as: .
cryptosystem may be additive or multiplicative
2. and is used for encryption and is used
homomorphism depending upon the algebraic operation
for decryption.
which can be addition or multiplication.
183. For the encryption of message and a F. ADDITIVE HOMOMORPHISM
random integer .The message is encrypted as: Additive homomorphism is stated as:
Proof:
4. The decryption function of the algorithm is given as:
B. CORRECTNESS
The correctness of the scheme is given as:
We can also prove the correctness of the additive property
of the scheme.
Here in the above equation we can change the order of the
modulus because is raised to and this will make no
The scheme is best suitable for integers.
effect on the remainder and we can write it as below and
manipulate further.
IV. DELEGATION COMPUTATION
Lets take an example of delegation of computation where
any power raised to
the user doesn’t have the required resources to perform
will produce the same remainder produced by , then for
the computation on the data. In this case the user
outsource his/her data to some service provider over the
network or to the cloud. Now the user follow the
following operation to perform the computation on his/her
Decryption of ciphertext produces the plaintext message . data.
C. HOMOMORPHISM
Our proposed scheme is homomorphic scheme, which
supports both the additive and multiplicative homomorphism
property. For messages and ,we have the corresponding
ciphertexts as and , and random integers and used
for deciphering respectively. The multiplicative and additive
homomorphicproperty, and their proofs are presented below.
D. MULTIPLICATIVE HOMOMORPHISM
E.
Multiplicative homomorphism is stated as:
is decryption and is encryption function.
Figure 1. Delegation of Computation
Proof: The property is given as:
User have two integer values
He/she wants to perform some
operation on the available data(addition/multiplication).
We can rewrite as: For this reason user encrypt his/her data and send it to
service provider along with the function to be performed.
The figure 1 given above depicts the all steps involved in
The same steps of decryption function can be taken to prove
the correctness of multiplicative property of the scheme and the delegation of computation.
we have: User selects two prime integers and to
obtain the encryption and decryption key then hecalculate
, and
For
.
, and
After the selection of the prime numbers the user
selects two random integers to randomize the ciphertext.
191. ,and VI. APPLICATION AREAS
2. The proposed scheme is both additive as well as
multiplicative homomorphic. The scheme can be used in
The encryption is performed as:
secure electronic voting system[3] due to its additive
homomorphism. This scheme can also be used in
multiparty computation[3], delegation of computation and
searching over encrypted data.
VII. CONCLUSION
The user sends the these two encrypted numbers along with We have proposed an HE scheme based on the
the function to the service provider. The service provider Carmichael’s theorem and the cyclic property of the
receives the number in encrypted format and is not authorized Carmichael’s function. The scheme is probabilistic in
to decrypt the numbers. The service provider perform the nature and uses a randomized integer for the encryption
required operation on the data as follows as: function. The scheme is best suitable for the integers.
Multiplication is computed as:
References
Addition is computed as: [1] R. Rivest, L. Adleman, and M Dertouzos, “On data banks and
privacy homomorphisms”, in Foundations of Secure
Computation, pp. 169–177, Academic Press, 1978.
After performing the required operations on the data, the
[2] Brickell and Y. Yacobi, “On privacy homomorphisms”, in
service provider send back the result to the user and then on Advances in Cryptology (EUROCRYPT ’87), vol. 304 of Lecture
receiving the result from the service provider the user decrypt Notes in
Computer Science, pp. 117–126, Springer, New York, NY, USA,
the data to obtain the actual result as follows as:
1987.
Multiplication is obtained as:
[3] Gerhard Potzelsberger, “KV Web Security: Applications of
Homomorphic Encryption”, May 23, 2013
[4] Caroline Fontaine and Fabien Galand, Review Article “A Survey
of
Addition is computed as:
Homomorphic Encryption for Nonspecialists” CNRS/IRISA-
TEMICS, Campus de Beaulieu, 35042 Rennes Cedex, France, 24
October 2007
[5] P. Paillier, “Public-key cryptosystems based on composite degree
After obtaining the actual result by decryption the user can residuosity classes,” in Advances in Cryptology (EUROCRYPT
use the numbers. ’99), vol. 1592 of Lecture Notes in Computer Science, pp. 223–
238, Springer, New York, NY, USA, 1999.”
V. SECURITY OF THE SCHEME
[6] C. Gentry, “Fully homomorphic encryption using ideal lattices”,
The security [9] of this scheme is based on large prime
Symposium on the Theory of Computing (STOC), 2009, pp. 169-
number. This scheme has the encryption function implements 178
the trapdoor function: for a given message we can compute [7] Craig Gentry and ShaiHalevi, “Implementing Gentry’s fully-
homomorphic encryption scheme,” Advances in Cryptology–
a function such that , no function exists by which
EUROCRYPT 2011, pp. 129– 148, 2011.
we can evaluate form such that . The scheme [8] Van Dijk, Marten, Craig Gentry, ShaiHalevi, and
VinodVaikuntanathan. “Fully homomorphic encryption over the
is probabilistic scheme: for a given message , we have a
Integers”. Advances in Cryptology EUROCRYPT 2010 (2010):
random integer, which randomize the ciphertext each time 24-4
message is encrypted. The scheme is secure against the chosen [9] Yu Yu, JussipekkaLeiwo, Benjamin Premkumar, “A Study on the
Security of Privacy Homomorphism”, Nanyangchnological
ciphertext attack. The major drawback is the decryption
University, School of Computer Engineering, Proceedings of the
function, if an adversary get the any information about then
Third International Conference on Information Technology: New
the message can be recovered easily. The security of the Generations (ITNG'06), IEEE 200
decryption function must have to enhance and development of
a complex decryption function is to be designed.
20