CN103200000B

CN103200000B - Shared key method for building up under a kind of quantum computation environment

Info

Publication number: CN103200000B
Application number: CN201310102022.4A
Authority: CN
Inventors: 王后珍; 张焕国
Original assignee: Wuhan University WHU
Current assignee: Wuhan University WHU
Priority date: 2013-03-27
Filing date: 2013-03-27
Publication date: 2016-03-16
Anticipated expiration: 2033-03-27
Also published as: CN103200000A

Abstract

The present invention relates to field of information security technology, particularly relate to the shared key method for building up under a kind of quantum computation environment, comprise the system of foundation and communicating pair A and B sets up shared key two steps.The present invention adopts polynomial homomorphism problem to give a kind of method for building up of shared key, there is the advantage such as attack that implementation efficiency is high, do not need cipher code arithmetic assisting processor, tight security, anti-quantum computer, in the security fields such as smart card, radio sensing network, than traditional secrete key exchange agreement as Diffie-Hellman IKE etc. has superiority.Method provided by the invention can be widely used in the information safety system such as network security, ecommerce field.

Description

A Shared Key Establishment Method in Quantum Computing Environment

技术领域technical field

本发明涉及信息安全技术领域，尤其涉及一种量子计算环境下的共享密钥建立方法。The invention relates to the technical field of information security, in particular to a method for establishing a shared key in a quantum computing environment.

背景技术Background technique

针对对称密码体制中密钥管理复杂的难题，1976年Diffie和Hellman开创性地提出了“公钥密码体制”的概念，指出可以在公开信道上传递秘密信息。与对称密码相比，公钥密码系统中加解密运算一般比较复杂、实现效率低，因而并不适合直接加密大量数据。通常的做法是：使用公钥密码技术(密钥建立协议)来建立一个共享会话密钥；然后，用会话密钥作为对称密码的密钥来加密大量明文信息。Aiming at the complex problem of key management in symmetric cryptosystems, Diffie and Hellman pioneered the concept of "public key cryptosystem" in 1976, pointing out that secret information can be transmitted on open channels. Compared with symmetric cryptography, encryption and decryption operations in public key cryptography systems are generally more complex and less efficient, so they are not suitable for directly encrypting large amounts of data. The usual practice is: use public key cryptography (key establishment protocol) to establish a shared session key; then, use the session key as the key of the symmetric cipher to encrypt a large amount of plaintext information.

一般来说，密钥建立协议可分为：密钥分发协议和密钥交换(协商)协议。密钥分发协议中，发送方A选择一个会话密钥并将其安全地传送给接收方B，通常需要第三方来负责或协助建立。而密钥交换协议中，通信双方共同产生会话密钥，没有任何一方可以事先决定这个值。从某种意义说，密钥交换协议较密钥分发协议有一定的优势。经典Diffie-Hellman密钥交换协议存在着中间人攻击的缺陷，改进的方法是引入认证机制。根据发展的需求，在Diffie-Hellman密钥交换协议的基础上，又出现许多改进的协议，其中，MQV协议已成为IEEEP1363标准。但是这些协议大都是基于离散对数或椭圆曲线离散对数，不能抵御量子计算的攻击。因此，量子计算安全的密钥建立协议值得我们深入研究。Generally speaking, key establishment protocols can be divided into: key distribution protocols and key exchange (negotiation) protocols. In the key distribution protocol, the sender A selects a session key and securely transmits it to the receiver B, usually requiring a third party to be responsible or assist in the establishment. In the key exchange protocol, both communication parties jointly generate a session key, and no party can determine this value in advance. In a sense, the key exchange protocol has certain advantages over the key distribution protocol. The classic Diffie-Hellman key exchange protocol has the defect of man-in-the-middle attack, and the improved method is to introduce authentication mechanism. According to the needs of development, on the basis of the Diffie-Hellman key exchange protocol, there are many improved protocols. Among them, the MQV protocol has become the IEEEEP1363 standard. However, most of these protocols are based on discrete logarithms or elliptic curve discrete logarithms, which cannot resist quantum computing attacks. Therefore, key establishment protocols for quantum computing security deserve our in-depth study.

量子密码学中的密钥建立协议实际上也分为密钥分发协议和密钥交换(协商)协议，一般统称量子密钥分发(QKD)协议。一般地，一个基本的点到点QKD链接是一个随机对称密钥分发系统，其安全性基于对量子通信过程有效的窃听检测。目前在量子信道上进行量子密钥分发已经比较接近实用，但是并不能把量子信道作为天然的保密信道来直接进行明文信息的保密通信。The key establishment protocol in quantum cryptography is actually divided into key distribution protocol and key exchange (negotiation) protocol, generally referred to as quantum key distribution (QKD) protocol. Generally, a basic point-to-point QKD link is a random symmetric key distribution system whose security is based on effective wiretapping detection for quantum communication processes. At present, quantum key distribution on quantum channels is relatively close to practicality, but quantum channels cannot be used as natural security channels to directly carry out secure communication of plaintext information.

目前，抗量子计算密码学领域的研究主要集中在公钥加密和数字签名方面，而具有抗量子计算潜力的密钥交换协议却研究较少。1999年Anshel等提出了基于一般非交换群的密钥交换协议，2001年他们又基于辫群提出了一个双方密钥交换协议，这两个协议后来被证明是不安全的。2000年美密会上Ko等提出了所谓的Diffie-Hellman类型的共轭问题(DHCP)，并基于此问题的困难性假设，提出了一个Diffie-Hellman型的双方密钥交换协议，然而，2003年Cheon等给出了求解这个问题的多项式时间算法，2005年Myasnikon等给出一个更高效的求解方法。2010年Boucher等在PQCrypto2010会议上基于一种特殊非交换乘法多项式提出了一种双方密钥交换协议，这个协议随后被Dubois等攻破。At present, the research in the field of anti-quantum computing cryptography mainly focuses on public key encryption and digital signature, while the research on key exchange protocols with the potential of anti-quantum computing is less. In 1999, Anshel et al. proposed a key exchange protocol based on general non-exchange groups, and in 2001 they proposed a two-party key exchange protocol based on braided groups. These two protocols were later proved to be insecure. Ko et al. proposed the so-called Diffie-Hellman type conjugate problem (DHCP) at the US Secret Conference in 2000, and based on the difficult assumption of this problem, proposed a Diffie-Hellman type two-party key exchange protocol. However, in 2003 Cheon et al. gave a polynomial time algorithm to solve this problem. In 2005, Myasnikon et al. gave a more efficient solution method. In 2010, Boucher et al. proposed a two-party key exchange protocol based on a special non-commutative multiplication polynomial at the PQCrypto2010 conference, which was subsequently broken by Dubois et al.

发明内容Contents of the invention

针对上述存在的技术问题，本发明的目的是提供一种量子计算环境下的共享密钥建立方法。In view of the above-mentioned existing technical problems, the object of the present invention is to provide a method for establishing a shared key in a quantum computing environment.

为达到上述目的，本发明采用如下的技术方案：To achieve the above object, the present invention adopts the following technical solutions:

一种量子计算环境下的共享密钥建立方法，其特征在于，包括以下步骤：A method for establishing a shared key in a quantum computing environment, characterized in that it comprises the following steps:

步骤1：建立系统：Step 1: Build the system:

选择有限域GF(q)，随机选取GF(q)上的m维方阵T₀和n维方阵U₀、以及n个变量m个二次多项式构成的非线性变换F，F可表示为：Select finite field GF(q), randomly select m-dimensional square matrix T ₀ and n-dimensional square matrix U ₀ on GF(q), and nonlinear transformation F composed of n variables and m quadratic polynomials, F can be expressed as :

F(x₁，…，x_n)＝(f₁(x₁，…，x_n)，…，f_m(x₁，…，x_n))F(x ₁ ,...,x _n )=(f ₁ (x ₁ ,...,x _n ),...,f _m (x ₁ ,...,x _n ))

这里，f_i为n元二次多项式函数，形式如下：Here, f _i is an n-ary quadratic polynomial function, the form is as follows:

${f f}_{i i} (({x x}_{11},, ... ...,, {x x}_{n no})) = = \underset{11 \leq \leq j j \leq \leq k k \leq \leq n no}{Σ Σ} {c c}_{i i j j k k} {x x}_{j j} {x x}_{k k} + + \underset{11 \leq \leq j j \leq \leq n no}{Σ Σ} {b b}_{i i j j} {x x}_{j j} + + {a a}_{i i}$

其中，所有参数x_j，x_k，a_i，b_ij，c_ijk∈GF(q)(1≤j≤k≤n，1≤i≤m)；Among them, all parameters x _j , x _k , a _i , b _ij , c _ijk ∈ GF(q)(1≤j≤k≤n, 1≤i≤m);

步骤2：通信双方A和B建立共享密钥；其过程包括6个子步骤：Step 2: Communication parties A and B establish a shared key; the process includes 6 sub-steps:

(1)A随机选取α_i，β_j∈GF(q)，其中0≤i≤m，0≤j≤n，计算私钥(1) A randomly selects α _i , β _j ∈ GF(q), where 0≤i≤m, 0≤j≤n, and calculates the private key

${T T}_{a a} = = {Σ Σ}_{i i = = 00}^{m m} {α α}_{i i} {T T}_{00}^{i i},, {U u}_{a a} = = {Σ Σ}_{j j = = 00}^{n no} {β β}_{j j} {U u}_{00}^{j j},,$

同时计算会话信息G_a＝T_aοFοU_a；Simultaneously calculate session information G _a =T _a οFοU _a ;

(2)B随机选取γ_i，δ_j∈GF(q)，其中0≤i≤m，0≤j≤n，计算私钥(2) B randomly selects γ _i , δ _j ∈ GF(q), where 0≤i≤m, 0≤j≤n, and calculates the private key

${T T}_{b b} = = {Σ Σ}_{i i = = 00}^{m m} {γ γ}_{i i} {T T}_{00}^{i i},, {U u}_{b b} = = {Σ Σ}_{j j = = 00}^{n no} {δ δ}_{j j} {U u}_{00}^{j j},,$

同时计算会话信息G_b＝T_bοFοU_b；Simultaneously calculate the session information G _b =T _b οFοU _b ;

(3)A发送会话信息G_a给B；(3) A sends session information G _a to B;

(4)B发送会话信息G_b给A；(4) B sends session information G _b to A;

(5)A用自己的私钥计算出共享密钥G_ba＝T_aοG_bοU_a；(5) A calculates the shared key G _ba =T _a οG _b οU _a with its own private key;

(6)B用自己的私钥计算出共享密钥G_ab＝T_bοG_aοU_b；(6) B uses its own private key to calculate the shared key G _ab =T _b οG _a οU _b ;

其中，上述步骤(1)(2)(5)(6)中符号“ο”表示映射之间的复合运算。Wherein, the symbol "o" in the above steps (1)(2)(5)(6) represents the composite operation between mappings.

本发明具有以下优点和积极效果：The present invention has the following advantages and positive effects:

1.本发明是一种安全性很高的密钥交换协议。其安全性性能主要基于多项式同态问题，该问题已被证明为NPC问题，另外，本发明继承了传统多变量公钥密码系统的优点，因此本发明具有抵抗量子计算机攻击的潜力；1. The present invention is a key exchange protocol with high security. Its security performance is mainly based on the polynomial homomorphism problem, which has been proved to be an NPC problem. In addition, the invention inherits the advantages of the traditional multivariable public key cryptosystem, so the invention has the potential to resist quantum computer attacks;

2.本发明是一种高效轻量的密钥交换协议，其运算主要为有限域上的乘法运算，如果我们选择较小的域参数如GF(2⁸)，则乘法可采用查表，效率较高，本方案可广泛应用于计算能力有限的嵌入式设备中。2. The present invention is a kind of high-efficiency and lightweight key exchange agreement, and its operation is mainly the multiplication operation on the finite field, if we choose smaller field parameter such as GF (2 ⁸ ), then multiplication can adopt look-up table, efficiency Higher, this scheme can be widely used in embedded devices with limited computing power.

附图说明Description of drawings

图1：是本发明的量子计算环境下的共享密钥建立方法的流程图。Fig. 1: is the flowchart of the method for establishing a shared key under the quantum computing environment of the present invention.

具体实施方式detailed description

下面结合附图和具体实施例来描述本发明提出的量子计算环境下的共享密钥建立方法。The method for establishing a shared key under the quantum computing environment proposed by the present invention will be described below in conjunction with the accompanying drawings and specific embodiments.

请见图1，本发明的量子计算环境下的共享密钥建立方法，包括以下步骤：Please see Fig. 1, the shared key establishment method under the quantum computing environment of the present invention, comprises the following steps:

步骤1：建立系统：Step 1: Build the system:

选择有限域GF(2¹⁶)，随机选取GF(2¹⁶)上的10维方阵T₀和12维方阵U₀、以及12个变量10个二次多项式构成的非线性变换F，F可表示为：Choose finite field GF(2 ¹⁶ ), randomly select 10-dimensional square matrix T ₀ and 12-dimensional square matrix U ₀ on GF(2 ¹⁶ ), and nonlinear transformation F composed of 12 variables and 10 quadratic polynomials, F can be Expressed as:

F(x₁，…，x₁₂)＝(f₁(x₁，…，x₁₂)，…，f₁₀(x₁，…，x₁₂))F(x ₁ ,...,x ₁₂ )=(f ₁ (x ₁ ,...,x ₁₂ ),...,f ₁₀ (x ₁ ,...,x ₁₂ ))

这里，f_i为12元二次多项式函数，形式如下：Here, f _i is a quadratic polynomial function with 12 elements, the form is as follows:

${f f}_{i i} (({x x}_{11},, ... ...,, {x x}_{1212})) = = \underset{11 \leq \leq j j \leq \leq k k \leq \leq 1212}{Σ Σ} {c c}_{i i j j k k} {x x}_{j j} {x x}_{k k} + + \underset{11 \leq \leq j j \leq \leq 1212}{Σ Σ} {b b}_{i i j j} {x x}_{j j} + + {a a}_{i i}$

其中，所有参数x_i，a_i，c_ijk∈GF(2¹⁶)(1≤j≤k≤12，1≤i≤10)；Among them, all parameters x _i , a _i , c _ijk ∈ GF(2 ¹⁶ )(1≤j≤k≤12, 1≤i≤10);

(1)A随机选取α_i，β_j∈GF(2¹⁶)，其中0≤i≤10，0≤j≤12，计算私钥(1) A randomly selects α _i , β _j ∈ GF(2 ¹⁶ ), where 0≤i≤10, 0≤j≤12, and calculates the private key

${T T}_{a a} = = {Σ Σ}_{i i = = 00}^{1010} {α α}_{i i} {T T}_{00}^{i i},, {U u}_{a a} = = {Σ Σ}_{j j = = 00}^{1212} {β β}_{j j} {U u}_{00}^{j j},,$

(2)B随机选取γ_i，δ_j∈GF(q)，其中0≤i≤10，0≤j≤12，计算私钥(2) B randomly selects γ _i , δ _j ∈ GF(q), where 0≤i≤10, 0≤j≤12, and calculates the private key

${T T}_{b b} = = {Σ Σ}_{i i = = 00}^{1010} {γ γ}_{i i} {T T}_{00}^{i i},, {U u}_{b b} = = {Σ Σ}_{j j = = 00}^{1212} {δ δ}_{j j} {U u}_{00}^{j j},,$

(3)A发送会话信息G_a给B；(3) A sends session information G _a to B;

(4)B发送会话信息G_b给A；(4) B sends session information G _b to A;

其中，上述步骤(1)(2)(5)(6)中符号“ο”表示映射间的复合运算。Wherein, the symbol "o" in the above steps (1)(2)(5)(6) represents the composite operation between mappings.

