几类同态加密方案的研究

发布时间：2018-05-20 10:31

本文选题：基于格的密码 + 无证书公钥密码系统　；参考：《西安电子科技大学》2016年博士论文

【摘要】：虽然在有效的全同态加密方案的构造上取得重大进展,但是全同态加密的计算代价还是十分昂贵的。造成这种局面的主要原因是对加密数据的同态操作比对明文数据的操作需要更多的计算。本文致力于同态加密方案的构造、方案效率的优化和方案功能拓展等方面的研究,引入诸如密文进化技术,逐步定比特填充法,具有同态性质的概率编码等新技术在一定程度上解决这个问题,并取得如下的主要成果。(1)设计了基于RLWE(Ring Learning With Errors)问题的双重批处理限层全同态加密方案。该方案允许双重打包许多明文进入到每一个密文中以实现单指令多数据型操作,从而有效地降低了密文的扩展比。同时,也给出了一种有效的密文进化技术。该技术使用给定的私钥转换阵就可以同态地对密文中的明文向量实现任意置换。(2)给出格上无证书加密方案。利用原像抽样算法抽取部分私钥并采用带误差的学习问题生成秘密值及公钥来构造格上无证书加密方案。在随机预言模型下,借助可抵抗拥有询问秘密值能力的两类攻击者,形式化地证明了该方案在选择明文和自适应选择身份攻击下(甚至是量子的)是密文不可区分的。使用两种不同的扩大明文空间的方法来进一步提高方案的效率。特别地,给出了逐步定比特填充法。它是一种由固定长度比特串去确定多个更长比特串的有效方法。该方法在构建多比特无证书加密起到重要作用。(3)为降低密钥尺寸,利用陷门抽样算法在优选的NTRU(Number Theory Research Unit)格上抽取部分私钥并使用多项式环上带误差的学习问题计算公钥等方法来构造格上无证书加密方案。它的安全性基于多项式环上带误差学习的判定问题和小多项式比判定问题这两个困难问题假设。为获取更高的效率,还提出一个无证书并行加密方案。该方案用中国剩余定理将扩大后的明文空间分解为多个不同素理想之积来实现并行加密。它还用中国剩余定理分解加密运算所在的多项式环获取中国剩余基来优化算法,使算法只涉及整数间运算。(4)引入概率同态编码新技术并基于带误差的学习问题构造出一个无证书的限层全同态加密方案。该技术可方便地把一个待加密的消息转化为环中两个元素。在无证书体制下,这两个元素可以使用用户的两个公钥分别加密。一旦同时知道这两个元素就能恢复原来的消息。否则,由编码的不确定性知,该消息可被完美隐藏。该方案借助Gentry等人提出的近似特征向量法以消除同态计算公钥,从而构造出真正意义上的无证书全同态加密方案。(5)给出关于Smart-Vercauteren所构造的同态加密方案的几个性质。这些性质不仅表明了私钥可以由一个向量简化为它的任一个分量,而且对每个i可以产生一个三元组(第i级简化明文空间,第i级简化密文空间,第i级简化私钥)。在这个三元组所组成的序列中第i级简化私钥可以解密第i级简化密文并且第i级简化私钥可由第i级代理密钥有效地计算出来。同时,第i+1级代理私钥可以利用第i级代理私钥有效算出。反之,由第i+1级代理私钥推导出第i级代理私钥是不可行的(这种方向上的推导除了前几步外)。利用上面的性质,给出一个简单且密钥和密文尺寸相对较短的分级加密方案。(6)提出一个加法同态的加密方案,它基于Smart-Vercauteren的全同态加密方案。这两个方案都工作在两个理想I和J上。作为独立的贡献,利用数域上的素理想分解给出理想I的一种二元表示,它可作为方案的公钥。通过选择具有更大解密半径的理想I来生成公私钥对,而不是像原方案选择理想J,这样可以使新方案比原方案有更大的明文空间。
[Abstract]:Although significant progress has been made in the construction of an effective homomorphic encryption scheme, the computational cost of all homomorphic encryption is still very expensive. The main reason for this situation is that the homomorphic operation of encrypted data is more computable than the operation of the plaintext data. This paper makes the construction of the homomorphic encryption scheme and the scheme efficiency. In the research of optimization and scheme function expansion, new technologies such as ciphertext evolution, gradual bit filling and probability coding with homomorphism are solved to some extent, and the following main achievements have been obtained. (1) a double batch limited layer based on the RLWE (Ring Learning With Errors) problem is designed. Full homomorphism encryption scheme. This scheme allows a double package of plaintext into each ciphertext to achieve single instruction and multiple data operations, thus effectively reducing the extension ratio of the ciphertext. At the same time, an effective cryptographic evolution technique is also given. The technique can be homomorphic to the plaintext in the ciphertext using a given private key transformation matrix. Vector implementation is arbitrary permutation. (2) a certificateless encryption scheme is given out. Using the original image sampling algorithm to extract part of the private key and use the learning problem with error to generate the secret value and the public key to construct a certificate free encryption scheme. Under the random oracle model, with the help of the two types of attackers that can resist the ability to ask the question of the secret value, it formally proves that It is clear that the scheme is not distinguishable in the selection of plaintext and adaptive selection of identity attacks (even quantum). Two different methods of expanding the plaintext space are used to further improve the efficiency of the scheme. In particular, a gradual fixed bit filling method is given. It is a kind of fixed length bit string to determine a number of longer bits. This method plays an important role in the construction of multi bit certificate free encryption. (3) to reduce the key size, we use the trapdoor sampling algorithm to extract some private keys on the preferred NTRU (Number Theory Research Unit) lattice and use the learning questions with error in the polynomial ring to compute the certificateless encryption on the lattice. In order to obtain higher efficiency, a certificate free parallel encryption scheme is proposed. In order to obtain higher efficiency, a certificate free parallel encryption scheme is proposed. The scheme uses the Chinese Remainder Theorem to decompose the enlarged plaintext space into a product of many different prime ideals. It also uses the Chinese Remainder Theorem to decompose the polynomial ring in the encryption operation to obtain the Chinese residual base to optimize the algorithm, so that the algorithm only involves the integer operation. (4) introducing the new technique of probability homomorphism coding and constructing a non certificate based all homomorphic encryption scheme based on the learning problem with error. This technique is convenient. A message to be encrypted into two elements in the ring. In a certificate free system, the two elements can be encrypted using two public keys of the user. Once the two elements are known to be able to restore the original message. Otherwise, the message can be perfectly hidden by the encoding uncertainty. The scheme is proposed with the help of Gentry et al. The approximate eigenvector method is used to eliminate the homomorphic public key, thus constructing a truly certificateless all homomorphism encryption scheme. (5) several properties of the homomorphic encryption scheme constructed by Smart-Vercauteren are given. These properties not only indicate that the private key can be reduced from one vector to any of its components, but also for each I. Produce a three tuple (I level simplified plaintext space, I level simplified ciphertext space, I level private key). In the sequence of three tuples, the simplified private key of the first level can decrypt the I level simplified ciphertext and the I level of the private key can be effectively calculated by the I agent key. At the same time, the i+1 level agent private key can be used to take advantage of the private key. I agent private key is effectively calculated. On the other hand, it is infeasible to derive the I agent private key from the i+1 agent's private key. (the derivation in this direction is in addition to the previous steps). Using the above properties, a hierarchical encryption scheme with simple and relatively short key and relatively short size is given. (6) an addition homomorphic encryption scheme is proposed, based on S The total homomorphism encryption scheme of mart-Vercauteren. These two schemes work on two ideal I and J. As an independent contribution, a two element representation of the ideal I is given by using the prime ideal decomposition on a number domain. It can be used as the public key of the scheme. By selecting a I with a larger decryption radius, the public key pair is generated instead of the original scheme. The ideal J can make the new scheme more explicit than the original one.
【学位授予单位】：西安电子科技大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TN918.4

【相似文献】