論文 / 著書情報
Article / Book Information
題目(和文)

暗号文拡大率が定数である Non-Committing 暗号の構成

Title(English)

Constructions for Non-Committing Encryption with Constant Ciphertext
Expansion

著者(和文)

吉田雄祐

Author(English)

Yusuke Yoshida

出典(和文)

学位:博士(理学),学位授与機関:東京工業大学,
報告番号:甲第12169号,
授与年月日:2022年9月22日,
学位の種別:課程博士,
審査員:田中 圭介,伊東 利哉,尾形 わかは,鹿島 亮,安永 憲司

Citation(English)

Degree:Doctor (Science),
Conferring organization: Tokyo Institute of Technology,
Report number:甲第12169号,
Conferred date:2022/9/22,
Degree Type:Course doctor,
Examiner:,,,,

学位種別(和文)

博士論文

Type(English)

Doctoral Thesis

Powered by T2R2 (Tokyo Institute Research Repository)

Constructions for Non-Committing Encryption
with Constant Ciphertext Expansion
by
Yusuke YOSHIDASupervisor: Keisuke TANAKA
School of Computing
Tokyo Institute of Technology
August 25, 2022

Abstract
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 satisﬁes asecurity 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 ﬁnd
an NCE scheme with small ciphertext expansion (required ciphertext length per bit ofmessage). This thesis proposes the ﬁrst 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 thescheme, one from the Decisional Diﬃe-Hellman (DDH) problem and another from theLearning 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 ofthis simpler scheme is O(λ) for security parameter λ. In detail, we use KEM to constructa weak NCE scheme with O(λ) ciphertext expansion. Weak NCE is NCE where its
correctness and security requirements are weakened. Then weak NCE is ampliﬁed to afull-ﬂedged NCE scheme using an information theoretical primitive called wiretap codes.
This ampliﬁcation 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.

–i–Note on This Thesis
This thesis reorganizes two papers those construct non-committing encryption schemes[YKT19,
YKXT20].
Historically, the ﬁrst paper introduced obliviously samplable chameleon encryption to
construct an NCE scheme with O(log λ) ciphertext expansion. This scheme is instantiatedbased on the DDH problem.
The second paper improved the ﬁrst paper by introducing the notion of weak NCE
and the use of wiretap codes. This work added instantiation based on the LWE problem,
which turned out to have a smaller public-key expansion than the DDH-based scheme.
Eventually, we achieved to construct NCE schemes with a constant ciphertext expansion.
This thesis excludes several obsolete parts in the above papers. For example, we do notdescribe the construction of O(log λ) ciphertext expansion scheme because the constantciphertext expansion scheme is properly improved. Instead, we describe the constructionof O(λ) ciphertext expansion scheme, that is constructed from obliviously samplable KEM.
This scheme is not very well in terms of ciphertext expansion, still, it contains the essenceof the proposed NCE construction. We also update several security deﬁnitions and related
proofs of NCE and its building blocks such as chameleon encryption. Especially, we start
to focus on the randomness used by the algorithms including the simulators which appear
only in the security deﬁnition. Security notions of the building blocks are deﬁned similarly
to the deﬁnition of NCE. We hope these deﬁnitions give a new viewpoint to understanding
the nature of NCE.

– ii –

Acknowledgements
本学位論文は東京工業大学 情報理工学院 数理・計算科学系 田中圭介研究室に在籍している間に行なった研究をまとめたものです．
初めに，指導教員である田中圭介教授に深く感謝します．先生の研究室にめぐり合う
ことが無ければこの研究が始まることもなく，先生の温かい指導と支援が無ければ満足してこの研究を完了させることもなかったでしょう．
次に，本論文の審査員を引き受けてくださった伊東利哉教授，尾形わかは教授，鹿島亮准教授，安永憲司准教授に感謝いたします．発表に対するコメントを通して，本研究に対する理解をさらに深めることができました．
本論文の研究に際し，多くの助言を頂きました北川冬航氏と草川恵太氏には特段の感謝を申し上げます．彼らとの議論を通して，私だけでは見通せなかったであろう深い知見を得ることができました．とりわけ北川氏にいただいた励ましと勇気は私の大きな支えでありました．
田中研究室のメンバー，元メンバー，関係者の方々を中心に，西 8 号館 11 階で共に楽しい時間を過ごした皆様に感謝します．彼らと過ごした時間を通して，私だけでは見渡せなかったであろう広い知識と経験に触れることができました．特に，原啓祐氏と手塚真徹
氏とは修士，博士課程を通しての多くのかけがえの無い経験を共有しました．
最後にこれまで理解と支援，応援をし続けてくれた家族に感謝します．
なお本研究は JSPS 科研費 JP19J22363 の助成を受けて行いました.

– iii –

Contents
1 Introduction
1.1 Backgrounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Existing Non-Committing Encryption Schemes . . . . . . . . . . . . . . . .
1.3 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 This Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
1
3
5
5
7

2 Basics and Deﬁnitions of NCE
2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Public-Key Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Non-Committing Encryption . . . . . . . . . . . . . . . . . . . . . . . . . .

8
8
9
11

3 NCE with O(λ) Ciphertext-Expansion
14
3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.1.1 Starting Point: Beaver’s Protocol . . . . . . . . . . . . . . . . . . . 14
3.1.2 Extension to Two-Round Weak NCE Scheme . . . . . . . . . . . . 16
3.1.3 Compress Ciphertext . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1.4 Related Works on Ampliﬁcation for Public-Key Encryption . . . . . 18
3.2 Wiretap Channel and Ampliﬁcation . . . . . . . . . . . . . . . . . . . . . . 19
3.2.1 Channel Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.2 Wiretap Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.3 Instantiation of Wiretap Codes . . . . . . . . . . . . . . . . . . . . 22
3.3 Weak Non-Committing Encryption . . . . . . . . . . . . . . . . . . . . . . 25
3.3.1 Deﬁnition of Weak Non-Committing Encryption . . . . . . . . . . . 25
3.3.2 Construction from Key Encapsulation Mechanism . . . . . . . . . . 26
3.4 Full-Fledged NCE from Weak NCE . . . . . . . . . . . . . . . . . . . . . . 31
4 NCE with Constant Ciphertext-Expansion
36
4.1 Idea Towards Constant Ciphertext-Expansion . . . . . . . . . . . . . . . . 36
4.1.1 Abstraction by Chameleon Encryption . . . . . . . . . . . . . . . . 38
4.2 Obliviously Samplable Chameleon Encryption . . . . . . . . . . . . . . . . 39
4.3 Instantiation based on the DDH Problem . . . . . . . . . . . . . . . . . . . 42iv

Contents

4.4

4.5
4.6

4.3.1 Preliminaries on the Decisional Diﬃe-Hellman Problem . . . . . . .
4.3.2 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Instantiation based on Lattices . . . . . . . . . . . . . . . . . . . . . . . .
4.4.1 Preliminaries on Lattices . . . . . . . . . . . . . . . . . . . . . . . .
4.4.2 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Construction of Weak NCE . . . . . . . . . . . . . . . . . . . . . . . . . .
Size and Expansion of the NCE Schemes . . . . . . . . . . . . . . . . . . .

5 Conclusion

42
44
47
48
49
53
58
60

–v–

Chapter 1
Introduction
Public-key encryption, the most fundamental cryptographic primitive for realizing secure
message transmission, has a number of security notions, which are required depending on
the situations in which it is used. When it is used in adaptively secure multi-party computation, we need adaptively secure public-key encryption, also known as non-committing
encryption.

1.1

Backgrounds

In secure multi-party computation (MPC) protocols, a group of parties can compute
some function of their private inputs by communicating with each other. The security
requirement of MPC protocols is that through the protocol, each party (possibly, someof them collude) cannot obtain information on the other party’s input, except what is
trivially extracted from the output of the function. To model this security requirement,
we consider an algorithm called adversary. The adversary corrupts some parties andtries to extract some non-trivial information about the inputs of non-corrupted parties.
Informally the protocol is secure if we can simulate what the adversary can see during
the protocol (in the case of public-key encryption, all the public keys and ciphertexts,
and secret keys and randomness used by the corrupted parties) only from what is triviallyclear to the adversary in an idealized world (i.e. input of corrupted parties).
Depending on when the adversary determines to corrupt parties, two types of adversarial settings, called static and adaptive, have been considered for MPC. In the static
setting, an adversary is required to declare which parties it corrupts before the protocol
starts. On the other hand, in the adaptive setting, an adversary can choose which parties
to corrupt on the ﬂy, and thus the corruption pattern can depend on the messages exchanged during the protocol. Security guarantee in the adaptive setting is more desirable
than that in the static setting since the former naturally captures adversarial behaviors
in the real world while the latter is somewhat artiﬁcial.
We premise there are authenticated channels between each pair of parties. Furthermore, if the provided channels are private, information-theoretically secure MPC protocols
11.1. Backgrounds
such as those proposed by Ben-Or et al. [BGW88] and Chaum et al. [CCD88] are secureagainst adaptive adversaries. On the other hand, for the MPC protocols relying on complexity assumption such as the one proposed by Goldreich et al. [GMW87], the security
proof fails against an adaptive adversary as observed by Damgård and Nielsen [DN00].
In order to use adaptively secure protocols without private channels are provided, we
have to establish private channels by using a public-key encryption scheme. For this aim,
non-committing encryption (NCE) was introduced by Canetti et al. [CFGN96]. Informally, an encryption scheme is said to be non-committing if it can generate a dummy
ciphertext that is indistinguishable from real ones but can later be opened to any message
by producing a secret key and encryption randomness that “explain” the ciphertext as an
encryption of the message.
At ﬁrst glance, it is weird to consider revealing a secret key to the adversary in a security
deﬁnition. But due to this property, NCE can be used to establish secure communicationon the adaptively secure MPC. This is because when the adaptive adversary corrupts
the sender and the receiver, it can obtain the secret key and encryption randomness. To
simulate such corruption, we must simulate the secret key and the randomness that is
consistent with the simulated public key and ciphertext, this is where the property of
NCE works. To summarize brieﬂy, the security of NCE is not only for the conﬁdentialityof the messages between non-corrupted parties but also for the security of the entire MPC
protocol, although messages corrupted by the adversary are revealed.
Canetti et al. showed that the information-theoretically secure MPC protocols are still
adaptively secure if private channels are replaced by NCE over insecure channels (assumed
they are authenticated). Canetti, Lindell, Ostrovsky, and Sahai [CLOS02] also showed aslightly augmented version of NCE is useful to achieve adaptive security in the universallycomposable (UC) setting.
The ability to open a dummy ciphertext to any message is generally achieved at theprice of eﬃciency. This is in contrast to the ordinary public-key encryption for which we
can easily obtain schemes the size of whose ciphertext is n + poly(λ) through the hybrid
encryption methodology, where n is the length of an encrypted message and λ is the security parameter. Thus, many previous works have focused on constructing eﬃcient NCE
schemes. Especially, they tried to improve ciphertext expansion which is the asymptotic
ratio of ciphertext length and message length since ciphertext length dominates the online
communication complexity of the protocol.
Indeed, a textbook on secure multiparty computation raised this as an open problem:“Finding a non-committing encryption scheme that can encrypt κ bits using
the order of κ bits of ciphertext is an important open problem in the theoryof adaptive secure multiparty computation.”— Cramer et al. , Secure Multiparty Computation and Secret Sharing [CDN15]–2–

1.2. Existing Non-Committing Encryption Schemes

1.2

Existing Non-Committing Encryption Schemes

Canetti et al. [CFGN96] constructed the ﬁrst NCE scheme, based on common-domain
trapdoor permutations which can be instantiated from the computational Diﬃe-Hellman(CDH) or RSA problem. Ciphertext expansion of their scheme is O(λ2 ).
Choi, Dachman-Soled, Malkin, and Wee [CDMW09] constructed an NCE scheme withciphertext expansion O(λ) from trapdoor simulatable PKE. Their construction can beinstantiated under many computational problems including factoring problem, since many
existing (ordinary) PKE schemes satisfy trapdoor simulatability.
The ﬁrst NCE scheme with sub-linear ciphertext expansion was proposed by Hemenway, Ostrovsky, and Rosen [HOR15]. They proposed an NCE scheme with ciphertext
expansion O(log n) for n-bit messages based on the Φ-hiding problem, which we can easily modify its ciphertext expansion to O(log λ) by dividing long messages to λ-bit blocks.
Hemenway, Ostrovsky, Richelson, and Rosen [HORR16] also showed constructions of NCE
with ciphertext expansion poly(log λ) from the learning with errors (LWE) and Ring-LWE
problems.
Canetti, Poburinnaya, and Raykova [CPR17] studied the construction of NCE in thecommon reference strings (CRS) model. They achieved optimal ciphertext expansion 1 +o (1) assuming the existence of indistinguishability obfuscation (iO) and one-way function.
Yoshida, Kitagawa, and Tanaka [YKT19] constructed an NCE scheme with ciphertext
expansion O(log λ) from a primitive called chameleon encryption (CE), which additionallysatisﬁes oblivious samplability. They showed an instantiation of obliviously samplable CE
based on the decisional Diﬃe-Hellman (DDH) problem.
Yoshida, Kitagawa, Xagawa, and Tanaka [YKXT20] improved their previous scheme
and constructed NCE scheme with constant ciphertext expansion from obliviously samplable chameleon encryption. They also showed another instantiation of obliviously samplable chameleon encryption based on the LWE problem, which reduces public-key size ofthe constructed NCE scheme.
Concurrently to Yoshida et al. [YKXT20], Brakerski, Branco, Döttling, Garg, andMalavolta [BBD+ 20] proposed NCE schemes with constant ciphertext expansion from the
LWE and DDH problems. Note that a previous version of their work claimed a constant ciphertext-expansion NCE from the quadratic residuosity (QR) assumption. This
result was retracted due to a bug in the QR construction. They introduced a primitive
called Packed Encryption with Partial Equivocality (PEPE) as a building block to construct their NCE scheme. Their construction basically follows the framework by Hemenway et al. [HORR16], whose origin further backs to Choi et al. [CDMW09].
We show the list of existing NCE schemes in Table 1.1.
Note on NCE Schemes on Composite Order Group. When constructing an NCE
scheme using a composite number N = pq, we should be careful in how keys are generated. In the key generation algorithm, if the composite number N = pq is sampled–3–

1.2. Existing Non-Committing Encryption Schemes
Reference
Canetti et al. [CFGN96]

CT Expansion
O λ2

PK Expansion
O λ2Assumption

Choi et al. [CDMW09]

O(λ)

O(λ)

Hemenway et al. [HOR15]

O(log λ)λ · poly(log λ)Φ-hiding

Hemenway et al. [HORR16]

poly(log λ)λ · poly(log λ)LWEHemenway et al. [HORR16]

poly(log λ)poly(log λ)Ring-LWE

Canetti et al. [CPR17] (∗)

1 + o (1)Indistinguishability Obfuscation

Yoshida et al. [YKT19]

O(log λ)Brakerski et al. [BBD+ 20]

O(1)1 + o (1)

O λ2

O λ2

Brakerski et al. [BBD+ 20]

O(1)Yoshida et al. [YKXT20]
Yoshida et al. [YKXT20]

Common-Domain TDP
Trapdoor Simulatable PKE

Obliviously Samplable CE (DDH)
PEPE (DDH)
PEPE (LWE)O(1)λ · poly(log λ)

O λ2

O(1)

λ · poly(log λ)Obliviously Samplable CE (LWE)

Obliviously Samplable CE (DDH)

Table 1.1: Comparison of existing (2-round) NCE schemes in terms of their ciphertext
and public-key expansion. The security parameter is denoted by λ. (∗) This scheme uses
common reference strings.
straightforwardly, i.e. sampling two primes p, q and outputs its product, we cannot use
hardness assumptions over the composite number in the security proof of non-committing
encryption. This is because the adversary can obtain the randomness used in the key generation, which contains the factorization of N . A way to avoid this problem is to sample
a Blum integer N = pq without knowing its factorization, however, unfortunately, we do
not know such an algorithm.
For this reason, NCE schemes constructed based on the hardness of the RSA or factorization of Blum integer [CFGN96, CDMW09] use Bach’s algorithm [Bac88, Kal03] togenerate a random (not necessarily Blum) integer N , together with its factorization. Since
N is a random integer, we can explain to the adversary that N is sampled obliviously.
However, the integer N sampled in this way may not be used as a public key for the RSAor Rabin encryption because N may be a prime number, or it may be a composite numberthat does not contain a large prime factor, such as a power of two. Therefore we generate
a suﬃciently large number of {Ni }, so that we can expect that one of them will be a Blum
integer Ni = pq, which is a secure public key. We can use an ampliﬁcation technique, that
executes number of encryption for each Ni , so that if one of the ciphertexts is encrypted
under secure public-key Ni , the entire scheme is secure. In this way, we can construct an
NCE scheme over the composite number, but this approach incurs O(λ2 ) overhead on the
ciphertext and public key. This is because the probability of a random integer being aBlum number is Ω(1/λ2 ) [RS94, GM06].
For the case of NCE schemes constructed based on the hardness of the quadratic
residuosity problem [BBD+ 20, LCC06], it seems necessary to use the CRS model in which
a trusted party generates the composite number N = pq and put it to the CRS.

–4–

1.3. Related Works

1.3

Related WorksMulti-Round NCE Protocols. In this thesis, we focus on NCE in a narrow sense,that is, public-key encryption that satisﬁes the non-committing security because it is a
simplest form of non-committing encryption. However, in order to realize secure channels
in adaptively secure MPC protocols, it is not necessarily for NCE to be a public-key
encryption, i.e. 2-round protocol. Indeed, in some literature, the terminology NCE wasalso used in a broader sense to indicate multi-round adaptively secure message transmission
protocols.
Beaver [Bea97] proposed a 3-round NCE scheme with ciphertext expansion O(λ) basedon the decisional Diﬃe-Hellman (DDH) problem. Damgård and Nielsen [DN00] generalized Beaver’s protocol and proposed a 3-round NCE scheme with ciphertext expansion
O(λ) based on a primitive called simulatable PKE, which can be instantiated based on
concrete problems such as the DDH, computational Diﬃe-Hellman (CDH), and learningwith errors (LWE) problems. Lei, Chen, and Chen [LCC06] proposed an instantiationof 3-round NCE protocol based on the quadratic residuosity (QR) problem in order toreduce computational costs of the protocol.
Zhu, Araragi, Nishide, and Sakurai [ZANS10] proposed 4-round NCE protocol andanalyzed it in the universally composable framework.
NCE in the Secure Erasure Model. Beaver and Haber [BH93] showed if honest parties are assumed to be able to erase sensitive local information completely, then adaptively
secure MPC can be obtained eﬃciently. However, as discussed by Canetti et al. [CFGN96],
such trusted erasure may be unrealistic in many scenarios.
NCE in the Random Oracle Model. Nielsen [Nie01] pointed out constructing NCE
in the random oracle model is easy.
Nielsen [Nie02] show that NCE is a separation between the random oracle model andthe non-programable random oracle model.
Camenisch, Lehmann, Neven, and Samelin [CLNS17] proposed a UC secure NCE
scheme in the random oracle model.

1.4This Thesis

We propose the ﬁrst NCE schemes with constant ciphertext expansion without the use of
iO or CRS. Along the way, we propose an alternative paradigm to construct NCE, that
diﬀers from the paradigm proposed by Choi et al. [CDMW09] and used by NCE schemes
to date [HOR15, HORR16, BBD+ 20]. By instantiating our paradigm with obliviously
samplable key-encapsulation mechanism, we obtain an NCE scheme that has similar parameter to the NCE scheme by Choi et al. . The NCE schemes with constant ciphertext–5–

