暗号文拡大率が定数である Non-Committing 暗号の構成
雄祐 吉田, 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.
•Sep 1, 2022•0 citations