Font Size: a A A

The Proofs Of PKE's Chosen Ciphertext Security And That Of 2~m-Root Identification Scheme's Security Under Concurrent Attacks

Posted on:2008-06-13Degree:DoctorType:Dissertation
Country:ChinaCandidate:Z X YanFull Text:PDF
GTID:1118360212494438Subject:Information security
Abstract/Summary:PDF Full Text Request
In 1991,Damgard proposed two simple public key encryption schemes in [16] .one of which is based on Diffie-Hellman/ElGamal cryptosystem.Its security depends on the intractability of computional discrete logrithms in finite field. That scheme seems to be secure against indifferent chosen ciphertext attacks,but in [49],Zheng and Se-berry pointed out that the scheme is at least not against adaptively chosen ciphertext attacks.Furthermore.he suggested that it should be improved by using one-way hash function.In 2001 and 2002,Soldera pointed out respectively in [46,47] that the scheme of Zheng and Seberry [49] still wasn't against adaptively chosen ciphertext attacks. In 1994,in [50] Zheng also improved the scheme of [49] by caconcatenating a random value after the message.getting the so called one-way-hash scheme against internal attacks.This scheme is regarded as one of practical schemes against adaptively chosen ciphertext attacks, but it is absent of rigorous proofs.The scheme is described as follows:Public key generating stage:x∈R {1,….p—1}, let y = gxmodp. then PK = (y.p).SK =xEncryption stage:given message m∈{0, l}p(k). (?)r∈R {1,…,p—1}.C1 = gr modp ;C2= {m||H(m||yrmodp)}(?)G(yr modp),then the ciphertext is (C1,C2). Decryption stage:given ciphertext (C1,C2)s = C1xmodp,t=C2(?)p(k)+1,?p(k)+l(k)],m = C2(?)1.?p(k)](?)G(s).if H(m||s) = t, output m; Otherwise, output "Reject".It can be seen that during the encryption stage the pole of G(yrmodp) is to hide m||H(m||yrmodp) in this scheme. In fact, as a label, the pole of H(m||yrmodp) is only to confirm the decrypted messages.So it is not necessary to keep it secret. Because no matter which changes for either m or r, it all can cause the label to change. Hence, unless the attacker knows (m, r) at the same time, he can't produce any valid cipher-text that can be fully verified through out the whole decryption stage.Hence,on basis of this scheme, we improve it and get a new scheme.The new encryption scheme is described as follows:Public key generating stage: x∈r {1,…,p- 1}, let y = gxmodp, then PK = (y,p).SK = x. Encryption stage: given message m∈{0, 1}p(k) (?)r∈R {1,…,p—1},C1 = grmodp;C2 = m (?) G(yrmodp) ;C3 = H (m||yrmodp) ;Then the ciphertext is (C1, C2, C3) . Decryption stage:given ciphertext, (C1,C2,C3).s = C1xmodp; m = C2(?) G(s) ;If H(m||s) = C3, output m ; Otherwise, output "Reject" .Under the CDH assumption,we prove it to be against adaptively chosen ciphertext attacks respectively by using the reduction method and sequence of games method.When we prove its security by using the mode of reduction, we reduct the security of the scheme to the difficulty of solving the CDH problem.Theorem 1.4.1 Let A = (A1,A2) be a chosen ciphertext attacker. Within the time t, A has made at most qD, qG and qH queries respectively to decryption oracle, random oracles G, H. Furthermore, its advantage successfully breaking the scheme is (?). then there exists an algorithm B such that the probability that it successfully solves the CDH problemThe upper bound of its running time t'≤t + qhT(C2) + [qG + qh + qd·qH]O(1), inwhichε(H) is the probability that a collision of H can be found and T(C2) is the time of calculating C2 during the encryption course. When we analyse the success probability of the whole reduction algorithm, we get a result which is used to evaluate the probability that A asks the G(yr* modp). My result is more accurate than that of Boneh [8]; Furthermore, his result is short of rigorous proof.Theorem 1.4.2 Let A be a chosen ciphertext attacker. Its advantage during the real attack on the scheme is Adv(A), thenPrreal[AskG]≥2Adv(A) .Remark: The result of Boneh in [8] is Prreal[AskG]≥Adv(A); The above result still holds for OAEP, OAEP+, SAEP. SAEP+.About the 2m-root identification scheme's security. Shoup proved that it is secure under the active attacks in [40] if factoring integers is hard. Bellare and Palacio proposed the notion of concurrent attack in [7] and proved that it is an extension of active attack.During the third part.this paper analyses the security of the 2m-root identification scheme under concurrent attacks .We first extend the "Reset lemma" of Bellare and Palacio[7]. We extend the two different challenges in the real number field there to the two different challenges in the mod 2l+1.Let, acc(SK, PK) denote the probability that prover makes verifier accept when the secret key and public key are SK and PK respectively.Let res(SK, PK) be the probability that,faced with verifier's two different chel-lenges in modulus 2l(k)+1,the prover makes verifier accept when the secret key and public key are SK and PK respectively. ThenAccording to the new reset lemma, we reduct the security of the 2m-root identification scheme into problem of finding the non-trivial factor of n.Theorem 3.4.2 Let ID = (K, P, V) be a 2m-root identification Scheme. The public modulus is n.Assume that there exists a concurrent attacker (V. P) such that the success probability it breaks ID isε(k), then there exists an algorithm A factoring n and for each k its success probability(1/4)ε(k)≥S(k)≥(1/8)[ε(k)-2-l(k)]2In which, l(k) is the smallest positive integer satisfying the inequality 2m > 2l(k)≥1/(ε(k)).When Shoup talked about the success probability of the algorithm factoring n in [40], he had only talked about the affection of the ratio of 1 lying in (3/4)-weighty rows among the whole matrix. We extend this to arbitrary t-weighty rows.(1) For fixed h, SK, PK,the probability that d1 = 1 lies in t-weighty rows is at least 1 -t;(2)If d1 = 1 lies in t-weighty rows, the probabilityε' that CH2 can be found in t-weighty rows such that CH2≠CH1mod 21(k)+1 satisfies thatε'≥t acc(h, SK. PK) - 2-l(k)-1.(3) For those h, SK, PK such that acc(h, SK, PK)≥ε(k) ,if A can repeat interaction with P to at least [1/(ε(k))] times. Once Succeeds,fixing the random choice of P,A again repeats the interaction with P to at least (?)[t acc(h,SK.PK) - 2-l(k)-1]-1] times,then the probability that the double chellenges experiment succeeds is at least (1—t)(1—(1/e))2.
Keywords/Search Tags:Chosen ciphertext security, Random oracle model, Same square-root set, Concurrent attack
PDF Full Text Request
Related items