Affiliation: Institute of Software, Chinese Academy of Sciences
Tweaking the Asymmetry of Asymmetric-Key Cryptography on Lattices: KEMs and Signatures of Smaller Sizes 📺
Currently, lattice-based cryptosystems are less efficient than their number-theoretic counterparts (based on RSA, discrete logarithm, etc.) in terms of key and ciphertext (signature) sizes. For adequate security the former typically needs thousands of bytes while in contrast the latter only requires at most hundreds of bytes. This significant difference has become one of the main concerns in replacing currently deployed public-key cryptosystems with lattice-based ones. Observing the inherent asymmetries in existing lattice-based cryptosystems, we propose asymmetric variants of the (module-)LWE and (module-)SIS assumptions, which yield further size-optimized KEM and signature schemes than those from standard counterparts. Following the framework of Lindner and Peikert (CT-RSA 2011) and the Crystals-Kyber proposal (EuroS&P 2018), we propose an IND-CCA secure KEM scheme from the hardness of the asymmetric module-LWE (AMLWE), whose asymmetry is fully exploited to obtain shorter public keys and ciphertexts. To target at a 128-bit quantum security, the public key (resp., ciphertext) of our KEM only has 896 bytes (resp., 992 bytes). Our signature scheme bears most resemblance to and improves upon the Crystals-Dilithium scheme (ToCHES 2018). By making full use of the underlying asymmetric module-LWE and module-SIS assumptions and carefully selecting the parameters, we construct an SUF-CMA secure signature scheme with shorter public keys and signatures. For a 128-bit quantum security, the public key (resp., signature) of our signature scheme only has 1312 bytes (resp., 2445 bytes). We adapt the best known attacks and their variants to our AMLWE and AMSIS problems and conduct a comprehensive and thorough analysis of several parameter choices (aiming at different security strengths) and their impacts on the sizes, security and error probability of lattice-based cryptosystems. Our analysis demonstrates that AMLWE and AMSIS problems admit more flexible and size-efficient choices of parameters than the respective standard versions.
Key Encapsulation Mechanism with Explicit Rejection in the Quantum Random Oracle Model
The recent post-quantum cryptography standardization project launched by NIST increased the interest in generic key encapsulation mechanism (KEM) constructions in the quantum random oracle (QROM). Based on a OW-CPA-secure public-key encryption (PKE), Hofheinz, Hövelmanns and Kiltz (TCC 2017) first presented two generic constructions of an IND-CCA-secure KEM with quartic security loss in the QROM, one with implicit rejection (a pseudorandom key is return for an invalid ciphertext) and the other with explicit rejection (an abort symbol is returned for an invalid ciphertext). Both are widely used in the NIST Round-1 KEM submissions and the ones with explicit rejection account for 40%. Recently, the security reductions have been improved to quadratic loss under a standard assumption, and be tight under a nonstandard assumption by Jiang et al. (Crypto 2018) and Saito, Xagawa and Yamakawa (Eurocrypt 2018). However, these improvements only apply to the KEM submissions with implicit rejection and the techniques do not seem to carry over to KEMs with explicit rejection.In this paper, we provide three generic constructions of an IND-CCA-secure KEM with explicit rejection, under the same assumptions and with the same tightness in the security reductions as the aforementioned KEM constructions with implicit rejection (Crypto 2018, Eurocrypt 2018). Specifically, we develop a novel approach to verify the validity of a ciphertext in the QROM and use it to extend the proof techniques for KEM constructions with implicit rejection (Crypto 2018, Eurocrypt 2018) to our KEM constructions with explicit rejection. Moreover, using an improved version of one-way to hiding lemma by Ambainis, Hamburg and Unruh (ePrint 2018/904), for two of our constructions, we present tighter reductions to the standard IND-CPA assumption. Our results directly apply to 9 KEM submissions with explicit rejection, and provide tighter reductions than previously known (TCC 2017).
IND-CCA-Secure Key Encapsulation Mechanism in the Quantum Random Oracle Model, Revisited 📺
With the gradual progress of NIST’s post-quantum cryptography standardization, the Round-1 KEM proposals have been posted for public to discuss and evaluate. Among the IND-CCA-secure KEM constructions, mostly, an IND-CPA-secure (or OW-CPA-secure) public-key encryption (PKE) scheme is first introduced, then some generic transformations are applied to it. All these generic transformations are constructed in the random oracle model (ROM). To fully assess the post-quantum security, security analysis in the quantum random oracle model (QROM) is preferred. However, current works either lacked a QROM security proof or just followed Targhi and Unruh’s proof technique (TCC-B 2016) and modified the original transformations by adding an additional hash to the ciphertext to achieve the QROM security.In this paper, by using a novel proof technique, we present QROM security reductions for two widely used generic transformations without suffering any ciphertext overhead. Meanwhile, the security bounds are much tighter than the ones derived by utilizing Targhi and Unruh’s proof technique. Thus, our QROM security proofs not only provide a solid post-quantum security guarantee for NIST Round-1 KEM schemes, but also simplify the constructions and reduce the ciphertext sizes. We also provide QROM security reductions for Hofheinz-Hövelmanns-Kiltz modular transformations (TCC 2017), which can help to obtain a variety of combined transformations with different requirements and properties.
On the Hardness of the Computational Ring-LWR Problem and Its Applications
In this paper, we propose a new assumption, the Computational Learning With Rounding over rings, which is inspired by the computational Diffie-Hellman problem. Assuming the hardness of R-LWE, we prove this problem is hard when the secret is small, uniform and invertible. From a theoretical point of view, we give examples of a key exchange scheme and a public key encryption scheme, and prove the worst-case hardness for both schemes with the help of a random oracle. Our result improves both speed, as a result of not requiring Gaussian secret or noise, and size, as a result of rounding. In practice, our result suggests that decisional R-LWR based schemes, such as Saber, Round2 and Lizard, which are among the most efficient solutions to the NIST post-quantum cryptography competition, stem from a provable secure design. There are no hardness results on the decisional R-LWR with polynomial modulus prior to this work, to the best of our knowledge.
Key Replacement Attack on a Certificateless Signature Scheme
Yap, Heng and Goi propose an efficient certificateless signature scheme based on the intractability of the computational Diffie-Hellman problem, and prove that the scheme is secure in the random oracle model. This paper shows that their certificateless signature scheme is vulnerable to key replacement attacks, where an adversary who replaces the public key of a signer can forge valid signatures on any messages for that signer without knowing the signer's private key.
On the Security of a Certificateless Public-Key Encryption
Certificateless public-key cryptosystem is a recently proposed attractive paradigm using public key cryptosystem, which avoids the key escrow inherent in identity-based public-key cryptosystems, and does not need certificates to generate trust in public keys. In 2005, Al-Riyami and Paterson proposed a new certificateless public-key encryption scheme and proved its security in the random oracle model. This paper shows that their scheme is vulnerable to adaptive chosen ciphertext attacks, and presents a countermeasure to overcome such a security flaw.
ID-Based Proxy Signature Using Bilinear Pairings
Identity-based (ID-based) public key cryptosystem can be a good alternative for certificate-based public key setting, especially when efficient key management and moderate security are required. A proxy signature scheme permits an entity to delegate its signing rights to another entity. But to date, no ID-based proxy signature schemes with provable security have been proposed. In this paper, we formalize a notion of security for ID-based proxy signature schemes and propose a scheme based on the bilinear pairings. We show that the security of our scheme is tightly related to the computational Diffie-Hellman assumption in the random oracle model.
Identity Based Threshold Proxy Signature
Identity-based (ID-based) public key cryptosystem can be a good alternative for certificate-based public key setting, especially when efficient key management and moderate security are required. In a $(t,n)$ threshold proxy signature scheme, the original signer delegates the power of signing messages to a designated proxy group of $n$ members. Any $t$ or more proxy signers of the group can cooperatively issue a proxy signature on behalf of the original signer, but $t-1$ or less proxy signers cannot. In this paper, we present an ID-based threshold proxy signature scheme using bilinear pairings. We show the scheme satisfies all security requirements in the random oracle model. To the best of authors' knowledge, our scheme is the first ID-based threshold proxy signature scheme.
Efficient and Optimistic Fair Exchanges Based on Standard RSA with Provable Security
In this paper, we introduce a new and natural paradigm for fair exchange protocols, called verifiable probabilistic signature scheme. A security model with precise and formal definitions is presented, and an RSA-based efficient and provably secure verifiable probabilistic signature scheme is proposed. Our scheme works well with standard RSA signature schemes, and the proposed optimistic fair exchange protocol is much concise and efficient, and suitable for practical applications.
- Yu Chen (2)
- Long Chen (3)
- Özgür Dagdelen (1)
- Jintai Ding (2)
- Shuqin Fan (1)
- Dengguo Feng (6)
- Yanfei Guo (1)
- Haodong Jiang (2)
- Zhi Ma (2)
- Phong Q. Nguyen (2)
- Yu Qin (1)
- Michael Snook (2)
- Hong Wang (1)
- Xueqing Wang (1)
- Jing XU (2)
- Bo Yang (1)
- Kang Yang (2)
- Yu Yu (1)
- Jiang Zhang (7)
- Zongyang Zhang (1)
- Zhenfei Zhang (1)
- YongBin ZHOU (1)