1.4. This Thesis
expansion are constructed by instantiating our new paradigm with obliviously samplable
chameleon encryption proposed as we described in [YKT19, YKXT20].
We show that obliviously samplable CE can be realized based on the DDH problem
and the LWE problem for super-polynomially large modulus. Thus, we obtain constantciphertext expansion NCE schemes based on the DDH problem and LWE problem.
One of the disadvantage of the DDH-based NCE scheme is its relatively large public-key
size. The size of public key for each message bit of the DDH-based scheme is O(λ2 ). Our
LWE based NCE scheme improves public-key size compared to the DDH-based scheme.
The size of the public key for each message bit of our LWE based scheme is λ · poly(log λ).
This is the same as that of NCE schemes proposed by Brakerski et al. [BBD+ 20] or Hemenway et al. [HORR16], which are also based on the LWE problem for super-polynomiallylarge modulus.
Weak Non-Committing Encryption. Our starting point is the observation that byadjusting the parameters of an NCE scheme proposed in [YKT19], its ciphertext expansion
can be reduced to a constant, at the cost of its perfect correctness and security.
Speciﬁcally, the scheme only satisﬁes weak correctness, which means that each bit ofdecrypted plaintext is ﬂipped with constant probability. Moreover, the scheme only satisﬁes weak security that only guarantees the secrecy of some part of encrypted plaintexts. In
Section 3.3, we formally deﬁne weak correctness and weak security for NCE and introduce
the notion of weak NCE as NCE satisfying only those weak correctness and weak security.
As a demonstration, we construct a weak NCE scheme from obliviously samplable KEM.
In Section 4.5, we give the description of the above scheme and its building block,obliviously samplable CE. Then we prove that the scheme is indeed a weak NCE scheme.
Ampliﬁcation for Non-Committing Encryption. Next, we show that we can amplify a weak NCE scheme into a full-ﬂedged NCE scheme in Section 3.2. As a tool ofampliﬁcation, we use a coding scheme called wiretap codes. More speciﬁcally, we deﬁne
a new security property, conditional invertibility for wiretap codes, which is essentiallya non-committing security for the wiretap codes. We show an instantiation of wiretap
codes constructed from randomness extractor and linear error-correcting codes satisﬁes
the conditional invertibility.
This ampliﬁcation increases the ciphertext expansion by only a constant factor. Thus,by applying this transformation to the weak NCE scheme shown in Section 4.5, we obtainan NCE scheme with a constant ciphertext expansion.
DDH-Based Instantiation. We propose a DDH-based instantiation of obliviously
samplable CE in Section 4.3. The construction is similar to the chameleon encryption
scheme based on the CDH problem, proposed by Döttling and Garg [DG17b].
A natural question would be “why we need to rely on the DDH assumption, not CDH?”
This is because a hash key and a ciphertext of the chameleon encryption scheme together–6–1.5. Notations
form multiple Diﬃe-Hellman tuples. Thus, it seems diﬃcult to sample them obliviously
unless we prove that the knowledge of exponent assumption [HT98, BP04] is false. In
order to solve this issue, we rely on the DDH assumption instead of the CDH assumption.
Under the DDH assumption, a hash key and a ciphertext of our chameleon encryption
are indistinguishable from independent random group elements, and thus we can performoblivious sampling of them in the above sense by sampling random group elements directlyfrom the underlying group.
Lattice-Based Instantiation. We propose a lattice-based instantiation of obliviously
samplable CE in Section 4.4. The construction is a natural composition of the latticebased hash encryption by Döttling et al. [DGHM18] and the lattice-based chameleon hashfunctions by Cash et al. [CHKP10].
One drawback of our construction is that we need the modulus of lattices to besuper-polynomially large for the correctness of it. This seems unavoidable since thechameleon encryption 1 implies non-interactive key exchange, which is considered diﬃcult to be realized from lattice problems for polynomially large modulus as discussed by
Guo et al. [GKRS20].

1.5

Notations

In this paper, PPT denotes probabilistic polynomial time. x ← X denotes an element x is
sampled from uniform distribution over a set X. y ← A(x; rA ) denotes that probabilistic
algorithm A takes x as input, outputs y using internal randomness rA . ε(λ) = negl(λ)
denotes function ε(·) is negligible, that is, ε(λ) = λ−ω(1) holds.
For an integer n, [n] denotes a set {1, . . . , n}. For a subset I ⊂ [n] and a vectorx = (xi )1≤i≤n ∈ {0, 1}n , xI denotes (xi )i∈I . For a matrix M = (mi )1≤i≤n ∈ {0, 1}k×n ,MI ∈ {0, 1}k×|I| denotes the matrix composed from column vectors mi of M for i ∈ I.
h2 (·) denotes the binary entropy function, h2 (p) = −p log p−(1−p) log(1−p). H(Y |X)
denotes the conditional entropy.

1

At least, for the current formalization of chameleon encryption, it implies non-interactive key exchange. There leaves the possibility of constructing NCE scheme from poly-modulus LWE via introducing
a relaxed version of chameleon encryption.

–7–

Chapter 2
Basics and Deﬁnitions of NCE
2.1

Overview

