Method of establishing public key cryptographic protocols against quantum computational attack

This application claims priority of Chinese patent application No. 201310382299.7 filed on Aug. 21, 2013, the entire content of which are hereby incorporated by reference.

The present invention relates to the field of information security, and in particular, to a cryptogram technology for establishing public key cryptographic protocols against the quantum computational attack.

The verification for a real identity of a person who sends and receives information, and the non-repudiation of the sent/received information after the information is sent or received and the guarantee of the integrity of data are two important issues about the theme of modern cryptography.

Disclosure of a key cryptogram system presents excellent answers to the issues of the two aspects, and more new ideas and solutions are being generated continually. In a public key system, an encryption key is different from a decryption key. People bring an encryption key to public, so that anyone can use the encryption key; but a decryption key is only known by a person performing decryption. In modern periods, the security of a public key cryptosystem is almost based on two categories of mathematic problems that are considered to be difficult to compute, a first category being a decomposition problem of a big prime number, for example, an RSA algorithm; and a second category being a discrete logarithm problem, for example, a key exchange algorithm of Diffie-Hellman, an El Gamal algorithm, an elliptic curve public key cryptographic algorithm (ECC for short), and the like.

In order to solve a problem that a hidden trouble exists in identity verification and security of data guarantee based on an existing public key cryptographic protocol, an objective of the present invention is to establish public key cryptographic protocols technology capable of resisting various known attacks, and provide various application protocols on this basis.

One manner for implementing the objective of the present invention is: a method of establishing public key cryptographic protocols against the quantum computational attack, which includes a method for generating a shared key. The method for generating a shared key is also referred to as generating a shared key protocol, and the method for generating a shared key includes the following steps:

(11) establishing an infinite non-abelian group G and two subgroups A and B of G, so that for any aεA and any bεB, the equation ab=ba is true;

(12) choosing, by a first entity of a protocol, an element g in G, where the first entity of the protocol chooses two elements b 1 , b 2 εA as private keys, and a second entity of the protocol chooses two elements d 1 , d 2 εB as private keys;

(13) choosing, by the second entity of the protocol, two elements c 1 , c 2 εB, computing y=d 1 c 1 gc 2 d 2 , and sending y to the first entity of the protocol;

(14) choosing, by the first entity of the protocol, four elements a 1 , a 2 , b 3 , b 4 εA, computing

x=b 1 a 1 ga 2 b 2 and z=b 3 a 1 ya 2 b 4 =b 3 a 1 d 1 c 1 gc 2 d 2 a 2 b 4 ,

and sending (x, z) to the second entity of the protocol;

(15) choosing, by the second entity of the protocol, two elements d 3 , d 4 εB, computing

w=d 3 c 1 xc 2 d 4 =d 3 c 1 b 1 a 1 ga 2 b 2 c 2 d 4

and

v=d 1 −1 zd 2 −1 =d 1 −1 b 3 a 1 d 1 c 1 gc 2 d 2 a 2 b 4 d 2 −1 =b 3 a 1 c 1 gc 2 a 2 b 4

and sending (w, v) to the first entity of the protocol;

(16) computing, by the first entity of the protocol,

u=b 1 −1 wb 2 −1 =b 1 −1 d 3 c 1 b 1 a 1 ga 2 b 2 c 2 d 4 b 2 −1 =d 3 c 1 a 1 ga 2 c 2 d 4 ,

and sending u to the second entity of the protocol; and

(17) computing, by the first entity of the protocol, K A =b 3 −1 vb 4 −1 =a 1 c 1 gc 2 a 2 , and computing, by the second entity of the protocol, K B =d 3 −1 ud 4 −1 =c 1 a 1 ga 2 c 2 ;

because a 1 , a 2 εA, and c 1 , c 2 εB, a 1 and c 1 are separately commute with a 2 and c 2 in multiplication, so that the first entity of the protocol and the second entity of the protocol reach a shared key K=K A =K B .

