All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Description

sdfdsfdsfds

Tags

Transcript

Hindawi Publishing CorporationEURASIP Journal on Information Security Volume 2007, Article ID 13801,10pagesdoi:10.1155/2007/13801
ReviewArticle
ASurveyofHomomorphicEncryptionforNonspecialists
CarolineFontaineandFabienGaland
CNRS/IRISA-TEMICS, Campus de Beaulieu, 35042 Rennes Cedex, France
Correspondence should be addressed to Caroline Fontaine,caroline.fontaine@irisa.frReceived 30 March 2007; Revised 10 July 2007; Accepted 24 October 2007Recommended by Stefan KatzenbeisserProcessing encrypted signals requires special properties of the underlying encryption scheme. A possible choice is the use of ho-momorphic encryption. In this paper, we propose a selection of the most important available solutions, discussing their propertiesand limitations.Copyright © 2007 C. Fontaine and F. Galand. This is an open access article distributed under the Creative Commons AttributionLicense, which permits unrestricted use, distribution, and reproduction in any medium, provided the srcinal work is properly cited.
1. INTRODUCTION
The goal of encryption is to ensure conﬁdentiality of datain communication and storage processes. Recently, its usein constrained devices led to consider additional features,such as the ability to delegate computations to untrustedcomputers. For this purpose, we would like to give the un-trusted computer only an encrypted version of the data toprocess. The computer will perform the computation on thisencrypted data, hence without knowing anything on its realvalue. Finally, it will send back the result, and we will decryptit. For coherence, the decrypted result has to be equal to theintended computed value if performed on the srcinal data.For this reason, the encryption scheme has to present a par-ticular structure. Rivest et al. proposed in 1978 to solve thisissue through
homomorphic encryption
[1]. Unfortunately,Brickell and Yacobi pointed out in[2] some security ﬂaws
in the ﬁrst proposals of Rivest et al. Since this ﬁrst attempt,a lot of articles have proposed solutions dedicated to nu-merous application contexts: secret sharing schemes, thresh-old schemes (see, e.g., [3]), zero-knowledge proofs (see, e.g.,[4]), oblivious transfer (see, e.g., [5]), commitment schemes
(see, e.g., [3]), anonymity, privacy, electronic voting, elec-tronic auctions, lottery protocols (see, e.g., [6]), protectionofmobileagents(see,e.g.,[7]),multipartycomputation(see,e.g.,[3]), mix-nets (see, e.g., [8,9]), watermarking or ﬁnger-
printing protocols (see, e.g., [10–14]), and so forth.
The goal of this article is to provide nonspecialists witha survey of homomorphic encryption techniques.Section 2recalls some basic concepts of cryptography and presents ho-momorphic encryption; it is particularly aimed at noncryp-tographers, providing guidelines about the main characteris-tics of encryption primitives: algorithms, performance, secu-rity.Section 3providesasurveyofhomomorphicencryptionschemes published so far, and analyses their characteristics.Mostschemeswedescribearebasedonmathematicalno-tions the reader may not be familiar with. In the cases thesenotions can easily be introduced, we present them brieﬂy.The reader may refer to[15] for more information concern-
ing those we could not introduce properly, or algorithmicproblems related to their computation.Before going deeper in the subject, let us introduce somenotation. The integer
(
x
) denotes the number of bits con-stituting the binary expansion of
x
. As usual,
Z
n
will denotethe set of integers modulo
n
, and
Z
∗
n
the set of its invertibleelements.
2. TOWARDSHOMOMORPHICENCRYPTION
2.1. Basicsaboutencryption
In this section, we will recall some important concepts con-cerning encryption schemes. For more precise information,the reader may refer to [16] or the more recent [17].
Encryption schemes are, ﬁrst and foremost, designed topreserve conﬁdentiality. According to Kercko
ﬀ
s’ principle(see [18,19] for the srcinal papers, or any book on cryp-
tography), their security must not rely on the obfuscation of their code, but only on the secrecy of the decryption key. Wecan distinguish two kinds of encryption schemes:
symmetric
2 EURASIP Journal on Information Security and
asymmetric
ones. We will present them shortly and dis-cuss their performance and security issues.
Symmetricencryptionschemes
Here “symmetric” means that encryption and decryption areperformed with the same key. Hence, the sender and the re-ceiver have to agree on the key they will use before perform-ing any secure communication. Therefore, it is not possi-ble for two people who never met to use such schemes di-rectly. This also implies to share a di
ﬀ
erent key with every one we want to communicate with. Nevertheless, symmet-ric schemes present the advantage of being really fast and areused as often as possible. In this category, we can distinguishblock ciphers (AES[20,21])
1
and stream ciphers (One-timepad presented inFigure 1[22], Snow 2.0 [23]),
2
which areeven faster.
Asymmetricencryptionschemes
In contrast to the previous family, asymmetric schemes in-troduce a fundamental di
ﬀ
erence between the abilities to en-crypt and to decrypt. The encryption key is public, as thedecryption key remains private. When Bob wants to send anencrypted message to Alice, he uses her
public key
to encryptthe message. Alice will then use her
private key
to decrypt it.Suchschemesaremorefunctionalthansymmetriconessincethere is no need for the sender and the receiver to agree onanything before the transaction. Moreover, they often pro-videmorefeatures.Theseschemes,however,haveabigdraw-back: they are based on nontrivial mathematical computa-tions, and much slower than the symmetric ones. The twomost prominent examples, RSA [24] and ElGamal [25], are
presented in Figures2and3.
Performanceissues
A block cipher like AES is typically 100 times faster than RSAencryption and 2000 times than RSA decryption, with about60MB per second on a modest platform. Stream ciphersare even faster, some of them being able to encrypt/decrypt100MB per second or more.
3
Thus, while encryption or de-cryption of the whole content of a DVD will take about aminute with a fast stream cipher, it is simply not realistic touse an asymmetric cipher in practice for such a huge amountof data as it would require hours, or even days, to encrypt ordecrypt.Hence, in practice, it is usual to encrypt the data we wantto transmit with an e
ﬃ
cient symmetric cipher. To provide
1
AES has been standardized; seehttp://csrc.nist.gov/groups/ST/toolkit/block ciphers.htmlfor more details.
2
Snow 2.0 is included in the draft of Norm ISO/IEC 18033-4,http://www .iso.org/iso/en/CatalogueDetailPage.CatalogueDetail?CSNUMBER
=
3997.
3
See, for example,http://www.ecrypt.eu.org/stream/perf/alpha/bench-marks/snow-2.0for some benchmark of Snow 2.0, or openssl for AES andRSA.
thereceiverwiththesecretkeyneededtorecoverthedata,thesender encrypts this key with an asymmetric cipher. Hence,the asymmetric cipher is used to encrypt only a short data,while the symmetric one is used for the longer one. Thesender and the receiver do not need to share anything be-fore performing the encryption/decryption as the symmet-ric key is transmitted with the help of the public key of thereceiver. Proceeding this way, we combine the advantages of both: e
ﬃ
ciency of symmetric schemes and functionalities of the asymmetric schemes.
Securityissues
Security of encryption schemes was formalized for the ﬁrsttime by Shannon [26]. In his seminal paper, Shannon in-troduced the notion of
perfect secrecy/unconditional secu-rity
, which characterizes encryption schemes for which theknowledge of a ciphertext does not give any information ei-ther about the corresponding plaintext or about the key. Heproved that the one-time pad is perfectly secure under someconditions,asexplainedinFigure 1.Infact,nootherscheme,
neither symmetric nor asymmetric, has been proved uncon-ditionally secure. Hence, if we omit the one-time pad, any encryption scheme’s security is evaluated with regard to thecomputational power of the opponent. In the case of asym-metric schemes, we can rely on their mathematical structuretoestimatetheirsecuritylevelinaformalway.Theyarebasedon some well-identiﬁed mathematical problems which arehard to solve in general, but easy to solve for the one whoknows the trapdoor, that is, the owner of the keys. Hence,it is easy for the owner of the keys to compute his/her pri-vate key, but no one else should be able to do so, as theknowledge of the public key should not endanger the privatekey. Through reductions, we can compare the security levelof these schemes with the di
ﬃ
culty of solving these math-ematical problems (factorizing large integers or computinga discrete logarithm in a large group) which are famous fortheir hardness. Proceeding this way, we obtain an estimateof the security level, which sometimes turns out to be op-timistic. This estimation may not be su
ﬃ
cient for severalreasons. First, there may be other ways to break the systemthan solving the reference mathematical problem [27,28].
Second, most of security proofs are performed in an ideal-ized model called the
random oracle model
, in which involvedprimitives, for example, hash functions, are considered truly random. This model has allowed the study of the security level for numerous asymmetric ciphers. Recent works show that we are now able to perform proofs in a more realisticmodel called the
standard model
. From[29] to[30], a lot of
papers compared these two models, discussing the gap be-tween them. In parallel with this formal estimation of thesecurity level, an empirical one is performed in any case, andnew symmetric and asymmetric schemes are evaluated ac-cording to published attacks.The framework of a security evaluation has been statedby Shannon in 1949[26]: all the considered messages are
encrypted with the same key—so, for the same recipient—and the opponent’s challenge is to take an advantage from allhis observations to disclose the involved secret/private key.
C. Fontaine and F. Galand 3Usually, to evaluate the attack capacity of the opponent, wedistinguish among several contexts [31]:
ciphertext-only at-tacks
(where the opponent has access only to some cipher-texts),
known-plaintext attacks
(where the opponent has ac-cess to some pairs of corresponding plaintext-ciphertexts),
chosen-plaintext attacks
(same as previous, but the opponentcan choose the plaintexts and get the corresponding cipher-texts), and
chosen-ciphertext attacks
(the opponent has accessto a decryption oracle, behaving as a black-box, that takesa ciphertext and outputs the corresponding plaintext). Theﬁrst context is the most frequent in real life, and results fromeavesdropping the communication channel; it is the worstcase for the opponent. The other cases may seem di
ﬃ
cult toachieve, and may arise when the opponent has a more pow-erful position; he may, for example, have stolen some plain-texts, or an encryption engine. The “chosen” ones exist in
adaptive
versions, where the opponent can wait for a compu-tation result before choosing the next input.
Howdowechoosetherightscheme?
The right scheme is the one that ﬁts your constraints in thebest way. By constraints, we may understand constraints intime, memory, security, and so forth. The two ﬁrst criteriaare very important in highly constrained architectures, of-ten encountered in very small devices (PDAs, smart cards,RFID tags, etc.). They are also important if we process a hugeamount of data, or numerous data at the same time, for ex-ample, video streams. Some schemes as AES or RSA are usu-ally chosen because of their reputation, but it is importantto note that new schemes are proposed each year. Indeed, itis necessary to keep a diversity in the proposals. First, it isnecessary in order to be able to face new kinds of require-ments. Second, because of security purpose, having all theschemes relying on the same structure may lead to a disasterin case an attack breaks this structure. Hence, huge interna-tional projects have been funded to ask for new proposals,with a fair evaluation to check their advantages and draw-backs, for example, RIPE, NESSIE,
4
and NIST’s call for thedesign of the AES,
5
CRYPTREC,
6
ECRYPT,
7
and so forth.
2.2. Probabilisticencryption
The most well-known cryptosystems are
deterministic
: fora ﬁxed encryption key, a given plaintext will always be en-crypted in the same ciphertext. This may lead to some draw-backs. RSA is a good example to illustrate this point:(i) particular plaintexts may be encrypted in a too muchstructured way: with RSA, messages 0 and 1 are alwaysencrypted as 0 and 1, respectively;(ii) it may be easy to compute partial information aboutthe plaintext: with RSA, the ciphertext
c
leaks one bit
4
seehttp://www.cryptonessie.org.
5
seehttp://csrc.nist.gov andhttp://csrc.nist.gov/CryptoToolkit/aes.
6
seehttp://www.ipa.go.jp/security/enc/CRYPTREC/index-e.html.
7
seehttp://www.ecrypt.eu.org.
of information about the plaintext
m
, namely, the so-called Jacobi symbol;(iii) when using a deterministic encryption scheme, it iseasy to detect when the same message is sent twicewhile processed with the same key.So, in practice, we prefer encryption schemes to be prob-abilistic. In the case of symmetric schemes, we introduce arandomvectorintheencryptionprocess(e.g.,inthepseudo-random generator for stream ciphers, or in the operatingmode for block ciphers), generally called
IV
. This vectormay be public, and transmitted as it is, without being en-crypted, but
IV
must be changed every time we encrypta message. In the case of asymmetric ciphers, the security analysis is more mathematical, and we want the randomizedschemes to remain analyzable in the same way as the deter-ministic schemes. Some adequate modes have been proposedto randomize already published deterministic schemes, asthe Optimal Asymmetric Encryption Padding OAEP for RSA(or any scheme based on a trap-door one-way permutation)[33].
8
Some new schemes, randomized by nature, have alsobeen proposed [25,34,35] (see also Figures3and4).
A simple consequence of this requirement to be proba-bilistic appears in the so-called
expansion
: since for a plain-text we require the existence of several possible ciphertexts,the number of ciphertexts is greater than the number of pos-sibleplaintexts.Thismeanstheciphertextscannotbeasshortas the plaintexts, they have to be strictly longer. The ratiobetween the length, in bits, of ciphertexts and plaintexts iscalled the
expansion
. Of course, this parameter is of practicalimportance. We will see in the sequel that e
ﬃ
cient proba-bilistic encryption schemes have been proposed with an ex-pansion less than 2 (e.g., Paillier’s scheme).
2.3. Homomorphicencryption
We will present in this section the basic deﬁnitions related to
homomorphic
encryption. The state of the art will be given inSection 3.The most common deﬁnition is the following. Let
M
(resp.,
C
) denote the set of the plaintexts (resp., ciphertexts).An encryption scheme is said to be
homomorphic
if for any given encryption key
k
the encryption function
E
satisﬁes
∀
m
1
,
m
2
∈
M
,
E
m
1
M
m
2
←−
E
m
1
C
E
m
2
(1)for some operators
M
in
M
and
C
in
C
, where
←
means“can be directly computed from,” that is, without any inter-mediate decryption.If (
M
,
M
) and (
C
,
C
) are groups, we have a
group ho-momorphism
. We say a scheme is
additively homomorphic
if we consider addition operators, and
multiplicatively homo-morphic
if we consider multiplication operators.Alotofsuchhomomorphicschemeshavebeenpublishedthat have been widely used in many applications. Note that
8
Note that there are a lot of more recent papers proposing variants or im-provements of OAEP, but it is not our purpose here.
4 EURASIP Journal on Information Security
Prerequisite
: Alice and Bob share a secret random keystream, say a binary one.
Goal
: Alice can send an encrypted message to Bob, and Bob can send an encrypted message to Alice.
Principle
: To encrypt a message, Alice (resp., Bob) XORs the plaintext and the keystream. To decrypt the receivedmessage, Bob (resp., Alice) applies XOR on the ciphertext and the keystream.
Security
: This scheme has been showed to be unconditionally secure by Shannon [26] if and only if the keystream is truly random,has the same length as the plaintext, and is used only once. Thus, this scheme is used only for very critical situations forwhich these constraints may be managed, as the red phone used by the USA and the USSR [32, pp. 715-716]. What wemay use more commonly is a similar scheme, where the keystream is generated by a pseudorandom generator, initializedby the secret key shared by Alice and Bob. A lot of such stream ciphers has been proposed, and their security remainsonly empirical. Snow 2.0 is one of these.
Figure
1: One-time pad—1917(used)/1926 (published[22]). Note that this scheme may be transposed in any group (
G
,+) other than(
{
0,1
}
,XOR), encryption being related to addition of the keystream, while decryption consists in subtracting the keystream.
Prerequisite
: Alice computed a (public, private) key: an integer
n
=
pq
, where
p
and
q
are well chosen large prime numbers,an integer
e
such that gcd(
e
,
φ
(
n
))
=
1, and an integer
d
which is the inverse of
e
modulo
φ
(
n
), that is,
ed
≡
1 mod
φ
(
n
);
φ
(
n
) denotes the Euler function,
φ
(
n
)
=
φ
(
pq
)
=
(
p
−
1)(
q
−
1). Alice’s public key is (
n
,
e
), andher private key is
d
;
p
and
q
have also to be kept secret, but are no more needed to process the data, they were only useful for Alice to compute
d
from
e
.
Goal
: Anyone can send an encrypted message to Alice.
Principle
: To send an encrypted version of the message
m
to Alice, Bob computes
c
=
m
e
mod
n
. To get back to the plaintext,Alice computes
c
d
mod
n
which, according to Euler’s theorem, is precisely equal to
m
.
Security
: It is clear that if an opponent may factor
n
and recover
p
and
q
, he will be able to compute
φ
(
n
), then
d
, and will be ableto decrypt Alice messages. So, the RSA problem (accessing
m
while given
c
) is weaker than the factorizationproblem. It is not known whether the two problems are equivalent or not.
Figure
2: RSA—1978[24].
in some contexts it may be of great interest to have this prop-erty not only for one operator but for two at the same time.Hence, we are also interested in the design of
ring/algebraic homomorphisms
. Such schemes would satisfy a relation of theform
∀
m
1
,
m
2
∈
M
,
E
m
1
+
M
m
2
←−
E
m
1
+
C
E
m
2
,
E
m
1
×
M
m
2
←−
E
m
1
×
C
E
m
2
.
(2)As it will be further discussed, no convincing algebraic ho-momorphicencryptionschemehasbeenfoundyet,andtheirdesign remains an open problem.Less formally, these deﬁnitions mean that, for a ﬁxed key
k
, it is equivalent to perform operations on the plaintextsbefore encryption, or on the corresponding ciphertexts afterencryption. So we require a kind of commutativity betweenencryption and some data processing operations.Of course, the schemes we will consider in the followinghave to be probabilistic ciphers, and we may consider
E
tobehave in a probabilistic way in the above deﬁnitions.
2.4. Newsecurityconsiderations
Probabilistic encryption was introduced with a clear pur-pose: security. This requires to properly deﬁne di
ﬀ
erent se-curity levels.
Semantic security
was introduced in[34], at the
sametimeasprobabilisticencryption,inordertodeﬁnewhatcould be a strong security level, unavailable without proba-bilistic encryption. Roughly, a probabilistic encryption is
se-mantically secure
if the knowledge of a ciphertext does notprovide any useful information on the plaintext to some hy-potheticaladversaryhavingonlyareasonablyrestrictedcom-putational power. More formally, for any function
f
andany plaintext
m
, and with only polynomial resources (thatis, with algorithms which time/space complexities vary as apolynomial function of the size of the inputs), the probabil-ity to guess
f
(
m
) (knowing
f
but not
m
) does not increaseif the adversary knows a ciphertext corresponding to
m
. Thismight be thought of as a kind of perfect secrecy in the casewhen we only have polynomial resources.Together with this strong requirement, the notion of
polynomial security
was deﬁned: the adversary chooses twoplaintexts, and we choose secretly at random one plaintextand provide to the adversary a corresponding ciphertext. Theadversary, still with polynomial resources, must guess whichplaintext we chose. If the best he can do is to achieve a prob-ability 1
/
2 +
ε
of success, the encryption is said to be
polyno-mially secure
. Polynomial security is now known as the
indis-tinguishability of encryptions
following the terminology anddeﬁnitions of Goldreich [36].Quite amazingly, Goldwasser and Micali proved theequivalence between polynomial security and semantic se-curity [34]; Goldreich extended these notions [36] preserv-
ing the equivalence. With this equivalence, it is easy to statethat a deterministic asymmetric encryption scheme cannotbe semantically secure since it cannot be indistinguishable:the adversary knows the encryption function, and thus cancompute the single ciphertext corresponding to each plain-text.

Similar documents

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks