Efficient Instantiation of LWE-based Public-Key Encryption and Commitment Schemes

Ziqing Wang, Dianhua Tang, Haomiao Yang +1 more

雄祐 吉田, Yusuke Yoshida

Public-key encryption is a cryptographic primitive used for establishing a secure channel between two parties.Depending on the situation and purpose, public-key encryption schemes must satisfy appropriate security requirements.Non-committing encryption (NCE) is a public-key encryption scheme that satisfies a security notion essential to establish a secure channel in adaptively secure multi-party computation (MPC) protocols.Informally, NCE can generate a dummy ciphertext.The dummy ciphertext is indistinguishable from the real ciphertext.Moreover, we can explain the dummy ciphertext as encryption of an arbitrary message by producing consistent randomness.It has been a challenge in the theory of adaptively secure MPC to find an NCE scheme with small ciphertext expansion (required ciphertext length per bit of message).This thesis proposes the first NCE schemes with constant ciphertext expansion in the standard model (i.e., without assuming the randomness used in the cryptosystem can be securely erased or use of the random oracle).We show two instantiations of the scheme, one from the Decisional Diffie-Hellman (DDH) problem and another from the Learning with Errors (LWE) problem.Before constructing the constant ciphertext expansion scheme, we demonstrate the new approach to constructing NCE through the construction of a simpler NCE scheme based on obliviously samplable key-encapsulation mechanism (KEM).The ciphertext expansion of this simpler scheme is O(λ) for security parameter λ.In detail, we use KEM to construct a weak NCE scheme with O(λ) ciphertext expansion.Weak NCE is NCE where its correctness and security requirements are weakened.Then weak NCE is amplified to a full-fledged NCE scheme using an information theoretical primitive called wiretap codes.This amplification increases the cipher text expansion only by a constant factor.The constant ciphertext expansion scheme is obtained by using a primitive called obliviously samplable chameleon encryption, instead of KEM in the above construction.We show instantiations of obliviously samplable chameleon encryption based on the DDH and the LWE problems.

Toi Tomita

Florian Göpfert

Since its proposal by Regev in 2005, the Learning With Errors (LWE) problem was used as the underlying problem for a great variety of schemes. Its applications are many-fold, reaching from basic and highly practical primitives like key exchange, public-key encryption, and signature schemes to very advanced solutions like fully homomorphic encryption, group signatures, and identity based encryption. One of the underlying reasons for this fertility is the flexibility with that LWE can be instantiated. Unfortunately, this comes at a cost: It makes selecting parameters for cryptographic applications complicated. When selecting parameters for a new LWE-based primitive, a researcher has to take the influence of several parameters on the efficiency of the scheme and the runtime of a variety of attacks into consideration. In fact, the missing trust in the concrete hardness of LWE is one of the main problems to overcome to bring LWE-based schemes to practice. This thesis aims at closing the gap between the theoretical knowledge of the hardness of LWE, and the concrete problem of selecting parameters for an LWE-based scheme. To this end, we analyze the existing methods to estimate the hardness of LWE, and introduce new estimation techniques where necessary. Afterwards, we show how to transfer this knowledge into instantiations that are at the same time secure and efficient. We show this process on three examples: - A highly optimized public-key encryption scheme for embedded devices that is based on a variant of Ring-LWE. - A practical signature scheme that served as the foundation of one of the best lattice-based signature schemes based on standard lattices. - An advanced public-key encryption scheme that enjoys the unique property of natural double hardness based on LWE instances similar to those used for fully homomorphic encryption.

Po-Wen Chi, Ming-Hung Wang, Yun‐Hsin Chuang

Richard Lindner, Chris Peikert