In the present invention, an algebra system in which an unsolvable problem exists is first established theoretically, and second, the unsolvability of the problem is used as security guarantee to establish a public key cryptographic algorithm. The security of the algorithm and the equivalence of the unsolvable problem of the present invention prove that the present invention is immune to the quantum computational attack and the like. Because the method of establishing public key cryptographic protocols of the present invention uses an unsolvable decision problem as the security guarantee, the method is powerfully guaranteed both theoretically and in an actual application aspect, and compared with the prior art, has the following advantages:

1. The security guarantee of a built public key cryptographic algorithm relies on the unsolvability of the problem rather than the computation difficulty of the problem, (a classic public key cryptographic algorithm is based on the computation difficulty);

2. That the security of the public key cryptographic algorithm of the present invention is equivalent to the unsolvability of the problem on which the public key cryptographic algorithm relies has been proved mathematically;

3. The public key cryptographic algorithm of the present invention resists the quantum computational attack.

The following further describes in detail establishment of public key cryptographic protocols against the quantum computational attack according to the present invention with reference to embodiments.

1. A Platform for Establishing Public Key Cryptographic Protocols

A platform for establishing all public key cryptographic protocols is an infinite non-abelian group G and two subgroups A and B of G, so that for any aεA and any bεB, the equation ab=ba is true. In addition, because of demands of encoding and key generating, G must further satisfy the following conditions:

1) Any word in terms of generators of G representing an element of G has an unique computable normal form;

2) G at least is in exponential growth, that is, the number of elements whose word length is a positive integer n in G is confined to an exponential function about n;

3) Multiplication and inversion of a group based on the normal form is computable.

Therefore, a braid group B n with n≧12 is taken as the infinite non-abelian group G, where B n has the foregoing properties and is a group defined by the following presentation:

B n = σ 1 ,σ 2 , . . . ,σ n−1 |σ i σ j =σ j σ i , |i−j|≧ 2, σ i σ i+1 σ i =σ i+1 σ i σ i+1 , 1≦ i≦n− 2 ,

the braid group B n contains the following two subgroups:

let m=└n/2┘ be a maximum integer not greater than n/2, and a left braid LB n and a right braid RB n of the braid group B n separately are

LB n = σ 1 ,σ 2 , . . . ,σ m−1 and RB n = σ m+1 ,σ m+2 , . . . ,σ n−1

that is, separately are subgroups generated by σ 1 , σ 2 , . . . , σ m−1 and σ m+1 , σ m+2 , . . . , σ n−1 , and for any aεLB n and any bεRB n , ab=ba is true.

When n≧12, LB n and RB n separately contain a subgroup isomorphic to the direct product of F 2 ×F 2 , that is, two free groups with ranks being 2:

LA= σ m−5 2 ,σ m−4 2 ,σ m−2 2 ,σ m−1 2 ≦LB n

and

RA= σ m+1 2 ,σ m+2 2 ,σ m+4 2 ,σ m+5 2 ≦RB n ,

and then a finite presentation group H whose word problem is unsolvable and that is generated by two elements constructs a Mihailova subgroup M LA (H) of LA and a Mihailova subgroup M RA (H) of RA again; the following is 56 generators of M LA (H), where i=m−5; and when i=m+1, 56 generators of M RA (H) can be obtained:

σ i 2 σ i+3 2 , σ i+1 2 σ i+4 2 , S ij , T ij , j= 1,2, . . . ,27

and 27 S ij s are (all σ i s in the following each S ij are replaced with σ i+3 s, and all σ i+1 s are replaced with σ i+4 s to obtain corresponding 27 T ij s, where j=1, 2, . . . , 27):

2. An Embodiment for Establishing Core Protocol 1 of Public Key Cryptographic Protocols System:

In this embodiment, two entities of the protocol are separately Alice and Bob,

1) Alice and Bob jointly choose an element g in B n , Alice chooses two elements b 1 , b 2 εLB n as private keys, and Bob chooses two elements d 1 , d 2 εRB n as private keys;

2) Bob chooses two elements c 1 , c 2 εRB n , computes y=d 1 c 1 gc 2 d 2 , and sends y to Alice;

