Tài liệu An identity-based broadcast signcryption scheme and its application to medical images sharing

An Identity-based Broadcast Signcryption Scheme and Its Application to M edical Images Sharing Dang Thu Hien Faculty of Information Technology University of Engineering and Technology Vietnam National University, Hanoi Supervised by Associate Professor Trinh Nhat Tien A thesis submitted in fulfillm ent of the requirements for the degree of Master o f Computer Science May, 2010 Table of C ontents A b stra ct ii Acknowledgem ent Ul L is t o f Figures V L is t o f Tables vi A b b re via tio n s v ii 1 2 In tro d u c tio n 1 1.1 Overview and M otivation..................................................................... 1 1.2 Related w o r k ....................................................................................... 4 1.3 Our contributions................................................................................. 6 1.4 Thesis organization........................................ ..................................... 6 P relim inaries 7 2.1 Bilinear pairings.................................................................................... 7 2.2 Computational assum ptions................................................................ 8 2.3 General model of identity-based broadcast sigucryption.................... 9 2.4 Requirements of I B B S ........................................................................ 10 2.5 Security notions for IBBS ................................................................... 11 2.5.1 Message confidentiality............................................................. 11 2.5.2 Existential unforgeability.......................................................... 13 Forking le m m a .................................................................................... 13 2.6 3 Identity-B ased Broadcast S igncryption Scheme 15 3.1 Description of the s c h e m e .......................................................................... 15 3.1.1 15 Setup ........................................................................................ T A B L E OF C O N T E N T S 3.1.2 Extract 3.2 ..................................................................................... 16 3.1.3 Signcryption............................................................................... 16 3.1.4 บ nsigncryption.......................................................................... 17 A n a lysis................................................................................................ 17 3.2.1 Consistency............................................................................... 18 3.2.2 18 Public ciphertext a u th e n tic ity ........................................................ 3.2.3 Public verifiability 3.3 .................................................................... 19 Security p r o o f s .................................................................................... 19 3.3.1 Message confidentiality.............................................................. 19 3.3.2 Existential unforgeability........................................................... 25 3.4 4 Efficiency evaluation and com parison................................................. 30 E xp e rim e n ta tio n and A p p lic a tio n 4.1 IBBS E xperim en ts...............................................................................33 4.1.1 Experimental se tu p ....................................................................33 4.1.2 Results and comparison 4.2 5 33 ........................................................... 34 Signcryption - Watermarking Model for Medical Image Sharing Conclusions and Future W o rk . . . 3b 39 P ublications lis t 41 B ib lio g ra p h y 42 List of Figures 4.1 Broadcast Signcryption - Watermarking Model List of Tables 3.1 C om putation costs comparison ...............................................................31 3.2 Com m unication costs c o m p a ris o n ............................................................32 4.1 Experim ental results comparison vii ............................................................35 Abbreviations BE EHR EUF-sIBBS-CMA Broadcast Encryption Electronic Health Record Existential Unforgeability of identity-based broad­ cast signcryption scheme against selective identity chosen message attacks ex GDHE exponentiation General Diffie-Hellman Exponent 1BBS Identity-Based Broadcast Signcryption ID Identity Indistinguishability of identity-based broadcast IND-sIBBS-CCA signcryption scheme against selective identity cho­ M SIC mu sen ciphertext attacks Master Secret Key multiplication pa pairing evaluation VK PKG Public Key Private Key Generator PKI Public Key Infrastructure q - Strong Diffie-Hellman q-SDH SC UN Signciyption บ nsigncryption Chapter 1 Introduction 1.1 Overview and M otivation Information is probably one of the most valuable possessions of mankind. The loss, illegitimate disclosure and modification of information, especially sensitive one, could cause bad consequences and seriously affect oil related people. On the other hand, the recent growth of digital technologies and computer networks have radi­ cally change the way we work and exchange ideas. By providing low-cost, fast and accurate ways to access data in digital form, communication over networks is now becoming easier and increasingly popular. However 1the advantages of digital infor­ mation and networked environment have also brought new challenges because they always contain vulnerability attacking weakness like eavesdropping, forgery, alter­ ation. Therefore, the need of secure and authenticated data transmission is more and more important and critical. Since the birth of public key cryptography in 1970s, the requirements of confi­ dentiality and authenticity are satisfied by using encryption and digital signature schemes respectively. W ith public/private key pairs, two entities can share informa­ tion in a secure manner. Public key cryptography has created a great evolution in cryptography but it cannot work efficiently without the support of certificate based public key infrastructures (PKI). Certificate binds a public key to its owner and PKI manages, distributes and revokes certificates. In order to get rid of public key certificates，in 1984, Adi Shamir introduced Identity-based cryptosystems [Sha84]. In this new paradigm, he suggested idea to use the user's unique and undeniable information as his/her public key whereas the 1 1.1. O verview and M otivation 2 corresponding private key can only be derived by a trusted Private Key Generator (PKG). These public keys can come from the user， ร name, email address or what­ ever convenient data so that it refers unambiguously and undeniably only to one user. This kind of information is denoted by Digital Identity. Useťs identity must be acknowledged by everyone, so this removes the need to authenticate or prove the relationship between the identity and the owner or wasting time in looking up public key before sending out a secret message. Consequently, identity-based cryptography promisingly provides a more convenient alternative to PKI. Several practical identity-based cryptographic schemes have been devised but until 2001, there was only one satisfactory scheme [BFOlj. Some others using parings were proposed after that [Pat02, CC02, Hes02]. Traditional encryption just provides security for one-to-one communication. Nowa­ days, there are many applications in which communication activities are one-tomany, where a user is not only able to send/receive data to/from another but also a group of users simultaneously. Actually, senders (called broadcasters) may need methods to distribute securely a message to a target set of receivers and ensure that all members in the set. get the correct message while non-members cannot eaves­ drop, forge or modify it. W ith conventional public key cryptography techniques， the broadcaster has to encrypt and sign messages then transmit individual encrypted message to every each receiver. Advantage of this solution is high security level be­ cause every user gets a different ciphertext and uses his own private key to decrypt. However, this solution is really inefficient. If there are I receivers, the broadcaster has to process I times on a same message to create I different ciphertexts. It needs a lot of time，storage and transmission costs. Thus, traditional public key cryptography is not a suitable approach for this problem. To handle the requirement of privacy in information broadcasting, a cryp­ tography topic called Broadcast Encryption (BE) was introduced by Fiat and Naor in [АМ94]. BE schemes allow senders to broadcast an encrypted message over an open channel to a target set of receivers. In a secure BE system, any legitimate receiver can use his private key to decrypt the broadcast but illegitimate users (who are not in target set) can obtain nothing about the messages. Today, because of its significant applications，broadcast encryption has gained considerable attention and deployed broadly. For example, distribution of copy­ righted materials, access control in encrypted file systems [Refb], satellite TV sub­ scription services, etc. Recent research indicates that broadcast encryption has wide 1.1. Overview and M otivation 3 application prospect ill securing electronic health records (EHR) [SW06，НТН09]. W ith the development of e-health, nowadays, the medial information are digital­ ized and stored for different purposes such as tele-medicine, cutting down the health care, long time storage, clinical research and epidemiological studies. Consider a sit­ uation that is ill order to discuss and obtain second opinions or professional advices, an EHR is distributed online to physicians, researchers, students or other external users. In medical field, the security of medical data is very important. They should he kept intact in every circumstance because any manipulation and perversion could lead to wrong diagnostic. On the other hand, EHRs contain sensitive patient infor­ mation which can influence on the patient’s health and even their lives so that they should be protected from unauthorized access and modification. When a broadcast system such as a electronic health system consists of multiple broadcasters, each user can produce ciphertexts and deliver to others. In that case, it opens an issue of authentication and non-repudiation. Hence, along with information privacy, data origin authenticity is also a vital aspect. For keeping message confidential and unforged, an already known approach named signature-then-encryption has been followed. However, it has a main draw­ back: the cost of distributing a message is essentially the sum of the cost for digital signature and that for encryption. In 1997, Zheng [Zhe97] addressed a question on reducing the cost of secure and authenticated message delivery and proposed a new cryptographic paradigm, called signcryption which “simultaneously fulfils both the functions of digital signature and public key encryption in a logically single step, and with a cost significantly lower than that required by the traditional signature fol­ lowed by encryption technique” . The efficiency of signcryption technique has been pointed out in several proposed schemes [ZY98，MB04，M102, LQ03] which costs much less in average computation time and message expansion than signature-thenencryption does. Since proposed, signcryption has been adapted to broadcast encryption to suffice the requirements of confidentiality and authenticity. However, to date, the research oil broadcast signcryption is still very limited. Most of proposed schemes need a particular component in ciphertext that corresponds to a designated receiver. Thus, their ciphertext size is equivalent to the number of receivers. In several other constructions with constant ciphertext size, the broadcaster has to negotiate a common secret value with all receivers beforehand. Prom some point of view, these constructions are not more efficient and convenient than one-toone signcryption. 1.2. R elated work 4 Realizing that almost, current broadcast signcryption schemes do not meet all of these properties, we aim to construct an efficient scheme which fulfils both se­ curity and efficiency. Additionally, the question on how to incorporate broadcast signcryption in securing EHRs inspires us to bring it to a specific application named medial image sharing. Since medical image is a special type of data in EHR, we con­ centrate on designing a model that combines the proposed broadcast signcryption scheme and watermarking technique to secure medical images sharing. 1.2 R elated work There are many proposals of broadcast encryption systems. In [KD98], Kurosawa and Desmedt presented a scheme in which public and private key are derived from secret polynomial of order k. The security of this algorithm is determined by the order of polynomial k. Each user learns a piece of information about the secret polynomial f(x ) from his private key. Hence，a set of more than к users can collude to recover the polynomial and break the system. Another scheme based on ID-based encryption algorithm of Boneh-Franklin [BF01] was introduced and analyzed in [YWCR07]. In [BSNS05], Joonsang et.al built a scheme based 011 binary scheme of Canetti et al. [CHкоз]. The best known fully collusion is the scheme of Dan Boneh, Gentry and Water [BGW05]. However, all these schemes result in a long size ciphertext. In 2007，Celile [Del07] proposed the first ID-based broadcast signcryption scheme with constant size ciphertext and pri­ vate key. This construction is based on the intractability of intractability of General Diffie-Hellman Exponent problem and its security is proved under random oracle model. In signcryption domain, the first scheme was proposed by Zheng [Zhe97]. After that, a lot of identity-based constructions have been introduced [M102, CML05, LQ03, МВ04]. Until now，the most secure schemes are [CML05] and [МВ04]. Although a lot of identity-based sigiicryption and broadcast encryption schemes lmve been devised，there were not many research ill broadcast signcryption. In 2000， Y.Mu et al. [MVOO] presented the first distributed signcryption scheme in which any user can signcrypt a message and deliver to a designated group of recipients. After that, Li et al. [LHL06] proposed a multi-receivers signcryption scheme based on bilinear parings. Another scheme based on bilinear pairing is also presented by 5 1.2. R elated work Ma Chun-bo et al. [bMAhL07]. However, in all schemes [bMAhL07, LHLOG, MVOOj, the algorithms are based on traditional public key, not identity.based. In [Boy03], the author built an identity-based signcryption scheme and extended it for multi-recipient case. The idea in this construction is carrying out the sign operation once while encrypt operation is performed independently for each recip­ ient. Another ID-based broadcast signcryption scheme was proposed by Bohio et al. in 2004 [BM04]. However, this scheme is inconvenient because it needs a preagreement. to establish a common secret key before signcrypting. Once this common value is out, the system will break. In addition, the weakness of forgery in this scheme was pointed out by Selvi et al. [SVK4-08]. Despite the authors gave a fix for this weakness, it still suffers from a major shortcoming: if a user leaves the group, the broadcast parameters must be changed and sent back to every remaining user. In 2006, Duan к Cao [DC06] proposed a multi-receiver ID-based signcryption scheme by extending broadcast encryption scheme in [BbNS05]. Recently, Tan [Tan08] pointed out that theiťs scheme is not secure under chosen ciphertext at­ tacks. In 2007, Yu et. al. [YYHZ07] introduced a new scheme and claim that it is secure in the random oracle model. However, it is shown to be insecure to forgery attack in [ХХ09]. Recently, F.Li et al’ [LXH08] also proposed another scheme of ID-based broad­ cast signcryption based on Chen and Malone-Lee's signcryption algorithm [CML05] and proved its security under random oracle model. Nonetheless, the size of cipher­ text is linear to the number of receivers and each receiver must share a common secret value with the broadcaster. Note that all above proposals do not have public ciphertext authenticity prop­ erty. In 2009，another scheme was introduced by [ЕА09]. This scheme was based on the signcryption scheme in [LQ03] and provided a noticeable property called public ciphertext authenticity which allows any third party can verify the ciphertext origin. This property is very useful for applications that need firewall or gateway authenti­ cation before passing the message. However, the ciphertext size of this scheme has a similar form with others，means that it needs a particular component for each receiver. In [SVSR09]，an effective scheme was proposed basing on the construction of broadcast encryption scheme in [Del07]. Although this scheme has constant size ciphertext but it does not meet the public ciphertext authenticity requirement. 1.3. O ur contributions 1.3 6 Our contributions In scope of a Master thesis, this work tries to design an efficient identity-based broadcast signcryption scheme whose ciphertext size does not depend on the quan­ tity of receivers and the size of system public key is linear with the maximal size of the set of receivers. In this scheme, the total number of possible users does not have to be fixed from the beginning. The algorithm only requires pairings compu­ tation in unsigncryption phase while does not in signcryption phase. Moreover, it achieves desirable security attributes of broadcast signcryption while most of current constructions do not. We analyze and prove the security (message confidentiality and existential unforgeability) of proposed scheme in random oracle models. Evaluation and compari­ son with several existing schemes in term of performance are also made theoretically and experimentally. At last, we construct a model that combines broadcast signcryption and watennarkiag for secure medical image sharing. Implementation of this construction shows experimental results and its potential for practical uses. 1.4 Thesis organization The rest of this thesis is organized as follows: C h a p te r 2 presents some preliminary definitions that are involved. The issues in this chapter include of bilinear parings and related computational assumptions, the general model, requirements and formal security notions of identity-based broadcast signcryption that we associate to. We also recall forking lemma which states the general security level of signature schemes. C h a p te r 3 describes the proposed identity-based broadcast signcryption scheme. Analysis and security proofs of proposed scheme are provided here. We also make some summaries and comparisons to evaluate its efficiency. C h a p te r 4 presents numerical experiments and discusses th e ir practical im ple­ mentations. The model construction o f incorporating the proposed scheme for secure medical image is also introduced in this chapter. Implementation and experimental results of this model are also developed and evaluated. C h a p te r 5 concludes our work and gives the future research directions based oil the obtained results so far. Chapter 2 Prelim inaries In this chapter, the background on the research of thesis is introduced. Basing on these definitions and assumptions, our scheme is constructed and proved to be secure. 2.1 Bilinear pairings Let Gi, Ơ 2 be two cyclic additive groups of prime order p and Gt be a cyclic multiplicative group of same order p. Denote g and h are the generators of G\ and G2 respectively. A bilinear pairings is a map e : Ơ1 X Ơ 2 —► G t with the following properties: 1. Bilinearity: For any arbitrary elements a, b of Zp, e(ga,h ๆ = e(g,h)ab = e(9\ h ๆ 2. Non-degeneracy：e(g} h) Ф \c r where 1 qt is the identity element of G t- 3. Computability: There is an efficient algorithm to compute e(g, h) for all g Ç. G\ and h € c?2. Actually, Gl and Ơ2 could be equal for simplicity. The map e derived from modifying either Weil or Tate pairing [BF01] is permissible for this kind of map. 7 2.2. C om putational assum ptions 2.2 8 Com putational assum ptions The complexity assumptions for the security of our scheme rely on the hardness of computational problems that were previously formalized in [BB04a, BB04b, BBG05]. We now recall these problems. D e fin itio n 1 . The q-Strong Diffie-Heilman problem (q-SDH) Given bilinear map groups (Gb Ơ 2, G t) of the same order p and generators g 6 Gl and h 6 Chi the q-S trong D iffie -H e llm a n problem (q -S Đ H ) consists in, given a tuple (h, ha, ha2, ha4)y finding a p a ir (c ， / i 士 ) e Zp X Ơ 2- The advantage of an algorithm Л in solving the q-SDH problem is: AdvsADH = P r ịA{h, hn,ha\...,h a4) ะ= ( c ,h ^ ) I ce z ;， с Ф -a We say that the Í/-SDH assumption holds in (G bƠ 2) if for any probabilistic poly­ nomial time algorithm Л, the advantage Adv^DH in solving the Ợ-SDH problem is negligibly small. D e fin itio n 2. The General Điffie-Heilman Exponent problem (GDHE) Let p be a prime integer and let s} ท be two positive integers. Let G and G f be two cyclic groups of order p with an efficient, non-degenerate bilinear mapping: e:G X G U r- Let 5 is a generator of G and set gT = e(g, g) € GT. Let P,Q e Рѵ[Х і,Х 2у..МЛЛП]Я be two s-tuples of n-variate polynomials over field Fpy means p - (РьР2，…， rO and Q = (ỢbỢ2,..., 9s) where pi,Qj are multi-variate polynomials (1 < i , j < ร). We impose that the first Pi = 91 = 1. Let P (x i^ X 2y tion h : Fp denote (P i(X i, 巧 ， …， 欠n ) ， …， Pe(하， め， …， 疋n)). For any func­ ÇI and a vector (X 1 ,X 2, x n) € i 주1, we write: h^Pị^Xị, X2ì •••J ^n)) *ᅳ(/l(pi (^lì ^2» •'•ì *^n))î We use similar notation for Q. *^2í *»M*^n))) ^ ^ Let / e FpfXi,Х г , X nỊ. The (P ,Q ,/)- General D iffie -H e llm a n E xponent problem ((Л Q ,/)-G D H E ) is defined as follows: Given the vector: 네 H (x l } ... xn) = (gp^ ,...， 1’•••， Xn)) € G 9 x G f, œmpute g요xレ， 1시ç. QTt The advantage of an algorithm Л in solving the GDHE problem is: 2.3. G eneral model of identity-based broadcast signcryption 9 AdvG ADHE = P r \a {P ,Q J ) = g ị (Xi…In) We say that the (P, Q, /)-G D H E assumption holds if for anv probabilistic poly­ nomial time algorithm v4, the advantage Adv^DHE is negligibly small. D e fin itio n 3. Dependent and Independent Polynomials W ith / . p, Q defined as in Definition 3, we say / and (P, Q) are dependent, denoted by / e (P, Q), if there exists a tuple of (ร2 + ร) components {a 냐}, {b ị} with 1 < ty j < ร such that: / = 5그 ij= i aij.Pi Pj + 2^k=ì We say that / and (P, Q) are independent if / and (P, Q) are not dependent and denoted by f ị (P,Ọ). In [BBG05Ị, it was pointed out that when J Ệ (P ,(ฐ), the (p ,(ฐ， / ) - GDHE problem is intractable. 2.3 General m odel of identity-based broadcast signcryption Broadcast signcryption schemes serve scenarios in which one person can distribute inform ation to I other people confidentially and authentically. An identity-based broadcast signcryption scheme (IBBS) consists of four algorithms: Setup, Extract, Signcryption and Unsigncryption. Setup creates general public parameters and mas­ ter secret key basing on security level parameters. Extract generates private key for every user depending on the userไร identity. Signcryption produces the signcrypted ciphertext from a broadcaster to an intended set of receivers. บ nsigncryption recov­ ers the original plaintext and verifies its integrity and authenticity. Let В is the broadcaster and R = { я ь R2, Я/} is the set of receivers. The detailed functions of these algorithms are described as follows: • Setup: Given security parameter A and the maximal size ไท of the set of receivers, PKG generates a master secret key M S K and a public key VfC. M S K is kept secret and V K is made public. • Extract: Given an identity ID 、the PKG computes the corresponding private key S jD and transfers it to the owner in a secure way. 2.4. R equirem ents of IBBS 10 • Signcryption: On input of public key V K and a set of designated identities R =ะ {/jD i ，JZ)2 ，•••，I D ị } with I < m, the broadcaster в computes ơ = Signcrypt(A/, R, Sịd b) and obtains Ơ as the signcrypted text the plaintext M . • Unsigncrytion: When receiving <71 a receiver with identity ỉD ị, 1 < i < I and corresponding private key SỉDi computes Unsigncrypt(cr, 5/D,, 人D ß /P だ) to obtain a valid plaintext Л/ or a symbol 丄 if a was an invalid signcrypted text. For the correctness constraint of identity-based broadcast signcryption，we require that: M = บ n s ig n c ry p t(S ig n c ry p t(M , VIC, R, S n)Bh S jd ^ I D b 、 VIC) 2.4 Requirem ents of IBBS According to [ENI09], a broadcast signcryption scheme basically should have the following properties: 1. Consistency: The signcrypted te xt formed properly by the signcryption al­ gorithm must be extracted and verified successfully by corresponding unsign- cryption algorithm. 2. Confidentiality: I t is impossible to obtain the content of the signcrypted mes­ sage w ith out the knowledge of target receivers’ private key. 3. บทforgeability: W ithout the knowledge of sender's private key, an attacker is infeasible to masquerade and create a signcrypted text which w ill be designcrypted and verified successfully by unsigncryption algorithm. 4. Public ciphertext authenticity: Any third party can verify the validity and the origin of the ciphertext without knowing the content of the message and getting any help from designated receivers. 5. Public verifiability: The receiver has ability to prove to a third party that the signcrypted ciphertext is a valid signature on the message without revealing his private key. This property ensures that the sender cannot deny his signature. 2.5. Security notions for IBBS 11 6. Efficiency: The communication load (size of signcrypted text) and computa­ tion cost (time to signcrypt and unsigncrypt) should be smaller than those of the best known signature-then-encryption schemes with the same provided functionalities and comparable parameters. 2.5 Security notions for IBBS There are two types of the security in any IBBS scheme: message confidentiality and unforgeability. Formal security definitions for signcryption schemes are defined by Malone-Lee [M102], consisting of indistingiiishability against adaptive chosen ci­ phertext attacks (for message confidentiality) and unforgeabiiity against adaptive chosen message attacks (for existential unforgeability). For broadcast signcryption, a widely accepted security definition is selective identity attack. Selective identity attack was firstly proposed by Canetti et al. [CHK03] in which the adversary must choose from the beginning the identity he wants to attack on. This idea is then modified and adapted to prove the security of broadcast encryption and signcryption schemes [ĐC06，Del07]. In this work, we inherit it and present two notions called indistingiiishability of identity-based broadcast signcryption against selective identity chosen ciphertext attacks (IND-sIBBS-CCA) and existential unforgeability of identity-based broadcast signcryption scheme against selective iden­ tity chosen message attacks (EUF-sIBBS-CMA). The detail of these notions is de­ scribed as below. 2.5.1 Message confide ntiality Let A denote an adversary and в denote a challenger. The message confidentiality is defined by considering the following game between A and ß. Basically, we improve the definition of [Del07] by adding some queries on signcryption and unsigncryption. In it: Both adversary and challenger are given 771as the maximal size of receivers. Л outputs a set of identities, denoted by R* ะ= {ID \, ID ịy …, I D ị} (I < m) that he wishes to attack on. Setup: The challenger runs the setup algorithm to obtain master secret key M SK. and public key VIC. The challenger sends V K to A while keeps M SÌC secret from Л. P hase 1: Adversary A starts to probe by issuing series of queries: 2.5. Security notions for IBBS 12 • Extraction queries: A produces an arbitrary id entity I D w ith a constraint that ID Ệ Ré and requests the corresponding private key. The challenger runs extraction algorithm to obtain Sị [) and returns it to the adversary. • Signcryption queries: A produces a message M , a broadcaster I D ß } a set R of I receivers with identities ID fi{ and requests the signcrypted ciphertext of Signcrypt(M ， VKy Ry 5ß). The challenger returns the corresponding Ơ. 參 Unsigncryption queries: A produces a broadcaster ID A and signcrypted text Ơ and request the result of operation Unsigncrypt( 10(л+ l)(fí+ Q )/2 k, a valid signature (M, ơ \ yh, ơ2). I f the triple (ơi, /i, СГ2) can be simulated witJwut. knowing the secret key, w ith an indistinguishable d istribu tion probability, then there is another machine which has control over the machine obtained fro m Л replacing interaction with the signer by simulation and produces two valid signatures (M , G\ 1h, Ơ2) and (M, ơ \ , h \ ơ!2 ) such that h Ф h! in expected time T f < 120686ỌT/6, The usage of this lemma w ill be more clear in the proof of existential unforgeab ility property of our scheme in next chapter.