Two Papers of the CS Department Accepted by CRYPTO 2023

Released Time: 2023-06-15

Recently, CRYPTO 2023International Cryptology Conference, top conference in the field of cryptography, released its acceptance results. Two papers from Prof. Liu Shenglis team and Prof. Yu Yus team on post-quantum public-key encryption and post-quantum digital signature got accepted. CRYPTO is one of the three top conferences held by International Association for Cryptologic Research (IACR). It publishes influential results on various areas in cryptography such as symmetric encryption, public key encryption, digital signature, security protocol, random number generation, and cryptanalysis.

 

Paper by Liu Shenglis team is titled “Almost Tight Multi-User Security under Adaptive Corruptions from LWE in the Standard Model. They construct the first digital signature (SIG) and public-key encryption (PKE) schemes with almost tight multi-user security under adaptive corruptions based on the learning-with-errors (LWE) assumption in the standard model. Their PKE scheme achieves almost tight IND-CCA security and SIG scheme achieves almost tight strong EUF-CMA security, both in the multi-user setting with adaptive corruptions. The security loss is quadratic in the security parameter, and independent of the number of users, signatures or ciphertexts. Previously, such schemes were only known to exist under number-theoretic assumptions or in classical random oracle model, thus vulnerable to quantum adversaries. To obtain schemes from LWE, they propose new frameworks for constructing SIG and PKE with a core technical tool named probabilistic quasi-adaptive hash proof system (pr-QA-HPS). They formalize a new property called evaluation indistinguishability. The evaluation indistinguishability, as well as other nice properties resulting from the probabilistic features of pr-QA-HPS, are crucial for the multi-user security proof of our frameworks under adaptive corruptions. As for instantiations, they construct pr-QA-HPS from the LWE assumption and prove its properties with almost tight reductions, which admit almost tightly secure LWE-based SIG and PKE schemes under our frameworks. Along the way, they also provide new almost-tight reductions from LWE to multi-secret LWE, which may be of independent interest. The integration of SIG and PKE results in an optimized SignCryption (SC) scheme. As by products, SIG and SC naturally derive the first strongly secure latticed-based message authentication code (MAC) and the first latticed-based authenticated encryption (AE) schemes achieving tight multi-user security with adaptive corruptions in the standard model. The first author is Assistant Prof. Han Shuai from the School of Cyber Science and Engineering, the second and corresponding author is Prof. Liu Shengli from the Department of Computer Science and Engineering. Prof. Gu Dawu and Assistant Prof. Wang Dongzhe also contributed.



图1.jpg



Paper by Yu Yus team is titled "Revisiting the Constant-sum Winternitz One-time Signature with Applications to SPHINCS+ and XMSS."  This paper investigates the optimality of one-time signatures in terms of encoding efficiency. It demonstrates that the WOTS+ one-time signature, when using the constant-sum encoding scheme (proposed by Bos and Chaum, Crypto 1992), is not only optimal in terms of size within the Winternitz one-time signature framework but also size-optimal among all tree-based one-time signature designs. Additionally, the work points out a security flaw in a DAG-based one-time signature design proven to be optimal in terms of size at ASIACRYPT 1996. This makes the constant-sum WOTS+ the most efficient one-time signature scheme currently available. Furthermore, the paper integrates the constant-sum WOTS+ into standard signature algorithms such as SPHINCS+ (NIST PQC standard) and XMSS, and evaluates their corresponding performance. The experiments show improvements in both signature time and signature size with the enhanced scheme. The first and second authors of the paper are doctoral students Kaiyi Zhang and Hongrui Cui respectively under the guidance of Yu Yu, who is the corresponding author of the paper.



图2.jpg



About CRYPTO

CRYPTO is one of the three top conferences held by International Association for Cryptologic Research (IACR). It is held annually since 1981. The conference publishes influential results on various areas in cryptography such as symmetric encryption, public key encryption, digital signature, security protocol, random number generation, and cryptanalysis. Each year top researchers and experts in cryptography gather together at the conference to share new thoughts, promoting theoretical innovation, research cooperation and technological progress in the area.



Contact webmaster@cs.sjtu.edu.cn

Copyright @ 2013 SJTU Computer Science & Engineering All Rights Reserved