3) Alice chooses four elements a 1 , a 2 , b 3 , b 4 εLB n , computes

x=b 1 a 1 ga 2 b 2 and z=b 3 a 1 ya 2 b 4 =b 3 a 1 d 1 c 1 gc 2 d 2 a 2 b 4 ,

and sends (x, z) to Bob;

4) Bob chooses two elements d 3 , d 4 εRB n , computes

w=d 3 c 1 xc 2 d 4 =d 3 c 1 b 1 a 1 ga 2 b 2 c 2 d 4

and

v=d 1 −1 zd 2 −1 =d 1 −1 b 3 a 1 d 1 c 1 gc 2 d 2 a 2 b 4 d 2 −1 =b 3 a 1 c 1 gc 2 a 2 b 4 ,

and sends (w, v) to Alice; and

5) Alice computes

u=b 1 −1 wb 2 −1 =b 1 −1 d 3 c 1 b 1 a 1 ga 2 b 2 c 2 d 4 b 2 −1 =d 3 c 1 a 1 ga 2 c 2 d 4 ,

and sends u to Bob,

In step 4) of the foregoing protocol, because d 1 , d 2 εRB n , and a 1 , a 2 , b 3 , b 4 εLB n , d 1 −1 and d 2 −1 separately commute with b 3 and a 1 and with b 4 and a 2 in multiplication, so that a final equation in the step is obtained. Likewise, a final equation in step 5) is obtained.

On the Basis of this Embodiment, an Exemplary Embodiment for Establishing a Key Exchange Protocol is:

The following procedures are performed after the five steps in the core protocol:

6) Alice computes K A =b 3 −1 vb 4 −1 =a 1 c 1 gc 2 d 2 and Bob computes K B =d 3 −1 ud 4 −1 =c 1 a 1 ga 2 c 2 .

Because a 1 , a 2 εLB n , and c 1 , c 2 εRB n , a 1 and c 1 separately commute with a 2 and c 2 in multiplication, so that Alice and Bob reach a shared key K=K A =K B .

On the Basis of this Embodiment, an Exemplary Embodiment for Establishing a Data Encryption Protocol is:

It is given that to-be-encrypted plaintext information (encoded) is mε{0, 1} k (that is, a 0-1 string with a length of k), and it is given that Θ: B n →{0, 1} k is a collision-resistant Hash function from the group B n to a plaintext space {0, 1} k . The private keys of Alice are (B n , LB n , RB n , g, Θ), and a 1 , a 2 , b 1 , b 2 , b 3 , b 4 εLB n are chosen, and the private keys are b 1 and b 2 . Bob chooses c 1 , c 2 , d 1 , d 2 , d 3 , d 4 εRB n , and uses d 1 and d 2 as the private keys. The following procedures are performed after the five steps in the core protocol:

6) Encrypting: Bob first computes K B =d 3 −1 ud 4 −1 =c 1 a 1 ga 2 c 2 , then computes (encrypts) t=Θ(K B )⊕m, uses t as ciphertext, and sends the ciphertext to Alice. ⊕ herein is the exclusive or operation.

7) Decrypting: Alice first computes K A =b 3 −1 vb 4 −1 =a 1 c 1 gc 2 a 2 , then computes (decrypts)

m ′=Θ( K A )⊕ t =Θ( K A )⊕(Θ( K B )⊕ m )

verification of m′=m: K A =K B is known according to a key exchange protocol, and therefore,

m ′=Θ( K A )⊕(Θ( K B )⊕ m )=Θ( K B )⊕(Θ( K B )⊕ m )=(Θ( K B )⊕Θ( K B ))⊕ m=m.

On the Basis of this Embodiment, an Exemplary Embodiment for Establishing a Digital Signature Protocol is:

It is given that to-be-encrypted plaintext information (encoded) is m, and it is given that Θ: B n →{0, 1} k is a collision-resistant Hash function. The public keys of Alice are (B n , LB n , RB n , g, Θ), and a 1 , a 2 , b 1 , b 2 , b 3 , b 4 εLB n are chosen, and the private keys are b 1 and b 2 . Bob chooses c 1 , c 2 , d 1 , d 2 , d 3 , d 4 εRB n , and uses d 1 and d 2 as the private keys. The following procedures are performed after the five steps in the core protocol:

6) Signing: Alice computes K A =b 3 −1 vb 4 −1 =a 1 c 1 gc 2 a 2 and S=Θ(mK A ), and Alice uses S as a signature of Alice for a file m and sends (S, m) to Bob.

7) Verifying: Bob computes K B =d 3 −1 ud 4 −1 =c 1 a 1 ga 2 c 2 and S′=Θ(mK B ), and if S′=S, Bob acknowledges that S is the signature of Alice for the file m; otherwise, Bob refuses to accept that S is the signature of Alice for the file m.

On the Basis of this Embodiment, an Exemplary Embodiment for an Identity Authentication Protocol on the Basis of the Core Protocol is:

Alice chooses an element g in B n , four elements a 1 , a 2 , b 1 , b 2 εLB n , and a collision-resistant Hash function Θ: B n→{0, 1} k , and computes x=b 1 a 1 ga 2 b 2 . The public keys of Alice are (B n , LB n , RB n , g, x, Θ), and the private keys are b 1 and

An authentication process is:

It is given that Alice is a prover and Bob is a verifier.

1) Bob chooses six elements c 1 , c 2 , d 1 , d 2 , d 3 , d 4 εRB n , the private keys are d 1 and d 2 . Bob computes

y=d 1 c 1 gc 2 d 2 and w=d 3 c 1 xc 2 d 4 ,

uses (y, w) as challenge 1, and sends the challenge 1 to Alice;

2) Alice chooses two elements b 3 , b 4 εLB n , computes

z=b 3 a 1 ya 2 b 4 and u=b 1 −1 wb 2 −1 =d 3 c 1 a 1 ga 2 c 2 d 4 ,

uses (z, u) as a response, and sends the response to Bob;

3) Bob computes v=d 1 −1 zd 2 −1 =b 3 a 1 c 1 gc 2 a 2 b 4 , uses v as challenge 2, and sends the challenge 2 to Alice;

4) Alice computes t=Θ(b 3 −1 vb 4 −1 )=Θ(a 1 c 1 gc 2 a 2 ), uses t as a commitment, and sends the commitment to Bob;

5) Bob computes t′=Θ(d 3 −1 ud 4 −1 )=Θ(c 1 a 1 ga 2 c 2 ), and verifies whether t=t→,

and if t=t′, Bob acknowledges an identity of Alice; otherwise, Bob refuses to acknowledge the identity.

3. An Embodiment for Establishing Core Protocol 2 of Public Key Cryptographic Protocols System:

In this embodiment, two entities of the protocol are separately Alice and Bob,

1.1) Alice and Bob jointly choose an element g in B n , Alice chooses two elements b 1 εLB n and d 2 εRB n as private keys, and Bob chooses two elements b 2 εLB n and d 1 εRB n as private keys;

2.1) Bob chooses two elements a 2 εLB n and c 1 εRB n , computes y=d 1 c 1 ga 2 b 2 , and sends y to Alice;

3.1) Alice chooses four elements a 1 , b 4 εLB n and c 2 , d 4 εRB n , computes

x=b 1 a 1 gc 2 d 2 and z=b 4 a 1 yc 2 d 4 =b 4 a 1 d 1 c 1 ga 2 b 2 c 2 d 4 ,

and sends (x, z) to Bob;

4.1) Bob chooses two elements b 3 εLB n , and d 3 εRB n , computes

w=d 3 c 1 xa 2 b 3 =d 3 c 1 b 1 a 1 gc 2 d 2 a 2 b 3

and

v=d 1 −1 zb 2 −1 =d 1 −1 b 4 a 1 d 1 c 1 ga 2 b 2 c 2 d 4 b 2 −1 =b 4 a 1 c 1 ga 2 a 2 c 2 d 4 ,

