Symmetric cryptographic solution to Yao’s millionaires’ problem and an evaluation of secure multiparty computations

Secure multiparty computation has become a central research focus in the international cryptographic community and in the future likely will represent an integral part of computing science. Protocols for Yao’s millionaires’ problem provide the building blocks for many secure multiparty computation protocols, which makes their efficiency critical. Unfortunately, all known protocols for Yao’s millionaires’ problem employ public key cryptography and thus are inefficient. This article constructs a new efficient solution to Yao’s millionaires’ problem based on symmetric cryptography. We first develop an efficient protocol for set-inclusion problems, which has independent interest for secure multiparty computations. The privacy-preserving property of the solution is demonstrated by a well-accepted simulation paradigm. To compare the security levels of different solutions, we propose a new security paradigm that quantitatively captures the security levels of different solutions and can determine which secure multiparty computation solution is preferable. This article thus provides an important supplement to the simulation paradigm. Together with the simulation paradigm, it offers a complete security evaluation benchmark for multiparty computations.     

Symmetric cryptographic protocols for extended millionaires’ problem

Yao’s millionaires’ problem is a fundamental problem in secure multiparty computation, and its solutions have become building blocks of many secure multiparty computation solutions. Unfortunately, most protocols for millionaires’ problem are constructed based on public cryptography, and thus are inefficient. Furthermore, all protocols are designed to solve the basic millionaires’ problem, that is, to privately determine which of two natural numbers is greater. If the numbers are real, existing solutions do ...     

保护隐私的曼哈顿距离计算及其推广应用

安全多方计算是信息时代保护隐私和信息安全的一项关键技术.安全多方科学计算是安全多方计算十分重要的组成部分,目前已经有许多安全多方科学计算问题的解决方案,但还有更多的问题值得人们去研究.关于曼哈顿距离的安全多方计算问题目前研究的结果很少,构造曼哈顿距离的安全计算协议在密码学中有着重要的理论意义,作为基础协议能够广泛应用于其他安全多方计算协议的构造,比如保密计算两点间路径问题,保密判定点与区间以及点与点集的关系问题,以及向量相似度的保密计算都可以归约到曼哈顿距离的安全多方计算问题.本文应用加密选择技巧与一种新的编码方法相结合,以Paillier加密算法为基础,对于不同的情形(无全集限制或有全集限制)设计两数之差绝对值的高效保密计算协议.并以此为基础,设计出两种不同情形下保密计算曼哈顿距离的协议.本文证明了在半诚实模型下这些协议是安全的,并通过模拟实验来测试协议的具体执行时间,理论分析和仿真结果表明本文方案是简单易行的.最后,文中给出实例阐明本文协议在理论以及实际中的广泛应用.     

基于字符串排序的高效保密数据库查询

安全多方计算是近年来国际密码学界研究的热点问题之一,是信息社会隐私保护的核心技术.保密地将字符串按照字典序排序问题是一个全新的安全多方计算问题,在信息安全领域有重要的实际意义和广泛的应用前景.它不仅可以提高保密数据库查询的效率,还可以解决大数据情况下的百万富翁问题.为了保密地判断两个字符串按照字典序排序的位置关系,本文首先设计了一种新的编码方法和一种基于ElGamal加密算法的云外包计算下的同态加密方案,在此基础上提出了一个高效,简单的协议,并对协议做了正确性和安全性分析,同时给出了协议计算复杂性和通信复杂性的理论分析与实验验证.最后将保密的字符串排序问题的协议应用于解决百万富翁问题,从根本上解决了大数据情况下的百万富翁问题.     

同态加密方案及安全两点直线计算协议

近年来,安全多方计算一直是密码领域的一个研究热点,保密几何计算是其一个重要分支.过两私有点坐标安全地计算一条直线问题在空间信息安全方面有重要应用前景.本文首先提出一个由加密方计算（或选取）加密底数的Paillier变体同态加密方案,并证明了其在标准模型下对适应性选择明文攻击（adaptive chosen-plaintext attack,CPA）是安全的.然后在半诚实模型下,基于该变体同态加密方案设计了一个能够安全计算过两私有点直线的协议.还可以将此协议推广应用到那些可以归约为安全计算两私有点坐标差商的所有安全多方几何计算问题,从而解决了原有的基于同态加密体制的安全两方计算协议存在的信息泄露问题.     

