- Số trang:
**53**| - Loại file:
**PDF**| - Lượt xem:
**27**| - Lượt tải:
**0**

nhattuvisu

Đã đăng **26972** tài liệu

Mô tả:

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.

- Xem thêm -