and sends (w, v) to Alice; and

5.1) Alice computes

u=b 1 −1 wd 2 −1 =b 1 −1 d 3 c 1 b 1 a 1 gc 2 d 2 a 2 b 3 d 2 −1 =d 3 c 1 a 1 gc 2 a 2 b 3 ,

and sends u to Bob;

In step 4) of the foregoing protocol, because d 1 , d 2 εRB n and a 1 , a 2 , b 3 , b 4 εLB n , d 1 −1 , d 2 −1 separately commute with b 3 and a 1 , and with b 4 and a 2 in multiplication, so that a final equation in the step is obtained. Likewise, a final equation in step 5) is obtained.

3.3 An application protocol

The following application protocol is established on the basis of the core protocol.

On the Basis of this Embodiment, an Exemplary Embodiment for Establishing a Key Exchange Protocol is:

the following procedures are performed after the five steps in the core protocol:

6.1) Alice computes K A =b 4 −1 vd 4 −1 =a 1 c 1 ga 2 c 2 and Bob computes

K B =d 3 −1 ub 3 −1 =c 1 a 1 gc 2 a 2 .

Because a 1 , a 2 εLB n , and c 1 , c 2 εRB n , a 1 and c 1 are separately commute with a 2 and c 2 in multiplication, so that Alice and Bob reach a shared key K=K A =K B .

On the Basis of this Embodiment, an Exemplary Embodiment for Establishing a Data Encryption Protocol is:

It is given that to-be-encrypted plaintext information (encoded) is mε{0, 1} k (that is, a 0-1 string with a length of k), and it is given that Θ: B n →{0, 1} k is a collision-resistant Hash function from the group B n to a plaintext space {0, 1} k . The public keys of Alice are (B n , LB n , RB n , g, Θ), a 1 , b 1 , b 4 εLB n and c 2 , d 2 , d 4 εRB n are chosen, and the private keys are b 1 and d 2 . Bob chooses a 2 , b 2 , b 3 εLB n and c 1 , d 1 , d 3 εRB n , and uses d 1 and b 2 as the private keys. The following procedures are performed after the five steps in the core protocol:

6.1) Encrypting: Bob first computes K B =d 3 −1 ub 3 −1 =c 1 a 1 gc 2 a 2 , then computes (encrypts) t=Θ(K B )⊕m, uses t as ciphertext, and sends the ciphertext to Alice. ⊕ herein is the exclusive or operation.

7.1) Decrypting: Alice first computes K A =b 4 −1 vd 4 −1 =a 1 c 1 ga 2 c 2 , then computes (decrypts)

m ′=Θ( K A )⊕ t =Θ( K A )⊕(Θ( K B )⊕ m )

verification of m′=m: K A =K B is known according to a key exchange protocol, and therefore,

m ′=Θ( K A )⊕(Θ( K B )⊕ m )=Θ( K B )⊕(Θ( K B )⊕ m )=(Θ( K B )⊕Θ( K B ))⊕ m=m.

On the Basis of this Embodiment, an Exemplary Embodiment for Establishing a Digital Signature Protocol is:

It is given that to-be-encrypted plaintext information (encoded) is m, and it is given that Θ: B n →{0, 1} k is a collision-resistant Hash function. The public keys of Alice are (B n , LB n , RB n , g, Θ), a 1 , b 1 , b 4 εLB n and c 2 , d 2 , εRB n are chosen, and the private keys are b 1 and d 2 . Bob chooses a 2 , b 2 , b 3 εLB n and c 1 , d 1 , d 3 εRB n , and uses d 1 and b 2 as the private keys. The following procedures are performed after the five steps in the core protocol:

6.1) Signing: Alice computes K A =b 4 −1 vd 4 −1 =a 1 c 1 ga 2 c 2 and S=Θ(mK A ), and Alice uses S as a signature of Alice for a file m and sends (S, m) to Bob.