云环境下集合隐私计算

多方保密计算是网络空间安全与隐私保护的关键技术,基于同态加密算法的多方保密计算协议是解决云计算安全的一个重要工具.集合隐私计算是多方保密计算的一个基本问题,具有广泛的应用.现有的集合隐私计算方案多是基于两方的情况,基于多方的方案较少,效率较低,且这些方案都不能扩展到云计算平台.本文首先设计了一种新的编码方案,根据新的编码方案和同态加密算法在云计算环境下构造了一个具有普遍适用性且抗合谋的保密计算集合并集问题解决方案.该方案中的同态加密算法既可以是加法同态又可以是乘法同态的加密算法.本文进一步利用哥德尔编码和ElGamal公钥加密算法构造了一种适用于云计算的高效集合并集计算方案.这些方案还可以对多个集合中的所有数据进行保密排序,并证明这些方案在半诚实模型下是安全的.本文中的方案经过简单改造,也可以保密地计算多个集合的交集.     

基于多比特全同态加密的安全多方计算

本文中,我们首先证明了李增鹏等人提出的多比特多密钥全同态加密方案(MFHE)满足密钥同态性质,利用此性质,可以通过门限解密得到最终解密结果.使用该方案,我们设计了一个在CRS模型下和半恶意攻击者模型下安全的三轮多方计算协议(MPC).该安全多方计算协议的安全性是基于容错学习问题(LWE)的两个变种问题Ferr-LWE和...     

标准模型下的高效强安全混合加密方案

如何设计标准模型下满足适应性选择密文安全（IND-CCA2）的高效加密方案,是公钥密码学领域的一个重要研究课题。基于判定型双线性Diffie-Hellman问题,提出了一个高效、短公/私钥长度、强安全的,基于对称加密算法、消息认证码算法、密钥分割算法等基础算法的一次一密型混合加密方案,分析了方案的安全性和效率。方案在标准模型下被证明具有IND-CCA2安全性,支持公开的密文完整性验证,与同类方案相比计算效率高。     

Encrypted polynomial control based on tailored two‐party computation

Encrypted control enables confidential controller evaluations in cloud‐based or networked control systems. Roughly speaking, an encrypted controller is a modified control algorithms that is capable of computing encrypted control actions based on encrypted system states. Encrypted control has been realized using different tools from cryptography such as homomorphic encryption, secret sharing, and multiparty computation. However, the vast majority of existing encrypted controllers is linear or makes intensive use of encrypted linear operations. In this article, we present a novel and flexible method for the encrypted implementation of arbitrary polynomial controllers. Technically, our approach builds on tailored two‐party computation combined with secret sharing and additively homomorphic encryption.     

高效的可验证多秘密共享方案

秘密共享是当前信息安全和密码学中一个重要的研究课题,在密钥托管、电子商务、安全多方计算、导弹发射控制等诸多领域均有广泛的应用。利用双变量单向函数的隐蔽性、离散对数问题的难解性,基于Hermite插值多项式提出了一个新的可验证多秘密共享方案以共享p个主秘密,该方案具有效率高、子秘密可重复使用、多个主秘密能同时被重构、可验证等特点。     

Lattice-based certificateless encryption scheme

Certificateless public key cryptography (CL-PKC) can solve the problems of certificate management in a public key infrastructure (PKI) and of key escrows in identity-based public key cryptography (ID-PKC). In CL-PKC, the key generation center (KGC) does not know the private keys of all users, and their public keys need not be certificated by certification authority (CA). At present, however, most certificateless encryption schemes are based on large integer factorization and discrete logarithms that are not secure in a quantum environment and the computation complexity is high. To solve these problems, we propose a new certificate-less encryption scheme based on lattices, more precisely, using the hardness of the learning with errors (LWE) problem. Compared with schemes based on large integer factorization and discrete logarithms, the most operations are matrixvector multiplication and inner products in our scheme, our approach has lower computation complexity. Our scheme can be proven to be indistinguishability chosen ciphertext attacks (IND-CPA) secure in the random oracle model.     

