Incremental Deterministic Public-Key Encryption

Motivated by applications in large storage systems, we initiate the study of incremental deterministic public-key encryption. Deterministic public-key encryption, introduced by Bellare, Boldyreva, and O’Neill (CRYPTO ’07), provides an alternative to randomized public-key encryption in various scenarios where the latter exhibits inherent drawbacks. A deterministic encryption algorithm, however, cannot satisfy any meaningful notion of security for low-entropy plaintexts distributions, but Bellare et al. demonstrated that a strong notion of security can in fact be realized for relatively high-entropy plaintext distributions. In order to achieve a meaningful level of security, a deterministic encryption algorithm should be typically used for encrypting rather long plaintexts for ensuring a sufficient amount of entropy. This requirement may be at odds with efficiency constraints, such as communication complexity and computation complexity in the presence of small updates. Thus, a highly desirable property of deterministic encryption algorithms is incrementality: Small changes in the plaintext translate into small changes in the corresponding ciphertext. We present a framework for modeling the incrementality of deterministic public-key encryption. Our framework extends the study of the incrementality of cryptography primitives initiated by Bellare, Goldreich and Goldwasser (CRYPTO ’94). Within our framework, we propose two schemes, which we prove to enjoy an optimal tradeoff between their security and incrementality up to lower-order factors. Our first scheme is a generic method which can be based on any deterministic public-key encryption scheme, and, in particular, can be instantiated with any semantically secure (randomized) public-key encryption scheme in the random-oracle model. Our second scheme is based on the Decisional Diffie–Hellman assumption in the standard model. The approach underpinning our schemes is inspired by the fundamental “sample-then-extract” technique due to Nisan and Zuckerman (JCSS ’96) and refined by Vadhan (J. Cryptology ’04), and by the closely related notion of “locally computable extractors” due to Vadhan. Most notably, whereas Vadhan used such extractors to construct private-key encryption schemes in the bounded-storage model, we show that techniques along these lines can also be used to construct incremental public-key encryption schemes.     

Better Security for Deterministic Public-Key Encryption: The Auxiliary-Input Setting

Deterministic public-key encryption, introduced by Bellare, Boldyreva, and O’Neill (CRYPTO ’07), provides an alternative to randomized public-key encryption in various scenarios where the latter exhibits inherent drawbacks. A deterministic encryption algorithm, however, cannot satisfy any meaningful notion of security when the plaintext is distributed over a small set. Bellare et al. addressed this difficulty by requiring semantic security to hold only when the plaintext has high min-entropy from the adversary’s point of view. In many applications, however, an adversary may obtain auxiliary information that is related to the plaintext. Specifically, when deterministic encryption is used as a building block of a larger system, it is rather likely that plaintexts do not have high min-entropy from the adversary’s point of view. In such cases, the framework of Bellare et al. might fall short from providing robust security guarantees. We formalize a framework for studying the security of deterministic public-key encryption schemes with respect to auxiliary inputs. Given the trivial requirement that the plaintext should not be efficiently recoverable from the auxiliary input, we focus on hard-to-invert auxiliary inputs. Within this framework, we propose two schemes: the first is based on the d-linear assumption for any d≥1 (including, in particular, the decisional Diffie–Hellman assumption), and the second is based on a rather general class of subgroup indistinguishability assumptions (including, in particular, the quadratic residuosity assumption and Paillier’s composite residuosity assumption). Our schemes are secure with respect to any auxiliary input that is subexponentially hard to invert (assuming the standard hardness of the underlying computational assumptions). In addition, our first scheme is secure even in the multi-user setting where related plaintexts may be encrypted under multiple public keys. Constructing a scheme that is secure in the multi-user setting (even without considering auxiliary inputs) was identified by Bellare et al. as an important open problem.     

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.)     

Public-Key Encryption Based on Chebyshev Polynomials