本实施例的安全性水平约为其主要的运算是有限域GF(2¹⁶)上的乘法运算，实现效率高，适合软硬件实现，其次，公钥为134680比特，私钥为3904比特，较SFLASH标准签名算法的密钥量小得多。The safety level of this example is about Its main operation is the multiplication operation on the finite field GF(2 ¹⁶ ), which is highly efficient and suitable for hardware and software implementation. Secondly, the public key is 134680 bits, and the private key is 3904 bits, which is smaller than the key amount of the SFLASH standard signature algorithm much.

本说明书未详细描述的内容属于本专业技术人员公知的现有技术。The content not described in detail in this specification belongs to the prior art known to those skilled in the art.

本发明采用多项式同态问题给出了一种共享密钥的建立方法，具有实现效率高、不需要密码算法协处理器、高度安全性、抗量子计算机的攻击等优点，在智能卡、无线传感网络等安全领域、比传统密钥交换协议如Diffie-Hellman密钥交换协议等有优势。本发明提供的方法可广泛应用于网络安全、电子商务等信息安全系统领域。The present invention adopts the polynomial homomorphic problem to provide a method for establishing a shared key, which has the advantages of high implementation efficiency, no need for a cryptographic algorithm coprocessor, high security, and anti-quantum computer attacks. In security fields such as networks, it has advantages over traditional key exchange protocols such as Diffie-Hellman key exchange protocols. The method provided by the invention can be widely used in information security system fields such as network security and e-commerce.

以上所述实施例仅是为充分说明本发明而所举的较佳的实施例，本发明的保护范围不限于此。本技术领域的技术人员在本发明基础上所作的等同替代或变换，均在本发明的保护范围之内。本发明的保护范围以权利要求书为准。The above-mentioned embodiments are only preferred embodiments for fully illustrating the present invention, and the protection scope of the present invention is not limited thereto. Equivalent substitutions or transformations made by those skilled in the art on the basis of the present invention are all within the protection scope of the present invention. The protection scope of the present invention shall be determined by the claims.

Claims

1. the shared key method for building up under quantum computation environment, is characterized in that, comprise the following steps:

Step 1: set up system:

Select finite field gf (q), the m on random selecting GF (q) ties up square formation T ₀square formation U is tieed up with n ₀, and the nonlinear transformation F that forms of n variable m quadratic polynomial, F can be expressed as:

F(x ₁，…，x _n)＝(f ₁(x ₁，…，x _n)，…，f _m(x ₁，…，x _n))

Here, f _ifor n unit quadratic polynomial function, form is as follows:

f_{i} (x_{1}, ..., x_{n}) = \underset{1 \leq j \leq k \leq n}{Σ} c_{i j k} x_{j} x_{k} + \underset{1 \leq j \leq n}{Σ} b_{i j} x_{j} + a_{i}

Wherein, all parameter x _j, x _k, a _i, b _ij, c _ijk∈ GF (q) (1≤j≤k≤n, 1≤i≤m);

Step 2: communicating pair A and B sets up shared key; Its process comprises 6 sub-steps:

(1) A random selecting α _i, β _j∈ GF (q), wherein 0≤i≤m, 0≤j≤n, calculate private key

T_{a} = Σ_{i = 0}^{m} α_{i} T_{0}^{i}, U_{a} = Σ_{j = 0}^{n} β_{j} U_{0}^{j},

Calculate session information G simultaneously _a=T _aο F ο U _a;

(2) B random selecting γ _i, δ _j∈ GF (q), wherein 0≤i≤m, 0≤j≤n, calculate private key

T_{b} = Σ_{i = 0}^{m} γ_{i} T_{0}^{i}, U_{b} = Σ_{j = 0}^{n} δ_{j} U_{0}^{j},

Calculate session information G simultaneously _b=T _bο F ο U _b;

(3) A sends session information G _ato B;

(4) B sends session information G _bto A;

(5) the A private key of oneself calculates shared key G _ba=T _aο G _bο U _a;

(6) the B private key of oneself calculates shared key G _ab=T _bο G _aο U _b;

Wherein, in above-mentioned steps (1) (2) (5) (6), symbol " ο " represents the compound operation between mapping.