An efficient ID-based cryptographic encryption based on discrete logarithm problem and integer factorization problem

ID-based encryption (identity-based) is a very useful tool in cryptography. It has many potential applications. The security of traditional ID-based encryption scheme wholly depends on the security of secret keys. Exposure of secret keys requires reissuing all previously assigned encryptions. This limitation becomes more obvious today as key exposure is more common with increasing use of mobile and unprotected devices. Under this background, mitigating the damage of key exposure in ID-based encryption is an important problem. To deal with this problem, we propose to integrate forward security into ID-based encryption. In this paper, we propose a new construction of ID-based encryption scheme based on integer factorization problem and discrete logarithm problem is semantically secure against chosen plaintext attack (CPA) in random oracle model. We demonstrate that our scheme outperforms the other existing schemes in terms of security, computational cost and the length of public key.     

Efficient and short certificateless signatures secure against realistic adversaries

The notion of certificateless cryptography is aimed to eliminate the use of certificates in traditional public key cryptography and also to solve the key-escrow problem in identity-based cryptography. Many kinds of security models have been designed for certificateless cryptography and many new schemes have been introduced based on the correspondence of the security models. In generally speaking, a stronger security model can ensure a certificateless cryptosystem with a higher security level, but a realistic model can lead to a more efficient scheme. In this paper, we focus on the efficiency of a certificateless signature (CLS) scheme and introduce an efficient CLS scheme with short signature size. On one hand, the security of the scheme is based on a realistic model. In this model, an adversary is not allowed to get any valid signature under false public keys. On the other hand, our scheme is as efficient as BLS short signature scheme in both communication and computation and, therefore, turns out to be more efficient than other CLS schemes proposed so far. We provide a rigorous security proof of our scheme in the random oracle model. The security of our scheme is based on the k-CAA hard problem and a new discovered hard problem, namely the modified k-CAA problem. Our scheme can be applied to systems where signatures are typed in by human or systems with low-bandwidth channels and/or low-computation power.     

半诚实模型下关于安全多方求解交集问题的研究

特殊情形下的安全多方计算问题是目前密码学界研究的热点,特殊的安全多方计算协议的设计与分析自然成为当前人们致力研究的热门课题。数据库共享过程中,如何在不暴露各自数据集的前提下计算出交集？一直是我们感兴趣的问题,问题的解决对实现新型、安全、公平的数据共享有着重要的意义。在半诚实模型下我们基于计算不可区分概念以及交换加密的安全性假设,给出了一个用于求解交集的特殊安全双方计算协议。该协议具有公平性、安全性,并借助茫然第三方的参与,使协议简单有效。作为茫然第三方不知道最后结果及参与方的秘密,也不能与参与方串谋作弊。文中对协议的安全性进行了理论证明和分析。该协议在政府文件共享、医疗机构的合作研究、数据挖掘等领域中有着广阔的应用前景。     

公平理性委托计算协议

已存在的安全计算集合关系的协议大多基于公钥加密算法,因此很难再嵌入到带有属性关系的公钥加密或密文搜索中.针对该问题,本文给出了非加密方法安全计算集合包含关系和集合交集的2个协议.我们首先利用（n,n）秘密共享的思想分别将原来2个问题转化为集合相等问题.在此基础上,结合离散对数,构造了安全计算集合包含关系的协议1和集合交集的协议2.最后的分析显示：我们的方案没有使用任何公钥加密方法,在保持了较优通信复杂性的同时,便于作为一种子模块嵌入到带有集合操作关系的公钥加密体制或者密文搜索体制中,从而丰富这些方案的功能.     

Tight chosen ciphertext attack （CCA）-secure hybrid encryption scheme with full public verifiability

In this paper, we propose a new ＂full public verifiability＂ concept for hybrid public-key encryption schemes. We also present a new hybrid public-key encryption scheme that has this feature, which is based on the decisional bilinear Diffie-Hellman assumption. We have proven that the new hybrid public-key encryption scheme is secure against adaptive chosen ciphertext attack in the standard model. The ＂full public verifiability＂ feature means that the new scheme has a shorter ciphertext and reduces the security requirements of the symmetric encryption scheme. Therefore, our new scheme does not need any message authentication code, even when the one-time symmetric encryption scheme is passive attacks secure. Compared with all existing publickey encryption schemes that are secure to the adaptive chosen ciphertext attack, our new scheme has a shorter ciphertext, efficient tight security reduction, and fewer requirements （if the symmetric encryption scheme can resist passive attacks）.     