We propose public-key encryption algorithms based on Chebyshev polynomials, which are secure, practical, and can be used for both encryption and digital signature. Software implementation and properties of the algorithms are discussed in detail. We show that our ElGamal-like and RSA-like algorithms (when Chebyshev polynomials are employed) are as secure as the original ElGamal and RSA algorithms.     

密钥与明文相关联的混沌图像加密算法

A novel image encryption scheme based on the modified skew tent map was proposed in this paper. In the key generating procedure, the algorithm generates a plaintext-dependent secret keys set. In the encryption process , the diffusion operation with cipher output feedback is introduced. Thus , cipher-image is sensitive to both initial keys and plaintext through only one round diffusion operation. The key space is large. As a result, the algorithm can effectively resist differential attacks, statistical attacks, brute-force attacks , known plaintext and chosen plaintext attacks . Performance test and security analysis demonstrates that this algorithm is eficient and reliable, with high potential to be adopted for secure communications.     

MSK-PK: A Public-Key Encryption Cryptosystem with Multiple Secret-Keys

By allowing intermediate nodes to combine multiple packets before forwarding them, the concept of network coding in multi-cast networks can provide maximum possible information flow. However, this also means traditional encryption methods are less applicable,since the different public-keys of receivers imply different ciphertexts which cannot be easily combined by network coding. While network coding itself may provide confidentiality, its effectiveness heavily depends on the underlying network ...     

基于纠错编码的多变量公钥加密方案

Advances in quantum computers pose potential threats to the currently used public key cryptographic algorithms such as RSA and ECC. As a promising candidate against attackers equipped with quantum computational power, Multivariate Public Key Cryptosystems (MPKCs) has attracted increasing attention in recently years. Unfortunately, the existing MPKCs can only be used as multivariate signature schemes, and the way to construct an efficient MPKC enabling secure encryption remains unknown. By employing the basic MQ trapdoors, this paper proposes a novel multivariate encryption scheme by combining MPKCs and code based public key encryption schemes. Our new construction gives a positive response to the challenges in multivariate public key cryptography. Thorough analysis shows that our scheme is secure and efficient, and its private key size is about 10 times smaller than that of McEliece type cryptosystems.     

抵御已知/选择明文攻击的混沌图像加密算法

论文在对现有一类典型图像混沌加密算法的分析基础上,提出了一种改进的图像混沌加密算法。该算法引入小波变换,可以有效地克服一些混沌加密算法不能抵御已知/选择明文攻击的缺陷。     

Deterministic Encryption with the Thorp Shuffle

We analyze the security of the Thorp shuffle, or, equivalently, a maximally unbalanced Feistel network. Roughly said, the Thorp shuffle on N cards mixes any \(N^{1-1/r}\) of them in \(O(r\lg N)\) steps. Correspondingly, making O(r) passes of maximally unbalanced Feistel over an n-bit string ensures CCA security to \(2^{n(1-1/r)}\) queries. Our results, which employ Markov chain techniques, particularly couplings, help to justify a practical, although still relatively inefficient, blockcipher-based scheme for deterministically enciphering credit card numbers and the like.     

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.     

A Simpler Construction of CCA2-Secure Public-Key Encryption under General Assumptions

In this paper we present a simpler construction of a public-key encryption scheme that achieves adaptive chosen ciphertext security (CCA2), assuming the existence of trapdoor permutations. We build on previous works of Sahai and De Santis et al. and construct a scheme that we believe is the easiest to understand to date. In particular, it is only slightly more involved than the Naor--Yung encryption scheme that is secure against passive chosen-ciphertext attacks (CCA1). We stress that the focus of this paper is on simplicity only.     

F-L公钥密码体制

本文利用三阶Fibonacci-Lucas序列理论建立了一种新的公钥密码体制──F－L公钥密码体制,并对该体制与LUC公朝密码体制做了比较和分析,说明该体制是比LUC更强的公钥体制,最后给出两种F－L数字签名体制。     

