RSA-OAEP Is Secure under the RSA Assumption

Recently Victor Shoup noted that there is a gap in the widely believed security result of OAEP against adaptive chosen-ciphertext attacks. Moreover, he showed that, presumably, OAEP cannot be proven secure from the one-wayness of the underlying trapdoor permutation. This paper establishes another result on the security of OAEP. It proves that OAEP offers semantic security against adaptive chosen-ciphertext attacks, in the random oracle model, under the partial-domain one-wayness of the underlying permutation. Therefore, this uses a formally stronger assumption. Nevertheless, since partial-domain one-wayness of the RSA function is equivalent to its (full-domain) onewayness, it follows that the security of RSA-OAEP can actually be proven under the sole RSA assumption, although the reduction is not tight.     

Instantiability of RSA-OAEP Under Chosen-Plaintext Attack

We show that the widely deployed RSA-OAEP encryption scheme of Bellare and Rogaway (Eurocrypt 1994), which combines RSA with two rounds of an underlying Feistel network whose hash ( i.e., round) functions are modeled as random oracles, meets indistinguishability under chosen-plaintext attack (IND-CPA) in the standard model based on simple, non-interactive, and non-interdependent assumptions on RSA and the hash functions. To prove this, we first give a result on a more general notion called “padding-based” encryption, saying that such a scheme is IND-CPA if (1) its underlying padding transform satisfies a “fooling" condition against small-range distinguishers on a class of high-entropy input distributions, and (2) its trapdoor permutation is sufficiently lossy as defined by Peikert and Waters (STOC 2008). We then show that the first round of OAEP satisfies condition (1) if its hash function is t-wise independent for t roughly proportional to the allowed message length. We clarify that this result requires the hash function to be keyed, and for its key to be included in the public key of RSA-OAEP. We also show that RSA satisfies condition (2) under the \(\Phi \)-Hiding Assumption of Cachin et al. (Eurocrypt 1999). This is the first positive result about the instantiability of RSA-OAEP. In particular, it increases confidence that chosen-plaintext attacks are unlikely to be found against the scheme. In contrast, RSA-OAEP’s predecessor in PKCS #1 v1.5 was shown to be vulnerable to such attacks by Coron et al. (Eurocrypt 2000).     

利用容错学习问题构造基于身份的全同态加密体制简

基于容错学习问题构造的一类全同态加密体制在云计算安全领域具有重要的潜在应用价值,但同时普遍存在着公钥尺寸较大的缺陷,严重影响其身份认证与密钥管理的效率。将基于身份加密的思想与基于容错学习问题的全同态加密相结合,提出一种基于身份的全同态加密体制,能够有效克服公钥尺寸对于全同态加密应用效率的影响。在随机喻示模型下,体制的安全性归约到容错学习问题难解性和陷门单向函数单向性,并包含严格的安全性证明。     

A New Public-Key Cryptosystem over a Quadratic Order with Quadratic Decryption Time

We present a new cryptosystem based on ideal arithmetic in quadratic orders. The method of our trapdoor is different from the Diffie—Hellman key distribution scheme or the RSA cryptosystem. The plaintext m is encrypted by mp ^r , where p is a fixed element and r is a random integer, so our proposed cryptosystem is a probabilistic encryption scheme and has the homomorphy property. The most prominent property of our cryptosystem is the cost of the decryption, which is of quadratic bit complexity in the length of the public key. Our implementation shows that it is comparably as fast as the encryption time of the RSA cryptosystem with e=2 ¹⁶ +1 . The security of our cryptosystem is closely related to factoring the discriminant of a quadratic order. When we choose appropriate sizes of the parameters, the currently known fast algorithms, for example, the elliptic curve method, the number field sieve, the Hafner—McCurley algorithm, are not applicable. We also discuss that the chosen ciphertext attack is not applicable to our cryptosystem. Received 29 June 1998 and revised 15 November 1998     

具有强安全性的不含双线性对的无证书签名方案

该文提出了一种满足强安全性的不需双线性对运算的无证书签名方案,能抵抗适应性选择消息和适应性选择身份的存在性伪造攻击,并且在随机预言模型下基于离散对数难题给出了完整的安全性证明。与现有的绝大多数无证书签名方案都是基于双线性对的不同,该文提出的新方案没有复杂的双线性对运算,具有明显的效率优势。另外,通过对王会歌等人的无证书签名方案进行分析,指出此方案是不安全的,并给出了具体的攻击方法。     