6.2) Verifying: Bob computes K B =d 3 −1 ub 3 −1 =c 1 a 1 gc 2 a 2 and S′=Θ(mK B ), and if S′=S, Bob acknowledges that S is the signature of Alice for the file m; otherwise, Bob refuses to accept that S is the signature of Alice for the file m.

On the Basis of this Embodiment, an Exemplary Embodiment for an Identity Authentication Protocol on the Basis of the Core Protocol is:

Alice chooses an element g in B n , four elements a 1 , b 1 εLB n and c 2 , d 2 εRB n , and a collision-resistant Hash function Θ: B n →{0, 1} k , and computes x=b 1 a 1 gc 2 d 2 . The public keys of Alice are (B n , LB n , RB n , g, x, Θ), and the private keys are b 1 and d 2 .

An authentication process is:

It is given that Alice is a prover and Bob is a verifier.

6.1) Bob chooses six elements c 1 , d 1 , d 3 εRB n and a 2 , b 2 , b 3 εLB n , and the private keys are b 2 and d 1 . Bob computes

y=d 1 c 1 ga 2 b 2 and w=d 3 c 1 xa 2 b 3 ,

uses (y, w) as challenge 1, and sends the challenge 1 to Alice;

6.2) Alice chooses two elements b 4 εLB n and d 4 εRB n , computes

z=b 4 a 1 yc 2 d 4 and u=b 1 −1 wd 2 −1 =d 3 c 1 a 1 gc 2 a 2 b 3 ,

uses (z, u) as a response, and sends the response to Bob;

6.3) Bob computes v=d 1 −1 zb 2 −1 =b 4 a 1 c 1 ga 2 c 2 d 4 , uses v as challenge 2, and sends the challenge 2 to Alice;

6.4) Alice computes t=Θ(b 4 −1 vd 4 −1 )=Θ(a 1 c 1 ga 2 c 2 ), uses t as a commitment, and sends the commitment to Bob;

6.5) Bob computes t′=Θ(d 3 −1 ub 3 −1 )=Θ(c 1 a 1 gc 2 a 2 ), and verifies whether t=t′,

and if t=t′, Bob acknowledges an identity of Alice; otherwise, Bob refuses to acknowledge the identity.

4. Security Analysis

We may only provide the security of a key exchange protocol.

First, definitions of three determining problems of a group are provided.

a subgroup membership problem (subgroup membership problem or generalized word problem, GWP for short): given a subgroup H whose generator set is X in group G, whether any element g in G can be represented by a word on X is determined, that is, whether g is an element in H is determined.

an element decomposition search problem (decomposition search problem, DSP for short): given that g and h are two elements in group G. It is known that two elements c and d exist in G, so that h=cgd. Decide whether two elements c′ and d′ in G can be obtained, so that h=c′gd′.

a generalized element decomposition search problem (generalized decomposition search problem, GDSP for short): given that g and h are two elements in group G, and H and K are two subgroups in G. It is known that an element c of H and an element d of K exist, so that h=cgd. Decide whether an element c′ of H and an element d′ of K can be obtained, so that h=c′gd′.

The DSP can be solved easily by letting c′=g −1 and d′=h. The decidability of the GDSP is not determined. However, for a decomposition equation h=cgd (c and d are unknown) in an infinite non-abelian group, it is impossible to certainly solve c and d. Because people do not know values of c and d, even if they enable h=c′gd′ by using so-called “solutions” c′ and d′ which are obtained through computation by solving the GDSP problem, they also cannot determine whether c′=c and d′=d. Particularly, if c and d are separately taken from subgroups C and D with an unsolvable GWP problem, a solver not only cannot determine whether c′=c and d′=d, but also cannot determine whether c′ and d′ respectively are elements in C and D.

In core protocol 1, information that can be acquired by an attacker Eve by using disclosed information and an interactive process with Alice and Bob is as follows:

an infinite non-abelian group G and two subgroups A and B in G, so that for any aεA and any bεB, ab=ba is true, an element g in G, and the following elements in G:

y=d 1 c 1 gc 2 d 2 , x=b 1 a 1 ga 2 b 2 , z=b 3 a 1 d 1 c 1 gc 2 d 2 a 2 b 4 , w=d 3 c 1 b 1 a 1 ga 2 b 2 c 2 d 4 , and

v=b 3 a 1 c 1 gc 2 a 2 b 4 and u=d 3 c 1 a 1 ga 2 c 2 d 4

It should be noted that Eve only knows x, y, z, w, u and v, but does not know corresponding decomposition expressions. If Eve can obtain c 1 ′, c 2 ′εB, and a 1 ′, a 2 ′εA by solving the GDSP problem, so that a 1 ′ga 2 ′=a 1 ga 2 and c 1 ′gc 2 ′=c 1 gc 2 , according to the multiplication commutativity of elements in A and B, it is obtained that

c 1 ′a 1 ′ga 2 ′c 2 ′=c 1 ′a 1 ga 2 c 1 ′=a 1 c 1 ′gc 2 ′a 2 =a 1 c 1 gc 2 a 2 =K

and therefore, Eve needs to first obtain elements a 1 ga 2 and c 1 gc 2 .

Because Eve does not know a 1 ga 2 and c 1 gc 2 , she cannot strip b 1 and b 2 from x to obtain a 1 ga 2 , or strip d 1 and d 2 from y to obtain c 1 gc 2 . Eve knows w=b 1 ub 2 and z=d 1 vd 2 (but does not know b 1 and b 2 , and d 1 and d 2 ). Now, even if Eve can solve the GDSP problem, to obtain b 1 ′, b 2 ′εA, and d 1 ′, d 2 ′εB, so that b 1 ′ub 2 ′=b 1 ub 2 and d 1 ′vd 2 ′=d 1 vd 2 , she also cannot determine b 1 ′=b 1 , b 2 ′=b 2 , and d 1 ′=d 1 , d 2 ′=d 2 . Therefore, Eve still cannot strip b 1 and b 2 from x to obtain a 1 ga 2 , or strip d 1 and d 2 from y to obtain c 1 gc 2 .

Particularly, in a specific implementation solution, a braid group B n with n≧12 is taken as an infinite non-abelian group G, subgroups LB n and RB n of B n are taken as A and B respectively, and private keys b 1 and b 2 , and private keys d 1 and d 2 are respectively chosen from a Mihailova subgroup M LA (H) of LB n and a Mihailova subgroup M RA (H) of RB n . In the foregoing attack of Eve, she obtains b 1 ′, b 2 ′εLB n and d 1 ′, d 2 ′εRB n by solving the GDSP problem, so that b 1 ′ub 2 ′=b 1 ub 2 and d 1 ′vd 2 ′=d 1 vd 2 . She must determine b 1 ′=b 1 , b 2 ′=b 2 and d 1 ′=d 1 , d 2 ′=d 2 . Because b 1 , b 2 εM LA (H) and d 1 , d 2 εM RA (H), she must first determine whether b 1 ′, b 2 ′εM LA (H), and whether d 1 ′, d 2 ′εM RA (H). However, the GWP problems of M LA (H) and M RA (H) are unsolvable, so that Eve cannot carry out an attack even if she uses a quantum computational system.

In core protocol 2, information that can be acquired by an attacker Eve by using disclosed information and an interactive process with Alice and Bob is as follows:

an infinite non-abelian group G and two subgroups A and B in G, so that for any aεA and any bεB, ab=ba is true, an element g in G, and the following elements in G:

y=d 1 c 1 ga 2 b 2 , x=b 1 a 1 gc 2 d 2 , z=b 4 a 1 d 1 c 1 ga 2 b 2 c 2 d 4 , w=d 3 c 1 b 1 a 1 gc 2 d 2 a 2 b 3 , and

v=b 4 a 1 c 1 ga 2 c 2 d 4 and u=d 3 c 1 a 1 gc 2 a 2 b 3

