新型多元公钥密码系统：安全加密与量子防护

198 浏览量更新于2024-08-27 收藏 578KB PDF 举报

“Extended Multivariate Public Key Cryptosystem with Secure Encryption Function” 是一篇由WANG Houzhen, ZHANG HuanGuo, WANG ZhangYi和TANG Ming共同发表在《科学中国：信息科学》2011年6月卷的研究论文，doi为10.1007/s11432-011-4262-3。该研究关注的是量子计算技术发展对当前公钥密码学，如RSA和ECC算法的威胁，并提出了一个新的多元公共密钥密码系统（MPKC），这个系统不仅可作为多变量签名方案，还能实现安全的加密功能。在当前的密码学领域，随着量子计算机的发展，传统的基于数论难题的加密算法（如RSA和椭圆曲线密码学ECC）面临着被破解的风险。量子计算机的强大计算能力可能导致这些算法的安全性不再可靠。因此，研究者转向了多元公共密钥密码系统，这是一种潜在的抵御量子计算攻击的解决方案。 MPKC是一种利用多变量方程组的复杂性来构建的密码系统，然而，尽管MPKC在多变量签名方案上有所应用，但如何构建一个能同时提供安全加密功能的MPKC仍然是个未解的问题。该论文中，作者们提出了一种创新的方法，他们基于基本的MQ（多元问题）陷门设计了一种新的MPKC结构。这种新系统利用MQ问题的难度来增加破解的复杂性，同时结合了哈希认证技术和Shamir的减法方法，以确保方案的安全性和效率。哈希函数在其中起到了关键作用，它们用于数据的预处理和验证，增加了密码系统的不可逆性和抗碰撞性。Shamir的减法则是一种秘密共享技术，可以分散密钥，使得只有拥有特定份额的人才能恢复原始密钥，这进一步增强了系统的安全性。作者们进行了全面的安全分析，证明了提出的MPKC方案不仅能够抵抗量子计算的威胁，而且在实际应用中表现出了高效性。这一贡献对多元公共密钥密码学的发展是一个积极的推动，为应对量子计算时代的加密挑战提供了新的思路和工具。这篇研究论文深入探讨了在后量子密码学时代，如何设计和实现一种既能提供安全签名又能实现安全加密的多元公共密钥密码系统，为密码学领域的研究提供了新的视角和可能的解决方案。

Wang H Z, et al. Sci China Inf Sci June 2011 Vol. 54 No. 6 1163

Table 1 List of symbols

Symbol Meaning

a degree k extension of the ﬁeld {0, 1}, where q = 2

n-dimensional vectorspace over F

a degree n extension of the ﬁeld F

H(·) a standard hash function such as SHA-1.

(·) an operation extracting the ﬁrst k bits of H(·) and mapping the bitstring into an element in F

a||b concatenation of variables a and b.

δ the number of extended input variables of public key, where 0 6 δ < n.

µ the number of increased equations of the central map for the “encrypt” operation (0 6 µ < δ), and

the number of deleted equations of the central map for the “sign” operation (−δ < µ 6 0).

systems such as McEliece cryptosystem [7]. Encryption and decryption processes are shown in Figure 2.

2.3 A survey of MPKCs

The security of MPKC schemes essentially depends on the two hard computational problems. One is based

on solving a set of randomly chosen nonlinear multivariate polynomial equations over a ﬁnite ﬁeld (called

MQ problem). This problem is known to be NP-hard [8]; that is, given a ciphertext y

, . . . , y

, ﬁnding

a plaintext solution x

, · · · , x

from quadratic equations of formula (1) is computationally infeasible.

Consequently, randomly chosen quadratic equations over ﬁnite ﬁeld F

like (1) is a one-way function.

However, in order to allow legitimate users to easily decrypt the ciphertext, the central map F is not

randomly chosen. Hence, two aﬃne bijective transformations U, T are employed to mask the central map

F as a hard one, i.e., the public key P = T ◦ F ◦ U. Here, P and F are the isomorphism of polynomials

(IP). Clearly, if an attacker can ﬁnd U and T from P , then the according MPKC is broken. However,

to ﬁnish this task requires the attacker to solve the so-called IP-problem which has been shown to be

NP-complete [9].

Generally speaking, MQ-problem and IP-problem cannot completely guarantee the security of MPKCs.

By now, all basic trapdoors (including MIA, HFE, OV and STS) are insecure, and must be modiﬁed using

some eﬀective measures for enhancing their security. Wolf [10] summarized ten modiﬁcations. In these

methods, only the minus method “–” proposed by Shamir [11] is believed to be secure and eﬃcient. The

idea of minus method is to enhance the security of basic multivariate schemes by removing the last r

coordinates from the public key or its central map. Accordingly, the resulting MPKC as an encryption

scheme runs q

times slower than the original scheme.

Apart from Shamir’s minus method, the plus method “+” and the Vinegar method “v” are believed to

be slightly more secure, while the Homogenising method “h” has no eﬀect on the security of the original

scheme. The subﬁeld method “/” and the branching metho d “⊥” are now known to be insecure. As to

the Fixing method “f”, the Sparse p olynomials “s”, the Internal perturbation “i” and the Masking “m”,

it remains unknown whether they have security eﬀect on the original MPKC scheme.

With some modiﬁcations and enhancing approaches, dozens of variants have been derived from the four

basic MQ trapdoors. However, most of these variants can only be used for signing messages. Furthermore,

their security has been seriously challenged and many eﬃcient attacks have been found [12]. Hence, there

is a rather pressing need to investigate new MQ-trapdoors or new enhancing methodologies to construct

MPKCs allowing secure encryption and signature. This observation motivates our work in this paper.

3 Extended multivariate public key cryptosystems

The key idea of EMC schemes is to increase a secret transformation L deﬁned in subsection 3.1 in the

outermost layer of the original MQ-trapdoor framework (Figure 1). More precisely, we use the map L

and some modiﬁcations to hide the basic MQ-trapdoors into a larger algorithm space; that is, we change

the original public key P : F

→ F

into P

: F

n+δ

→ F

n+µ

(δ > µ). Accordingly, the asymmetry of input

剩余10页未读，继续阅读

执念高

粉丝: 10
资源: 952

新型多元公钥密码系统：安全加密与量子防护

数据安全：加密技术与公钥系统解析

DES与RSA混合密码系统：优势互补的加密方案

硬件安全模块：保护加密密钥与确保数据安全

RSA加密 公钥、密钥生成工具

C++实现AES加密算法(128位密钥)

Java DES Plus: 安全加密与解密密码实践

CFCA Java版服务器端接口详细功能指南：加密、证书、密钥与签名操作

Logistic映射下混沌图像加密的密钥分析与安全性提升

SQLServer加密解密函数：非对称密钥与证书对称加密

密码学概述与杂凑函数分类：密钥与单表加密解析

最新资源

RSA加密公钥、密钥生成工具