可证安全的高效无证书有序多重签名方案

无证书有序多重签名可用于解决信任链推荐信息的认证问题。秦艳琳等提出一个高效的无证书有序多重签名方案,并在随机语言机模型下证明方案的安全性可归约为CDH（computational Diffie-Hellman）困难问题。对该方案的安全性证明过程进行分析,指出方案难以抵抗伪造攻击：攻击者已知某个多重签名,则可以伪造其他消息的多重签名。随后构造一个更加高效的无证书有序多重签名方案,方案使用更少的双线性对,且只有一个签名消息,占用更小的计算代价和通信代价。最后证明方案在随机预言机模型下具有不可伪造性。     

加密邮件系统中基于身份的可搜索加密方案

在加密邮件系统中,公钥可搜索加密技术可以有效地解决在不解密的情况下搜索加密邮件的问题。针对公钥可搜索加密复杂的密钥管理问题,该文在加密邮件系统中引入了基于身份的密码体制。针对可搜索加密的离线关键字猜测攻击问题,该文采用了在加密关键字和生成陷门的同时进行认证,并且指定服务器去搜索加密电子邮件的方法。同时,在随机预言机模型下,基于判定性双线性Diffie-Hellman假设,证明方案满足陷门和密文不可区分性安全。数值实验结果表明,在陷门生成和关键字密文检测阶段,该方案与现有方案相比在计算效率上较高。     

The Twin Diffie–Hellman Problem and Applications

We propose a new computational problem called the twin Diffie–Hellman problem. This problem is closely related to the usual (computational) Diffie–Hellman problem and can be used in many of the same cryptographic constructions that are based on the Diffie–Hellman problem. Moreover, the twin Diffie–Hellman problem is at least as hard as the ordinary Diffie–Hellman problem. However, we are able to show that the twin Diffie–Hellman problem remains hard, even in the presence of a decision oracle that recognizes solutions to the problem—this is a feature not enjoyed by the Diffie–Hellman problem, in general. Specifically, we show how to build a certain “trapdoor test” that allows us to effectively answer decision oracle queries for the twin Diffie–Hellman problem without knowing any of the corresponding discrete logarithms. Our new techniques have many applications. As one such application, we present a new variant of ElGamal encryption with very short ciphertexts, and with a very simple and tight security proof, in the random oracle model, under the assumption that the ordinary Diffie–Hellman problem is hard. We present several other applications as well, including a new variant of Diffie and Hellman’s non-interactive key exchange protocol; a new variant of Cramer–Shoup encryption, with a very simple proof in the standard model; a new variant of Boneh–Franklin identity-based encryption, with very short ciphertexts; a more robust version of a password-authenticated key exchange protocol of Abdalla and Pointcheval. This paper was solicted by the Editors-in-Chief as one of the best papers from EUROCRYPT 2008, based on the recommendation of the program committee. Part of this work completed while at CWI. Supported by the research program Sentinels. Supported by NSF award number CNS-0716690.     

指定测试者的基于身份可搜索加密方案

对指定测试者的基于身份可搜索加密(dIBEKS)方案进行了研究。指出Tseng等人所提dIBEKS方案并不是完全定义在基于身份密码系统架构上,而且方案不能满足dIBEKS密文不可区分性。首次提出了基于身份密码系统下的指定测试者可搜索加密方案的定义和安全需求,并设计了一个高效的dIBEKS新方案。证明了dIBEKS密文不可区分性是抵御离线关键字猜测攻击的充分条件,并证明了新方案在随机预言模型下满足适应性选择消息攻击的dIBEKS密文不可区分性、陷门不可区分性,从而可以有效抵御离线关键字猜测攻击。     

Optimal Security Proofs for Full Domain Hash,Revisited