The Cubic Public-Key Transformation

This note proposes the use of the cubic transformation for public-key applications and random event and number generation, in a manner akin to the Rabin cipher. Transformations modulo a prime p or a composite n = pq, where p and q are primes, are so used that each transformed value has only three roots. Such a transformation, together with additional tag information, makes it possible to uniquely invert each transformed value. The effectiveness of the method as a random number generator (used in a variant with nine roots) comes from the fact that the cryptanalyst must contend with a ninefold branching at each step.     

一种适用于多种公钥密码算法的模运算处理器

文章设计了一种能够实现多种公钥密码算法（如RSA、ECC、DSA等）的协处理器。通过分析几种常用的公钥密码算法，归纳了一组最常用的基本模运算指令。基于基本指令，设计优化了处理器硬件结构。用微代码循环调用执行这些基本指令，实现其他各种模运算指令。基于这些模运算指令，处理器可实现多种公钥密码算法的运算。该处理器支持从106位到2048位多种长度的模运算。采用流水线结构设计，处理速度较快。处理器占用芯片面积小，核心电路等效门数约为26000门，适用于智能卡等对芯片面积有严格限制的应用。     

椭圆曲线公钥制密码系统的软件控制设计

本文采用兼容PIC16C72的8位嵌入式微处理器做控制芯片，完成了一种仿ElGamal的数字签名算法。并且与设计的点乘硬件芯片一起构成了一种椭圆曲线公钥制密码系统。该系统工作时钟为20MHz，一秒钟内可以完成10次签名，签名速度与国外见于报道的同类产品相当。     

Fast Multi-precision Multiplication for Public-Key Cryptography on Embedded Microprocessors

Multi-precision multiplication is one of the most fundamental operations on microprocessors to allow public-key cryptography such as RSA and elliptic curve cryptography (ECC). In this paper, we present a novel multiplication technique that increases the performance of multiplication by sophisticated caching of operands. Our method significantly reduces the number of needed load instructions which is usually one of the most expensive operations on modern processors. We evaluate our new technique on an 8-bit ATmega128 and a 32-bit ARM7TDMI microcontroller and compare the results with existing solutions. For the ATmega128, our implementation needs only 2395 clock cycles for a 160-bit multiplication. The number of required load instructions is reduced from 167 (needed for the best known hybrid multiplication) to only 80. On the ARM7TDMI, our implementation needs only 281 clock cycles as opposed to 357. For both platforms, the proposed technique outperforms related work by a factor of about 10–23%. We also show that the method scales very well even for larger Integer sizes (required for RSA) and limited register sets. It fully complies with existing multiply–accumulate instructions that are integrated in most of the available processors.     

一种抗共谋的公钥叛逆者追踪方案

利用非奇次线形方程组解的结构,提出了一种新的公钥叛逆者追踪方案.与现有方案相比较,本方案具有完全的黑盒子追踪性和抗共谋能力,即一定数量的叛逆者通过共谋构造一个解密钥时,其成功的概率小于预先设置的概率门限值.此外,本方案没有使用陷门离散对数.     

高密度背包型公钥密码体制的设计

该文提出了一类新的易解背包问题,基于此问题构造了一个新的加法背包型公钥密码体制。该公钥密码体制具有较高的背包密度,因此可以抵抗低密度子集和攻击。对该密码体制的其它的攻击方法进行了分析。     

可公开验证的ElGamal／RSA加密

可公开验证加密允许任何实体验证加密的消息和先前承诺的秘密一样,但不会泄漏明文的任何信息。这在公平交换、防欺骗的秘密分享和安全多方计算中有重要应用。该文分别给出可公开验证的ElGamal加密和RSA加密方案。其中前者是Stalderr方案的改进,改进后的方案是语义安全的而Stalder方案达不到语义安全性。同时将该方案推广到了多个接受者的情形,最后给出了高效的可公开验证RSA加密方案。