In this chapter, we introduce the deﬁnition of non-committing encryption. Before describing concrete deﬁnitions, we brieﬂy and informally explain how to deﬁne semantic security
for a general algorithm A, which we consider as a generalization of key generation or encryption of primitives appear in this thesis. Then we show how to deﬁne non-committing
security and oblivious samplability as its extension.
Semantic Security Consider an execution of algorithm y ← A(x; rA ), where we want todeﬁne that the information on input x is hidden.
Semantic security (or static security as opposed to adaptive security) is deﬁned in
the following style: There exists a simulator algorithm Sim, such that for all x,cA(x; rA ) ≈ Sim(1λ ; rSim )holds. The left-hand side is often called real-life execution and the right-hand side
is ideal-world execution.
Oblivious Samplability We deﬁne oblivious samplability 1 in the following style: Thereb and an invert sampling algorithm InvA ,exists an obliviously sampling algorithm A
such that for all x,cb λ ; r b ), r b )(A(x; rA ), InvA (rA )) ≈ (A(1AA
holds. Oblivious samplability essentially says that the output y can be sampled
without using any randomness except y itself. In more detail, the real-life executionb λ ; r b ), where r b doesy ← A(x; rA ) can be simulated by oblivious sampling yb ← A(1AA
not contains conﬁdential information that aﬀect the security, i.e. it can be revealed
to the adversary. Furthermore, we also need to explain to the adversary that as if
1

This notion is also called “trapdoor simulatability” in [CDMW09]. “simulatability” in [DN00] is a
simpler notion where Inv take y as input instead of trapdoor rA . Actually, we only need simulatability
rather than trapdoor simulatability in this thesis.

82.2. Public-Key Encryptionb λ ; r′ ). Notey is obliviously sampled by showing rA′b ← InvA (rA ) that satisfy y = A(1bAbthat since A plays the role of Sim of the semantic security, oblivious samplability
implies semantic security.
In this thesis oblivious samplability is deﬁned for key encapsulation mechanism andchameleon encryption.
Non-Committing Security We deﬁne non-committing security or adaptive security inthe following style: There exists a simulator algorithm Sim and an opening algorithm
Open, such that for all x,c(A(x; rA ), rA ) ≈ (Sim(1λ ; rSim ), Open(rSim , x))
holds. Non-committing security captures a situation where the randomness rA is
revealed to the adversary after adaptive corruption. In the ideal world, the simulator
not only need to simulate the output y ′ ← Sim(1λ ; rSim ), it need to explain y ′ isas if the outcome of real-life execution by opening a consistent randomness rA′ ←Open(rSim , x) that satisfy y ′ = A(x; rA′ ). Note that non-committing security also
implies semantic security.
In this thesis, non-committing-style security is deﬁned for public-key encryption(thus, it is called non-committing encryption), wiretap codes, and hash function inhash encryption (thus, it is called chameleon hash in chameleon encryption).
From the above, we can see duality between the deﬁnitions of oblivious samplability
and non-committing security. In oblivious samplability, Inv fakes the real-life execution
as if it is ideal-world execution by producing rA′b . In non-committing security, Open fakes
the ideal-world execution as if it is real-life execution by producing rA′ . In general, idealworld execution is less structured than real-life execution since it does not need to consider
functional requirements such as correctness. Since it is easier to fake structured things
as less structured things than their opposite, oblivious samplability seems easier to beachieved than non-committing security. Indeed natural instantiations of public-key encryption based on the DDH or LWE satisfy oblivious samplability, while we do not knowa natural non-committing encryption scheme. Thus many studies including this thesistackle the problem of constructing non-committing encryption from obliviously samplable
cryptographic primitives. Although it might be meaningless in practice, we leave the opposite, constructing obliviously samplable encryption from non-committing encryption as
future work.

2.2

Public-Key Encryption

We proceed to concrete deﬁnitions from here. Since non-committing encryption can beseen as public-key encryption that satisﬁes a non-committing security notion, we provide–9–2.2. Public-Key Encryption
the deﬁnition of public-key encryption and its static security notion known as semantic
security for comparison.
Deﬁnition 2.1 (Public-Key Encryption). A public-key encryption scheme consists of thefollowing PPT algorithms (Gen, Enc, Dec), where Gen is the key-generation algorithm, Enc
is the encryption algorithm, and Dec is the decryption algorithm. We explicitly display
the randomness used in Gen and Enc as they are the target of attention in the study of
non-committing encryption.
• Gen 1λ ; rGen : Given the security parameter 1λ , it outputs a public key pk and asecret key sk. The randomness used in this algorithm is denoted by rGen 2 .
• Enc (pk, m; rEnc ): Given a public key pk and a plaintext m ∈ {0, 1}µ , it outputs aciphertext CT . The randomness used in this algorithm is denoted by rEnc .
• Dec (sk, CT ): Given a secret key sk and a ciphertext CT , it outputs m or ⊥.
Public-Key/Ciphertext Expansion In this thesis, we measure the size of the public
key and ciphertext by its asymptotic ratio to the length of the message. Public-key expansion and ciphertext expansion of a public-key encryption scheme is deﬁned by |pk|/|m|and |CT |/|m|, respectively for a enough long message |m| = poly(λ).
Remark 1. It is rare to focus on the above asymptotic measure of public-key expansion
or ciphertext expansion if we only consider the static security of public-key encryption
schemes. Since we can encrypt any polynomially long message by a single public key, itspublic-key expansion is trivially almost 0, or we can use the hybrid encryption techniquewith an eﬃcient secret-key encryption scheme, hence its ciphertext expansion is triviallyalmost 1. However, in the context of non-committing encryption, we cannot reuse a single
public key to encrypt multiple messages, nor does there exist an eﬃcient non-committing
secret-key encryption scheme. Essentially the most eﬃcient non-committing secret-key
encryption scheme is the one-time pad, so it is useless to compress the ciphertext by thehybrid encryption technique.
Deﬁnition 2.2 (Correctness). The correctness of a public-key encryption scheme is deﬁned as follows: For any message m, its ciphertext should be decrypted to the original
message with overwhelming probability.
Formally, we say that a public-key encryption scheme PKE = (Gen, Enc, Dec) is correct
if for all message m,
Pr [m ̸= Dec (sk, Enc (pk, m; rEnc ))] = negl(λ)
holds, where (pk, sk) ← Gen 1λ ; rGen and the probability is taken over the choice of rGen
and rEnc .
2

Since we can reproduce the secret key sk from the key-generation randomness rGen , we can use rGen
as a secret key. In other words, we can understand the key-generation algorithm as pk ← Gen(1λ ; sk).

– 10 –

2.3. Non-Committing Encryption
Security Informally, a public-key encryption scheme is semantically secure (staticallysecure) if the views of the static adversary in the real and ideal experiments are indistinguishable. In other words, the public key and ciphertext of the scheme can be simulated
without knowledge of the message.
Deﬁnition 2.3 (Semantic Security). For a public-key encryption scheme PKE = (Gen, Enc, Dec),
consider the following PPT simulator Sim:• Sim 1λ ; rSim : Given the security parameter 1λ , it outputs a simulated public key
pk, a simulated ciphertext CT .
For a stateful PPT adversary A, we deﬁne the following real and ideal experiments.
ExpRealPKE,A(pk, sk) ← Gen 1λ ; rGenm ← A (pk)CT ← Enc (pk, m; rEnc )out ← A (CT )ExpIdeal
PKE,A(pk, CT ) ← Sim 1λ ; rSimm ← A (pk)out ← A (CT )We say that PKE is semantically secure if there exist a PPT simulator Sim such that for
all PPT adversary A,




Ideal
AdvPKE,A (λ) := Pr out = 1 in ExpReal= negl(λ)
PKE,A − Pr out = 1 in ExpPKE,A
holds.
Note that this deﬁnition is equivalent to the well-known indistinguishability against
chosen plaintext attack (IND-CPA) security.

2.3

Non-Committing Encryption

Deﬁnition 2.4 (Non-Committing Encryption). A non-committing encryption scheme isa public-key encryption scheme that satisﬁes the following non-committing security.
Informally, a non-committing encryption scheme is secure, or equivalently, a public-key
encryption scheme satisﬁes non-committing security or adaptive security, if the views of theadaptive adversary upon the corruption of both sender and receiver are indistinguishable.
In other words, not only the public key and ciphertext of the scheme can be simulated
without knowledge of the plaintext, but also the randomness used in Gen and Enc can be
simulated given the corrupted message.
Deﬁnition 2.5 (Non-Committing Security). For a non-committing encryption scheme
NCE = (Gen, Enc, Dec), consider the following PPT simulators (Sim, Open):• Sim 1λ ; rSim : Given the security parameter 1λ , it outputs a simulated public key
pk and a simulated ciphertext CT .
– 11 –

2.3. Non-Committing Encryption• Open(rSim , m): Given the simulation randomness rSim and a message m, it outputs
randomness for key generation rGen and encryption rEnc .
For a stateful adversary A, we deﬁne two experiments as follows.
ExpRealNCE,A(pk, sk) ← Gen 1λ ; rGenm ← A (pk)CT ← Enc (pk, m; rEnc )out ← A (CT, rGen , rEnc )ExpIdeal
NCE,A(pk, CT ) ← Sim 1λ ; rSimm ← A (pk)(rGen , rEnc ) ← Open(rSim , m)out ← A (CT, rGen , rEnc )We say that NCE is secure if there exist PPT simulators (Sim, Open) such that for all PPT
adversary A,




Ideal
AdvNCE,A (λ) := Pr out = 1 in ExpReal= negl(λ)
NCE,A − Pr out = 1 in ExpNCE,Aholds.
We also introduce a slightly weaker security notion of non-committing encryption,
where the message to be encrypted is chosen independently of the public key. We use thisstyle of security deﬁnition throughout this thesis because it is easier to deﬁne and prove
such security notions, especially, in the sentence of the obliviously samplable chameleon
encryption scheme constructed based on the LWE in Section 4.4.2.
Deﬁnition 2.6 (Non-Committing Security for pk-independent Messages). We say that
NCE is secure with respect to public-key independent message if there exist PPT simulators(Sim, Open) such that for all PPT adversary A and message m, for the following modiﬁed
experiments′

ExpRealNCE,A(pk, sk) ← Gen 1λ ; rGen
CT ← Enc (pk, m; rEnc )out ← A (CT, rGen , rEnc )′ExpIdeal
NCE,A(pk, CT ) ← Sim 1λ ; rSim
(rGen , rEnc ) ← Open(rSim , m)out ← A (CT, rGen , rEnc ), the advantage AdvNCE,A (λ) is negligible.
Note that a non-committing encryption scheme NCE′ that is secure with respect toa public-key independent message can be easily converted to NCE that satisﬁes the noncommitting security (Deﬁnition 2.5) via the hybrid encryption technique with one-time
pad, similarly in the sentence of semantically secure public-key encryption. In our NCE
schemes, the ampliﬁcation presented in section 3.4 contains the one-time pad.
Limitations of NCE schemes Due to its security requirement, non-committing encryption schemes have inherent limitations that standard public-key encryption schemes
do not have.
– 12 –

2.3. Non-Committing Encryption
Lemma 2.1. Let NCE be a non-committing encryption scheme for message m. Then its
secret key sk, key-generation randomness rGen and encryption randomness rEnc must belarger than the message length, i.e., |sk| , |rGen | , |rEnc | ≥ |m|.
This is because of the ability of NCE that it can open the simulated ciphertext to anarbitrary message. In detail, for any message, there exists a secret key that can decrypt
the ciphertext to the message, thus the space of secret key must be larger than the message
space. Similarly, there exists encryption randomness that can encrypt the message to theciphertext, thus space of encryption randomness must be larger than the message space.
Lemma 2.2. Non-committing encryption scheme in the standard model, which does not
use the random oracle nor common reference strings, cannot achieve the perfect correctness, i.e., Pr [m ̸= Dec (sk, Enc (pk, m; rEnc ))] ̸= 0.
Consider a simulated ciphertext is opened in two ways. Then there should exist twopairs of the secret key and encryption randomness that satisfy
Enc(pk, m0 ; rEnc0 ) = CT, Dec(sk0 , CT ) = m0 ,Enc(pk, m1 ; rEnc1 ) = CT, Dec(sk1 , CT ) = m1 .
This causes the case where during an honest execution of the non-committing encryption
scheme, the receiver generates key pair (pk, sk0 ), and the sender encrypts message m1 withencryption randomness rEnc1 . In this case, the decryption fails as
Dec(sk0 , Enc(pk, m1 ; rEnc1 )) = m0 .

– 13 –

Chapter 3
NCE with O(λ)
Ciphertext-Expansion
3.1

Overview

In this section, we show high-level ideas behind our construction of weak NCE.
As a starting point, we review the three-round NCE protocol proposed by Beaver [Bea97],
which contains a fundamental idea to build NCE from the DDH problem. Next, we observethat the Beaver’s protocol can be transformed to a two-round NCE scheme. Although theresulting scheme is not fully secure NCE, we can regard it as a weak variant of NCE which
we call weak NCE. Then we show a simple idea to transform a weak NCE scheme to asecure NCE, whose ciphertext expansion is O(λ).

3.1.1Starting Point: Beaver’s Protocol

Beaver’s NCE protocol essentially executes two Diﬃe-Hellman key exchange protocols inparallel. This protocol can send a 1-bit message. Ciphertext expansion of this protocol isO(λ). We describe the protocol below and in Figure 3.1.
Step1. Let G be a group of order p with a generator g. The sender picks a random bitz ← {0, 1} and an exponent αz ← Zp , then sets Az = g αz . The sender also generates
a random group element A1−z ← G obliviously, i.e., without knowing the discrete logof A1−z . The sender sends (A0 , A1 ) to the receiver and stores the secret sk = (z, αz ).
The random coin used in this step is (z, αz , A1−z ).
Step2. The receiver picks a random bit x ← {0, 1} and an exponent ρx ← Zp , andthen sets Bx = g ρx . The receiver also obliviously generates B1−x ← G. The receiver computes Kx = Ax ρx and obliviously samples K1−x ← G. The receiversends ((B0 , B1 ), (K0 , K1 )) to the sender. The random coin used in this step is(x, ρx , B1−x , K1−x ).

14

3.1. Overview
SenderInput: m ∈ {0, 1}
z ← {0, 1}
αz ← Zp
Az = g αz(A0 , A1 )A1−z ← G−−−−−−−−−−−−→(K0 , K1 ), (B0 , B1 )←−−−−−−−−−−−−αz
if Bz = Kzw
w := z ⊕ m−−−−−−−−−−−−→
else w := ⊥Receiverx ← {0, 1}
ρx ← Zp
Bx = g ρx
B1−x ← G
Kx = Ax ρx
K1−x ← G
if w ̸= ⊥Output: m = w ⊕ x

Figure 3.1: The description of Beaver’s protocol [Bea97].
Step3. The sender checks whether x = z holds or not, by checking if Bz αz = Kz holds.
With overwhelming probability, this equation holds if and only if x = z. If x = z,
the sender sends w := z ⊕ m, otherwise quits the protocol.
Step4. The receiver recovers the message by computing w ⊕ x.
Next, we describe the simulator for this protocol.
Simulator The simulator simulates a transcript (A0 , A1 ), ((B0 , B1 ), (K0 , K1 )), and w as
follows. It generates α0 , α1 , ρ0 , ρ1 ← Zp and sets((A0 , A1 ), (B0 , B1 ), (K0 , K1 )) = ((g α0 , g α1 ), (g ρ0 , g ρ1 ), (g α0 ρ0 , g α1 ρ1 )).
The simulator also generates w ← {0, 1}.
The simulator can later open this transcript to either message 0 or 1. In other words,
for both messages, the simulator can generate consistent sender and receiver random
coins. For example, when opening it to m = 0, the simulator sets x = z = w, andoutputs (w, αw , A1−w ) and (w, ρw , B1−w , K1−w ) as the sender’s and receiver’s opened
random coins, respectively.
Security Under the DDH assumption on G, we can prove that any PPT adversary A
cannot distinguish the pair of transcript and opened random coins generated in thereal protocol from that generated by the simulator. The only diﬀerence of them isthat K1−x is generated as a random group element in the real protocol, but it isgenerated as A1−x ρ1−x = g α1−x ρ1−x in the simulation. If the real protocol proceeds
to Step.4, we have x = z with overwhelming probability. Then, the random coinsused by the sender and receiver (and thus given to A) does not contain exponents of
A1−x and B1−x , that is, α1−x and ρ1−x . Thus, under the DDH assumption, A cannot
distinguish randomly generated K1−x ← G from A1−x ρ1−x = g α1−x ρ1−x . Thus, thisprotocol is a secure NCE protocol.
– 15 –

3.1. Overview
This protocol succeeds in transmitting a message only when z = x, and otherwise
it fails. Note that even when z ̸= x, the protocol can transmit the message correctly
because in Step.3, the sender knows the receiver’s secret x. However, in this case, wecannot construct a successful simulator. In order to proof the security based on the DDH
assumption, we have to ensure that either one of exponent pair (α0 , ρ0 ) or (α1 , ρ1 ) is notrevealed to the adversary. However, when z ̸= x, the exponents related to both 0 and 1 iscorrupted, hence we cannot use the DDH assumption, and the security proof fails.
Next, we show how to extend this protocol into a two-round weak NCE scheme andobtain a scheme with ciphertext expansion O(λ).

3.1.2

Extension to Two-Round Weak NCE Scheme

As a ﬁrst attempt, we consider an NCE scheme NCE1lin that is a natural extension of
Beaver’s three-round NCE protocol. Intuitively, NCE1lin is Beaver’s protocol in which therole of the sender and receiver is reversed, and the sender sends a message even when z
and x are diﬀerent. Speciﬁcally, the receiver generates the public key pk = (A0 , A1 ) andsecret key (z, ρz ), and the sender generates the ciphertext CT = ((B0 , B1 ), (K0 , K1 ), w),
where (A0 , A1 ), (B0 , B1 ), (K0 , K1 ), and w := x ⊕ m are generated in the same way as
those in Beaver’s protocol. When decrypting the CT , the receiver ﬁrst recovers the valueof x by checking whether Bzρz = Kz holds or not, and then computes w ⊕ x.
Of course, NCE1lin is not a secure NCE scheme in the sense that we cannot construct a
successful simulator when z ̸= x for the same reason explained above. However, we can ﬁx
this problem and construct a secure NCE scheme by running multiple instances of NCE1lin .
In NCE1lin , if z coincides with x, we can construct a simulator similarly to Beaver’s
protocol, which happens with probability 21 . Thus, if we run multiple instances of it, we
can construct simulators successfully for some fraction of them. Based on this observation,
we construct an NCE scheme NCElin as follows. We also describe NCElin in Figure 3.2.
Let the length of messages be µ = O(SP ) and n = O(µ). We later specify the concrete
relation of µ and n. The receiver ﬁrst generates z1 · · · zn = z ← {0, 1}n . Then, for everyi ∈ [n], the receiver generates a pubic key of NCE1lin , (Ai,0 , Ai,1 ) in which the single bit
randomness is zi . We let the exponent of Ai,zi be ρi , that is, Ai,zi = g ρi . The receiversends these n public keys of NCE1lin as the public key of NCElin to the sender. The secret
key is (z, ρ1 , . . . , ρn ).
When encrypting a message m, the sender ﬁrst generates x1 · · · xn = x ← {0, 1}n .
Then, for every i ∈ [n], the sender generates ((Bi,0 , Bi,1 ), (Ki,0 , Ki,1 )) in the same way as
NCE1lin , where we “encapsulate” xi by using the i-th public key (Ai,0 , Ai,1 ). We call it i-th
encapsulation. Finally, the sender generates w = m ⊕ H(x), where H is a hash function
explained later in more detail.

– 16 –

3.1. Overview

Receiverz ← {0, 1}n∀i ∈ [n], αi ← Zp
Ai,zi = g αi
A1,0 , . . . , An,0A1,1 , . . . , An,1Ai,1−zi ← G!

−−−−−−−−−−−−−−−−−−−−−−−−−→

SenderInput: m ∈ {0, 1}µx ← {0, 1}n∀i ∈ [n], ρi ← Zp
Bi,xi = g ρiBi,1−xi ← G
Ki,xi = Ai,xi ρiKi,1−xi ← G!
!
B1,0 , . . . , Bn,0
K1,0 , . . . , Kn,0,
, w w = H(x) ⊕ m
B1,1 , . . . , Bn,1
K1,1 , . . . , Kn,1

if Bi,zi αi = Ki,zi←−−−−−−−−−−−−−−−−−−−−−−−−−

xi := zi
else xi := 1 − zi
Output: m = w ⊕ H(x)Figure 3.2: The description of NCElin .
The resulting ciphertext is
B1,0 , . . . , Bn,0
B1,1 , . . . , Bn,1!

! !
K1,0 , . . . , Kn,0,,w .
K1,1 , . . . , Kn,1

Decryption is done by recovering each xi in the same way as NCE1lin and computing w ⊕H(x).
The simulator for this scheme runs as follows. It ﬁrst generates z1 · · · zn = z ← {0, 1}nand x1 · · · xn = x ← {0, 1}n . Then, for every index i ∈ [n] such that zi = xi , it simulates
the i-th public key and encapsulation in the same way as the simulator for NCE1lin (andthus Beaver’s protocol). For every index i ∈ [n] such that zi ̸= xi , it simply generates
i-th public key and encapsulation in the same way as NCElin does in the real execution.
Finally, it generates w ← {0, 1}µ .
Although the ciphertext generated by the simulator is not “fully non-committing”
about x, still, it loses the information of bits of x such that xi = zi . Thus, if we canprogram the output value of the hash function H freely by programming only those bitsof x, the simulator can later open the ciphertext to any message, and we see that NCElinis a secure NCE scheme.
To realize this idea, we ﬁrst set n > 2µ in order to ensure that the simulated ciphertext loses the information of at least µ-bits of x with overwhelming probability. This isguaranteed by the Chernoﬀ bound. The ciphertext rate of NCElin is O(λ), that is alreadythe same as the best rate based on the DDH problem achieved by the construction of
Choi et al. [CDMW09].
– 17 –

3.1. Overview

3.1.3

Compress Ciphertext

We compress the! ciphertext of above scheme in two way. The ﬁrst part of the ciphertext
B1,0 , . . . , Bn,0
is compressed to a single group element by using chameleon encryption.
B1,1 , . . . , Bn,1
We will explain this compression in the next chapter.
In this section! we focus on the compression of the second part of the ciphertext
K1,0 , . . . , Kn,0
. Recall that each Ki,b is a group element of size λ. However its property
K1,1 , . . . , Kn,1
as a group element is not used in the scheme as only in the decryption algorithm, Ki,b iscompared with Bi,zi αi . We replace this comparison of group elements to the comparisonof hash value of them, i.e., HG (Ki,zi ) vs. HG (Bi,zi αi ). Henceforth Ki,b denotes the hashvalue of length ℓ, which we can choose arbitrary.
We want ℓ to be as small as possible as it directly reﬂects to the ciphertext size.
However if we choose too much small ℓ, the probability of Ki,1−zi = HG (Bi,zi αi ), hence theprobability of decryption error becomes large. We can ﬁx this decryption error using error
correcting codes, but as the error probability increases, the rate of the codes decreases,
resulting in large ciphertext. Therefor we must choose appropriate constant ℓ that balances
ciphertext size and error probability. We also choose appropriate wiretap codes, whose
rate is as high as possible, to amplify the two problem of this weak NCE scheme: weaksecurity due to its construction, and weak correctness caused by compressing ciphertext.

3.1.4

Related Works on Ampliﬁcation for Public-Key Encryption

Studies on security ampliﬁcation have asked and answered the question:“How far can we weaken a security deﬁnition so that schemes satisfying thedeﬁnition can still be transformed into those satisfying full-ﬂedged security?”
Dwork, Naor, and Reingold [DNR04] ﬁrst studied the ampliﬁcation of public-key encryption. They showed that a public-key encryption scheme that satisﬁes weak forms of
one-wayness and correctness can be transformed into one satisﬁes the ordinary correctness
and IND-CPA security. Holenstein and Renner [HR05] showed a more eﬃcient ampliﬁcation method, starting from a scheme satisfying weak forms of IND-CPA security andcorrectness. Lin and Tessaro [LT13] provided an ampliﬁcation method for schemes with
IND-CCA security.
In this work, we show an ampliﬁcation method for NCE, which can be seen as one ofthis line of research.

– 18 –

3.2. Wiretap Channel and Ampliﬁcation

3.2

Wiretap Channel and Ampliﬁcation

In this section we introduce the wiretap channel model, wiretap codes, and its instantiation.

3.2.1

Channel Model

When a sender transmits a message x ∈ {0, 1}n through a channel ChR, the receiver getsa noisy version of the message x̃ ∈ {0, 1, ⊥}n . We deﬁne the procedure of such channels asprobabilistic functions, x̃ ← ChR(x; rch ). We review two channel models, Binary Erasure
Channel (BEC) and Binary Symmetric Channel (BSC).
Let Bpn be the n-bit Bernoulli distribution with parameter p. In other words, rch ← Bpn
is an n-bit string where for each i ∈ [n], Pr[rchi = 1] = p and Pr[rchi = 0] = 1 − p.
Deﬁnition 3.1 (Binary Erasure Channel (BEC)). Through a binary erasure channel
BECp , each bit of input x ∈ {0, 1}n is erased with probability p.
BECp (x; rch ) samples randomness rch ← Bpn . Output of the channel is x̃ where x̃i = ⊥if rchi = 1 and x̃i = xi if rchi = 0.
We also denote the output of BEC by xI ← BECp (x; rch ) where I = {i ∈ [n] | rchi = 0}
is the set of non-erased indices.
Deﬁnition 3.2 (Binary Symmetric Channel (BSC)). Through a binary symmetric channel
BSCp , each bit of input x ∈ {0, 1}n is ﬂipped with probability p.
BSCp samples randomness rch ← Bpn . Output of the channel is x̃ = x ⊕ rch .
We denote by BEC≤p , a binary symmetric channel with parameter p′ ≤ p.

3.2.2

Wiretap Codes

When weak NCE is used to communicate, roughly speaking, the receiver gets a noisy
version of the transmitted message x, and the adversary can see some partial informationof x. In fact, such a situation is very natural and studied as physical layer security in the
Information and Coding (I&C) community since the wiretap channel model was proposed
by Wyner [Wyn75]. Based on this observation, in this section, we show how to amplify aweak NCE scheme into a full-ﬂedged one by using wiretap codes. 1
Wiretap Codes As described in Figure 3.3, when the sender transmits a message x
over the wiretap channel, on one hand, the receiver gets the message aﬀected by noise overreceiver channel ChR(x). On the other hand, an adversary can interrupt the transmission
and gets a noisier version of the message ChA(x).
1

In literature, wiretap codes sometimes appeared in the name of “encryption” or “one-way secret-key
agreement”. It can be also interpreted as a kind of secret sharing scheme.

– 19 –

3.2. Wiretap Channel and Ampliﬁcation

ChA

Senderm

Encodex

ChA(x)

Adversary ChR(x)m′
Receiver
ChR
DecodeFigure 3.3: Wiretap channel model.
In such a model, using the diﬀerence in the amount of noise the receiver and theadversary are aﬀected, wiretap codes WC enable us to transmit a message m correctly tothe receiver while keeping it information-theoretically secure against the adversary.
Wiretap codes have an encoding and a decoding algorithm similar to error-correcting
codes. Wiretap codes satisfy two properties. One is correctness, which ensures that thereceiver can decode codewords even if they are aﬀected by some amount of noise. The
other is security, which guarantees that the adversary can get no information about themessage given some part of the codeword. It is known that the encoding algorithm must
use randomness to satisfy security.
Originally in the I&C community, the security of wiretap codes was deﬁned by mutual
information. Bellare et al. [BTV12b, BT12, BTV12a] proposed several equivalent deﬁnitions in a cryptographic manner. Among them, we recall one adopting the distinguishingstyle of security below. Then we proposed a new security property, conditional invertibility
for wiretap codes, which we need in the security proof of our ampliﬁcation for NCE.
Note that the following deﬁnition adopts the seeded version of wiretap codes also
proposed by Bellare et al. [BTV12b]. In the seeded wiretap channel, the sender, receiver,and an adversary can see a public random seed. We adopt the seeded wiretap codes togive a simple construction of the codes. The seed can be removed without increasing therate of the codes by a transformation shown in [BT12]. In this work, we put the seed intoa part of the public key when constructing NCE.
Deﬁnition 3.3 (Wiretap Codes). (Seeded) wiretap codes WC consist of the following PPT
algorithms (WC.Setup, WC.Encode, WC.Decode).
• WC.Setup(1λ ): Given the security parameter 1λ , it samples a public seed p.
• WC.Encode(p, m; s): It encodes a message m ∈ {0, 1}µ with a public seed p andrandomness s ← S, and outputs a codeword x ∈ {0, 1}n .
• WC.Decode(p, x): On input a noisy codeword x ∈ {0, 1}n and a public seed p, it
outputs a message m.
Rate of Wiretap Codes. The rate of WC is the length of messages over the length ofcodewords µ/n ∈ (0, 1). The rate of WC is at most the secrecy capacity of the wiretap
channel. The secrecy capacity of wiretap channel, deﬁned with symmetric channels ChR– 20 –

3.2. Wiretap Channel and Ampliﬁcation
and ChA, is equal to H(U |ChA(U )) − H(U |ChR(U )) for a uniformly random bit U [Leu77],
where H(Y |X) denotes the conditional entropy.
Usually, wiretap codes are required to satisfy the following correctness and security.
As a security property, we present a deﬁnition of distinguishing security adopted forseeded wiretap codes. This is a natural extension of the distinguishing security for seedless
wiretap codes proposed by Bellare et al. [BTV12b].
Correctness: WC is correct over the receiver’s channel ChR if for all message m ∈ {0, 1}µand public seed p, we have
Pr[WC.Decode(p, ChR(WC.Encode(p, m))) ̸= m] = negl(λ) .
Note that correctness holds when the message length |m| = µ is enough large,
concretely, |m| = Ω(λ) is enough.
Security: WC is DS-secure against adversary’s channel ChA if for any unbounded stateful
adversary A, we havep ← WC.Setup(1λ ), (m0 , m1 ) = A(p),



 1
b
←
{0,
1},
x
←
WC.Encode(p,
m
),
b


Pr b = b′
= negl(λ) .
−

 2
x̃
←
ChA(x;
r
),
ch


′
b = A(x̃)
Next, we introduce a new security property for wiretap codes, conditional invertibility.
Intuitively, this security notion states that after the adversary sees the partial information x̃ ← ChA(x) resulted from the codeword x of a message m′ , we can eﬃciently
explain that x̃ has resulted from another message m. The security deﬁnition involves a
PPT inversion algorithm WC.Invert, which on inputs seed p, a condition x̃, and a messagem, outputs randomness s′ and rch ′ such that ChA(WC.Encode(p, m; s′ ); rch ′ ) is equal to thecondition x̃.
Conditional invertibility implies the ordinary distinguishing security. It can be seen as
non-committing security for wiretap codes. Note that wiretap codes are inherently noncommitting in the sense that they usually required to statistically lose the information of
messages. Thus, the only point conditional invertibility additionally requires is that theinversion can be computed eﬃciently.
Deﬁnition 3.4 (Conditional Invertibility). For an unbounded stateful adversary A anda PPT algorithm WC.Invert, deﬁne two experiments as follows:
ExpRealWC,Ap ← WC.Setup(1λ )(m, m′ ) = A(p)x ← WC.Encode(p, m; s)x̃ ← ChA(x; rch )out = A (x̃, s, rch )ExpIdealWC,Ap ← WC.Setup(1λ )(m, m′ ) = A(p)x ← WC.Encode(p, m′ ; s)x̃ ← ChA(x; rch )(s′ , rch ′ ) ← WC.Invert(p, x̃, m)
out = A (x̃, s′ , rch ′ )– 21 –

3.2. Wiretap Channel and Ampliﬁcation
We say that WC is invertible conditioned on ChA if there exists a PPT inverter WC.Invert
such that for any unbounded adversary A,




Ideal
Pr out = 1 in ExpReal= negl(λ)
WC,A − Pr out = 1 in ExpWC,A
holds.

3.2.3

Instantiation of Wiretap Codes

Overview. We recall a modular construction of wiretap codes proposed by Bellare et al. [BTV12b]
called Invert-then-Encode construction. The building blocks are error-correcting codes
and invertible extractors. This idea of composing error-correcting codes and extractors can be found also in the construction of a linear secret sharing scheme proposedby Cramer et al. [CDD+ 15].
Consider an seeded extractor Ext : {0, 1}k → {0, 1}µ which on inputs X ∈ {0, 1}kand a seed p, outputs m ∈ {0, 1}µ . The extractor is invertible if there is an eﬃcient
inverter Inv, which on inputs m ∈ {0, 1}µ and seed p, samples a preimage X ∈ {0, 1}kusing randomness s. The Invert-then-Encode construction takes input m with seed p, ﬁrst
inverts the extractor X ← Inv(m, p; s), then encodes X by the error-correcting code as
x = Encode(X).
For a concrete instantiation, Bellare et al. suggested to use the polar codes [Ari09] aserror-correcting codes to achieve the optimal rate. Note that we can compute the encodingof input m by mG where G is a generator matrix of the linear error-correcting code.
Invertible extractors can be instantiated using multiplication over GF(2k ). Concretely,
the extractor takes inputs x ∈ {0, 1}k and seed p ∈ GF(2k ), and outputs the ﬁrst µ bit ofx ⊙ p, where ⊙ denotes multiplication over GF(2k ). The inverter Inv for this extractor is
obtained by Inv(m, p; s) = (m∥s) ⊙ p−1 .
Construction. We describe the construction of wiretap codes for µ = O(λ) bit messages. For a longer message, we can encode it by ﬁrst dividing it into blocks of µ bit andthen encoding each block by the following codes (see [BT12]).
Let µ, k, n = O(λ). Let G ∈ {0, 1}k×n be a generator matrix of a linear error-correcting
code, and ECC.Decode a corresponding decoding algorithm. Choose a constant ϵ > 0 suchthat the error-correcting code can be correct over ChR = BSC≤ϵ . We construct wiretap
codes which is correct over ChR = BSC≤ϵ and invertible conditioned on ChA = BEC0.5 .
Thus, in this construction, the wiretap decoding algorithm takes as input x′ ← BSCϵ (x),and the wiretap inverter algorithm takes as input xI ← BEC0.5 (x; rch ) where I ∈ [n] is theset of non-erased indices determined by a uniformly random n-bit string rch .
• WC.Setup(1λ ): Sample and output p ← GF(2k ) \ {0}.
• WC.Encode(p, m; s): For input m ∈ {0, 1}µ , sample s ← {0, 1}k−µ , output x =((m∥s) ⊙ p)G ∈ {0, 1}n .
– 22 –

3.2. Wiretap Channel and Ampliﬁcation• WC.Decode(p, x′ ): Output the ﬁrst µ bits of ECC.Decode(x′ ) ⊙ p−1 .
• WC.Invert(p, xI , m): On input a condition xI ← BEC0.5 (x; rch ), sample and output
s′ which satisﬁes xI = ((m∥s′ ) ⊙ p)GI .
P
Concretely, let i zi ci + c0 (ci ∈ {0, 1}k , zi ∈ {0, 1}) be the general solution of linear
equation xI = yGI . Then, uniformly sample a solution {zi }i of linear equation m =
P
P
−1
−1
′
−1
i zi (ci ⊙p ){1,...,µ} +(c0 ⊙p ){1,...,µ} . Finally, output s =i zi (ci ⊙p ){µ+1,...,k} +(c0 ⊙ p−1 ){µ+1,...,k} .
It also outputs randomness for the channel rch ′ = rch , which is a uniformly random
n-bit string representing the non-erased indices I.
Rate of the Scheme. The rate µ/n of the scheme can be set to a constant smaller than
( nk − 12 ). If the rate k/n of the error-correcting codes is close to its capacity 1 − h2 (ϵ), therate of WC can be close to its secrecy capacity 1/2 − h2 (ϵ), which is the optimal rate ofwiretap codes.
Correctness. The correctness of the wiretap codes directly follows from the correctnessof the underlying error-correcting codes.
Conditional Invertibility. To show the invertibility conditioned on BEC0.5 , we need toshow that distributions of (x̃, s, rch ) are statistically indistinguishable in the real and ideal
experiments of the deﬁnition. We introduce the hybrid experiment deﬁned as follows:
ExpRealWC,Ap ← WC.Setup(1λ )(m, m′ ) = A(p)x ← WC.Encode(p, m; s)x̃ ← ChA(x; rch )out = A (x̃, s, rch )ExpHybridWC,Ap ← WC.Setup(1λ )(m, m′ ) = A(p)x ← WC.Encode(p, m; s′ )x̃ ← ChA(x; rch )(s′ , rch ′ ) ← WC.Invert(p, x̃, m)
out = A (x̃, s′ , rch ′ )ExpIdealWC,Ap ← WC.Setup(1λ )(m, m′ ) = A(p)x ← WC.Encode(p, m′ ; s)x̃ ← ChA(x; rch )(s′ , rch ′ ) ← WC.Invert(p, x̃, m)
out = A (x̃, s′ , rch ′ )Before the proof we recall useful lemma, the Chernoﬀ bound and the leftover hashlemma.
Lemma 3.1 (Chernoﬀ Bound). Let X be a binomial random variable. If E [X] ≤ µ, thenδ2

for all δ > 0, Pr [X ≥ (1 + δ)µ)] ≤ e− 2+δ µ holds.
Lemma 3.2 (Leftover Hash Lemma). Let H := {h : {0, 1}n → {0, 1}ℓ } be a universal
hash family. If ℓ ≤ H∞ (x)−ω(log λ), (h, h(x)) and (h, u) are statistically indistinguishable
where u ← {0, 1}ℓ .
Claim 3.3. The distribution of output in the real and hybrid experiments are same.

– 23 –

3.2. Wiretap Channel and Ampliﬁcation
Proof. In general, for a function f : X → Y,{(x, y) | x ← X , y = f (x)} ≡ (x′ , y) | x ← X , y = f (x), x′ ← f −1 (y)holds, where f −1 (y) denotes the set of preimages of y.
By applying the above fact to fp,m (s, rch ) = ChA(WC.Encode(p, m; s); rch ), what we−1(x̃).
need to show is that WC.Invert implements sampling (s′ , rch ′ ) ← fp,mSince we consider ChA = BEC0.5 , WC.Invert can uniquely determine rch ′ = rch fromthe representation of x̃ = xI . Recall that WC.Invert samples s′ satisfying xI = ((m∥s′ ) ⊙p)GI = BEC0.5 (WC.Encode(p, m; s′ ); rch ) uniformly at random. Hence, the claim follows.

Claim 3.4. The hybrid and ideal experiments are statistically close if the wiretap codes
are secure in the ordinarily sense.
Proof. Consider the adversary A that distinguished the two experiments. We can construct another adversary A′ against the security of the wiretap codes as follows: Givenp, run A′ on p and obtain m, m′ ; send them to its challenger and receive x̃; compute(s, rch ) ← WC.Invert(p, x̃, m); run A′ on x̃, s, rch and receive out; output out. The claim isproven, since the simulation by A is perfect.
Claim 3.5. The wiretap codes are secure in the ordinarily sense.
Bellare et al. [BTV12b] show a detailed security proof of the wiretap codes for general
ChA. Below, we show a speciﬁc security proof for ChA = BEC0.5 .
Proof. Recall that the parameter is selected to satisfy µ/n < (k/n − 1/2). Let 2δ :=((k − µ)/n − 1/2) > 0 be a constant.
Since ChA = BEC0.5 , the input for the adversary is xI = ((m∥s) ⊙ p)GI . By the
Chernoﬀ bound, |I| < ( 12 + δ)n holds except negligible probability.
Let us decompose the submatrix of the generator GI = P DQ, where P ∈ {0, 1}k×k
and Q ∈ {0, 1}|I|×|I| are invertible. Furthermore D = (di,j ) ∈ {0, 1}k×|I| satisﬁes di,i = 1
for 1 ≤ i ≤ r := Rank(GI ) and di,j = 0 for other elements. We interpret the multiplication by D as getting the ﬁrst r bits and concatenating 0|I|−r . Thus xI = ((((m∥s) ⊙p)P )[r] ∥0|I|−r )Q.
For input m∥s and seed p, hp (m∥s) := ((m∥s ⊙ p)P )[r] forms a universal hash family.
Note that the input has min-entropy H∞ (m∥s) = k − µ.
Since r ≤ |I| ≤ ( 12 + δ)n ≤ k − µ − δn < H∞ (m∥s) − ω(log λ) holds, by the left overhash lemma, (p, hp (m∥s)) is statistically indistinguishable from (p, u) where u ← {0, 1}r .
Therefore xI is statistically indistinguishable from (u∥0|I|−r )Q, which is independent ofm. Thus, the claim is proven.
By combining the above three claims, conditional invertibility of the wiretap codes
follows.
– 24 –

3.3. Weak Non-Committing Encryption

3.3

Weak Non-Committing Encryption

In this section, we formalize the weak correctness and weak security for a non-committing
encryption scheme. Then, we show a simple construction of weak non-committing encryption scheme that has O(λ) public-key and ciphertext expansion.

3.3.1

Deﬁnition of Weak Non-Committing Encryption

Informally, we say that a public-key encryption scheme is weakly correct if it has decryption
error for each message bit.
Deﬁnition 3.5 (Weak Correctness). We say that an NCE scheme NCE = (Gen, Enc, Dec)
is weakly correct if it has non-negligible decryption error for each message bit. Speciﬁcally,
we say that NCE has ϵ-decryption error if for all message m ∈ {0, 1}µ and index i ∈ [µ],Pr [mi ̸= Dec (sk, Enc (pk, m; rEnc ))i ] ≤ ϵholds, where (pk, sk) ← Gen 1λ ; rGen and the probability is taken over the choice of rGen
and rEnc .
Note that the procedure of encryption and decryption of NCE works as the binary
symmetric channelDec(sk, Enc(pk, · )) = BSC≤ϵ (·).
Furthermore, we say that NCE satisﬁes correctness If ϵ = negl(λ), the weak correctness
corresponds to the correctness, Deﬁnition 2.2.
Deﬁnition 3.6 (Weak Non-Committing Security). Weak security allows an adversary
to learn some partial information of a plaintext Leak(m). Still, it guarantees that otherinformation of m remains hidden.
For an NCE scheme NCE = (Gen, Enc, Dec) and a probabilistic function Leak, consider
the following PPT simulators (SimGen, SimEnc, Open):• SimGen(1λ ; rSimGen ): Given the security parameter 1λ , it outputs a simulated public
key pk.
• SimEnc(rSimGen , m̃ ← Leak(m; r); rSimEnc ): Given the simulation randomness rSimGen
and a partial information of a plaintext m̃ which is computed by the probabilistic
function Leak with randomness r, it outputs a simulated ciphertext CT .
• Open(rSimGen , rSimEnc , m, r): Given the simulation randomness rSimGen , rSimEnc , a message m and the randomness r used by Leak, it outputs randomness for key generationrGen and encryption rEnc .

– 25 –

3.3. Weak Non-Committing Encryption
For an adversary A and a message m, deﬁne two experiments as follows.
Real
ExpWeak
NCE,A(pk, sk) ← Gen 1λ ; rGen
CT ← Enc (pk, m; rEnc )Ideal
ExpWeak
NCE,A
pk ← SimGen(1λ ; rSimGen )CT ← SimEnc(rSimGen , Leak(m; r); rSimEnc )(rGen , rEnc ) ← Open(rSimGen , rSimEnc , m, r)out ← A (pk, CT, rGen , rEnc ) out ← A (pk, CT, rGen , rEnc )We say that NCE is weakly secure with respect to Leak if there exist PPT simulators(SimGen, SimEnc, Open) such that for any PPT adversary A and any message m,Weak Real
Ideal
AdvWeak− Pr out = 1 in ExpWeak
NCE,A (λ) := Pr out = 1 in ExpNCE,A
NCE,A=negl(λ)
holds.
Remind that in this deﬁnition, following the style of Deﬁnition 2.6, the challenge
message is ﬁxed in advance independently of the public key.
Weak security with respect to Leak = ⊥ in which the target message is chosen by theadversary is exactly the same notion as the full-ﬂedged security for NCE which we recall
below.
Deﬁnition 3.7 (Weak Non-Committing Encryption). We say NCE is a weak non-committing
encryption scheme if it satisﬁes the above weak correctness and weak security.

3.3.2

Construction from Key Encapsulation Mechanism

In this section we show a construction of weak non-committing scheme with O(λ) publickey and ciphertext expansion. Before describe the construction, we deﬁne its building
block, key-encapsulation mechanism (KEM). Basically KEM is almost a public-key encryption scheme, in which the encapsulation algorithm E, instead of taking message m as
input, outputs a session key K ∈ {0, 1}ℓ that is indistinguishable to a uniformly random
string. Furthermore we require KEM to satisfy oblivious samplability which guarantees
that we can sample random public-key and ciphertext without knowing corresponding
randomness rGen , rEnc .
Deﬁnition 3.8 (Key-Encapsulation Mechanism). A key-encapsulation mechanism KEM
consists of the following PPT algorithms (G, E, D), where G is the key-generation algorithm,
E is the encapsulation algorithm, and D is the decapsulation algorithm.
• G(1λ ; rG ): Given the security parameter 1λ , it outputs a public key pk and a secretkey sk.
• E(pk; rE ): Given the public key pk, it outputs a ciphertext ct and a session key
K ∈ {0, 1}ℓ .
– 26 –

3.3. Weak Non-Committing Encryption• D(sk, ct): Given the secret key sk and the ciphertext ct, it outputs the session key
K.
Deﬁnition 3.9 (Correctness). The correctness for key-encapsulation mechanism meansthat the session keys output by the encapsulation and decapsulation algorithms are thesame. In formal, we say a key-encapsulation mechanism is correct if after executing(pk, sk) ← G(1λ ), (ct, K) ← E(pk),
Pr[K ̸= D(sk, ct)] = negl(λ)
holds.
Deﬁnition 3.10 (Oblivious Samplability). Consider the following oblivious sampling alb E),
b and an invert sampling algorithm
gorithms for key-generation and encapsulation (G,InvKEM .
b λ ; r b ): Given the security parameter 1λ , it outputs a obliviously sampled public• G(1Gb The randomness used in this algorithm r b is essentially its output pk
b itself.
key pk.
G
b pk;
b rb ): Given a public key pk,
b it outputs a obliviously sampled ciphertext ct.
b The
• E(
E
b itself.
randomness used in this algorithm rEb is essentially its output ct• InvKEM (rG , rE ): Given randomness for real-life execution of KEM (rG , rE ), it outputs
randomness for oblivious sampling (rGb , rEb ).
For a PPT adversary A, we deﬁne the following real and ideal experiments.
ExpRealKEM,A(pk, sk) ← G(1λ ; rG )(ct, K) ← E(pk; rE )(rGb , rEb ) ← InvKEM (rG , rE )out ← A(pk, ct, K, rGb , rEb )ExpIdealKEM,Abb λ; rb )pk, ← G(1Gb pk;
b rb )b ← E(ct
EℓK ← {0, 1}
b ct,
b K, rGb , rEb )out ← A(pk,We say that KEM is obliviously samplable if there exist above algorithms such that for
all PPT adversary A,




Ideal
= negl(λ)
AdvKEM,A (λ) := Pr out = 1 in ExpReal
KEM,A − Pr out = 1 in ExpKEM,Aholds.
If KEM satisﬁes the above oblivious samplability, its public-key is obliviously samplable.
Concretely, there exist InvG , such thatnocb r b | pk,b ← G(1b λ; rb )pk, rGb | (pk, sk) ← G(1λ ; rG ), rGb ← InvG (rG ) ≈ pk,
GG
holds.
– 27 –

3.3. Weak Non-Committing Encryption
Construction Let KEM = (G, E, D) be an obliviously samplable key-encapsulation mechanism as in the above. We construct a weak non-committing encryption scheme NCE =(Gen, Enc, Dec) for single bit message x ∈ {0, 1}. Weak non-committing encryption scheme
for multiple number of bits can be obtained by repeating the scheme for single bit in parallel.

Gen 1λ ; rGen :• Sample a uniformly random bit z ← {0, 1}.
• Generate a key pair of KEM: (pkz , skz ) ← G(1λ ; rG ).
b λ ; r b ).
• Obliviously sample a public key: pk1−z ← G(1G• Output pk := (pk0 , pk1 ) and sk := (z, skz ).
This key-generation algorithm uses randomness rGen = (z, rG , rGb ).
Enc(pk, x ∈ {0, 1}; rEnc ) :• Execute encapsulation: (ctx , Kx ) ← E(pkx ; rE ).
b• Obliviously sample a ciphertext: ct1−x ← E(pkb ).
1−x ; rE
• Sample a uniformly random session key: K1−x ← {0, 1}ℓ .
• Output CT := (ct0 , ct1 , K0 , K1 ).
This encryption algorithm uses randomness rEnc = (rE , rEb , K1−x ).
Dec (sk, CT ) :• If Kz = D(skz , ctz ), output x = z, otherwise x = 1 − z. Equivalently, output
W
x = z ⊕ ℓt=1 (Kz ⊕ D(skz , ctz ))t .
Theorem 3.6 (Weak Correctness). Let ℓ be a constant noticeably larger than log(1/ϵ)−1.
Suppose KEM is correct, then the above NCE has ϵ-decryption error.
Proof. Decryption error is caused either when x ̸= z and Kz = D(skz , ctz ) happen or x = z
and the underlying KEM scheme causes decryption error.

Pr[x ̸= Dec (sk, CT )]= Pr[z = x] Pr[x ̸= Dec (sk, CT ) |z = x] + Pr[z ̸= x] Pr[[x ̸= Dec (sk, CT ) |z ̸= x]
1= (Pr[Kx ̸= D(skz , ctx )|z = x] + Pr[K1−x = D(skz , ct1−x )|z ̸= x])
2

1
1
=
negl(λ) + ℓ ≤ ϵ22– 28 –

3.3. Weak Non-Committing Encryption
Theorem 3.7 (Weak Security). If KEM is an obliviously samplable key-encapsulation
mechanism, then NCE is weakly secure with respect to Leak = BEC0.5 .
Proof. We construct a tuple of simulators as follows.
SimGen(1λ ; rSimGen ) :• Generate two KEM key pairs: (pk0 , sk0 ) ← G(1λ ; rG,0 ) and (pk1 , sk0 ) ← G(1λ ; rG,1 ).
• Output a simulated public key pk := (pk0 , pk1 ).
SimEnc(rSimGen , x̃ ← BEC0.5 (x; rch ); rSimEnc ) :• Regenerate pk0 and pk1 from rSimGen .
• If x̃ = ⊥,– Execute the encapsulation twice: (ct0 , K0 ) ← E(pk0 ; rE,0 ) and (ct1 , K1 ) ←E(pk1 ; rE,1 ).
– Output a simulated ciphertext CT := (ct0 , ct1 , K0 , K1 ).
• If x̃ = x ̸= ⊥, just execute CT ← Enc(pk, x; rEnc ).
Open(rSimGen , rSimEnc , x, rch ) :• Set z := x ⊕ 1 ⊕ rch .2• If z = x (⇔ x̃ = ⊥),– Execute the invert sampling: (rG,1−z, rE,1−z) ← InvKEM (rG,1−z , rE,1−z ).
bb– Output simulated randomness:rGen := z, rG,z , rG,1−z
and rEnc := rE,x , rE,1−x, K1−x .
bb• If z ̸= x (⇔ x̃ ̸= ⊥),– Execute invert sampling for the key-generation: (rG,1−z) ← InvG (rG,1−z ).
b– Output simulated randomness: rGen := z, rG,z , rG,1−z
and rEnc .
b
Let A be a PPT adversary against weak security of NCE. The message is set to x ∈{0, 1}. We deﬁne the following sequence of experiments.
Real. Speciﬁcally, the experiment
Exp 0: This experiment is exactly the same as ExpWeak
NCE,Aproceeds as follows.

1. Sample a uniformly random bit z ← {0, 1}.
2. Generate a key pair of KEM: (pkz , skz ) ← G(1λ ; rG ).
Remind that rch = 1 ⇔ z = x means that message to the adversary is erased in BEC, and thus theencryption is secure.
2– 29 –

3.3. Weak Non-Committing Encryptionb λ ; r b ).
3. Obliviously sample a public key: pk1−z ← G(1G
4. Set pk := (pk0 , pk1 ) and rGen := (z, rG , rGb ).
5. Execute encapsulation: (ctx , Kx ) ← E(pkx ; rE ).
b 1−x ; rb ).
6. Obliviously sample a ciphertext: ct1−x ← E(pkE
7. Sample a uniformly random session key: K1−x ← {0, 1}ℓ .
8. Set CT := (ct0 , ct1 , K0 , K1 ) and rEnc := (rE , rEb , K1−x ).
9. Output of this experiment is out ← A(pk, CT, rGen , rEnc ).
Exp 1: This experiment is the same as Exp 0, except that the sampling z ← {0, 1} isreplaced to the followings:• Compute x̃ ← BEC(x; rch ).
• Set z := x ⊕ 1 ⊕ rch .
Since rch is sampled from B0.5 , z computed in Exp 1 is also uniformly random. Thus
Pr[out = 1] in Exp 0 and Exp 1 are the same.
Exp 2: This experiment is the same as Exp 1, except that if z = x, or equivalently x̃ = ⊥,oblivious sample of the public key, the ciphertext, and the session key pk1−z ←ℓb λ ; r b ), ct1−x ← E(pkb
G(1b ), K1−x ← {0, 1} is replaced to the followings:
1−x ; rE
G
• Generate public key by the key-generation: (pk1−z , sk1−z , ) ← G(1λ ; rG,1−z ),• Generate ciphertext and session key by the encapsulation: (ct1−x , K1−x ) ←E(pk1−x ; rE,1−x ).
• The randomness is inverted as (rG,1−z, rE,1−z) ← InvKEM (rG,1−z , rE,1−z ).
bb
We also rename (rG , rE ) to (rG,z , rE,x ).
Lemma 3.8. Assume the oblivious samplability of KEM, the diﬀerence of Pr[out =1] between Exp 1 and Exp 2 is negligible.
Exp 3: This experiment is the same as Exp 2, except that if z ̸= x, or equivalentlyb λ ; r b ) is replaced tox̃ = x ̸= ⊥, the oblivious sample of the public key pk1−z ← G(1G
the following:• Generate public key by the key-generation: (pk1−z , sk1−z , ) ← G(1λ ; rG,1−z ).
• The randomness is inverted as (rG,1−z) ← InvG (rG,1−z ).
b
We also rename rG to rG,z .
Lemma 3.9. Assume the oblivious samplability of public key, the diﬀerence ofPr[out = 1] between Exp 2 and Exp 3 is negligible.
– 30 –

3.4. Full-Fledged NCE from Weak NCE
Ideal
Now, Exp 3 is exactly the same as ExpWeak. Speciﬁcally, this experiment proceeds
NCE,A
as follows.

1. Generate two KEM key pairs: (pk0 , sk0 ) ← G(1λ ; rG,0 ) and (pk1 , sk0 ) ← G(1λ ; rG,1 ).
2. Set pk := (pk0 , pk1 ).
3. If x̃ = ⊥, execute the encapsulation twice: (ct0 , K0 ) ← E(pk0 ; rE,0 ) and (ct1 , K1 ) ←E(pk1 ; rE,1 ).
4. If x̃ = x ̸= ⊥, just execute Enc(pk, x; rEnc ).
5. Set CT := (ct0 , ct1 , K0 , K1 ).
6. Set z := x ⊕ 1 ⊕ rch .
7. If z = x (⇔ x̃ = ⊥),• Execute the invert sampling: (rG,1−z, rE,1−z) ← InvKEM (rG,1−z , rE,1−z ).
bb• Output simulated randomness:
and rEnc := rE,x , rE,1−x, K1−x .
rGen := z, rG,z , rG,1−zbb8. If z ̸= x (⇔ x̃ ̸= ⊥),• Execute invert sampling for the key-generation: (rG,1−z) ← InvG (rG,1−z ).
b• Output simulated randomness: rGen := z, rG,z , rG,1−z
and rEnc .
b
9. Output of this experiment is out ← A(pk, CT, rGen , rEnc ).
By combining the above lemma, the proof of Theorem 3.7 completes.

3.4

Full-Fledged NCE from Weak NCE

In this section, we amplify a weak NCE scheme into a full-ﬂedged one using conditionallyinvertible wiretap codes.
Construction. Let NCE = (Gen, Enc, Dec) be a weak NCE scheme which has ϵ-decryption
error and weak security with respect to BEC0.5 , and wiretap codes WC = (WC.Setup, WC.Encode,
WC.Decode) which is correct over receiver channel BSC≤ϵ and conditionally invertible
against the adversary channel BEC0.5 . We construct a full-ﬂedged NCE scheme NCE′ =(Gen′ , Enc′ , Dec′ ) as follows. Note that this construction includes the hybrid encryption
with one-time pad, thus the ampliﬁed scheme satisﬁes the non-committing security formessages that is chosen depending on the public key.
Gen′ (1λ ) :• Sample a public seed of the wiretap codes p ← WC.Setup(1λ ).
– 31 –

3.4. Full-Fledged NCE from Weak NCE• Generate a key pair of weak NCE (pk, sk) ← Gen 1λ ; rGen .
• Output (pk ′ , sk ′ ) := ((p, pk), sk).
The randomness for key generation rGen ′ is rGen .
Enc′ (pk ′ , m) :• Sample a key for one-time pad k ← {0, 1}µ .3• Encode the key as x ← WC.Encode(p, k; s) ∈ {0, 1}n .
• Compute CT ← Enc(pk, x; rEnc ).
• Output ciphertext CT ′ = (CT, m ⊕ k).
The randomness for encryption rEnc ′ is (rEnc , k, s).
Dec′ (sk ′ , CT ′ ) :• Parse CT ′ as (c1 , c2 ).
• Compute k = WC.Decode(p, Dec(sk, c1 )).
• Output m = c2 ⊕ k.
Ciphertext Expansion. The ciphertext expansion of NCE′ isciphertext expansion of NCE+ 1.
rate of WC(3.1)

Since the rate of the wiretap codes is constant, this ampliﬁcation increases ciphertext expansion only by a constant factor. Combining the ciphertext expansion given in
Section 4.5, we will estimate its concrete value for our scheme in Section 5.
Public-key Expansion. The public-key expansion of NCE′ ispublic-key expansion of NCE + o(1)(3.2)

because this ampliﬁcation only puts common random seed p into public-key, whose size is
independent to the message length, thus it dose not increase public-key expansion of theampliﬁed NCE scheme asymptotically.
Correctness. Due to the decryption error of NCE, each bit of the decrypted code word x
is ﬂipped with probability at most ϵ. The wiretap codes correct this error as shown below.
Theorem 3.10 (Correctness). If NCE has ϵ-decryption error, and WC is correct over BSC≤ϵ ,then NCE′ is correct.
3

Note that weak security of NCE requires the challenge message to be independent of the public key.
To address this issue, we use one-time pad in this ampliﬁcation.

– 32 –

3.4. Full-Fledged NCE from Weak NCE
Proof. The probability of NCE′ fails to decrypt is evaluated as
Pr[k ̸= WC.Decode(p, Dec(sk, Enc(pk, x)))]= Pr[k ̸= WC.Decode(p, BSC≤ϵ (WC.Encode(p, k; s)))]= negl(λ) .
Thus NCE′ is correct.
Security. We now show the non-committing security of NCE′ .
Theorem 3.11 (Security). If NCE is weakly secure with respect to BEC0.5 , and WC isinvertible conditioned on BEC0.5 , then NCE′ is secure.
Proof. We ﬁrst construct a simulator of NCE′ (Sim′ , Open′ ) from the simulator (SimGen, SimEnc,
Open) of NCE, and the inverter WC.Invert of WC.
Sim′ (1λ ) :• Sample p ← WC.Setup(1λ ).
• Generate pk ← SimGen(1λ ; rSimGen ).
• Sample k ← {0, 1}µ .
• Compute x̃ ← BEC0.5 (WC.Encode(p, 0µ ; s′ ); rch ′ ).
• Compute CT ← SimEnc(rSimGen , x̃; rSimEnc ).
• Set pk ′ = (p, pk), CT ′ = (CT, k).
• Output (pk ′ , CT ′ ).
Open′ (rSim , m) :• (s, rch ) ← WC.Invert(p, x̃, m ⊕ k).
• (rGen , rEnc ) ← Open(rSimGen , rSimEnc , WC.Encode(p, m ⊕ k; s), rch ).
• Output (rGen ′ , rEnc ′ ) = (rGen , (rEnc , m ⊕ k, s)).
Let A be an adversary against the security of NCE′ . We then deﬁne the following
experiments:
Exp 0 : This experiment is the same as ExpReal
NCE′ A . Speciﬁcally,
1. Sample p ← WC.Setup(1λ ).


2. Generate the key pair (pk, sk) ← Gen 1λ ; rGen .
3. Run the adversary to output plaintext m ← A(p, pk).
4. Sample k ← {0, 1}µ and encoded it as x ← WC.Encode(p, k; s).
5. Encrypt the codeword as CT ← Enc(pk, x; rEnc ).
– 33 –

3.4. Full-Fledged NCE from Weak NCE
6. Output of this experiment is out ← A((CT, m ⊕ k) , rGen , (rEnc , k, s)).
Exp 1 : In this experiment, we use the simulator (SimGen, SimEnc, Open) for NCE. The
ciphertext CT is simulated by SimEnc only given partial information of the messagex̃ ← Leak(x), where Leak = BEC0.5 and x ← WC.Encode(p, k; s) now. Speciﬁcally,
1. Sample p ← WC.Setup(1λ ).
2. Simulate the public key as pk ← SimGen(1λ ; rSimGen ).
3. Run the adversary to output plaintext m ← A(p, pk).
4. Sample k ← {0, 1}µ and encoded it as x ← WC.Encode(p, k; s).
5. Compute partial information x̃ ← BEC0.5 (x; rch ).
6. Simulate the ciphertext as CT ← SimEnc(rSimGen , x̃; rSimEnc ).
7. Explain the randomness for key generation and encryption as(rGen , rEnc ) ← Open(rSimGen , rSimEnc , WC.Encode(p, k; s), rch ).
8. Output of this experiment is out ← A((CT, m ⊕ k) , rGen , (rEnc , k, s)).
Exp 2 : In this experiment, we completely eliminate the information of k from the inputof SimEnc to simulate the ciphertext. Later WC.Invert determines the randomness s
used in the encode. Speciﬁcally,
1. Sample p ← WC.Setup(1λ ).
2. Simulate the public key as pk ← SimGen(1λ ; rSimGen ).
3. Run the adversary to output plaintext m ← A(p, pk).
4. Sample k ← {0, 1}µ , but the codeword is x ← WC.Encode(p, 0µ ; s′ ).
5. Compute partial information x̃ ← BEC0.5 (x; rch ′ ).
6. Simulate the ciphertext as CT ← SimEnc(rSimGen , x̃; rSimEnc ).
7. Invert the randomness for encode as (s, rch ) ← WC.Invert(p, x̃, k).
8. Explain the randomness for key generation and encryption as(rGen , rEnc ) ← Open(rSimGen , rSimEnc , WC.Encode(p, k; s), rch ).
9. Output of this experiment is out ← A((CT, m ⊕ k) , rGen , (rEnc , k, s)).
Exp 3 : In this experiment, we completely eliminate m from the ciphertext by switchingk to m ⊕ k. Speciﬁcally,
1. Sample p ← WC.Setup(1λ ).
2. Simulate the public key as pk ← SimGen(1λ ; rSimGen ).
3. Run the adversary to output plaintext m ← A(p, pk).
4. Sample k ← {0, 1}µ , but the codeword is x ← WC.Encode(p, 0µ ; s′ ).
– 34 –

3.4. Full-Fledged NCE from Weak NCE
5. Compute partial information x̃ ← BEC0.5 (x; rch ′ ).
6. Simulate the ciphertext as CT ← SimEnc(rSimGen , x̃; rSimEnc ).
7. Invert the randomness for encoding as (s, rch ) ← WC.Invert(p, x̃, m ⊕ k).
8. Explain the randomness for key generation and encryption as(rGen , rEnc ) ← Open(rSimGen , rSimEnc , WC.Encode(p, m ⊕ k; s), rch ).
9. Output of this experiment is out ← A((CT, k) , rGen , (rEnc , m ⊕ k, s)).
Note that the last experiment Exp 3 is identical to ExpIdeal
NCE′ A .
We show the diﬀerence between each experiments are negligible.
Lemma 3.12. If NCE is weakly secure with respect to BEC0.5 , the diﬀerence of Pr[out = 1]
in Exp 0 and Exp 1 is negligible.
This lemma directly follows from the weak security of NCE. Note that the message
encrypted by NCE is the key of one-time pad k, which is independent of the public key.
Lemma 3.13. If WC is invertible conditioned on BEC0.5 , the diﬀerence of Pr[out = 1] in
Exp 1 and Exp 2 is negligible.
By the conditional invertibility of WC, the following items are statistically indistinguishable.
• (BEC0.5 (WC.Encode(p, k; s); rch ), (s, rch ))• (BEC0.5 (WC.Encode(p, 0µ ; s′ ); rch ′ ), (s, rch ))where (s, rch ) is output of WC.Invert(p, BEC0.5 (WC.Encode(p, 0µ ; s′ ); rch ′ ), k)′′
The lemma follows because (CT ′ , rGen
, rEnc), and hence out in Exp 1 are computed fromthe former item, while those in Exp 2 are computed from the latter item.

Lemma 3.14. Pr[out = 1] is identical in Exp 2 and Exp 3.
This lemma holds unconditionally, because (k, m ⊕ k) and (m ⊕ k, k) distribute identically when k is sampled uniformly at random.
Combining the above lemmas, we complete the proof of Theorem 3.11.

– 35 –

Chapter 4
NCE with Constant
Ciphertext-Expansion
In this chapter, we show the main contribution of this thesis, construction of a noncommitting encryption scheme with constant ciphertext expansion. First, in section 4.1,
we give a brief idea to compress ciphertext of the scheme presented in section 3.1. Then,in section 4.2, we introduce obliviously samplable chameleon encryption, which is thecentral building block of the NCE scheme with constant ciphertext expansion. Section 4.3
and 4.4 shows the instantiations of obliviously samplable chameleon encryption based on
the DDH and LWE problem, respectively. Finally, we construct a weak NCE schemewith constant ciphertext expansion from obliviously samplable chameleon encryption insection 4.5. Note that we can obtain a full-ﬂedged NCE scheme with constant ciphertext
expansion via the transformation presented in section 3.4.

4.1

Idea Towards Constant Ciphertext-Expansion

We show how to achieve the ciphertext expansion O(1) by compressing the ciphertext ofNCElin . This is done by compressing the ﬁrst part of the ciphertext of NCElin , that is,!
B1,0 , . . . , Bn,0.
B1,1 , . . . , Bn,1
By this step, we compress it into just a single group element.
Compressing a matrix of group elements into a single group element. We
realize that we do not need all of the elements {Bi,b }i∈[n],b∈{0,1} to decrypt the ciphertext.
Although the receiver gets both Bi,0 and Bi,1 for every i ∈ [n], the receiver uses only Bi,zi .
ρiRecall that the receiver recovers the value of xi by checking whether Bi,z= Ki,zi holds.
iThis recovery of xi can be done even if the sender sends only Bi,xi , and not Bi,1−xi .
ρiThis is because, similarly to the equation HG (Bi,z) = Ki,zi , with overwhelming probi
ρiability, the equation HG (Bi,xi ) = Ki,zi holds if and only if zi = xi . For this reason, we can
36

4.1. Idea Towards Constant Ciphertext-Expansion
compress the ﬁrst part of the ciphertext on NCElin into (B1,x1 , . . . , Bn,xn ).
We further compress (B1,x1 , . . . , Bn,xn ) into a single group element generated by mulQ
tiplying them, that is, y = j∈[n] Bj,xj . In order to do so, we modify the scheme so thatthe receiver can recover xi for every i ∈ [n] using y instead of Bi,xi . Concretely, for everyi ∈ [n], the sender computes Ki,xi asY αKi,xi = HG 
Ai,xj i  ,j∈[n]where αj is the exponent of Bj,xj for every j ∈ [n] generated by the sender. The sender still
generates Ki,1−xi as a random ℓ bit string for every i ∈ [n]. In this case, with overwhelming
probability, the receiver can recover xi by checking whether Ki,zi = HG (y αi ) holds.
However, unfortunately, it seems diﬃcult to prove the security of this construction.
In order to delete the information of xi for indices i ∈ [n] such that zi = xi as in the
proof of NCElin , we have to change the distribution of Ki,1−xi from a random string toQαj) so that Ki,0 and Ki,1 are symmetrically generated. However, we cannot
HG ( j∈[n] Ai,1−ximake this change by relying on the DDH assumption since all αj are given to the adversary
as a part of the sender random coin. Thus, in order to avoid this problem, we further
modify the scheme and construct an NCE scheme NCE as follows.
The resulting NCE scheme NCE. In NCE, the receiver ﬁrst generates z ← {0, 1}n and{Ai,b }i∈[n],b∈{0,1} in the same way as NCElin . Moreover, instead of the sender, the receiver
obliviously generates Bi,b = g αi,b for every i ∈ [n] and b ∈ {0, 1}, and adds them into the
public key. Moreover, for every i ∈ [n], the receiver addsαρi
= Ai,zj,bi }j∈[n],b∈{0,1} s.t. (j,b)̸=(i,1−zi ){Bj,bto the public key. In order to avoid the leakage of the information of z from the public
key, for every i ∈ [n], we have to add
αj,b{Ai,1−z}i j∈[n],b∈{0,1} s.t. (j,b)̸=(i,zi )to the public key. However, the receiver cannot do it since the receiver generates Ai,1−zi
obliviously. Thus, instead, the receiver adds the same number of random group elements
into the public key. At the beginning of the security proof, we can replace them with
αj,b{Ai,1−z}by relying on the DDH assumption, and eliminate the ini j∈[n],b∈{0,1} s.t. (j,b)̸=(i,zi )
formation of z from the public key. For simplicity, below, we suppose that the public key
αj,bincludes {Ai,1−z}instead of random group elements.
i j∈[n],b∈{0,1} s.t. (j,b)̸=(i,zi )When encrypting a message m by NCE, the sender ﬁrst generates x ← {0, 1}n andQcomputes y = j∈[n] Bj,xj . Then, for every i ∈ [n], the sender computes Ki,xi asY αj,xKi,xi = HG 
Ai,xi j  = HG (y ρi )j∈[n]

– 37 –

4.1. Idea Towards Constant Ciphertext-Expansion
ααnjust multiplying Ai,x1,xi 1 , . . . , Ai,xn,xincluded in the pubic key. Recall that Ai,xi = g ρi . Noteiαi,1−zthat Ai,zi i is not included in the public key, but we do not need it to compute Ki,xi .
The sender generates Ki,xi as a random string for every i ∈ [n] as before. The resulting
ciphertext is!!
K1,0 , . . . , Kn,0y,.
K1,1 , . . . , Kn,1

The receiver can recover xi by checking whether Ki,zi = HG (y αi ) holds, and decrypt the
ciphertext.
By deﬁning the simulator appropriately, the security proof of NCE proceeds in a similar
way to that of NCElin . In NCE, for indices i ∈ [n] such that zi = xi , we can eliminatetheQ
αj,xj
information of xi . We can change Ki,1−xi from a random string to HGbyj∈[n] Ai,1−xi
αi,xi
relying on the fact that Ai,1−x
is indistinguishable from a random group element by thei
DDH assumption. By this change, Ki,0 and Ki,1 become symmetric and the ciphertext
loses the information of xi . Then, the remaining part of the proof goes through in asimilar way as that of NCElin except the following point. In NCE, the ﬁrst component ofQ
the ciphertext, that is, y = j∈[n] Bj,xj has the information of x. In order to deal with theQissue, in our real construction, we replace y with g r j∈[n] Bj,xj , where r ← Zp . Then, yno longer leaks any information of x. Moreover, after y is ﬁxed, for any x′ ∈ {0, 1}n , we
′ Q
can eﬃciently ﬁnd r′ such that y = g r j∈[n] Bj,x′ j . This is important to ensure that thesimulator of NCE runs in polynomial time.

4.1.1

Abstraction by Chameleon Encryption

We can describe NCE by using obliviously samplable chameleon encryption. Informally,
chameleon encryption is public-key encryption whose public key corresponds to the output
of a chameleon hash function, and whose secret key corresponds to the preimage of thatQ
hash. In the construction of NCE, g r j∈[n] Bj,xj can be seen as an output of the chameleon
hash function
H(x; r) = g r

Y

Bj,xj ,

j∈[n]

where {Bi,b }i∈[n],b∈{0,1} is the hash key. Moreover, by deﬁning chameleon encryption as
key encapsulation mechanism instead of public-key encryption1 , group elements contained in the public key and {Ki,b }i∈[n],b∈{0,1} together form multiple ciphertexts of anchameleon encryption scheme. Oblivious samplability of chameleon encryption makes it
possible to deal with the above stated issue of sampling random group elements instead
αj,bof {Ai,1−z}
for every i ∈ [n].
i j∈[n],b∈{0,1} s.t. (j,b)̸=(i,zi )1

In other words, we deﬁne it so that it satisﬁes a property called recyclability introduced by Garg andHajiabadi [GH18]. For more details, see Remark 2 in the next section.

– 38 –

4.2. Obliviously Samplable Chameleon Encryption
Relation with trapdoor function of Garg and Hajiabadi. We ﬁnally remark thatthe construction of NCE can be seen as an extension of that of trapdoor function (TDF)
proposed by Garg and Hajiabadi [GH18].
Q
If we do not add the random mask g r to y = j∈[n] Bj,xj , the key encapsulation partof a ciphertext of NCE, that is,!!
K1,0 , . . . , Kn,0y,K1,1 , . . . , Kn,1
is the same as an output of the TDF constructed by Garg and Hajiabadi. The majordiﬀerence between our NCE scheme and their TDF is the secret key. A secret key of their
TDF contains all discrete logs of {Ai,b }i∈[n],b∈{0,1} , that is, {ρi,b }i∈[n],b∈{0,1} . On the other
hand, a secret key of our NCE scheme contains half of them corresponding to the bit
representation of z, that is, {ρi,zi }i∈[n] . Garg and Hajiabadi already stated that their TDF
can be inverted with {ρi,zi }i∈[n] for any z ∈ {0, 1}n , and use this fact in the security proofof a chosen ciphertext security of a public-key encryption scheme based on their TDF. By
explicitly using this technique in the construction, we achieve non-committing property.
We observe that construction techniques for TDF seem to be useful for achieving NCE.
Encryption schemes that can recover an encryption random coin with a message in thedecryption process, such as those based on TDFs, is said to be randomness recoverable.
For randomness recoverable schemes, receiver non-committing property is suﬃcient toachieve full (that is, both sender and receiver) non-committing property. This is because
an encryption random coin can be recovered from a ciphertext by using a key generation
random coin.

4.2

Obliviously Samplable Chameleon Encryption

Chameleon encryption (CE) was proposed by Döttling and Garg [DG17b]. Since then,variant of chameleon encryption is appeared in studies on identity based encryption[DG17a,
DGHM18, BLSV18], secure MPC [CDG+ 17, GS18a], adaptive garbling schemes [GS18b,
GOS18], and so on. We deﬁne its obliviously samplable variant, obliviously samplable
chameleon encryption as a building block of NCE schemes with constant ciphertext expansion. Note that in order to give a uniﬁed view of oblivious samplability, the following
deﬁnition of obliviously samplable chameleon encryption is further modiﬁed from the previous deﬁnition [YKT19, YKXT20]. We show an instantiation of obliviously samplable
chameleon encryption based on the DDH problem in Section 4.3. The instantiation basedon the LWE problem is described in Section 4.4.
Deﬁnition 4.1 (Obliviously Samplable Chameleon Encryption). An obliviously samplable chameleon encryption scheme CE consists of the following PPT algorithms (G, H, E1 , E2 , D),
where key-generation algorithm G and hash function H compose a family of probabilistic– 39 –

4.2. Obliviously Samplable Chameleon Encryption
hash functions, (E1 , E2 ) is the associated encapsulation algorithm, and D is the algorithm
for its decapsulation.
G 1λ ; rG : Given the security parameter 1λ , it outputs a hash key hk.
H (hk, x; rH ) : Given a hash key hk and an input x ∈ {0, 1}n , it outputs a hash value y.
E1 (hk, (i, b); rE ) : Given a hash key hk, an index i ∈ [n], b ∈ {0, 1}, it outputs a ciphertextct.
E2 (hk, (i, b), y; rE ) : Given a hash key hk, an index i ∈ [n], b ∈ {0, 1}, and a hash value y,using the same randomness as E1 , it outputs K ∈ {0, 1}ℓ .
D (hk, (x, rH ), ct) : Given a hash key hk, a preimage of the hash function (x, rH ), and aciphertext ct, it outputs K ∈ {0, 1}ℓ .
An obliviously samplable CE scheme satisﬁes the following correctness, trapdoor collision
property, oblivious samplability of hash keys, and security with oblivious samplability.
Deﬁnition 4.2 (Correctness). We say that a obliviously samplable chameleon encryption
scheme is correct if for all x ∈ {0, 1}n and i ∈ [n], after execution of
hk ← G 1λ ; rG , y ← H (hk, x; rH ) ,ct ← E1 (hk, (i, xi ); rE ), K ← E2 (hk, (i, xi ), y; rE ),Pr[K ̸= D (hk, (x, rH ), ct)] = negl(λ)
holds, where xi denotes the i-th bit of x.
Deﬁnition 4.3 (All-in-One Security). We give an all-in-one security deﬁnition for obliviously samplable chameleon encryption, which is required to construct the proposed NCE
scheme. This deﬁnition contains non-committing security for the hash function of chameleon
encryption and oblivious samplability for the associated encryption scheme.
Consider the following PPT algorithms for simulation and opening of chameleon hashand oblivious sampling and invert of associated encryption (SimCH, OpenCH , Eb1 , InvCE ).
We introduce an obliviously sampling algorithms for ciphertexts.
• SimCH(1λ ; rSimCH ): Give a security parameter 1λ , it simulates a hash key hk and ahash value y.
• OpenCH (rSimCH , x): Give an input x to the chameleon hash, it outputs randomnessfor key-generation and hash (rG , rH ).
• Eb1 hk, (i, b); rEb : Given a hash key hk, an index i ∈ [n], and b ∈ {0, 1}, it outputs ab without using any randomness except ct
b itself.
ciphertext ct• InvCE (hk, rE ): Give a hash key hk and randomness for encryption rE , it outputs
randomness for oblivious sampling ciphertext rEb .
– 40 –

4.2. Obliviously Samplable Chameleon Encryption
For a chameleon encryption scheme and a stateful adversary A, we deﬁne two experiments as follows.
ExpReal
hk ← G 1λ ; rGy ← H (hk, x; rH )ct ← E1 (hk, (i, 1 − xi ); rE )K ← E2 (hk, (i, 1 − xi ), y; rE )rEb ← InvCE (hk, rE )
out = A hk, y, ct, K, rG , rH , rEb

ExpIdeal(hk, y) ← SimCH(1λ ; rSimCH )(rG , rH ) ← OpenCH (rSimCH , x)
ct ← Eb1 (hk, (i, (1 − xi ); rEb ))K ← {0, 1}ℓout = A hk, y, ct, K, rG , rH , rEb



We say that CE is secure if there exist above algorithms such that for all x ∈ {0, 1}n , i ∈{0, 1}, and for all PPT adversary A,AdvCE,A (λ) := Pr out = 1 in ExpReal − Pr out = 1 in ExpIdeal = negl(λ)
holds.
The above all-in-one security captures the required security notion at once. However
when we use it in the security proof of NCE scheme, it is useful to separate it into thechameleon hash part and the associated encryption part. We give separated security
deﬁnitions below.
Deﬁnition 4.4 (Security of Chameleon Hash). As an extension of hiding property ofchameleon hash function, we deﬁne a non-committing style security notion for chameleon
hash function. Note that this security notion is diﬀerent from the one usually deﬁned forchameleon hash functions. Usually, the hash algorithm with another input H(hk, x′ ; rH )plays the role of generating the hash value y in the ideal world. Non-committing property
is somewhat weaker than the usual chameleon property, still, it is enough for constructionof the NCE scheme.
Furthermore, this security notion captures oblivious samplability of the hash key. Thismeans that in the real world, we can sample a hash key without knowing trapdoor information contained in rSimCH which is used in the opening in the ideal world. So, thisprimitive can be called non-committing hash function with oblivious key generation, rather
than chameleon hash function.
ExpReal
hk ← G 1λ ; rGy ← H (hk, x; rH )out = A (hk, y, rG , rH )ExpIdeal(hk, y) ← SimCH(1λ ; rSimCH )(rG , rH ) ← OpenCH (rSimCH , x)
out = A (hk, y, rG , rH )We say that CE is secure if there exist above algorithms such that for all x ∈ {0, 1}n , andfor all PPT adversary A,AdvCE,A (λ) := Pr out = 1 in ExpReal − Pr out = 1 in ExpIdeal = negl(λ)
holds.
– 41 –

4.3. Instantiation based on the DDH Problem
Next, we focus on the obliviously samplable security of the associated encryption undersimulated chameleon hash.
Deﬁnition 4.5 (Oblivious Samplability of Associated Encryption). We say ciphertext ofthe chameleon encryption scheme is obliviously samplable (under simulated chameleonhash) if for any x ∈ {0, 1}n , i ∈ [n], and PPT adversary A, deﬁne two experiments asfollows.
ExpReal(hk, y) ← SimCH(1λ ; rSimCH )ct ← E1 (hk, (i, 1 − xi ); rE )K ← E2 (hk, (i, 1 − xi ), y; rE )rEb ← InvCE (hk, rE )
out = A hk, y, ct, K, rEb

ExpIdeal(hk, y) ← SimCH(1λ ; rSimCH )ct ← Eb1 (hk, (i, (1 − xi ); rEb ))K ← {0, 1}ℓout = A hk, y, ct, K, rEb

Then, we haveAdvCE,A (λ) := Pr out = 1 in ExpReal − Pr out = 1 in ExpIdeal = negl(λ) .
Remark 2 (On the Recyclability). The above syntax of chameleon encryption is diﬀerent
from that of original chameleon encryption proposed by Döttling and Garg [DG17b].
We deﬁne chameleon encryption to satisfy a property called recyclability introduced by
Garg and Hajiabadi [GH18], in which recyclability is deﬁned for one-way function withencryption, that is a similar primitive to chameleon encryption.
More speciﬁcally, in our deﬁnition, there are two encryption algorithms E1 and E2 . E1
outputs only a ciphertext and E2 outputs only a session key. In the original deﬁnition byDöttling and Garg, there is a single encryption algorithm that outputs the key encapsulation part and a message masked by the session key part at once. What is important hereis that, an output of E1 does not depend on a hash value y. This makes it possible torelate a single output of E1 with multiple hash values. (In other words, a single output of
E1 can be recycled for multiple hash values.) We need this property in the constructionof NCE and thus adopt the above deﬁnition.

4.3

Instantiation based on the DDH Problem

We show an instantiation of obliviously samplable chameleon encryption scheme based on
the DDH problem. The main idea for this construction is based on the original constructionof chameleon encryption proposed by Döttling and Garg [DG17b].

4.3.1

Preliminaries on the Decisional Diﬃe-Hellman Problem

We give a deﬁnition of the decisional Diﬃe-Hellman (DDH) assumption and its variants
used in the proof of Theorem 4.3. Below, we let G be a cyclic group of prime order p witha generator g.
– 42 –

4.3. Instantiation based on the DDH Problem
Let H = {HG : G → {0, 1}ℓ } be a family of universal hash functions for the groupelements. We use this hash function in the construction of chameleon encryption scheme
to compress the session key size to constant ℓ.
We start with the standard DDH assumption.
Deﬁnition 4.6 (Decisional Diﬃe-Hellman Assumption). We say that the DDH assumption holds if for any PPT adversary A,|Pr [A (g1 , g2 , g1ρ , g2ρ ) = 1] − Pr [A (g1 , g2 , u1 , u2 ) = 1]| = negl(λ)
holds, where g1 , g2 , u1 , u2 ← G and ρ ← Zp .
We also deﬁne a generalized version of the DDH assumption. This generalized version
is useful in the proof of oblivious samplability of the chameleon encryption scheme.
Deﬁnition 4.7 ( n-Generalized DDH Assumption). We say that the n-Generalized DDH
assumption holds if for any PPT adversary A,






|Pr A {gi }i∈[n] , {giρ }i∈[n] = 1 − Pr A {gi }i∈[n] , {ui }i∈[n] = 1 | = negl(λ)
holds, where gi , ui , ← G for all i ∈ [n] and ρ ← Zp .
Note that the 2-generalized DDH assumption is exactly same as the standard DDH
assumption. Moreover n-generalized DDH assumption with n ≥ 2 is equivalent to thestandard DDH assumption.
Lemma 4.1. Assume the DDH assumption holds, the n-generalized DDH assumption
also holds.
Proof. Let A be an adversary against the n-generalized DDH problem. We construct a
reduction algorithm A′ that solves the DDH problem.
At ﬁrst, the reduction algorithm receives (g1 , g2 , u1 , u2 ) where (u1 , u2 ) = (g1ρ , g2ρ ) or
2×(n−2)
uniformly random group elements. Then samples {(si , ti )}i∈{3,...,n} ← Zp
and set gi =

si ti
si ti
g1 g2 , ui = u1 u2 for i = 3, ..., n. The reduction algorithm executes A {gi }i∈[n] , {ui }i∈[n]and output its result.
We have!
!
!
g3 g4 . . . gn
1
log(g2 )s3 s4 . . . s nlog=,
u3 u4 . . . unlog(u1 ) log(u2 )t3 t4 . . . tn
where the ﬁrst logarithm is applied to each component, and the base of these logarithm
is g1 .
In case (u1 , u2 ) = (g1ρ , g2ρ ) holds, we have {gi }i∈[n] are uniformly and independently
random and ui = us1i ut2i = g1ρsi g2ρti = (g1si g2ti )ρ = giρ holds.
!
1log(g2 )In case (u1 , u2 ) are random group elements, The matrix
is nonlog(u1 ) log(u2 )singular with overwhelming probability. Therefore {gi }i∈[n] , {ui }i∈[n] are uniformly andindependently random with overwhelming probability.
– 43 –

4.3. Instantiation based on the DDH Problem
In each case, the reduction algorithm simulates the n-generalized DDH problem for A.
Thus it solves the DDH problem with the same but negligible loss of advantage as A.

4.3.2

Construction

We construct a chameleon encryption scheme CE = (G, H, E1 , E2 , D) based on the hardnessof the DDH problem.
Let G be a cyclic group of order p with a generator g. The description of the group
G is generated in G and shared among other algorithms with its generator g. Strictly
speaking, the randomness used to generate the group description should be described inrG . We omit is because this does not matter if the group is oblivious samplable.
In the construction, we use a universal hash family H = {HG : G → {0, 1}ℓ }. Below,
let HG be a hash function sampled from H uniformly at random, and it is also shared to
all the algorithms implicitly.
G 1λ ; rG :• For all i ∈ [n] and b ∈ {0, 1}, sample gi,b ← G.
!!
g1,0 , . . . , gn,0
• Output hk := g,.
g1,1 , . . . , gn,1
The randomness used in this algorithm is rG :=!
g1,0 , . . . , gn,0.
g1,1 , . . . , gn,1

H (hk, x; rH ) :• Sample r ← Zp .
• Outputy = grYgi,xi .

i∈[n]

The randomness used in this algorithm is rH := r.
E1 (hk, (i, b); rE ) :• Parse hk as

g1,0 , . . . , gn,0g,
g1,1 , . . . , gn,1!!
.

• Sample ρ ← Zp and compute c := g ρ .
• Compute ci,b := (gi,b )ρ and ci,1−b := ⊥.
• For all j ∈ [n] such that j ̸= i , compute cj,0 := (gj,0 )ρ and cj,1 := (gj,1 )ρ

– 44 –

4.3. Instantiation based on the DDH Problem• Outputct :=c1,0 , . . . , cn,0c,
c1,1 , . . . , cn,1!!
.

E2 (hk, (i, b), y; rE ) :• Output K ← HG (y ρ ).
The randomness commonly used in the above two algorithm is rE := ρ.
D (hk, (x, rH ), ct) :!!
c1,0 , . . . , cn,0• Parse ct as c,.
c1,1 , . . . , cn,1
 Q
• Output K ← HG cr i∈[n] ci,xi .

Size of Parameters The group elements is represented in λ bit string. The length of
the hash key and ciphertext are both (2n + 1)λ.
Theorem 4.2 (Correctness). This DDH-based chameleon encryption scheme is correct.
Proof. Since the hash function on the group HG is common for all algorithm, it is enoughto show the equivalence of the inputs to HG in E2 and D, that is examined as

ρ
Y
Y
Y
y ρ = g r
gi,xi  = (g ρ )r
(gi,xi )ρ = cr
ci,xi .
i∈[n]

i∈[n]

i∈[n]

Theorem 4.3. This obliviously samplable chameleon encryption scheme is secure assuming the hardness of the DDH problem.
Proof. First, we construct algorithms appear in the security deﬁnition.
SimCH(1λ ; rSimCH ) :• For all i ∈ [n], and b ∈ {0, 1}, sample αi,b ← Zp and set gi,b := g αi,b .
• Sample r ← Zp and compute y = g r .
!!
g1,0 , . . . , gn,0
• Output hk := g,and y.
g1,1 , . . . , gn,1
The randomness used in this algorithm is rSimCH :=OpenCH (rSimCH , x) :– 45 –! !
α1,0 , . . . , αn,0,r .
α1,1 , . . . , αn,1

4.3. Instantiation based on the DDH Problem• Recompute gi,b = g αi,b for all i and b.
• OutputrG :=g1,0 , . . . , gn,0
g1,1 , . . . , gn,1!
and rH := r −Xαi,xi .

i∈[n]


Eb1 hk, (i, b); rEb :• Set ci,1−b := ⊥, and sample c ← G and ci,b ← G.
• For all j ∈ [n] such that j ̸= i, sample cj,0 ← G and cj,1 ← G.
!!
c1,0 , . . . , cn,0
• Output ct := c,.
c1,1 , . . . , cn,1
The randomness used in this algorithm is rEb =c1,0 , . . . , cn,0c,
c1,1 , . . . , cn,1!!
.

InvCE (hk, rE ) :• Recompute c and ci,b for all i ∈ [n], b ∈ {0, 1} from gi,b and ρ in the same way
as E1 .
!!
c1,0 , . . . , cn,0
• Output rEb := c,.
c1,1 , . . . , cn,1Lemma 4.4 (Non-Committing Security of Hash). The chameleon hash function in theabove chameleon encryption scheme satisﬁes Deﬁnition 4.4 unconditionally.
Proof. To proof this lemma, we need to check the distribution of (hk, y, rG , rH ) is identicalin the real and ideal experiments. Especially, it is enough to check the randomness (rG , rH )is identically distributed and (hk, y) is determined from these randomness.
The randomness for key generation rG appears in the real experiment is random 2ngroup elements gi,b . In the ideal experiment, the group elements gi,b are computed fromtheir uniformly random exponent αi,b , which are eventually uniformly random group elements. Thus rG distributes identically in the both experiments. Since The hash key hk isdetermined by rG , it is also identically distributed in the experiments.
The randomness for hash rH is sampled from Zp in the real experiment. In the idealPexperiment, rH = r − i∈[n] αi,xi where r is uniformly random, hence rH is also uniformly
random and distributed identically to the real experiment. Since we can compute y fromhk, x, rH asYP
y = g r = g r− i∈[n] αi,xi
gi,xi = H(hk, x; rH )i∈[n]in the ideal experiment, thus y is also identically distributed.

– 46 –

4.4. Instantiation based on Lattices
Lemma 4.5 (Oblivious Samplability of Ciphertext). Assume the 2n + 1-generalized DDH
problem is hard, the associated encryption part of the chameleon encryption scheme satisﬁes the oblivious samplability (Deﬁnition 4.5).
Proof. Let A be an adversary that attacks the oblivious samplability of the chameleon
encryption. We construct a reduction algorithm A′ that solves the 2n + 1-generalized
DDH problem.
Given the generalized DDH instance {gi∗ }i∈[2n+1] , {u∗i }i∈[2n+1] , the reduction algorithm simulates hk, y, ct, K, rEb as follows.
∗
1. Set g := g1∗ and (g1,0 , . . . , gn,0 , g1,1 , . . . , gn,1 ) := (g2∗ , . . . , g2n) except gi,xi is uniformly!!
g1,0 , . . . , gn,0
sampled. The hash key is set to hk := g,.
g1,1 , . . . , gn,1∗
2. The hash value is set to y := g2n+1.
∗∗
3. Set c = u∗1 , and (c1,0 , . . . , cn,0 , c1,1 , . . . , cn,1 ) := (u2 , . . . , u2n ) except ci,xi is set to ⊥.
!!
c1,0 , . . . , cn,0The ciphertext is set to ct := c,.
c1,1 , . . . , cn,1

4. The session key is set to K := HG (u∗2n+1 ).
5. The inverted randomness for encryption rE is set to the same as ct.

The reduction algorithm executes A with input hk, y, ct, K, rEb and output its result.

In case the received tuple {gi∗ }i∈[2n+1] , {u∗i }i∈[2n+1] is the generalized DDH instance,
i.e. it satisﬁes u∗i = gi∗ ρ for all i ∈ [2n + 1], the reduction algorithm perfectly simulates
the view of A in the real experiment of oblivious samplability.
In case the received tuple is uniformly and independently random, the reduction algorithm simulates the view of A in the ideal experiment of oblivious samplability except
the session key K is hash of a random group element, not uniformly random string. Thisgap closes if we choose the hash HG to satisﬁes that if its input is uniformly random, its
output is also uniformly random. More concretely, we can use a universal hash family as
HG .
Remind that 2n + 1-generalized DDH problem is as hard as the DDH problem.
Combining the above two lemma, the proof of Theorem 4.3 completes.

4.4

Instantiation based on Lattices

We propose a lattice-based construction of obliviously samplable CE. The public-Key
length of the proposed scheme is λ · poly(log λ), which is smaller than O(λ2 ) of the construction from the DDH problem.
– 47 –

4.4. Instantiation based on Lattices
The construction is similar to the construction of hash encryption from LWE proposedby Döttling et al. [DGHM18]. However we need a super-polynomially large modulus Zq
for the scheme to satisfy correctness. Although security of the hash encryption is claimed
to be proved from a valiant of the LWE assumption, called extended-LWE, we prove thesecurity directly from the LWE assumption.
Before describing our construction, we recall preliminaries on lattices.

4.4.1

Preliminaries on Lattices

Notations Let A, B be matrices or vectors. [A|B] and [A; B] denotes concatenationof columns and rows respectively. A\i denotes the matrix obtained by removing the i-th
column of A.
The n-dimensional Gaussian function with parameter s is deﬁned as
ρs (x) := exp(−π∥x∥2 /s2 ).
For positive real s and countable set A, the discrete Gaussian distribution DA,s is deﬁnedbyXρs (y).
DA,s (x) = ρs (x)/y∈A

We note that, if s = ω(log m),
Prr←DZm ,s√[∥r∥ ≤ s m] ≥ 1 − 2−m+1 .

(See [MR07].)
Parameters. We let n = λ, m = O(n log q) (e.g., m = 2n log q), q = 2poly(log λ) . Let χ be√
the discrete Gaussian distribution over Z with parameter s = ω( m log n), that is, DZ,s .
Rounding function round : Zq → {0, 1} is deﬁned as round(v) = ⌊2v/q⌉. If input for
round is a vector v ∈ Zℓq , the rounding is applied to each component. Let ℓ be a constant.
Deﬁnition 4.8 ((Decisional) Learning with Errors [Reg05]). The LWE assumption withrespect to n dimension, m samples, modulus q, and error distribution χ over Zq statesthat for all PPT adversary A, we have
Pr[A(A, S T A + E) = 1] − Pr[A(A, B) = 1] = negl(λ) ,m×ℓwhere A ← Zn×m
, S ← Zn×ℓ
, B ← Zm×ℓ.
qq ,E ← χq

Deﬁnition 4.9 (Lattice Trapdoor [GPV08, MP12]). There exists following PPT algorithms TrapGen and Sample.
TrapGen(1λ ) : Output a matrix AT ∈ Zn×m
together with its trapdoor T .
q
Sample(AT , T , u, s) : Given a matrix AT with its trapdoor T , a vector u ∈ Znq , and aparameter s, output a vector r ∈ Zm .
– 48 –

4.4. Instantiation based on Lattices
These algorithms satisfy the following two properties.
1. AT is statistically close to uniform in Zn×m.
q√
2. If s ≥ ω( m · log n), then r ∈ Zm output by Sample(AT , T , u, s) is statisticallyclose to DZm ,s conditioned on r ∈ Λu (AT ) := {r ∈ Zm | AT r ≡ u (mod q)}.

4.4.2

Construction

We construct an obliviously samplable CE scheme from the LWE problem on superpolynomially large modulus. Note that only in this section, we denotes the length of x by
|x| = N .
G 1λ ; rG :• Sample+m)
A ← Zn×(N.
q• Output hk := A.
The randomness used in this algorithm is rG := A.
H (hk, x; rH ) :m• Sample r ∈ Zm
q according to distribution RH = χ .

• Output
y := A · [x; r] ∈ Znq .
The randomness used in this algorithm is rH := r.
E1 (hk, (i, b); rE ) :• Sample S ← Zn×ℓand E ← χℓ×(N +m) .
q• Output+m−1)
ct := S T A\i + E\i ∈ Zℓ×(N.
qE2 (hk, (i, b), y; rE ) :• Compute v = S T (y − b · ai ) + ei , where ai and ei are the i-th rows of A andE.
• Output K := round(v).
The randomness commonly used in the above two algorithm is rE := (S, E).
D (hk, (x, rH ), ct) :• Compute v ′ = ct · [x\i ; r].
• Output K := round(v ′ ).
– 49 –

4.4. Instantiation based on Latticesℓ×(N +m)

Size of Parameters The ciphertext space of this chameleon encryption is Zq,
poly(log λ)where q = 2, ℓ = O(1), m = O(n log q) = λ · poly(log λ). We set N = O(λ), i.e.,
when weak NCE is constructed from this chameleon encryption scheme, it can encrypt
message of length O(λ). Thus the length of ciphertexts is|ct| = poly(log λ) · O(1) · (O(λ) + λ · poly(log λ)) = λ · poly(log λ).
The length of the hash key is|hk| = poly(log λ) · λ · (O(λ) + λ · poly(log λ)) = λ2 · poly(log λ).
Theorem 4.6 (Correctness). This LWE-based chameleon encryption scheme is correct.
Proof. Let ∆ := vj − vj′ , where vj and vj′ are the j-th component of the inputs to therounding function in the computation of E2 and D respectively.
∆=
sj T (y − xi · ai ) + ei,j − ctj · [x\i ; r]
= sj T (A · [x; r] − xi · ai ) + ei,j − sj T A\i + e\i,j [x\i ; r]

= ei,j − e\i,j [x\i ; r]≤ ∥ej ∥ · ∥[x; r∥√√≤ s N + m · N + s2 m ≤ s2 (N + m),
holds with overwhelming probability. The probability of decryption error on j-th bit isbounded by
Pr[round(vj ) ̸= round(vj′ )] ≤ 2∆/q = negl(λ) ,which is negligible since the modulus q is super-polynomially large. Thus, by taking theunion bound for all |v| = ℓ bits, the probability of decryption error is bounded by
Pr[round(v) ̸= round(v ′ )] ≤ 2ℓ∆/q = negl(λ) .

Theorem 4.7. This obliviously samplable chameleon encryption scheme is secure assuming the hardness of the LWE problem.
Proof. First, we construct algorithms appear in the security deﬁnition.
SimCH(1λ ; rSimCH ) :, T ) ← TrapGen(1λ ).
and (AT ∈ Zn×m
• Sample R ← Zn×Nq
q
• Sample y ← Znq .
• Output hk := A = [R | AT ] and y.
The randomness used in this algorithm is rSimCH := (R, T , y).
– 50 –

4.4. Instantiation based on Lattices
OpenCH (rSimCH , x) :• Set y ′ := y − Rx.
• Using the lattice trapdoor, sample a short vectorr ← Sample(AT , T , y ′ , s).
• Output rG := A and rH := r.

Eb1 hk, (i, b); rEb :• Sample and output+m−1).
ct ← Zℓ×(NqThe randomness used in this algorithm is rEb = ct.
InvCE (hk, rE ) :ℓ×(N +m−1)• Recompute ct := S T A\i + E\i ∈ Zq.

• Output rEb := ct.
Lemma 4.8 (Non-Committing Security of Hash). The chameleon hash function in theabove chameleon encryption scheme satisﬁes the security in Deﬁnition 4.4 unconditionally.
Proof. This directly follows form the properties of lattice trapdoor. First, R distributes
uniformly at random, and the distribution of AT output by TrapGen(1λ ) is also statisticallyclose to uniform. Thus the entire hash key generated by the simulator is statisticallyindistinguishable from uniformly random matrix. This is the same distribution as thehash key generated by the key generation algorithm.
Second, the opened randomness for the hash rH for x, H(hk, x; rH ) = y holds, because
the lattice trapdoor samples r such that AT r ≡ y ′ (mod q) where y ′ = y − Rx mod q.
Moreover the distribution of r is statistically close to χm conditioned on y ≡ Rx + AT r(mod q).
Lemma 4.9 (Oblivious Samplability of Ciphertext). Assume the LWE problem is hard,
the associated encryption part of the chameleon encryption scheme satisﬁes the oblivious
samplability (Deﬁnition 4.5).
Proof. Let A be an adversary that attacks the oblivious samplability of the chameleon
encryption. We construct a reduction algorithm A′ that breaks the LWE assumption with
(N + m) samples by using A as follows:n×(N +m)ℓ×(N +m)
1. A′ receives A = [R | AT ] ∈ Zq
, B ∈ Zq
, where B is either S T A+E
or uniformly random.
– 51 –

4.4. Instantiation based on Lattices
2. A′ setsa′ := (2xi − 1) ai − A\i [x\i ; r] ,R′ := [a1 | · · · | ai−1 | a′ | ai+1 | · · · | aN ].
Remind that the matrix R′ is the same as the received matrix R except for the i-th
column is replaced by vector a′ . Furthermore, A′ set s
hk := [R′ | AT ], y := hk · [x; r], ct := B\i ,K := round(bi ), and rEb := ct.
3. Finally, A′ returns A(hk, y, ct, K, rEb ).
In the LWE case, that is, B = S T A + E and bi = S T ai + ei , A′ statistically simulates
the real experiment of the oblivious samplability:
1. The hash key hk = [R′ | AT ] generated by the reduction perfectly simulates the hash
key since the only diﬀerent element, i-th column of R′ is also distributes uniformly
random.
2. The distribution of ct is perfectly correct.
3. The distribution of K = round(bi ) is also perfectly correct. This is because by our
reduction algorithm, we have y = H(hk, x; r) = hk · [x; r] = A\i [x\i ; r] + xi a′ . Thus,in the computation of K ← E2 (hk, (i, 1 − xi ), y; rE ), we computevi = S T (y − (1 − xi ) · a′ ) + ei
= S T (A\i [x\i ; r] + xi a′ − (1 − xi ) · a′ ) + ei
= S T (A\i [x\i ; r] + (2xi − 1)a′ ) + ei
= S T A\i [x\i ; r] + (2xi − 1)(2xi − 1) ai − A\i [x\i ; r]
= S T A\i [x\i ; r] + ai − A\i [x\i ; r] + ei



+ ei

= S T ai + ei = bi ,where we use the fact (2xi − 1)(2xi − 1) = 1 for xi ∈ {0, 1} to move forth line toﬁfth line. Therefore, K = round(vi ) = round(bi ) has the correct distribution.
Also in the random case, A′ perfectly simulates the ideal experiment of the oblivious
samplability.
Therefore, assuming the LWE assumption, the associated encryption satisﬁes oblivious
samplability.
Combining the above two lemma, the proof of Theorem 4.7 completes.

– 52 –

4.5. Construction of Weak NCE

4.5

Construction of Weak NCE

In this section, we show a construction of weak NCE scheme NCE based on an obliviously
samplable chameleon encryption scheme CE. The constructed weak NCE scheme canencrypt n bit message. It satisﬁes weak security with respect to Leak = BEC0.5 . Decryption
error of this scheme is ϵ, where we can set ϵ to be arbitrarily small constant by appropriately
choosing the constant parameter ℓ; we require that ϵ ≥ 1/2ℓ+1 + negl(λ). Its ciphertext
expansion is constant, 2ℓ + o(1).
This construction is similar to the construction from obliviously samplable KEM described in section 3.3.2. It is also similar to the construction of trapdoor function proposed
by Garg and Hajiabadi [GH18].
Gen 1λ ; rGen :• Sample a uniformly random string z ← {0, 1}n .
• Generate a hash key: hk ← G 1λ ; rG .
• For all i ∈ [n] and b ∈ {0, 1}, compute and obliviously sample ciphertexts:E (hk, (i, b); r ) (if b = z )1Eiicti,b ←.

Eb1 hk, (i, b); rb(otherwise)Ei• Output
pk :=ct1,0 , . . . , ctn,0hk,
ct1,1 , . . . , ctn,1!!
and sk := (z, (rE1 , . . . , rEn )) .

(4.1)





The key generation randomness rGen is rG , z, {rEi }i∈[n] , rEib i∈[n] .
Enc(pk, x ∈ {0, 1}n ; rEnc ) :• Parse public key pk as the equation 4.1.
• Compute the hash function: y ← H(hk, x; rH ).
• For all i ∈ [n] and b ∈ {0, 1}, compute the decapsulation or sample uniformly
random session keys:D (hk, (x, r ), ct ) (if b = x )Hi,bi
Ki,b ←.
{0, 1}ℓ(otherwise)• Output
CT :=K1,0 , . . . , Kn,0y,K1,1 , . . . , Kn,1

– 53 –

!!
.

(4.2)

4.5. Construction of Weak NCEThe encryption randomness rEnc is rH , {Ki,1−xi }i∈[n] .
Dec (sk, CT ) :• Parse sk and CT as the equations 4.1 and 4.2, respectively.
• For all i ∈ [n], compute

z
i
xi :=
1 − zi(if Ki,zi = E2 (hk, (i, zi ), y; rEi )).

(otherwise)• Output x.
Ciphertext Expansion. Ciphertext length of this scheme is |CT | = |y| + 2nℓ, wherelength of output of the chameleon hash |y| does not depend on n. Therefore ciphertext
expansion of this scheme is|CT | /n = 2ℓ + o(1).
Public-key Expansion. Public-key length is |hk| + 2n |ct|.
Next, we show that NCE is a weak NCE scheme. Concretely, we show that NCE has
ϵ-decryption error and satisﬁes weak security with respect to BEC0.5 .
Theorem 4.10 (Weak Correctness). Let ℓ be a constant noticeably larger than log(1/ϵ)−
1. If CE satisﬁes correctness, then NCE has ϵ-decryption error.
Proof. Let x ∈ {0, 1}n be a message encrypted by NCE and z ∈ {0, 1}n a random string
sampled when generating a key pair of NCE.
We fail to decrypt xi if the underlying chameleon encryption causes correctness error when zi = xi , or uniformly random ℓ bit string Ki,1−zi accidentally coincides withE2 (hk, (i, zi ), y; rEi ) when zi ̸= xi . The probability of the former is negligible since CE iscorrect, and that of the later is 1/2ℓ . Thus, the probability of failure to decrypt xi isevaluated as
Pr [xi ̸= (Dec (sk, CT ))i ]"#
zi = xi ∧ D hk, (x, r), cti,xi ̸= E2 hk, (i, zi ), y; rEi= Pr∨ zi ̸= xi ∧ Ki,1−xi = E2 hk, (i, zi ), y; rEi


1
1
=
negl(λ) + ℓ ≤ ϵ .
22Theorem 4.11 (Weak Security). If CE is an obliviously samplable CE scheme, then NCE
is weakly secure with respect to Leak = BEC0.5 .
Proof. We construct a tuple of simulators as follows.
– 54 –

4.5. Construction of Weak NCE
SimGen 1λ ; rSimGen :• Generate (hk, y) ← SimCH(1λ ; rSimCH ).


• For all i ∈ [n] and b ∈ {0, 1}, compute ciphertexts: cti,b ← E1 hk, (i, b); rEi,b .
!!
ct1,0 , . . . , ctn,0• Output a simulated public key pk := hk,.
ct1,1 , . . . , ctn,1

The randomness used in simulating public key rSimGen is rSimCH , {rEi,b }i∈[n],b∈{0,1} .
SimEnc(rSimGen , xI ← BEC0.5 (x; rch ); rSimEnc ) :• Regenerate (hk, y) from rSimGen .

• For all i ∈/ I, compute Ki,b ← E2 hk, (i, b), y; rEi,b for b ∈ {0, 1}.
• For all i ∈ I, compute
Ki,b ←

E

2

hk, (i, b), y; rEi,b

{0, 1}ℓ(if b = xi ).

(otherwise)• Output a simulated ciphertext CT :=K1,0 , . . . , Kn,0y,K1,1 , . . . , Kn,1!!

The randomness used in simulating ciphertext rSimEnc is ({Ki,1−xi }i∈I ). zOpen(rSimGen , rSimEnc , x, rch ) :• Open randomness (rG , rH ) ← OpenCH (rSimCH , x).
• Set z = x ⊕ 1n ⊕ rch .
• For all i ∈ [n], invert randomness to oblivious sampling rEi,1−z← InvCE (hk, rEi,1−zi ).
bi• Output simulated randomnesson
rGen := rG , z, rEi,zi i∈[n] , rEi,1−z
b
i

i∈[n]





and rEnc := rH , {Ki,1−xi }i∈[n] .

Let A be a PPT adversary against weak security of NCE and x ∈ {0, 1}n . We deﬁne
the following sequence of experiments.
Real. Speciﬁcally, the experiment
Exp 0: This experiment is exactly the same as ExpWeak
NCE,Aproceeds as follows.

1. Generate hk ← G 1λ ; rG and z ← {0, 1}n .

2. For all i ∈ [n] and b ∈ {0, 1}, computeE (hk, (i, b); r ) (if b = z )1Eiicti,b ←.
Eb1 (hk, (i, b); rb ) (otherwise)Ei– 55 –

4.5. Construction of Weak NCE
3. Setpk :=ct1,0 , . . . , ctn,0hk,
ct1,1 , . . . , ctn,1

!!







and rGen := rG , z, {rEi }i∈[n] , rEib i∈[n] .

4. Compute y ← H(hk, x; rH ).
5. For all i ∈ [n] and b ∈ {0, 1}, computeD (hk, (x, r), ct ) (if b = x )i,bi
Ki,b ←
{0, 1}ℓ(otherwise) .
6. SetCT :=K1,0 , . . . , Kn,0y,K1,1 , . . . , Kn,1!!

and rEnc := rH , {Ki,1−xi }i∈[n] .

7. Output of this experiment is out ← A(pk, CT, rGen , rEnc ).
Exp 1: In this experiment, instead of sampling z ← {0, 1}n , we ﬁrst compute xI ←BEC0.5 (x; rch ) and set z = x ⊕ 1n ⊕ rch .
nNotice that z distributes uniformly at random over {0, 1}n also in Exp 1 since rch ← B0.5.
Thus, Pr[out = 1] in Exp 1 is identical to that in Exp 0. Also notice that i ∈ I iﬀ zi ̸= xi
holds by the setting of z.

Exp 2: This experiment is the same as Exp 1 except for executing (hk, y) ← SimCH(1λ ; rSimCH )and (rG , rH ) ← OpenCH (rSimCH , x) instead of hk ← G 1λ ; rG , y ← H (hk, x; rH ).
From the security of the chameleon hash in CE, the diﬀerence of Pr[out = 1] between
Exp 1 and Exp 2 is negligible.
In the following experiments, we eliminate information of xi for i ∈/ I from the ciphertext CT = (y, {Ki,b }i∈[n],b∈{0,1} ).
Exp 3.j: This experiment is deﬁned for j = 0, . . . , n. Exp 3.j is the same experiment as
Exp 2 except that we modify the procedures 2. and 5. as follows.

2. For all i ≤ j, compute cti,b for b ∈ {0, 1} as cti,b ← E1 hk, (i, b); rEi,b . Then,
execute invert sampling as rEib ← InvCE (hk, rEi,1−zi ).
For all i > j, compute them in the same way as Exp 2.
5. For all i ≤ j, if i ∈/ I, compute Ki,0 , Ki,1 as Ki,xi ← D (hk, (x, rH ), cti,xi ) and
Ki,1−xi ← E2 hk, (i, 1 − xi ), y; rEi,1−xi .
For all i ≤ j, if i ∈ I, compute them in the same way as Exp 2.
Also, for all i > j, compute them in the same way as Exp 2 regardless of whetheri ∈ I or not.
– 56 –

4.5. Construction of Weak NCE
Note that Exp 3.0 is exactly the same as Exp 2.
Lemma 4.12. If CE satisﬁes security with oblivious samplability, the diﬀerence of Pr[out =1] between Exp 3.(j − 1) and Exp 3.j is negligible for every j ∈ [n].
Proof. Using A, we construct a reduction algorithm A′ which attacks the oblivious samplability of associated encryption in CE with respect to x and j.
What diﬀer in Exp 3.(j − 1) and Exp 3.j are ctj,1−zj and Kj,1−xj if j ∈/ I. For j ∈ I,
only ctj,1−zj diﬀer. We consider the following two cases.
Case 1. j ∈/ I (zj = xj ) : ctj,1−zj is output of Eb1 hk, (j, 1 − zj ); rEj
in Exp 3.(j − 1) orb

E1 hk, (j, 1 − zj ); rEj,1−zj in Exp 3.j. Kj,1−xj is uniformly random string or output
of E2 hk, y; rEi,1−xj , respectively. In this case, the reduction algorithm A′ , given∗(hk∗ , y ∗ , ct∗ , K ∗ , rEb∗ ), embed hk = hk∗ , y = y ∗ , ctj,1−zj = ct∗ , Kj,1−xj = K ∗ , rEj
b = rEband simulate other parts of the experiment.
bin Exp 3.(j−Case 2. j ∈ I (zj ̸= xj ) : ctj,1−zj is output of either E1 hk, (j, 1 − zj ); rEjb1) or E1 hk, (j, 1 − zj ); rEj,1−zj in Exp 3.j. Kj,xj = D(hk, (x, rH ), ctj,xj ) is computedin the same way in both experiments.
In this case, the reduction algorithm A′ , given (hk∗ , y ∗ , ct∗ , K ∗ , rEb∗ ), embed hk =∗hk∗ , y = y ∗ , ctj,1−zj = ct∗ , rEj
b = rEb and simulate other parts of the experiment.
In both cases, A′ returns output out ← A(pk, CT, rGen , rEnc ).
Depending on A′ playing in either ExpReal or ExpIdeal , A′ perfectly simulates Exp 3.(j−1)
or Exp 3.j for A.
Hence assuming the associated encryption of the chameleon encryption scheme satisﬁes
security, the diﬀerence of Pr[out = 1] in Exp 3.(j − 1) and Exp 3.j is negligible.

Exp 4: This experiment is the same as Exp 3.n except that Ki,xi is generated by Ki,xi ←E2 hk, (i, xi ), y; rEi,xi instead of Ki,xi ← D (hk, (x, rH ), cti,xi ) for every i ∈ [n].
From the correctness of chameleon encryption scheme, the diﬀerence of Pr[out = 1]
between Exp 3.n and Exp 4 is negligible.
Ideal
in which Leak = BSC0.5 is used. In
This experiment is exactly the same as ExpWeak
NCE,Adetail, the experiment proceeds as follows.
1. Generate (hk, y) ← SimCH(1λ ; rSimCH ).

2. For all i ∈ [n], b ∈ {0, 1}, compute cti,b ← E1 hk, (i, b); rEi,b .
3. Setpk :=ct1,0 , . . . , ctn,0hk,
ct1,1 , . . . , ctn,1– 57 –!!
.

4.6. Size and Expansion of the NCE Schemes
4. For all i ∈/ I, compute Ki,b ← E2 hk, (i, b), y; rEi,b for b ∈ {0, 1}.
5. For all i ∈ I, compute
Ki,b ←

E

2

hk, (i, b), y; rEi,b(if b = xi ){0, 1}ℓ

6. SetCT :=.

(otherwise)

K1,0 , . . . , Kn,0y,K1,1 , . . . , Kn,1!!
.

Note that this CT can be computed only from xI , where I = {i ∈ [n] | zi ̸= xi }.
7. Compute (rG , rE ) ← OpenCH (rSimCH , x).
8. Set z = x ⊕ 1n ⊕ rch .
9. Set the randomness as








rGen := rG , z, rEi,zi i∈[n] , rEib i∈[n]
rEnc := rH , {Ki,1−xi }i∈[n] .
10. out ← A(pk, CT, rGen , rEnc )From the above arguments, we see that NCE satisﬁes weak security with respect toLeak = BSC0.5 . This completes the proof of Theorem 4.11.

4.6

Size and Expansion of the NCE Schemes

Finally, we summarize up ciphertext and public-key expansion of the proposed NCE
scheme. Remind that the expansion of ciphertext and public-key is the length of them
per message length for enough long messages.
Ciphertext Expansion The ciphertext expansion of the ampliﬁed NCE scheme isciphertext expansion of weak NCE+ 1,
rate of wiretap codes
where the rate of the wiretap codes is constant. We need “+1” in hybrid encryption with
one-time pad, which makes NCE satisfy non-committing security for public-key dependent
messages.
The ciphertext expansion of the weak NCE scheme is,|CT | /n =

|y|
+ 2ℓ,
n

– 58 –

4.6. Size and Expansion of the NCE Schemes
where n = Θ(|m|) is length of the code word.
When instantiated based on the DDH, the size of hash |y| = λ. Thus the ciphertext
expansion is constant for messages longer than |m| = Ω(λ)
When instantiated based on the LWE, the size of hash |y| = λpoly(log λ). Thus the
ciphertext expansion is constant for messages longer than |m| = Ω(λpoly(log λ)).
Now we estimate concrete ciphertext expansion of the resulting NCE scheme for messages longer than |m| = ω̃(λ). For such a long enough message, ciphertext expansion of
the weak NCE scheme approaches 2ℓ. Suppose the wiretap codes used in the ampliﬁcationachieve the secrecy rate
1/2 − h2 (ϵ) =1+ ϵ log ϵ + (1 − ϵ) log(1 − ϵ),21where ϵ is error rate of each message bit 2ℓ+1
. The ciphertext expansion of the resulting
NCE scheme has a minimum value appropriately 27 when ℓ = 5.

Public-Key Expansion Public-key expansion of the ampliﬁed NCE scheme is|p| + |hk| + 2n |ct|,|m|where the length of public seed for the wiretap codes is |p| = O(λ). When instantiated fromthe DDH-based chameleon encryption scheme, the hash key has length |hk| = (2n + 1)λand the ciphertext length |ct| = (2n + 1)λ. The resulting public-key expansion is O(λ2 ).
When instantiated from the LWE-based chameleon encryption scheme, the hash key
has length |hk| = λ2 · poly(log λ) and the ciphertext length |ct| = λ · poly(log λ). The
resulting public-key expansion is λ · poly(log λ).
Note that these lengths of the hash key and ciphertext of the chameleon encryption
schemes are evaluated for messages length |m| = O(λ). If we need to construct an NCE
scheme for messages of length ω(λ), we ﬁrst divide the message into λ bit blocks, thenencrypt each block using the NCE scheme for λ bit message.
Expansion Trade-Oﬀ between Public-key and Ciphertext The public-key expansion of the DDH-based NCE scheme is O(λ2 ). We can reduce it at expense of larger ciphertext expansion. In concrete, we set message length to |m| = λc for constant 0 ≤ c ≤ 1.
Then the ciphertext expansion becomes O λ(1−c) and public-key expansion O λ(1+c) .
This trade-oﬀ technique allows us to freely bridge the gap between the schemes withconstant ciphertext expansion and O(λ) ciphertext expansion.

– 59 –

Chapter 5
Conclusion
In this thesis, we constructed NCE schemes with constant ciphertext expansion based on
the DDH or LWE problem.
In Chapter 2, we observe that the target of this thesis, non-committing security, andits building block, oblivious samplability can be deﬁned in a similar manner through thefocus on the randomness used by algorithms and simulators.
In Chapter 3, we proposed an NCE scheme with O(λ) ciphertext expansion whichis constructed from obliviously samplable KEM. Along the way, we deﬁned weak NCE.
Given that the full-ﬂedged NCE is a tool to establish private channels in adaptively secure
MPC, weak NCE can be interpreted as a tool to establish wiretap channels in adaptively
secure MPC. Through wiretap channels, we can securely transmit a message by encodingwith wiretap codes that satisfy conditional invertibility.
This construction contains a fundamental idea to realize NCE. We believe it will help
us further understand non-committing encryption, oblivious samplability, and possibly
other security notions related to randomness used by algorithms.
In Chapter 4, We proposed a weak NCE scheme that has constant ciphertext expansion,
which is ampliﬁed to an NCE scheme with constant ciphertext expansion. This weak NCE
is constructed from obliviously samplable chameleon encryption. This thesis aims to ﬁnd
a suitable form of deﬁnition for chameleon encryption. As a result, the security deﬁnitionof chameleon encryption can be regarded as a combination of non-committing security ofhash function and oblivious samplability of the associated encryption. We believe thisdeﬁnition makes it easy to understand what security notion is essentially required in theconstruction of NCE schemes.
We also showed the public-key expansion of our NCE scheme can be reduced to λ ·poly(log λ) if it is instantiated from the LWE problem. One may think that the useof the ring-LWE problem may further reduce public-key expansion similar to the LWEbased NCE scheme by Hemenway et al. [HORR16]. However, unfortunately, it seems
that the ring-LWE problem is not helpful to reduce the public-key size asymptotically.
Constructing an NCE scheme with constant ciphertext expansion and better public-key
expansion is a natural future direction.
60

References[Ari09]Erdal Arikan. Channel polarization: a method for constructing capacityachieving codes for symmetric binary-input memoryless channels. IEEE
Trans. Inf. Theory, 55(7):3051–3073, 2009.

[Bac88]Eric Bach. How to generate factored random numbers. SIAM J. Comput.,
17(2):179–193, 1988.

[BBD+ 20]

Zvika Brakerski, Pedro Branco, Nico Döttling, Sanjam Garg, and Giulio Malavolta. Constant ciphertext-rate non-committing encryption from standard assumptions. In Rafael Pass and Krzysztof Pietrzak, editors, TCC 2020: 18th
Theory of Cryptography Conference, Part I, volume 12550 of Lecture Notes in
Computer Science, pages 58–87, Durham, NC, USA, November 16–19, 2020.
Springer, Heidelberg, Germany.

[Bea97]

Donald Beaver. Plug and play encryption. In Burton S. Kaliski Jr., editor, Advances in Cryptology – CRYPTO’97, volume 1294 of Lecture Notes
in Computer Science, pages 75–89, Santa Barbara, CA, USA, August 17–21,
1997. Springer, Heidelberg, Germany.

[BGW88]Michael Ben-Or, Shaﬁ Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended
abstract). In 20th Annual ACM Symposium on Theory of Computing, pages
1–10, Chicago, IL, USA, May 2–4, 1988. ACM Press.

[BH93]

Donald Beaver and Stuart Haber. Cryptographic protocols provably secureagainst dynamic adversaries. In Rainer A. Rueppel, editor, Advances in Cryptology – EUROCRYPT’92, volume 658 of Lecture Notes in Computer Science,
pages 307–323, Balatonfüred, Hungary, May 24–28, 1993. Springer, Heidelberg, Germany.

[BLSV18]

Zvika Brakerski, Alex Lombardi, Gil Segev, and Vinod Vaikuntanathan.
Anonymous IBE, leakage resilience and circular security from new assumptions. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in
Cryptology – EUROCRYPT 2018, Part I, volume 10820 of Lecture Notes in61

References
Computer Science, pages 535–564, Tel Aviv, Israel, April 29 – May 3, 2018.
Springer, Heidelberg, Germany.
[BP04]

Mihir Bellare and Adriana Palacio. The knowledge-of-exponent assumptions
and 3-round zero-knowledge protocols. In Matthew Franklin, editor, Advances in Cryptology – CRYPTO 2004, volume 3152 of Lecture Notes in
Computer Science, pages 273–289, Santa Barbara, CA, USA, August 15–19,
2004. Springer, Heidelberg, Germany.

[BT12]

Mihir Bellare and Stefano Tessaro. Polynomial-time, semantically-secure encryption achieving the secrecy capacity. Cryptology ePrint Archive, Report
2012/022, 2012. https://eprint.iacr.org/2012/022.

[BTV12a]Mihir Bellare, Stefano Tessaro, and Alexander Vardy. A cryptographic treatment of the wiretap channel. Cryptology ePrint Archive, Report 2012/015,
2012. https://eprint.iacr.org/2012/015.

[BTV12b]

Mihir Bellare, Stefano Tessaro, and Alexander Vardy. Semantic security for
the wiretap channel. In Reihaneh Safavi-Naini and Ran Canetti, editors,
Advances in Cryptology – CRYPTO 2012, volume 7417 of Lecture Notes in
Computer Science, pages 294–311, Santa Barbara, CA, USA, August 19–23,
2012. Springer, Heidelberg, Germany.

[CCD88]David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty unconditionally secure protocols (extended abstract). In 20th Annual ACM Symposiumon Theory of Computing, pages 11–19, Chicago, IL, USA, May 2–4, 1988.
ACM Press.

[CDD+ 15]

Ronald Cramer, Ivan Bjerre Damgård, Nico Döttling, Serge Fehr, andGabriele Spini. Linear secret sharing schemes from error correcting codes
and universal hash functions. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology – EUROCRYPT 2015, Part II, volume 9057 ofLecture Notes in Computer Science, pages 313–336, Soﬁa, Bulgaria, April 26–30, 2015. Springer, Heidelberg, Germany.

[CDG+ 17]

Chongwon Cho, Nico Döttling, Sanjam Garg, Divya Gupta, Peihan Miao,and Antigoni Polychroniadou. Laconic oblivious transfer and its applications. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology– CRYPTO 2017, Part II, volume 10402 of Lecture Notes in Computer Science, pages 33–65, Santa Barbara, CA, USA, August 20–24, 2017. Springer,
Heidelberg, Germany.

[CDMW09] Seung Geol Choi, Dana Dachman-Soled, Tal Malkin, and Hoeteck Wee.
Improved non-committing encryption with applications to adaptively se– 62 –

References
cure protocols. In Mitsuru Matsui, editor, Advances in Cryptology – ASIACRYPT 2009, volume 5912 of Lecture Notes in Computer Science, pages
287–302, Tokyo, Japan, December 6–10, 2009. Springer, Heidelberg, Germany.
[CDN15]

Ronald Cramer, Ivan Damgård, and Jesper Buus Nielsen. Secure Multiparty
Computation and Secret Sharing. Cambridge University Press, 2015.

[CFGN96]

Ran Canetti, Uriel Feige, Oded Goldreich, and Moni Naor. Adaptively secure
multi-party computation. In 28th Annual ACM Symposium on Theory ofComputing, pages 639–648, Philadephia, PA, USA, May 22–24, 1996. ACM
Press.

[CHKP10] David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert. Bonsai trees,or how to delegate a lattice basis. In Henri Gilbert, editor, Advances in
Cryptology – EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer
Science, pages 523–552, French Riviera, May 30 – June 3, 2010. Springer,
Heidelberg, Germany.
[CLNS17]

Jan Camenisch, Anja Lehmann, Gregory Neven, and Kai Samelin. Uc-secure
non-interactive public-key encryption. In 30th IEEE Computer Security Foundations Symposium, CSF 2017, Santa Barbara, CA, USA, August 21-25,
2017, pages 217–233. IEEE Computer Society, 2017.

[CLOS02]

Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, and Amit Sahai. Universallycomposable two-party and multi-party secure computation. In 34th Annual
ACM Symposium on Theory of Computing, pages 494–503, Montréal, Québec,
Canada, May 19–21, 2002. ACM Press.

[CPR17]

Ran Canetti, Oxana Poburinnaya, and Mariana Raykova. Optimal-rate noncommitting encryption. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology – ASIACRYPT 2017, Part III, volume 10626 of Lecture
Notes in Computer Science, pages 212–241, Hong Kong, China, December 3–
7, 2017. Springer, Heidelberg, Germany.

[DG17a]Nico Döttling and Sanjam Garg. From selective IBE to full IBE and selective
HIBE. In Yael Kalai and Leonid Reyzin, editors, TCC 2017: 15th Theoryof Cryptography Conference, Part I, volume 10677 of Lecture Notes in Computer Science, pages 372–408, Baltimore, MD, USA, November 12–15, 2017.
Springer, Heidelberg, Germany.

[DG17b]Nico Döttling and Sanjam Garg. Identity-based encryption from the DiﬃeHellman assumption. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology – CRYPTO 2017, Part I, volume 10401 of Lecture Notes– 63 –

Referencesin Computer Science, pages 537–569, Santa Barbara, CA, USA, August 20–
24, 2017. Springer, Heidelberg, Germany.
[DGHM18] Nico Döttling, Sanjam Garg, Mohammad Hajiabadi, and Daniel Masny. New
constructions of identity-based and key-dependent message secure encryption
schemes. In Michel Abdalla and Ricardo Dahab, editors, PKC 2018: 21stInternational Conference on Theory and Practice of Public Key Cryptography,
Part I, volume 10769 of Lecture Notes in Computer Science, pages 3–31, Riode Janeiro, Brazil, March 25–29, 2018. Springer, Heidelberg, Germany.
[DN00]

Ivan Damgård and Jesper Buus Nielsen. Improved non-committing encryption schemes based on a general complexity assumption. In Mihir Bellare,
editor, Advances in Cryptology – CRYPTO 2000, volume 1880 of Lecture
Notes in Computer Science, pages 432–450, Santa Barbara, CA, USA, August 20–24, 2000. Springer, Heidelberg, Germany.

[DNR04]Cynthia Dwork, Moni Naor, and Omer Reingold. Immunizing encryption
schemes from decryption errors. In Christian Cachin and Jan Camenisch, editors, Advances in Cryptology – EUROCRYPT 2004, volume 3027 of Lecture
Notes in Computer Science, pages 342–360, Interlaken, Switzerland, May 2–6,
2004. Springer, Heidelberg, Germany.

[GH18]Sanjam Garg and Mohammad Hajiabadi. Trapdoor functions from the computational Diﬃe-Hellman assumption. In Hovav Shacham and Alexandra
Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, Part II, volume10992 of Lecture Notes in Computer Science, pages 362–391, Santa Barbara,
CA, USA, August 19–23, 2018. Springer, Heidelberg, Germany.

[GKRS20]

Siyao Guo, Pritish Kamath, Alon Rosen, and Katerina Sotiraki. Limits on
the eﬃciency of (ring) LWE based non-interactive key exchange. In Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, and Vassilis Zikas, editors,
PKC 2020: 23rd International Conference on Theory and Practice of Public
Key Cryptography, Part I, volume 12110 of Lecture Notes in Computer Science, pages 374–395, Edinburgh, UK, May 4–7, 2020. Springer, Heidelberg,
Germany.

[GM06]

Andrew Granville and Greg Martin. Prime number races. Am. Math. Mon.,113(1):1–33, 2006.

[GMW87]

Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental
game or A completeness theorem for protocols with honest majority. In Alfred
Aho, editor, 19th Annual ACM Symposium on Theory of Computing, pages
218–229, New York City, NY, USA, May 25–27, 1987. ACM Press.

– 64 –

References[GOS18]

Sanjam Garg, Rafail Ostrovsky, and Akshayaram Srinivasan. Adaptive garbled RAM from laconic oblivious transfer. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, Part III,
volume 10993 of Lecture Notes in Computer Science, pages 515–544, Santa
Barbara, CA, USA, August 19–23, 2018. Springer, Heidelberg, Germany.

[GPV08]Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hardlattices and new cryptographic constructions. In Richard E. Ladner and Cynthia Dwork, editors, 40th Annual ACM Symposium on Theory of Computing,pages 197–206, Victoria, BC, Canada, May 17–20, 2008. ACM Press.

[GS18a]Sanjam Garg and Akshayaram Srinivasan. Adaptively secure garbling withnear optimal online complexity. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2018, Part II, volume10821 of Lecture Notes in Computer Science, pages 535–565, Tel Aviv, Israel,
April 29 – May 3, 2018. Springer, Heidelberg, Germany.

[GS18b]Sanjam Garg and Akshayaram Srinivasan. Two-round multiparty secure computation from minimal assumptions. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2018, Part II, volume10821 of Lecture Notes in Computer Science, pages 468–499, Tel Aviv, Israel,
April 29 – May 3, 2018. Springer, Heidelberg, Germany.

[HOR15]

Brett Hemenway, Rafail Ostrovsky, and Alon Rosen. Non-committing encryption from Φ-hiding. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, TCC 2015: 12th Theory of Cryptography Conference, Part I, volume9014 of Lecture Notes in Computer Science, pages 591–608, Warsaw, Poland,
March 23–25, 2015. Springer, Heidelberg, Germany.

[HORR16] Brett Hemenway, Rafail Ostrovsky, Silas Richelson, and Alon Rosen. Adaptive security with quasi-optimal rate. In Eyal Kushilevitz and Tal Malkin,editors, TCC 2016-A: 13th Theory of Cryptography Conference, Part I, volume 9562 of Lecture Notes in Computer Science, pages 525–541, Tel Aviv,
Israel, January 10–13, 2016. Springer, Heidelberg, Germany.
[HR05]

Thomas Holenstein and Renato Renner. One-way secret-key agreement andapplications to circuit polarization and immunization of public-key encryption. In Victor Shoup, editor, Advances in Cryptology – CRYPTO 2005,
volume 3621 of Lecture Notes in Computer Science, pages 478–493, Santa
Barbara, CA, USA, August 14–18, 2005. Springer, Heidelberg, Germany.

[HT98]

Satoshi Hada and Toshiaki Tanaka. On the existence of 3-round zeroknowledge protocols. In Hugo Krawczyk, editor, Advances in Cryptology –– 65 –

References
CRYPTO’98, volume 1462 of Lecture Notes in Computer Science, pages 408–
423, Santa Barbara, CA, USA, August 23–27, 1998. Springer, Heidelberg,
Germany.
[Kal03]Adam Kalai. Generating random factored numbers, easily. Journal of Cryptology, 16(4):287–289, September 2003.

[LCC06]

Feiyu Lei, Wen Chen, and Kefei Chen. A non-committing encryption scheme
based on quadratic residue. In Albert Levi, Erkay Savas, Hüsnü Yenigün, Selim Balcisoy, and Yücel Saygin, editors, Computer and Information Sciences ISCIS 2006, 21th International Symposium, Istanbul, Turkey, November 1-3,
2006, Proceedings, volume 4263 of Lecture Notes in Computer Science, pages
972–980. Springer, 2006.

[Leu77]

Sik K. Leung-Yan-Cheong. On a special class of wiretap channels (corresp.).
IEEE Trans. Inf. Theory, 23(5):625–627, 1977.

[LT13]

Huijia Lin and Stefano Tessaro. Ampliﬁcation of chosen-ciphertext security.
In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology– EUROCRYPT 2013, volume 7881 of Lecture Notes in Computer Science,
pages 503–519, Athens, Greece, May 26–30, 2013. Springer, Heidelberg, Germany.

[MP12]

Daniele Micciancio and Chris Peikert. Trapdoors for lattices: Simpler, tighter,faster, smaller. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology – EUROCRYPT 2012, volume 7237 of Lecture Notes
in Computer Science, pages 700–718, Cambridge, UK, April 15–19, 2012.
Springer, Heidelberg, Germany.

[MR07]

Daniele Micciancio and Oded Regev. Worst-case to average-case reductions
based on Gaussian measures. SIAM J. Comput., 37(1):267–302, 2007.

[Nie01]

Jesper Buus Nielsen. Non-committing encryption is too easy in the random
oracle model. BRICS Report Series, 8(47), 2001.

[Nie02]Jesper Buus Nielsen. Separating random oracle proofs from complexity theoretic proofs: The non-committing encryption case. In Moti Yung, editor,
Advances in Cryptology – CRYPTO 2002, volume 2442 of Lecture Notes in
Computer Science, pages 111–126, Santa Barbara, CA, USA, August 18–22,
2002. Springer, Heidelberg, Germany.

[Reg05]

Oded Regev. On lattices, learning with errors, random linear codes, andcryptography. In Harold N. Gabow and Ronald Fagin, editors, 37th Annual
ACM Symposium on Theory of Computing, pages 84–93, Baltimore, MA,
USA, May 22–24, 2005. ACM Press.
– 66 –

References[RS94]

Michael Rubinstein and Peter Sarnak. Chebyshev’s bias. Experimental Mathematics, 3(3):173–197, 1994.

[Wyn75]

Aaron D Wyner. The wire-tap channel.
54(8):1355–1387, 1975.

[YKT19]

Yusuke Yoshida, Fuyuki Kitagawa, and Keisuke Tanaka. Non-committing
encryption with quasi-optimal ciphertext-rate based on the DDH problem.
In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology– ASIACRYPT 2019, Part III, volume 11923 of Lecture Notes in Computer
Science, pages 128–158, Kobe, Japan, December 8–12, 2019. Springer, Heidelberg, Germany.

Bell system technical journal,[YKXT20] Yusuke Yoshida, Fuyuki Kitagawa, Keita Xagawa, and Keisuke Tanaka. Noncommitting encryption with constant ciphertext expansion from standard
assumptions. In Shiho Moriai and Huaxiong Wang, editors, Advances in
Cryptology – ASIACRYPT 2020, Part II, volume 12492 of Lecture Notes in
Computer Science, pages 36–65, Daejeon, South Korea, December 7–11, 2020.
Springer, Heidelberg, Germany.
[ZANS10]

Huafei Zhu, Tadashi Araragi, Takashi Nishide, and Kouichi Sakurai. Adaptive and composable non-committing encryptions. In Ron Steinfeld and Philip
Hawkes, editors, Information Security and Privacy - 15th Australasian Conference, ACISP 2010, Sydney, Australia, July 5-7, 2010. Proceedings, volume6168 of Lecture Notes in Computer Science, pages 135–144. Springer, 2010.

– 67 –