It should be noted that, Eve only knows x, y, z, w, u, and v, but does not know corresponding decomposition expressions. If Eve can obtain c 1 ′, c 2 ′εB, and a 1 ′, a 2 ′εA by solving the GDSP problem, so that a 1 ′gc 2 ′=a 1 gc 2 and c 1 ′ga 2 ′=c 1 ga 2 , according to the multiplication commutativity of elements in A and B, it is obtained that

c 1 ′a 1 ′gc 2 ′a 2 ′=c 1 ′a 1 gc 2 c 1 ′=a 1 c 1 ′ga 2 ′c 2 =a 1 c 1 ga 2 c 2 =K

and therefore, Eve needs to first obtain elements a 1 gc 2 and c 1 ga 2 .

Because Eve does not know a 1 gc 2 and c 1 ga 2 , she cannot strip b 1 and d 2 from x to obtain a 1 gc 2 , or strip d 1 and b 2 from y to obtain c 1 ga 2 . Eve knows w=b 1 ud 2 and z=d 1 vb 2 (but does not know b 1 and b 2 , and d 1 and d 2 ). Now, even if Eve can solve the GDSP problem, to obtain b 1 ′, b 2 ′εA, and d 1 ′, d 2 ′εB, so that b 1 ′ud 2 ′=b 1 ud 2 and d 1 ′vb 2 ′=d 1 vb 2 , she also cannot determine b 1 ′=b 1 , b 2 ′=b 2 and d 1 ′=d 1 , d 2 ′=d 2 . Therefore, Eve still cannot strip b 1 and d 2 from x to obtain a 1 gc 2 , or strip d 1 and b 2 from y to obtain c 1 ga 2 .

Particularly, in a specific implementation solution, a braid group B n with n≧12 is taken as an infinite non-abelian group G, subgroups LB n and RB n of B n are taken as A and B respectively, and private keys b 1 and b 2 , and private keys d 1 and d 2 are respectively chosen from a Mihailova subgroup M LA (H) of LB n and a Mihailova subgroup M RA (H) of RB n . In the foregoing attack of Eve, she obtains b 1 ′, b 2 ′εLB n and d 1 ′, d 2 ′εRB n by solving the GDSP problem, so that b 1 ′ud 2 ′=b 1 ud 2 and d 1 ′vb 2 ′=d 1 vb 2 . She must determine b 1 ′=b 1 , b 2 ′=b 2 and d 1 ′=d 1 , d 2 ′=d 2 . Because b 1 , b 2 εM LA (H) and d 1 , d 2 εM RA (H), she must first determine whether b 1 ′, b 2 ′εM LA (H), and whether d 1 ′, d 2 ′εM RA (H). However, the GWP problems of M LA (H) and M RA (H) are unsolvable, so that Eve cannot carry out an attack even if she uses a quantum computational system.

5. Choosing of a Parameter

In an exemplary embodiment, a braid group B n has an exponent of n≧12, subgroups in each protocol are A=LB n and B=RB n , choosing of a 1 , a 2 , c 1 , and c 2 needs to satisfy that their product a 1 a 2 c 1 c 2 is not less than 256 bits, each of private keys b 1 , b 2 , d 1 and d 2 is not less than 256 bits, and each of protection layer elements b 3 , b 4 , d 3 , and d 4 is not less than 128 bits.

It is particularly pointed out that, to resist the quantum computational attack, it is suggested that private keys b 1 and b 2 , and d 1 and d 2 be respectively chosen from Mihailova subgroups M LA (H) and M RA (H) of the braid group B. Therefore, because of the unsolvability of the GWP of M LA (H) and M RA (H), as described in the security analysis, even if a quantum computational system is used, b 1 and b 2 , and d 1 and d 2 also cannot be attacked.

The foregoing describes the method of establishing public key cryptographic protocols against the quantum computational attack according to the present invention, so as to help to understand the present invention. However, the implementation manners of the present invention are not limited by the foregoing embodiments, any variation, modification, replacement, combination, and simplification made without departing from the principle of the present invention shall be an equivalent replacement manner and fall within the protection scope of the present invention.