基于茫然传输协议的FATE联邦迁移学习方案

利用不同来源的数据参与机器学习模型的训练,能够使得训练出的模型的预测结果更加准确,然而大量的数据收集则会产生隐私方面的相关问题。FATE联邦迁移学习是一种基于同态加密的联邦学习框架,但FATE联邦迁移学习中同态加密计算复杂,收敛速度相对较慢,导致模型训练效率低。提出一种基于茫然传输协议的安全矩阵计算方案。通过实现矩阵加法和乘法及数乘的安全计算,完成参与两方交互下具有数据隐私保护特性机器学习模型的损失函数计算与梯度更新,并以此构造更高效的FATE联邦迁移学习算法方案。在此基础上,通过茫然传输扩展协议和通信批量处理,减少需要调用的茫然传输协议的数量,缩减通信轮数,从而降低茫然传输协议带来的通信消耗。性能分析结果表明,该方案的安全模型满足安全性和隐私保护性,并且具有一定的可扩展性,在局域网环境下,相比基于同态加密的方案,模型收敛的平均时间缩短约25%,并且随着数据样本特征维度的增加,该方案仍能保持稳定的收敛速度。     

一个可证明安全的无证书盲环签名方案

为了设计一种有效的盲环签名方案, 同时克服公钥证书密码体制中的复杂证书管理以及基于身份密码体制中的密钥托管问题, 将盲环签名和无证书密码体制相结合, 充分利用两者的优势, 并通过使用双线性对技术, 在随机预言模型下基于k-碰撞攻击算法(k-CAA)困难问题和修改的逆计算Diffie-Hellman(mICDH)困难问题, 提出了一种有效的无证书盲环签名方案。最后, 对方案的正确性和安全性进行了分析, 证明了该方案满足适应性选择消息攻击下的存在不可伪造性、盲性和无条件匿名性。     

抗主动攻击的保密比较协议

互联网、物联网和大数据的迅速发展,为数据共享带来了无限的机遇,也给私有数据的隐私保护带来了严峻的挑战.安全多方计算是数据共享中隐私保护的关键技术,是密码学的一个重要研究方向,也是国际密码学界研究的热点.保密比较两个数的大小是安全多方计算的一个基本问题,是构建其他隐私保护协议的一个基本模块.当比较的数较小时,还没有可靠的能够抵抗主动攻击的保密比较问题解决方案.很多应用场景中的参与者可能会发动主动攻击,因为尚没有抗主动攻击的保密比较协议,这些场景中的保密比较问题还无法解决.因而研究抗主动攻击的保密比较问题解决方案有重要理论与实际意义.提出了一种加密-选择安全多方计算模式和编码+保密洗牌证明的抵抗主动攻击方法.在此基础上,设计了半诚实模型下安全的保密比较协议,用模拟范例证明了协议的安全性;分析了恶意参与者可能实施的主动攻击,结合ElGamal密码系统的乘法同态性、离散对数与保密洗牌的零知识证明设计阻止恶意行为的措施,将半诚实模型下安全的保密比较协议改造成抗主动攻击的保密比较协议,并用理想-实际范例证明了协议的安全性.最后分析了协议的效率,并通过实验验证协议是可行的.     

基于单个服务器的双线性对运算外包算法

双线性对运算是公钥密码算法的基本运算之一,在基于身份加密、基于属性加密等密码体制中有重要应用。现有可行的双线性对外包算法均基于两个不可信服务器,这在实际应用中不易实现。针对此问题,提出一种基于单个服务器的双线性对运算外包算法。通过少量的预计算,即可对用户的输入进行盲化处理,实现输入及输出的保密性,并能有效地验证外包结果的正确性。实验结果表明,所提算法只需进行常数次点加和模乘运算,极大地降低用户的计算代价,并且可验证性概率可达到2/5。与现有的双线性外包算法相比,所提算法仅需要调用一个不可信服务器,在实际应用中更易实现。