【作者】 潘平；

【导师】 许成谦；

【作者基本信息】 北京邮电大学 ， 信息安全， 2013， 博士

【摘要】 自公钥密码学概念提出以来,许多优秀的公钥密码体制相继被提出并得到完善。目前,大多数未被攻破的公钥密码体制都是基于交换代数结构的困难问题,如大整数分解问题、有限域上的离散对数问题等。然而,由于量子计算的最新研究成果,许多基于交换代数结构的难题假设不再困难。于是,为了能够抵抗已有的量子算法攻击,人们开始积极寻求基于某些非交换代数结构的难题假设,并且基于这些难题假设构造安全的公钥密码体制。迄今为止,人们已经提出了许多基于非交换代数结构的公钥密码体制,特别是辫群密码体制吸引了大量的研究。但是,几乎所有发表的基于辫群的密码方案遭到了攻击。因此人们又开始积极探索除辫群以外的其他非交换代数结构以及它们在公钥密码体制中的应用。特别是,寻找合适的非交换代数结构及其相关的密码学难题假设,以及对成熟的基于交换代数结构的公钥密码体制给出非交换的模拟是一个挑战。在此背景下,本文对基于几类典型非交换代数结构上的公钥密码体制进行了深入的研究,所取得的主要研究成果如下：1.在环Z12上截断多元多项式的矩阵半群上共轭搜索问题(CSP)困难假设的基础上,给出了两个新的密码学难题假设：基于共轭搜索问题的哈希Diffie-Hellman假设(简称CSP-HDH)和基于共轭搜索问题的预言Diffie-Hellman假设(简称CSP-ODH),并且基于这些难题假设构造了新的公钥加密方案,即CSP-DHIES。该方案是首次对DHIES加密体制的非交换模拟。分别在CSP-HDH假设和CSP-ODH假设下,CSP-DHIES方案在标准模型下各自达到选择明文攻击下的不可区分性安全和自适应选择密文攻击下的不可区分安全。2.基于内自同构群上的离散对数问题困难假设下,构造了一类变色龙哈希函数和强不可伪造的一次签名方案。由于该方案可取得较小的运行参数,使得其运行时间和存储空间具有很大的优势。该方案是首次基于非交换群上的一类变色龙哈希函数和强不可伪造的一次签名方案。3.基于内自同构群上的离散对数问题困难假设下,提出了三个签名方案。这些签名方案可分别看作是Schnorr签名方案、DSA签名方案和mNyberg-Rueppel签名方案的非交换模拟。4.基于内自同构群上的离散对数问题困难假设下,提出了三个盲签名方案：Inn-Schnorr盲签名方案、Inn-DSA盲签名方案和Inn-mNyberg-Rueppel盲签名方案。这些盲签名方案可分别看作是Schnorr盲签名方案、DSA盲签名方案和mNyberg-Rueppel盲签名方案的非交换模拟。另外,这些盲签名方案均满足盲性和适应性选择消息攻击下的“多一”不可伪造性。5.基于内自同构群上的离散对数问题困难假设下,提出了非交互式可验证秘密分享方案。该秘密分享方案在秘密的保密性上是无条件安全,而子秘密的正确性依赖于内自同构群上的离散对数问题困难假设。该秘密分享方案可看作是Pederson秘密分享方案的非交换模拟。更多还原

【Abstract】 Since the inception of public key cryptography, many excellent publickey cryptosystems (PKCs) have been proposed and improved. At present, most of unbroken PKCs are based on difficult problems from commutative algebraic structures, such as integer factoring problem, discrete logarithm problem, etc. However, since recent development of quantum computation, many intractability assumptions based on commutative algebraic structures are no longer difficult. Therefore, in order to resist currently known quantum algorithm attacks, reseachers pay attention to new difficult problems from non-commutative algebraic structures and building secure PKCs based thereon.Up to date, many PKCs based on non-commutative algebraic structures have been proposed. In particular, cryptosystems based on braid groups attracted a great deal of research. Unfortunately, almost all published braid-based cryptographic schemes have been shown to be insecure. Thus, people have made lots of effort on developing PKCs based on other non-commutative algebraic structures. Moreover, it is a challenge to find suitable non-commutative algebraic structures and relevant cryptographic assumptions, and then to construct non-commutative variants of mature PKCs based on commutative algebraic structures. Under this background, this dissertation focus on studying PKCs based on several kinds of typical non-commutative algebraic structures.The main originalities and results of this dissertation are summarized as follows:1. Propose two new conjugation-related cryptography assumptions, CSP-based hash Diffie-Hellman problem (CSP-HDH) and CSP-based oracle Diffie-Hellman problem (CSP-ODH), based on a special monoid of matrices of truncated multi-variable polynomials over the ring Z12, where the conjugacy search problem is assumed to be intractable. Moreover, based onthe above assumptions, a new public-key cryptosystem, CSP-based Diffie-Hellman integrated encryption scheme (CSP-DHIES), is proposed. The construction can be viewed as the first non-communicativevariant of the well-known DHIES cryptosystem. Under the intractability assumptions of CSP-HDH and CSP-ODH, the scheme is both indistinguishable against chosen-plaintext attacks and self-adaptively chosen-ciphertext attacks in the standard model, respectively.2. Propose a family of chameleon hash functions and strongly unforgeable one-time signature schemes based on the intractability assumption of the discrete logarithm problem over inner automorphism groups. Since the sizes of the working parameters used in the constructions can be shorter significantly, this leads to remarkable gains for both in running time and in storage space. As far as we know, this is the first time to build a family of chameleon hash functions and one-time signature schemes based on non-commutative groups.3. Propose three signature schemes based on the intractability assumption of the discrete logarithm problem over inner automorphism groups. These schemes can be viewed as non-communicative variants of Schnorr signature scheme, DSA signature scheme and mNyberg-Rueppel signature scheme.4. Propose three blind signature schemes based on the intractability assumption of the discrete logarithm problem over inner automorphism groups. The proposed schemes are proved to be blind and one-more unforgery against adaptively chosen-message attacks. These schemes can be seen as non-communicative variants of Schnorr blind signature scheme, DSA blind signature scheme and mNyberg-Rueppel blind signature scheme, respectively.5. Propose a non-interactive verifiable secret sharing scheme based on the intractability assumption of the discrete logarithm problem over inner automorphism groups. The secret sharing scheme protects the privacy of the secret unconditionally, but the correctness of the shares depends on DLP-IAG assumption. As far as we know, this is the first time to build a non-interactive verifiable secret sharing scheme based on non-commutative groups.更多还原