RSA Full Domain Hash (RSA-FDH) is a digital signature scheme, secure against chosen message attacks in the random oracle model. The best known security reduction from the RSA assumption is non-tight, i.e., it loses a factor of \(q_s\), where \(q_s\) is the number of signature queries made by the adversary. It was furthermore proven by Coron (Advances in cryptology—EUROCRYPT 2002, Lecture notes in computer science, vol 2332. Springer, Berlin, pp 272–287, 2002) that a security loss of \(q_s\) is optimal and cannot possibly be improved. In this work, we uncover a subtle flaw in Coron’s impossibility result. Concretely, we show that it only holds if the underlying trapdoor permutation is certified. Since it is well known that the RSA trapdoor permutation is (for all practical parameters) not certified, this renders Coron’s impossibility result moot for RSA-FDH. Motivated by this, we revisit the question whether there is a tight security proof for RSA-FDH. Concretely, we give a new tight security reduction from a stronger assumption, the Phi-Hiding assumption introduced by Cachin et al. (Advances in Cryptology—EUROCRYPT’99. Lecture notes in computer science, vol 1592. Springer, Berlin, pp 402–414, 1999). This justifies the choice of smaller parameters in RSA-FDH, as it is commonly used in practice. All of our results (positive and negative) extend to the probabilistic signature scheme PSS (with message recovery).     

A Forward-Secure Public-Key Encryption Scheme

Cryptographic computations are often carried out on insecure devices for which the threat of key exposure represents a serious concern. Forward security allows one to mitigate the damage caused by exposure of secret keys. In a forward-secure scheme, secret keys are updated at regular periods of time; exposure of the secret key corresponding to a given time period does not enable an adversary to "break" the scheme (in the appropriate sense) for any prior time period. We present the first constructions of (non-interactive) forward-secure public-key encryption schemes. Our main construction achieves security against chosen-plaintext attacks in the standard model, and all parameters of the scheme are poly-logarithmic in the total number of time periods. Some variants and extensions of this scheme are also given. We also introduce the notion of binary tree encryption and construct a binary tree encryption scheme in the standard model. Our construction implies the first hierarchical identity-based encryption scheme in the standard model. (The notion of security we achieve, however, is slightly weaker than that achieved by some previous constructions in the random oracle model.)     

Trapdoor Security Lattice-Based Public-Key Searchable Encryption with a Designated Cloud Server

Cloud storage technique has becoming increasingly significant in cloud service platform. Before choosing to outsource sensitive data to the cloud server, most of cloud users need to encrypt the important data ahead of time. Recently, the research on how to efficiently retrieve the encrypted data stored in the cloud server has become a hot research topic. Public-key searchable encryption, as a good candidate method, which enables a cloud server to search on a collection of encrypted data with a trapdoor from a receiver, has attracted more researchers’ attention. In this paper, we propose the frist efficient lattice-based public-key searchable encryption with a designated cloud server, which can resist quantum computers attack. In our scheme, we designate a unique cloud server to test and return the search results, thus can remove the secure channel between the cloud server and the receiver. We have proved that our scheme can achieve ciphertext indistinguishability under the hardness of learning with errors, and can achieve trapdoor security in the random oracle model. Moreover, our scheme is secure against off-line keyword guessing attacks from outside adversary.     

密码学中的随机预言模型与标准模型

随机预言模型与标准模型是密码学可证明安全理论中非常重要的两类模型。在此对这两种模型进行了描述,并研究了运用它们证明密码方案或协议安全性时所采取的不同技术,包括随机预言模型在加密和数字签名方案中的应用研究,以及标准模型下可证明安全性理论在加密方案中的应用研究。此外对进一步研究方向进行了展望。     

Pairing-Free ID-Based Key-Insulated Signature Scheme

Without the assumption that the private keys are kept secure perfectly, cryptographic primitives cannot be deployed in the insecure environments where the key leakage is inevitable. In order to reduce the damage caused by the key exposure in the identity-based (ID-based) signature scenarios efficiently, we propose an ID-based key-insulated signature scheme in this paper, which eliminates the expensive bilinear pairing operations. Compared with the previous work, our scheme minimizes the computation cost without any extra cost. Under the discrete logarithm (DL) assumption, a security proof of our scheme in the random oracle model has also been given.     

Pairing-Free Certificateless Key-Insulated Encryption with Provable Security

Certificateless encryption attracts a lot of attention so far by eliminating the key escrow problem in identity-based encryption and public key certificates in the traditional public key cryptography. By considering the threat from the key exposure, it is desirable to incorporate the idea of key-insulated cryptosystem into the certificateless encryption. In this paper, we have designed an efficient certificateless key-insulated encryption (CL-KIE) scheme to achieve this goal. By our approach, the computational performance of our scheme has been improved significantly in terms of reduction on running time and storage. We also gave the security proof of the new CL-KIE scheme against the chosen plaintext attacks (CPAs) in the random oracle, considering the assumption of the computational Diffie-Hellman (CDH) problem.     

