137
ing the underlying plaintext. In their El Gamal based
scheme,withmodulusasafeprimep= 2q+1,theproxy
is entrusted with the delegationkey b=a mod q forthe
purpose of divertingciphertexts from Alice to Bob via
computing (mg
k
mod p;(g
ak
)
b=a
mod p). The authors
noted, however, that this scheme containedan inherent
restriction: it is bidirectional; thatis, the value b=a can
beusedtodivertciphertextsfromAlicetoBobandvice
versa. Thus, this scheme is only useful when the trust
relationship between Alice and Bob is mutual. (This
problem can be solved, forany scheme, by generating
anadditional,otherwiseunused,keypairforthedelega-
tee, but this introduces additional overhead.) The BBS
scheme contains further problems. Delegation in the
BBS scheme is transitive, which means that the proxy
alone can create delegation rights between two entities
that have never agreed on this. For example, from the
values a=b andb=c, the proxycan re-encryptmessages
from Alice to Carol. Anotherdrawbacktothis scheme
isthatiftheproxyandBobcollude,theycanrecoverher
secretkeyas (a=b)b= a!
Jakobsson [26] developed a quorum-based protocol
where the proxy is divided into sub-components, each
controlling a share of the re-encryption key; here, the
keys of the delegator are safe so long as some of the
proxies arehonest. A similar approachwas considered
byZhou,Mars,SchneiderandRedz[39].
Recently, IvanandDodis[14]realizedunidirectional
proxy encryption for El Gamal, RSA, and an IBE
scheme by sharing the user’s secret key between two
parties. They also solved the problem of the proxy
alone assigning new delegation rights. In their unidi-
rectional El Gamal scheme, Alice’s secret key s is di-
vided into two shares s
1
and s
2
,where s = s
1
+s
2
,
and distributed to the proxy and Bob. On receiv-
ing ciphertexts of the form (mg
sk
;g
k
), the proxy rst
computes (mg
sk
=(g
k
)
s
1
), which Bob can decrypt as
(mg
s
2
k
=(g
k
)
s
2
) = m. Although this scheme offers
some advantages over the BBS approach, it introduces
newdrawbacksaswell. Thesesecret-sharingschemes
donotchange ciphertexts for Alice into ciphertexts for
Bob in the purest sense (i.e., so that Bob can decrypt
them withhis ownsecretkey),theydelegatedecryption
byrequiringBobtostore additionalsecrets (i.e., shares
fs
(i)
2
g)thatmayin practicebedifcultforhim toman-
age. For example, in our le system in Section 4, the
number of secrets a user must manage should remain
constant regardless of the number of les it accesses.
OneexceptionistheIvan-DodisIBEscheme[14]where
the global secret that decrypts all ciphertexts is shared
betweenthe proxyand thedelegatee. Thus, the delega-
teeneedonlystoreasinglesecret, butanobviousdraw-
backisthatwhentheproxyandanydelegateeinthesys-
temcollude,theycandecrypteveryoneelse’smessages.
Thus, proxy re-encryption protocols combining the
variousadvantagesoftheBBSandIvan-Dodisschemes,
along with new features such as time-limited delega-
tions, remained an open problem. (We provide a list
of these desirable features in Section 3.) Our re-
sults can be viewed as contributing both to the set of
key-insulated [12, 13, 15] and signcryption [3, 4, 38]
schemes, where Alice may expose her secret key with-
out needing to change her public key and/or use the
same public key for encryption and signing purposes.
This work should not be confused with the universal
re-encryption literature [24], which re-randomizes ci-
phertextsinsteadofchangingthe publickey.
1.2. Applications ofProxy Re›encryption
Proxy re-encryption has many exciting applications
in addition to the previous proposals [6, 14, 26, 39]
foremailforwarding,lawenforcement,andperforming
cryptographic operationsonstorage-limited devices. In
particular, proxy cryptographyhas natural applications
tosecurenetworklestorage. Thefollowingparagraphs
describepotentialapplicationsofproxyre-encryption.
SecureFileSystems. Asecurele system is anatural
application of proxy re-encryption because the system
oftenassumesamodelofuntrustedstorage.
Anumberofdistributedlesystemsbuildcondential
storage out of untrusted components by using crypto-
graphicstorage[2, 5,22,28]. Condentialityisobtained
by encrypting the contents of stored les. These en-
cryptedlescanthenbestoredonuntrustedleservers.
Theserveroperatorscandistributeencryptedles with-
outhavingaccess totheplaintextles themselves.
Inasingle-usercryptographiclesystem,accesscon-
trolis straightforward. Theusercreates allthekeys pro-
tectingcontent. Thus, thereis nokeydistributionprob-
lem. Withgroupsharingincryptographicstorage,group
membersmustrendezvouswithcontentownerstoobtain
decryptionkeysforaccessingles.
Systems with cryptographic storage such as the
SWALLOW object store [32]or CNFS [25]assume an
out-of-bandmechanism for distributingkeys for access
control. Other systems such as Cepheus [18] use a
trustedaccess controlservertodistributekeys.
Theaccess controlservermodelrequires agreat deal
oftrustintheserveroperator. Shouldtheoperatorprove
unworthyofthistrust,heorshecouldabusetheserver’s
key material to decrypt any data stored on the system.
174
Furthermore,eveniftheaccesscontrolserveroperatoris
trustworthy,placingsomuchcriticalkeydatainasingle
locationmakesforaninvitingtarget.
In contrast, our system makes use of a semi-trusted
access controlserver. We proposeasignicant security
improvementtotheaccesscontrolincryptographicstor-
age, usingproxycryptographytoreduce the amountof
trustintheaccess controlserver. Inourapproach,keys
protectinglesarestoredencryptedunderamasterpub-
lic key, usingone ofthe schemes in Section 3. When a
userrequestsa key,the access controlserveruses proxy
cryptographyto directly re-encrypt the appropriate key
totheuserwithout learningthe keyin the process. Be-
cause the access control server does not itself possess
the master secret, it cannot decrypt the keys it stores.
The master secret key can be stored ofine, by a con-
tentownerwhousesitonlytogeneratethere-encryption
keysusedbythe access controlserver. InSection 4, we
describeourimplementationandprovideaperformance
evaluationofourconstructions.
Outsourced Filtering of Encrypted Spam. Another
promising applicationof proxy re-encryption is the l-
teringofencryptedemailsperformedbyauthorizedcon-
tractors. The sheer volume of unsolicited email, along
with rapid advances in lter-avoidance techniques, has
overwhelmedthelteringcapabilityofmanysmallbusi-
nesses, leading to a potential market for outsourced
email ltering. New privacy regulations, such as
the US Health Insurance Portability and Accountabil-
ity Act (HIPAA), are encouraging companies to adopt
institution-wideemailencryptiontoensurecondential-
ity of patient information [1]. By accepting encrypted
emailfrom outside sources,institutionsbecomespam
targets and lters are only effective on messages that
arerstdecrypted(whichcouldbeunacceptablycostly).
Usingproxyre-encryption, it becomes possibletoredi-
rect incoming encrypted email to an external ltering
contractorattheinitialmailgateway,withoutriskingex-
posureofplaintextsatthegatewayitself. Usingourtem-
porary proxy re-encryption scheme presented in Sec-
tion3.2,ahealthcareinstitutioncanperiodicallychange
lteringcontractorswithoutchangingitspublickey.
1.3. Roadmap
The rest ofthis paperconsists ofthefollowing. Sec-
tion 2 gives some number theoretic preliminaries and
denitions necessary to understand our schemes and
their security guarantees. Section 3 presents improved
proxy re-encryption schemes as well as a discussion
on the factors to consider when comparing proxy re-
encryption schemes. Section 4 highlights the design,
implementation, and performancemeasurementsofour
proxyre-encryptionlesystem. Weprovideconcluding
remarksinSection5.
2. Denitions
Ourprotocolsarebasedonbilinearmaps[7,8,9,27]),
whichweimplementedusingthefastTatepairings[21].
Denition 2.1(BilinearMap) Wesay amape : G
1
^
G
1
!G
2
isabilinearmapif: (1)G
1
andG
2
aregroups
ofthesame primeorderq;(2)foralla;b2 Z
q
,g 2G
1
,
and h 2
^
G
1
, then e(g
a
;h
b
) = e(g;h)
ab
is efciently
computable; (3) the map is non-degenerate (i.e., if g
generates G
1
and h generates
^
G
1
, then e(g;h) gener-
atesG
2
);and(4)thereexistsacomputableisomorphism
from
^
G
1
toG
1
.(Here,G
1
mayequal
^
G
1
.)
Now, we explainthedifferentcomponents ofa proxy
re-encryption scheme. We willbe informal in this sec-
tion, referring an interested reader to Appendix A for
precisedenitions.
Denition 2.2(UnidirectionalProxyRe-encryption)
A re-encryption scheme is a tuple of (possi-
bly probabilistic) polynomial time algorithms
(KG;RG;
~
E;R;
~
D), where:
(KG;
~
E;
~
D) formthestandardkeygeneration, en-
cryption, anddecryptionalgorithms.
On input (pk
A
;sk
A
;pk
B
;sk
B
), the re-encryption
key generation algorithm, RG, outputs a key
rk
A!B
for the proxy. The fourth input marked
witha’’is optional.
On input rk
A!B
and ciphertext C
A
, the re-
encryptionfunction, R,outputsC
B
.
Correctness. Alice should always be able to de-
crypt ciphertexts encrypted under pk
A
; while Bob
should be able to decrypt re-encrypted ciphertexts
R(rk
A!B
;C
A
). The encryption algorithm
~
Emay al-
low multiple types of encryption, suchas rst-level en-
cryptions that cannot be re-encrypted and second-level
encryptions that canbe. This gives the sendera choice
between encrypting a message only to Alice or to Al-
ice and herdelegateeBobwithinthe samesystem. For
re-encryptedciphertexts, we requirethattheunderlying
plaintextremainconsistenti.e.,Bobshouldgetexactly
whatAlicewassupposedtoreceive.1
1
Note, this only applies to ciphertexts that were honestly gener-
ated by thesender; no guaranteeisimplied inthecaseofmalformed
ciphertexts.
147
Security. Our security denition has two parts: stan-
dard security, requiring that the cryptosystem remain
semantically-secure [23] even when all re-encryption
keysarepublic;andmastersecretsecurity,whereadel-
egator’smastersecretkeyis not recoverable. Oursecu-
rity denition is similarto that of IvanandDodis [14].
Although their denition was for CCA2 security, they
instead used CPA security for the El Gamal, RSA, and
IBE-basedschemes. The rst main differencebetween
ourdenitions is thatweconsiderthe securityofauser
against a group of colluding parties; i.e., the security
of a delegator against the proxy and many delegatees,
whereas the Ivan-Dodis denition focused on a single
delegatee. Second, we discuss the system’s securityfor
circulardelegations;thatis, whenanadversarywatches
Alice and Bob delegate to each other. Finally, master
secretsecurityis anewguaranteeforthedelegator.
3. ImprovedProxy Re-encryption Schemes
Totalkaboutimprovements,weneedtogetasense
ofthebenetsanddrawbacksofpreviousschemes. Here
isa listof, inouropinion, themost usefulpropertiesof
proxyre-encryptionprotocols:
1. Unidirectional: Delegationfrom A ! B does not
allowre-encryptionfromB ! A.
2. Non-interactive:Re-encryptionkeyscanbegener-
ated by Alice using Bob’s public key; no trusted third
party or interaction is required. (Such schemes were
calledpassiveinBBS[6].)
3. Proxy invisibility: This is an importantfeatureof-
fered by the original BBS scheme. The proxy in the
BBS schemeis transparentin the sensethatneitherthe
sender of an encrypted message nor any of the dele-
gatees have to be aware of the existence of the proxy.
Clearly, transparencyisverydesirable butit is achieved
intheBBSschemeatthepriceofallowingtransitivityof
delegationsandrecoveryofthemastersecretsofthepar-
ticipants. Our pairing-based schemes, to be described
shortly, offer a weaker form of transparencywhich we
callproxyinvisibility. Inparticular, we allowthesender
tobeawareoftheproxyanddecidewhethertogenerate
an encryption that can be opened only by the intended
recipient(rst-levelencryption)orby anyofthe recipi-
ent’sdelegatees(second-levelencryption). Ontheother
hand, wecanensure that anydelegateewillnotbeable
to distinguish a rst-level encryption (computed under
his public key)from a re-encryptionof a ciphertext in-
tended for another party (we are assuming that the en-
cryptedmessagedoesnotrevealinformationthatwould
helpthedelegateetomakethisdistinction).
4. Original-access: Alice can decrypt re-encrypted
Property
BBS [6] ID[14] Thiswork
1. Unidirectional
No
Yes
Yes
2. Non-interactive
No
Yes
Yes
3. Proxyinvisible
Yes
No
Yes
4. Original-access
Yes
y
Yes
Yes
y
5. Keyoptimal
Yes
No
Yes
6. Collusion-safe
No
No
Yes
7. Temporary
Yes
y
Yes
y
Yes
y
8. Non-transitive
No
Yes
Yes
9. Non-transferable
No
No
No
Table 1. We compare known proxy re›
encryption schemes based on the ad›
vantages described above; no scheme
achieves property 9. We refer to the uni›
directionalschemes of Ivan›Dodis. indi›
cates master secret key only. y indicates
possible to achieve with additional over›
head.
ciphertexts thatwere originallysenttoher. Insome ap-
plications, itmaybe desirabletomaintainaccess to her
re-encryptedciphertexts. This is an inherent feature of
the Ivan-Dodis schemes (since the re-encryptionkey is
ashare ofthe original); the BBS scheme and the pair-
ing schemes presentedhere can achieve this feature by
adding an additional term to the ciphertext: for exam-
ple, in BBS a re-encrypted ciphertext with original ac-
cess looks like (mg
k
;g
ak
;(g
ak
)
b=a
). This may impact
proxyinvisibility.
5. Key optimal: The size of Bob’s secret storage re-
mains constant, regardless ofhow manydelegations he
accepts. We call this a key optimalscheme. Inthepre-
vious ElGamal and RSAbasedschemes [14], the stor-
age of both Bob and the proxy grows linearly with the
numberofdelegationsBobaccepts. Thisisanimportant
consideration, since the safeguardingand management
ofsecretkeysisoftendifcultinpractice.
6. Collusion-safe: One drawback of all previous
schemes is thatbycolludingBobandthe proxycanre-
coverAlice’s secret key: for Ivan-Dodis, s = s
1
+s
2
;
forBBS,a = (a=b)b. Wewillmitigatethis problem
allowingrecoveryofa weaksecret key only. Ina bi-
linearmapsetting,supposeAlice’spublickeyise(g;g)
a
andhersecretkeyis a;thenwemightallowBobandthe
proxytorecoverthevaluega, butnotaitself. Thus,Al-
icecandelegatedecryptionrights,whilekeepingsigning
rights forthesamepublickey. Inpractice, ausercanal-
ways usetwopublickeysforencryptionandsignatures,
butitis theoreticallyinterestingthatshedoesn’tneedto
doso. Prior work on signcryption exploredthis area
(e.g., [38, 4, 3]); here we present, what can be viewed
185
as, therstsignREcryptionscheme(althoughwewill
not be formallyconcerning ourselves with the security
ofthesignaturesinthiswork).
7. Temporary: Ivan and Dodis [14] suggested ap-
plying generickey-insulationtechniques [15, 12, 13]to
theirconstructions to form schemes where Bob is only
able to decrypt messages intended for Alice that were
authored during some specic time period i. Citing
space considerations, theydidnotpresent any concrete
constructions. InSection3.2, weprovideabilinearmap
construction designed specically for this purpose. In
our construction,a trustedserverbroadcasts a newran-
dom numberat each time period, which each user can
thenusetoupdatetheirdelegatedsecretkeys. Thisisan
improvementover using currentkey-insulated schemes
where the trusted server needs to individually interact
with each user to help them update their master (and
therefore,delegation)secretkeys.
8. Non-transitive: The proxy, alone, cannot re-
delegate decryption rights. For example, from rk
a!b
andrk
b!c
,hecannotproducerk
a!c
.
9. Non-transferable: The proxy and a set of collud-
ingdelegateescannotre-delegatedecryptionrights. For
example, from rk
a!b
, sk
b
,and pk
c
, they cannot pro-
duce rk
a!c
.We are not aware of any scheme that has
thisproperty,anditisaverydesirableone. Forinstance,
ahospitalmaybeheldlegallyresponsibleforsafeguard-
ing the encryptedlesofitspatients;thus, ifit chooses
todelegatedecryptioncapabilities to a local pharmacy,
itmay needsomeguaranteethatthis informationgoes
nofurther. First, we shouldask ourselves: is transfer-
abilityreallypreventable?Thepharmacycanalwaysde-
cryptand forwardthe plaintextlestoa drugcompany.
However, this approachrequires that the pharmacy re-
mainanactive, onlineparticipant. Whatwewanttopre-
ventisthepharmacy(plustheproxy)providingthedrug
companywithasecretvaluethatitcanuseofinetode-
crypt the hospital’s ciphertexts. Again, the pharmacy
can trivially send its secret key to the drug company.
Butindoingso, it assumes a securityriskthat is as po-
tentially injurious toitselfas the hospital. Achieving a
proxyschemethat is non-transferable,inthesense that
theonlywayforBobtotransferofinedecryptioncapa-
bilitiestoCarolistoexposehisownsecretkey,seemsto
bethemainopenproblem leftforproxyre-encryption.
3.1. New Unidirectional Proxy Re›encryption
Schemes
A First Attempt.
As Ivan and Dodis pointed
out [14], one method for constructing proxy re-
encryption schemes is to create a cryptosystem that
hastwodecryptionalgorithms withtwo differentsecret
keys. Thesecryptosystemstypicallysupportarst-level
secret key that decrypts all ciphertexts encryptedunder
the correspondingpublickey, and a second-level secret
key that maydecryptonlyciphertextsofa certainform
underthe same public key. Notice thatthere are trivial
solutions to the proxyre-encryption problem when Al-
iceis allowedtouse twodifferentkeypairs, butwe are
interestedinsolutions thatminimizethenumbertokeys
tosafeguardandmanagewhileremainingefcient.
Inthe fullversionofthis paper, we present a variant
of the Paillier cryptosystem with rst and second-level
secret keys proposed by Cramer and Shoup [11]. Al-
ice keeps the rst-level key for herself and sends the
second-level key to Bob as a delegation, with a proxy
added to further regulate which ciphertexts Bob may
read. Thisapproachisinteresting,becauseitisbasedon
an assumption otherthan bilinearmaps; and offers the
collusion-safety (i.e., protection of the rst-level se-
cretkey)thattheschemesofIvan-Dodislack. However,
liketheIvan-Dodisschemes [14],itisnotkeyoptimal.
ASecondAttempt. Tominimizeauser’ssecretstorage
andthus become key optimal, we presentthe BBS [6],
ElGamalbased[16]schemeoperatingovertwo groups
G
1
;G
2
of primeorderq witha bilinearmape : G
2
1
!
G
2
. The system parameters are random generatorsg 2
G
1
andZ = e(g;g) 2G
2
.
KeyGeneration (KG). AuserA’s keypair is of
theformpk
a
=g
a
;sk
a
=a:
Re-Encryption Key Generation (RG). A user A
delegatestoB bypublishingthere-encryptionkey
rk
A!B
=gb=a 2 G
1
,computedfrom B’s public
key.
First-Level Encryption (E
1
). To encrypt a mes-
sage m 2 G
2
under pk
a
in such a way that it
canonlybedecryptedbytheholderofsk
a
,output
c= (Z
ak
;mZ
k
).
Second-LevelEncryption(E
2
). Toencryptames-
sage m 2 G
2
under pk
a
in such a way that it
canbe decrypted by A and her delegatees, output
c= (g
ak
;mZ
k
).
Re-Encryption(R). Anyonecanchangeasecond-
levelciphertextforAintoarst-levelciphertextfor
Bwithrk
A!B
=g
b=a
. From c
a
=(g
ak
;mZ
k
),
compute e(g
ak
;g
b=a
) = Z
bk
and publish c
b
=
(Z
bk
;mZ
k
).
Decryption (D
1
). To decrypt a rst-level cipher-
text c
a
= (;) with sk = a, compute m =
=1=a.
Discussion of Scheme. This scheme is very attractive;
363
it is unidirectional, non-interactive, proxy transparent,
collusion-safe, key optimal, and non-transitive. How-
ever, its security requires the assumptionthat a cannot
bederivedfrom seeingthea-throotofapolynomialset
ofrandomvalues(whichisplausibleinagroupofprime
order), inaddition totheassumption that the following
problemis hardin(G
1
;G
2
):
Given(g;g
a
;g
b
;Q), forg G
1
; a;b Z
q
andQ2 G
2
,decideifQ= e(g;g)
a=b
:
There isevidencethat the computationalBilinear In-
verse Dife-Hellman problem is hard[37], but this de-
cisionalversionhas not been studied enough. Next, we
provide a solution which makes fewer (and more stan-
dard)assumptions.
AThird Attempt. Theglobalsystemparameters(g;Z)
remainunchanged.
KeyGeneration (KG). A userA’s key pair is of
the form pk
a
= (Za
1
;ga
2
)and sk
a
= (a
1
;a
2
).
(Ausercan encrypt, sign, anddelegate decryption
rights allunder Z
a
1
;if the value g
a
2
is present, it
signies that the user is willing to accept delega-
tions.)
Re-Encryption Key Generation (RG). A user
Adelegatesto B publishingthere-encryptionkey
rk
A!B
=g
a
1
b
2
2G
1
,computedfromB’s public
information.
First-Level Encryption (E
1
). To encrypt a mes-
sage m 2 G
2
under pk
a
in such a way that it
canonlybe decryptedbytheholderofsk
a
,output
c
a;1
=(Z
a
1
k
;mZ
k
)(toachieve proxy invisibility
outputc
a;1
=(Z
a
2
k
;mZ
k
)atnosecurityloss).
Second-LevelEncryption(E
2
). Toencryptames-
sage m 2 G
2
under pk
a
in such a way that it
can be decrypted byA and her delegatees, output
c
a;r
=(g
k
;mZ
a
1
k
).
Re-Encryption (R). Anyonecanchangeasecond-
level ciphertext for A into a rst-level cipher-
text for B with rk
A!B
=
g
a
1
b
2
.
From
c
a;r
= (g
k
;mZ
a
1
k
), compute e(g
k
;g
a
1
b
2
) =
Z
b
2
a
1
k
and publish c
b;2
= (Z
b
2
a
1
k
;mZ
a
1
k
) =
(Z
b
2
k
0
;mZ
k
0
).
Decryption (D
1
;D
2
). To decrypt a rst-level ci-
phertextc
a;i
=(;) with secret key sk
a
,output
=
1=a
i
=mfori2 f1;2g.
DiscussionofScheme. Thisschemeissimilartothepre-
viousone,excepttoacceptdelegations,ausermuststore
two secret keys. The security of this scheme relies on
an extension of the decisional bilinear Dife-Hellman
(DBDH) assumption [7, 10]; the proof of Boneh and
Franklin[7] that the DBDHproblem is hardin generic
groups, in the sense of Shoup [36], can be easily ex-
tended to this problem, when one recalls that the ad-
ditional parameter e(g;g)bc
2
is represented as a ran-
dom string in the range of the mapping. Furthermore,
we note that the semantic security for a user who ac-
cepts, but does not give delegations can be reduced to
the CoDDH problem; that is, given (g;g
a
;Z
b
;Q) for
random a;b Z
q
and an elementQ 2 G
2
,decide if
Q = Z
ab
. Original rst-level ciphertexts of the form
(Z
a
2
k
;mZ
k
)are exactly like El Gamal [16] and thus
their security only depends on DDH in G
2
. However,
under the CoDDH assumption, Alice’s security is as-
sured even when people send her second-level cipher-
texts (not knowing that she isn’t making any delega-
tions). ProofofTheorem3.1isinAppendixB.
Theorem 3.1 The above scheme is correct and secure
assuming thatfor random g G
1
,a;b;c Z
q
,and
Q2 G
2
,given (g;g
a
;g
b
;g
c
;e(g;g)
bc
2
;Q)it is hard to
decideifQ= e(g;g)
abc
(standardsecurity)andthedis-
cretelogarithmassumption(master secretsecurity).
3.2. Temporary Unidirectional Proxy Re›
encryption
In addition to the global parameters (g;Z), suppose
there is atrusted serverthat broadcasts a random value
h
i
2G
1
foreachtimeperiodi 1 forall users tosee.
LetZ
i
=e(g;h
i
)2G
2
.WeenableAlicetodelegateto
Bobonlyfortimeperiodi, say, whilesheis onvacation,
asfollows.
KeyGeneration (KG). AuserA’s keypair is of
theform pk
a
=(g
a
0
;g
a
r
);sk
a
=(a
0
;a
r
), (plusa
temporarysecreta
i
fortimeperiodiwhichwillbe
generatedinRG).
Re-Encryption Key Generation (RG). A user A
publiclydelegatestoB duringtimeperiodias fol-
lows: (1) B chooses and stores a random value
b
i
2Z
q
,and publishes h
b
i
i
;then, (2) A computes
andpublishes rk
i
A!B
=h
a
r
b
i
=a
0
i
.
First-LevelEncryption (E
1
). Toencryptm 2G
2
under pk
a
during time period i, output c
a;0
=
(Z
a
0
k
i
;mZ
k
i
).
Second-LevelEncryption (E
2
). To encryptm 2
G
2
under pk
a
during time period i, output c
a;i
=
(g
a
0
k
;mZ
a
r
k
i
).
Re-Encryption(R). Anyonecanchangeasecond-
level ciphertext for A into a rst-level ciphertext
for B with rk
A!B;i
= h
a
r
b
i
=a
0
i
. From c
a;i
=
173
(g
a
0
k
;mZ
a
r
k
i
), compute e(g
a
0
k
;rk
A!B
)
=
Z
b
i
a
r
k
i
and publish c
b;i
= (Z
b
i
a
r
k
i
;mZ
a
r
k
i
) =
(Z
b
i
k
0
i
;mZk
0
i
).
Decryption (D
1
). To decryptc
a;i
=(;), com-
putem= =
1=a
i
fora
i
2fa
0
;a
1
;a
2
;:::g.
DiscussionofScheme.Asingleglobalchangecaninval-
idate all previous delegations withoutanyuser needing
tochangetheirpublickey. ProofofTheorem3.2appears
inthefullversionofthis paper.
Theorem 3.2 The above scheme is correct and secure
assuming that for randomg G
1
,a;b;c Z
q
and
Q2 G
2
,given (g;g
a
;g
b
;g
c
;Q) it is hard to decide if
Q = e(g;g)
ab
2
=c
(standard security) and the discrete
logarithmassumption(mastersecretsecurity).
4. Encrypted File Storage
Our le system uses an untrusted access control
server to manage access to encrypted les stored on
distributed, untrusted block stores. We use proxy re-
encryption toallow foraccess control withoutgranting
fulldecryptionrightstotheaccess controlserver.
To our knowledge, no experimental implementation
ofproxyre-encryptionexists,whichmakesitdifcultto
argueabouttheeffectivenessoftheproxyre-encryption
primitive.
Overview. In ourle system, enduserson client ma-
chineswishtoobtainaccess tointegrity-protected,con-
dential content. A contentownerpublishes encrypted
contentin the form ofa many-reader, single-writer le
system. The owner encrypts blocks of content with
unique, symmetric content keys. A contentkeyis then
encryptedwithanasymmetricmasterkeytoformalock-
box. Thelockboxresides withtheblockitprotects.
Untrusted block stores make the encrypted content
available to everyone. Users download the encrypted
content from a block store, then communicate with an
access control serverto decryptthe lockboxes protect-
ing the content. The contentownerselects whichusers
should have access to the content and gives the appro-
priate delegationrightstothe access controlserver.
AccessControlUsingProxyCryptography. Wepro-
poseanimprovementontheaccesscontrolservermodel
that reduces the server’s trust requirements by using
proxycryptography. In ourapproach, the keys used to
encrypt les are themselvessecurelyencryptedundera
masterpublickey,usingoneoftheschemesinSection3.
Because the access controlserver does not possess the
mastersecret,itcannotbecorruptedsoastogainaccess
to the le keys and access encrypted les. The secret
master secret key remains ofine, in the care of a con-
tentownerwhousesitonlytogeneratethere-encryption
keys used bythe access controlserver. When anautho-
rized user requests access to a le, the access control
serverusesproxycryptographytodirectlyre-encryptthe
appropriatecontentkey(s)from themasterpublickeyto
the user’spublickey.
Thisarchitecture has signicantadvantagesoversys-
tems withtrustedaccess controlservers. Thekeymate-
rialstoredontheaccesscontrolservercannotbeusedto
accessstoredles, whichreducestheneedtoabsolutely
trust the server operator, and diminishes the server’s
value to attackers. The master secret key itself is only
requiredby acontentownerwhen new users are added
tothe system, andcantherefore be storedsafelyofine
where it is less vulnerable to compromise. Finally the
schemes in Section 3 are unidirectional, meaning that
users do not need to reveal or otherwise compromise
theirsecretkeysinordertojointhesystem. Thisallows
contentownerstoaddusers tothesystemwithoutinter-
action, simply by obtaining their public key. Because
this system works with users’ long-term keys (rather
than generating ephemeral keys for the user), there is
an additional incentive for users not to reveal their de-
cryptionkeys.
The proposed design fundamentally changes the se-
curityofanaccesscontrolserverstoragesystem. Inthis
newmodel,muchofthesecurityreliesonthestrengthof
aprovably-securecryptosystem, ratherthan onthetrust
of a server operator for mediating access control. Be-
cause the access control servercannot successfully re-
encrypt a le key to a user without possessing a valid
delegationkey,theaccesscontrolservercannotbemade
to divulge le keys to a user who has not been specif-
ically authorized by the content owner, unless this at-
tacker has previously stolen a legitimate user’s secret
key.
Chefs. We implemented our le system on top of
Chefs[19],a condentiality-enabledversionofthe SFS
Read-Only le system [20]. Chefs is a single-writer,
many-readerle system thatprovides decentralized ac-
cess control in integrity-protected content distribution.
Acontent owner creates a signed, encrypted database
from a directory tree of content. The database is then
replicatedonuntrustedhosts(e.g., volunteers). Aclient
locatesareplica,thenrequeststheencryptedblocks.
Chefs tags each content block with a lockbox. The
lockbox contains a 128-bit AES key, itself encrypted
79
4. Re-encrypted lockbox
3. Encrypted lockbox
1. Block request
Block Store
Client
Access Control
Server
2. Encrypted data block
Figure 1. Typical operation of the proxy re›encryption le system. The user’s client machine
fetchesencryptedblocksfrom the blockstore. Eachblock includes alockboxencryptedunder
amaster public key. The client then transmits lockboxes to the access control server for re›
encryption under the user’s public key. If the access control server possesses the necessary
re›encryption key, it re›encrypts the lockbox and returns the new ciphertext. The client can
then decryptthe re›encrypted block with the user’s secretkey.
withasharedgroupAES key. Chefsassumes anout-of-
band mechanism forcontentowners todistribute group
keystousers.
WechosetheChefsarchitecturebecauseitallowedus
toexperiment withdifferent granularities ofencryption
(per-leandper-directory)whileprovidingatransparent
lesysteminterfaceforourexperiments.
4.1. Designand Implementation
WemodiedChefstoincludeanaccesscontrolserver.
Every block in a Chefs database is encrypted with a
128-bitAES contentkeyin CBC mode. Dependingon
the granularityof the encryption, a content key can be
sharedacross all oftheblocksinaparticularle, direc-
tory or database, or unique keys can be used for each
block. Content keys are themselves encrypted under
asystem master key using the third bilinear El Gamal
scheme from Section 3.1. This encryption results in a
setoflockboxesstoredwiththeledata, eitherinleor
directoryinodes (per-le and per-directoryencryption)
orwithintheblocks themselves(per-blockencryption).
The proxyre-encryptionmakes the sealed lockbox 512
bits,eventhoughitstillonlyprotectsa128-bitAESkey.
Whenaclientencountersablockforwhichitdoesnot
possess a content key, it asks the access control server
to re-encrypt the lockbox from the master key to the
client’spublickey. Iftheaccesscontrolserverpossesses
anappropriatere-encryptionkeyforthisclientandmas-
terkey, itperforms the appropriateproxyre-encryption
and returns the result to the client, which can then de-
cryptthelockbox. Figure1illustratesthis procedure.
Each re-encryption call necessarily results in a
round-trip network request, in addition to the proxy
re-encryption and client-side decryption of the re-
encrypted ciphertext. Thus, the choice of encryption
granularity greatly affects the number of re-encryption
calls made from the client to the access control server,
whichinturnaffects theperformanceofthesystem.
4.2. ExperimentalResults
In implementing a proxy re-encryption le system,
we had two goals in mind. First, we wished to show
that proxyre-encryptioncouldbesuccessfully incorpo-
ratedintoabasiccryptographiclesystem. Second,we
sought to prove that the additional security semantics
providedbya proxyre-encryptingaccesscontrolserver
cameatanacceptablecosttosystem performance.
To achieve this second goal, we conducted a num-
ber of benchmarks using the proxy-enabled Chefs le
system, using various granularities of content key us-
age (per-block and per-le). Along with these exper-
iments, we conducted microbenchmarks of the proxy
re-encryption functions used in our implementation, as
wellasapplication-levelbenchmarksmeasuringlesys-
tem performance. To provide a standard of compari-
son,weconductedthesame experimentsonanunmodi-
edChefscongurationwithnoaccesscontrolserveror
proxyre-encryption,usingonlyasinglepresetAES key
tosecurethe contentsofthedatabase.
Experimental Setup. For the purposes of our test-
ing, we used two machines to benchmark the proxy-
enabled Chefs le system. The client machine con-
sisted of an AMD Athlon 2100+ 1.8 GHz with 1 GB
RAM and an IBM 7200 RPM, 40 GB, Ultra ATA/100
hard drive. The server machine was an Intel Pentium
42.8 GHz with 1 GB RAM and a Seagate Barracuda
7200 RPM, 160 GB, Ultra ATA/100 hard drive. Both
101
Parameter
Encryption
Decryption
Re-encryption
Decryption
size
(byoriginalrecipient)
(bydelegatee)
256-bit
3.1ms
8.6ms
8.4ms
1.5ms
512-bit
7.7ms
21.9ms
21.7ms
3.4ms
Table2.Average operationtimes for the bilinear El Gamalproxy re›encryptionscheme on
our clientmachine. Alloperations refer to re›encryptable second›levelciphertexts.
systems were running Debian testing/unstable. The
client and the server were situated in different cities,
representingadistributedlesystem scenario. Wemea-
sured the round-triplatency between the twomachines
at13ms, andthemaximumsustainedthroughputofthe
networklinkat 7 Mbit/sec. We implementedthe cryp-
tographic primitives for the bilinear El Gamal scheme
using version 4.83 of the MIRACL cryptographic li-
brary[35], which contains efcientimplementationsof
the Tate pairing as well as fastmodularexponentiation
andpointmultiplication.
Cryptographic Benchmark. Average times for the
cryptographic operations in the bilinear proxy re-
encryption scheme (thethirdone from Section3.1)are
giveninTable2,andprovidesomebasisforunderstand-
ing the impact of the proxy re-encryption on overall
le system performance. These results indicate that re-
encryptionistheoneofthemosttime-consumingofthe
cryptographic operations performed in our le system.
Inourlesystem, weuse512-bitproxyre-encryptionto
protectcontentkeys in lockboxes.
We conducted our benchmarks using the 512-bit pa-
rameter size for the proxy re-encryption scheme, and
various encryption granularities, including per-block
and per-le. Our microbenchmarks, presented in Fig-
ures 2 and 3, include runs of the small-le and large-
le tests from the LFS suiteofle system performance
tests [33]. We use the read phases of the LFS test to
measurethefundamentalperformanceofoursystem.
The rst test consists of a sequential read of a large
le. Thesecondtestreads severalsmallles. Thesetwo
tests capture common workloads in a typical le sys-
tem. Foreach ofthesetests, weexperimentedwithdif-
ferent encryptiongranularities, includingper-blockand
per-le settings. The smallle benchmarkin particular
isaworst-casescenarioforaproxy-enabledlesystem,
as it requires a largenumberoflockboxre-encryptions
relativeto the amount of data read. On the otherhand,
the large-le case tends to exhibit exactly the opposite
effect,astheratioofre-encryptionstodatareadismuch
smaller. In general, all per-block encryption scenarios
tend to be the least efcient (andleast practical) when
proxyre-encryptionisenabled.
Small-leBenchmark. TheSFSROandChefsbench-
marks each generate 2,022RPCs to fetch content from
the blockstore(1,000 les, 10 directories, and oneroot
directory eachgeneratingtwoRPCs: one forthe in-
ode, oneforthecontent).
Note that Chefs adds virtually no discernible over-
head,eventhoughtheclientdecryptseverycontentfetch
with 128-bit AES in CBC mode. With the round-trip
time accounting foratleast26seconds ofthe measure-
ment, the network overshadows the cost of cryptogra-
phy.
Theproxyre-encryptionlesystem rstmakes 2,022
fetches of content, just like Chefs. With per-le gran-
ularityofcontentkeys, the small-lebenchmarkgener-
ates1,011re-encryptionRPCs. Theproxyre-encryption
le system takes about 44 seconds longer than Chefs.
We attribute 39 seconds ofthis difference tothe 13 ms
round-trip time, 21.7 ms re-encryption time on the
server, and 3.4 ms delegatee decryption time on the
client foreach RPC (See Table 2). We hopeto explain
the remaining 5 seconds by conducting measurements
onisolatedportionsofourclientcode.
With per-blockgranularity, the small-le benchmark
generates 2,022re-encryptionRPCs. Aleordirectory
consists ofaninodeanddata block, thus eachreadnow
generates two re-encryptions. The proxyre-encryption
le system takes about 87 seconds longer than Chefs.
Because the per-blockre-encryptiongenerates twice as
many re-encryption RPCs as the per-le scenario, the
resultsconcurwithourexpectations.
Large-le Benchmark. The large-le benchmark
generates 5,124 RPCs to fetch 40 MB ofcontent from
the blockstore(twoRPCs fortherootdirectory,twofor
the le, and 5,120 forthele data). Inthe SFSRO and
Chefsexperiments, the7MBitbandwidthlargelydomi-
nates thethroughput.
Becausethelarge-leworkloadinvolvesonlyasingle
le, the per-le proxy re-encryption has nodiscernible
93
0
50
100
Read time (seconds)
SF
S
R
O
C
h
efs
P
er file
P
er b
lock
Proxy
Re-encryption
Figure 2. Small›le microbenchmark from
LFSsuite. We perform acomplete read on
1,0001KBlesdispersedin10directories.
0.0
0.2
0.4
0.6
0.8
Throughput (MBytes/s)
S
F
SR
O
C
h
efs
P
er file
P
er b
lo
ck
Proxy
Re-encryption
Figure 3. Large›le microbenchmark from
LFS suite. We perform a sequential read
on a 40 MB le in 8 KBblocks.
cost. There are a mere two proxyre-encryptionRPCs
(oneforthe root, one forthele). Theper-blockproxy
re-encryptiongenerates 5,124re-encryptionRPCs, thus
we expect a signicant degradation of throughput be-
causeofthenumberofextraround-trips.
The cost of per-block re-encryption is prohibitively
expensive for large les. We expect that per-le gran-
ularityorper-le-systemgranularitywillbe muchmore
common than per-block granularity. For instance, we
donotexpectusersto grant access to portions ofa sin-
gle le. Rather, we expect users would share access-
controlledcontentincollections ofles similarto a
collectionofWebpagesora directorysubtree.
Application-levelBenchmark. Ourapplication-level
benchmarkconsists ofanEmacs version21.3compila-
tion. Thesourcecode is storedinourlesystem, while
the resulting binaries are written to a local disk. This
workload requires access to approximately 300 les.
The results of this test are presented in Figure 4, and
show that the per-le and even per-block proxy cryp-
tography adds negligible overhead for this application
workload. We believe the cost is nominal forthe addi-
tionalsecuritysemantics ofproxyre-encryption.
Scalability. We also measured how well the access
control server performs under a heavy load. Figure 5
showsthatourproxyre-encryptionservercanscaleupto
1,000pendingrequestsbeforeexhibitingsigns ofstress.
We replayed atrace ofproxyre-encryptionRPCs. This
required no computationon the client side, but caused
the server toperform proxyre-encryption. We startby
issuinga single request, waitingforthe responsebefore
issuinganotherrequest. Tosimulatemanysimultaneous
clients, we gradually increase the window size of out-
standingRPCs.
Our server is able to sustain 100 re-encryptions/sec
until reaching about 1,000 outstanding requests. The
server coped with up to 10,000 outstanding re-
encryption requests, but quickly spiraled downwards
thereafter. Note that our server is faster than the client
machine,abletoperformasingleproxyre-encryptionin
9ms.
4.3. Discussion
Ouraccesscontrolserveractslikeacredentialsdown-
load service. For instance, PDM [31] stores encrypted
credentials on a server. A user decrypts the credentials
with a password. PDM works ne when an encrypted
credential is available to a single individual. However,
ourlesystem supportsgroupaccesscontrol. Wecould
Documents you may be interested
Documents you may be interested