多用户环境下无证书认证可搜索加密方案

可搜索加密技术的提出使用户能够将数据加密后存储在云端,而且可以直接对密文数据进行检索。但现有的大部分可搜索加密方案都是单用户对单用户的模式,部分多用户环境下的可搜索加密方案是基于传统公钥密码或基于身份公钥密码系统,因此这类方案存在证书管理和密钥托管问题,且容易遭受内部关键词猜测攻击。该文结合公钥认证加密和代理重加密技术,提出一个高效的多用户环境下无证书认证可搜索加密方案。方案使用代理重加密技术对部分密文进行重加密处理,使得授权用户可以利用关键字生成陷门查询对应密文。在随机预言模型下,证明方案具有抵抗无证书公钥密码环境下两类攻击者的内部关键词猜测攻击的能力,且该方案的计算和通信效率优于同类方案。     

单双钥混合体制的选择密文安全性

该文主要讨论单双钥混合体制的选择密文安全性IND-CCA的定义和相关结论。在对两种不同用途的单双钥混合体制及其安全性的研究之后发现它们的IND-CCA定义中允许敌手访问的预言机不同,我们将其统一为:对只能询问混合体制整体解密机的敌手的安全性,从而统一了混合体制的安全结论,为正确使用混合体制提供了依据。我们提出了一种混合体制:REACT+,并证明了其IND-CCA安全性。     

Public key searchable encryption scheme based on blockchain

Aiming at the trapdoor security problem of the public key encryption scheme,a random number constructing trapdoor and index was introduced to defend against keyword guessing attacks from the server and avoid data leakage caused by server curious behavior.Research on trusted issues of third parties,the blockchain mechanism with a searchable encryption scheme was combined,and smart contracts as trusted third parties for retrieval was used,which could prevent keyword guessing attacks inside the server and ensure retrieval.The correctness of the results,thereby limiting the malicious behavior of the server when sending data.The solution was analyzed for security and the verification scheme satisfies IND-KGA security.Experiments in real data sets,compared with other programs,prove that the program has certain advantages in time overhead.     

Paillier''s Trapdoor Function Hides up to O ( n ) Bits

At EuroCrypt '99 Paillier proposed a new encryption scheme based on higher residuosity classes. The new scheme was proven to be one-way under the assumption that computing N -residuosity classes in Z _N2 ^* is hard. Similarly the scheme can be proven to be semantically secure under a much stronger decisional assumption: given w ∈ Z _N2 ^* it is impossible to decide if w is an N -residue or not. In this paper we examine the bit security of Paillier's scheme. We prove that if computing residuosity classes is hard, then given a random w it is impossible to predict the least significant bit of its class significantly better than at random. This immediately yields a way to obtain semantic security without relying on the decisional assumption (at the cost of several invocations of Paillier's original function). In order to improve efficiency we then turn to the problem of simultaneous security of many bits. We prove that Paillier's scheme hides n-b (up to O(n) ) bits if one assumes that computing the class c of a random w remains hard even when we are told that c<2 ^b . We thoroughly examine the security of this stronger version of the intractability of the class problem. An important theoretical implication of our result is the construction of the first trapdoor function that hides super-logarithmically (up to O(n) ) many bits. We generalize our techniques to provide sufficient conditions for a trapdoor function to have this property.     

抗关键词猜测的授权可搜索加密方案

大多数可搜索加密方案仅支持对单关键词集的搜索,且数据使用者不能迅速对云服务器返回的密文进行有效性判断,同时考虑到云服务器具有较强的计算能力,可能会对关键词进行猜测,且没有对数据使用者的身份进行验证。针对上述问题,该文提出一个对数据使用者身份验证的抗关键词猜测的授权多关键词可搜索加密方案。方案中数据使用者与数据属主给授权服务器进行授权,从而验证数据使用者是否为合法用户;若验证通过,则授权服务器利用授权信息协助数据使用者对云服务器返回的密文进行有效性检测;同时数据使用者利用服务器的公钥和伪关键词对关键词生成陷门搜索凭证,从而保证关键词的不可区分性。同时数据属主在加密时,利用云服务器的公钥、授权服务器的公钥以及数据使用者的公钥,可以防止合谋攻击。最后在随机预言机模型下证明了所提方案的安全性,并通过仿真实验验证,所提方案在多关键词环境下具有较好的效率。