Reconstructing Chameleon Hash:

Full Security and the Multi-Party Setting

Kwan Yin Chan Liqun Chen
kychan@cs.hku.hk liqun.chen@surrey.ac.uk
The University of Hong Kong University of Surrey
Pokfulam, Hong Kong Guildford, United Kingdom

Yangguang Tian Tsz Hon Yuen∗

yangguang.tian@surrey.ac.uk john.tszhonyuen@monash.edu
University of Surrey Monash University
Guildford, United Kingdom Clayton, Australia

ABSTRACT 1 INTRODUCTION
Chameleon hash (CH) function differs from a classical hash func- Chameleon hash (CH) function was introduced by Krawczyk and
tion in a way that a collision can be found with the knowledge of a Rabin at NDSS 2000 [21]. A chameleon-hash CH function is a trap-
trapdoor secret key. CH schemes have been used in various crypto- door collision-resistant hash function parameterized by a public
graphic applications such as sanitizable signatures and redactable key. Chameleon hash outputs a hash value ℎ and a randomness (or
blockchains. In this work, we reconstruct CH to ensure advanced check string) 𝑟 for a given message 𝑚 and a public key pkch . The
security and usability. Our contributions are four-fold. First, we owner of the secret key skch can use 𝑟, 𝑚 to generate a different
propose the first CH scheme, which supports full security, meaning randomness 𝑟 ′ for another message 𝑚 ′ . The hash output pairs (ℎ, 𝑟 )
the inclusion of both full indistinguishability and full collision- and (ℎ, 𝑟 ′ ) are valid for the message 𝑚 and 𝑚 ′ respectively. In the
resistance. These two properties are required in the strongest CH classical CH construction [21]:
security model in the literature. We achieve this by our innovative
ℎ = 𝑔𝑚 pk𝑟ch,
design of removing the CH public key during the computation of
the hash value. Second, we investigate the security of CH in the where 𝑔 is a generator and pkch = 𝑔skch . In order to adapt ℎ to a
multi-party setting and introduce the new properties of claimability different message 𝑚 ′ , the owner of the secret key just needs to
and deniability under this setting. Third, we present and implement calculate 𝑟 ′ such that:
two instantiations of our CH scheme: an ECC-based one and a
𝑚 + skch · 𝑟 = 𝑚 ′ + skch · 𝑟 ′ .
post-quantum lattice-based one. Our implementation demonstrates
their practicality. Finally, we discuss the possible use cases in the The operation of computing (𝑚, 𝑟 ) is referred to as “hashing" and
blockchain. of computing (𝑚 ′, 𝑟 ′ ) as “adapting".
CH functions have been used as building blocks for many crypto-
CCS CONCEPTS graphic primitives and real-life applications, including online/offline
• Security and privacy → Mathematical foundations of cryp- signatures [31], sanitizable signatures [1], double-authentication-
tography. preventing signatures [27], ring signatures [24], asynchronous
payment channels [29], redactable blockchains [2] and privacy-
KEYWORDS preserving payment channel networks [33].
Chameleon hash, Full Security, Multi-party Setting, Post-Quantum
Cryptography
1.1 Full Security in Chameleon Hash
A chameleon hash usually needs to achieve indistinguishability
ACM Reference Format:
(IND) and collision-resistance (CollRes). IND means that the ran-
Kwan Yin Chan, Liqun Chen, Yangguang Tian, and Tsz Hon Yuen. 2024.
Reconstructing Chameleon Hash: Full Security and the Multi-Party Setting. domness associated with a chameleon hash does not reveal whether
In ACM Asia Conference on Computer and Communications Security (ASIA it was derived from hashing or adapting. The full indistinguisha-
CCS ’24), July 1–5, 2024, Singapore, Singapore. ACM, New York, NY, USA, bility property [30] implies that any third parties cannot break
16 pages. https://doi.org/10.1145/3634737.3656291 indistinguishability even if the secret key skch is generated by the
∗ Corresponding
adversary. CollRes means that given the public key pkch , no third
parties can find two pairs (𝑚, 𝑟 ) and (𝑚 ′, 𝑟 ′ ) that are valid under
author

pkch and map to the same chameleon hash value ℎ. The full collision-
resistance property [11] implies that the adversary can adaptively
query the CHAdapt oracle and use a queried message 𝑚 as the
This work is licensed under a Creative Commons Attribution International 4.0 License. attack on the collision-resistance property as long as the pair (ℎ, 𝑚)
ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore was not involved in the CHAdapt oracle query. The definitions
© 2024 Copyright held by the owner/author(s).
ACM ISBN 979-8-4007-0482-6/24/07 of IND and CollRes are various in the literature, including weak
https://doi.org/10.1145/3634737.3656291 [21], enhanced [2], standard [7] and full security [11] for CollRes,

1076
ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore Kwan Yin Chan, Liqun Chen, Yangguang Tian, and Tsz Hon Yuen

and standard [7], strong [12] and full security [30] for IND. The an attacker who knows a valid (𝑚, 𝑟 ) under pkch . He can pick a
complete discussions can be found in [11, Section 5 & Appendix random 𝑟 ′ and calculate:
A]. A CH scheme supporting IND (or CollRes) but not full IND 𝑟 /𝑟 ′ ′ ′
pk𝐴 = pkch · 𝑔 (𝑚−𝑚 )/𝑟 ,
(or full CollRes) is said that it holds standard IND (or standard
CollRes). As discussed in [11], the full indistinguishability and the for any message 𝑚 ′ . Now we can see that (𝑚 ′, 𝑟 ′ ) and ℎ is valid
full collision-resistance are the strongest security models in the under pk𝐴 , since:
literature.1 ′ ′ ′ 𝑟 /𝑟 ′ ′ ′ ′
𝑔𝑚 pk𝑟𝐴 = 𝑔𝑚 (pkch · 𝑔 (𝑚−𝑚 )/𝑟 )𝑟 = 𝑔𝑚 pk𝑟ch = ℎ.
Full indistinguishability. The RSA-based CH construction from We observe that this attack is outside the existing security model
Brzuska et al. [4] has full indistinguishability and standard collision- of CollRes. In fact, this attack also applies to schemes in which
resistance. In this scheme, the hash algorithm picks a randomness ℎ is additive/multiplicative homomorphic over pkch . Details can
𝑟 and sets the hash value ℎ = 𝐻 (𝑚) · RSA.Encpkch (𝑟 ), where 𝐻 is a be found in the Appendix A. A simple solution to avoid this key
full domain hash function. By use of the secret key skch , one can replacement attack is to change the hash value to (ℎ, 𝐻 ′ (pkch ))
set for some hash function 𝐻 ′ . An additional checking over 𝐻 ′ (pkch )
ℎ = 𝐻 (𝑚) · RSA.Encpkch (𝑟 ) = 𝐻 (𝑚 ′ ) · RSA.Encpkch (𝑟 ′ ), is needed to prevent the key replacement attack. Since the fix is
simple, we do not change the existing models to capture this attack,
with different pairs (𝑚, 𝑟 ) and (𝑚 ′, 𝑟 ′ ). Hence, due to the security and we also do not write 𝐻 ′ (pkch ) explicitly in the rest of the paper.
of RSA.Enc, it achieves full indistinguishability. In the proof of From this attack, we observe that even if we use pkch in the
the standard collision-resistant, the CHAdapt oracle query is an- calculation of ℎ, it cannot prevent the key replacement attack. On
swered by (the oracle of) the one-more RSA problem in [30]. In the other hand, it may even harm the full indistinguishability with
the challenge phase, the adversary returns a new message 𝑚 ∗ that the use of pkch (the case of [11]).
has not queried before, and hence the output of the adversary can
be used to solve the one-more RSA problem. However, the same Our Solution: “Hashing" without CH Public Key. In this pa-
proof cannot work in the full collision-resistance model, since the per, we reconstruct the chameleon hash and change the way we
adversary is allowed to return some old message 𝑚 that is queried calculate the hash value ℎ. Surprisingly, we find out that it is not
to the CHAdapt oracle before. necessary for the “hash value" ℎ to contain any information about
the owner public key pkch . In contrast, we can use pkch only when
Full collision-resistance. Derler et al. [11] proposed a generic we calculate the “randomness" 𝑟 , i.e.:
construction of chameleon hashes (denoted as DSS20) by using
ℎ = 𝐹ℎ (𝑚, 𝜌), 𝑟 = 𝐹𝑟 (𝑚, 𝜌, pkch ),
public key encryption (or a commitment [10]) and a zero-knowledge
proof. In DSS20 [11], the hash value ℎ = Encpkch (𝑚; 𝜌), which is the for some functions 𝐹ℎ , 𝐹𝑟 and internal randomness 𝜌. The hash
encryption of 𝑚 under the randomness 𝜌. The randomness 𝑟 is the value ℎ itself is not bound to any public key, and hence it can
non-interactive zero-knowledge (NIZK) proof of knowing 𝜌 with bind to anyone only when the creator generates 𝑟 . By using this
respect to ℎ, or knowing skch with respect to pkch . They achieve new structure, we can achieve full indistinguishability since the
full collision-resistance by the use of NIZK proof in generating knowledge of skch cannot help to distinguish if 𝑚 is bound in ℎ.
𝑟 . By using the simulator of the NIZK proof, the CHAdapt oracle We also choose to use a NIZK proof system for 𝐹𝑟 to achieve full
query can be answered without the knowledge of the secret key collision-resistance.
skch . However, DSS20 [11] cannot achieve full indistinguishability, We give a new generic construction of chameleon hash by using a
since they define the hash value ℎ = Encpkch (𝑚; 𝜌). By using the one-way function 𝐹 , a collision-resistant hash function 𝐻 mapping
decryption key, the original message 𝑚 is decrypted and breaks the from the message space to the range of 𝐹 , and a NIZK proof system
full indistinguishability. for disjunctive relation (the so-called OR proof). Suppose that pkch
As summarized in Table 1, it is an open problem to design a is generated from 𝐹 (skch ). In order to hash a message 𝑚, we first
chameleon hash with full indistinguishability and full collision- pick a random 𝜌 and calculate
resistance. ℎ = 𝐹 (𝜌) ⊕ 𝐻 (𝑚),

1.2 High-Level Idea of Our Scheme where ⊕ is the bitwise XOR operation. The randomness 𝑟 is the
NIZK proof of knowing 𝜌 such that:
Before presenting our solution, we first describe a practical attack
on CollRes, which is not considered in the existing security model. 𝐹 (𝜌) = ℎ ⊕ 𝐻 (𝑚) ∨ 𝐹 (𝜌) = pkch .
This attack inspires us to formulate our new generic construction The chameleon hash function outputs (ℎ, 𝑟 ). To verify the output
of chameleon hash with full security. (ℎ, 𝑟 ), one just needs to validate the NIZK proof.
Security in the Multi-key Setting. The existing security models To adapt (ℎ, 𝑟 ) to another message 𝑚 ′ , the owner of skch calcu-
of chameleon-hash only consider a single public key pkch . For lates another NIZK proof 𝑟 ′ for the above relation, but proving the
CollRes, no polynomial time attacker can output ℎ and two pairs knowledge of skch instead of 𝜌, and it is now written as:
(𝑚, 𝑟 ) and (𝑚 ′, 𝑟 ′ ) that are valid under pkch . However, we consider 𝐹 (skch ) = ℎ ⊕ 𝐻 (𝑚 ′ ) ∨ 𝐹 (skch ) = pkch .
a key replacement attack for the classical CH construction [21] by
We can easily instantiate the generic construction in the elliptic
1 Thereis another property called uniqueness [7], but it is not considered as a funda- curve (ECC) setting and lattice-based setting. They are both practi-
mental property. cal for real-world use cases.

1077
Reconstructing Chameleon Hash: Full Security and the Multi-Party Setting ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore

Table 1: The comparison of security models between various CHs. − indicates IND is not required in [2, 21].

[21] [2] [7] [12] [30] [11] [10] Ours

CollRes Weak Enhanced Standard Standard Standard Full Full Full
IND - - Standard Strong Full Standard Strong Full
Multi-Party × ✓ × ✓ ✓ × × ✓

1.3 Chameleon Hash in the Multi-Party Setting it from the classical CH construction [21]. For a message 𝑚 and
Apart from the generic construction, the key replacement attack randomly chosen 𝑟 1, 𝑟 2 , compute:
also inspires us to reconsider the security of chameleon hash, es- (1) (2)
pecially in the multi-party setting. Several CH schemes in Table 1 ℎ = 𝑔𝑚 (pkch )𝑟 1 (pkch )𝑟 2 ,
support multi-party setting, meaning that multiple trapdoor hold-
(1) (2)
ers can perform adapting [12, 30]. Multi-party settings in the CH for two owner public keys pkch , pkch . However, if the first owner
(1)
scheme [9] and sanitizable signatures [5, 8] have been used in real wants to adapt it, he can only change 𝑟 1 to 𝑟 1′ such that 𝑚+skch ·𝑟 1 =
applications, such as content protection and secure routing. (1)
𝑚 ′ + skch · 𝑟 1′ . After adapting, he outputs (𝑚 ′, 𝑟 1′ , 𝑟 2 ). It trivially
The Creator and the Owner. The existing IND and CollRes secu- violates (the multi-owner version of) indistinguishability, since the
rity models mainly consider attacks from a third party. In the model hash outputs (𝑚, 𝑟 1, 𝑟 2 ) and (𝑚 ′, 𝑟 1′ , 𝑟 2 ) are not generated by the
of full indistinguishability [30] and strong indistinguishability [12], (2)
second owner pkch .
the adversary can also obtain the secret key skch . However, none Therefore, it is an open problem to define the security model
of the existing models considers the ability of the original creator of the multi-owner version of indistinguishability, and to give a
of the hash output. To the best of our knowledge, there is not even secure construction. Fortunately, our generic construction can be
a formal name for this role. We name the one who created ℎ as the easily extended to the multi-owner setting. Since the construction
Creator, while the one who owns the secret key skch as the Owner. of ℎ does not involve any public key, we do not need to change
Claimability and Deniability. Next, we consider the ability of it. We just need to extend the disjunctive proof to a multiple one
the Creator. Consider the application that the hash output (ℎ, 𝑟 ) when generating 𝑟 .
is written in a redactable blockchain by the Creator, and then it
is later modified to (ℎ, 𝑟 ′ ) by the Owner using a smart contract. 1.4 Our Contributions
Theoretically, it is possible that the Creator can claim the authorship In this paper, we study two main open problems in chameleon-hash:
of ℎ, or claim that the original message 𝑚 is associated with ℎ. For
example in DSS20 [11], ℎ = Encpkch (𝑚; 𝜌). By outputting (𝑚, 𝜌), • Achieving full indistinguishability and full collision-resistance
the Creator can claim the creation of ℎ and the original message at the same time.
𝑚 if the Owner cannot recover valid encryption randomness for • Evaluating the (in)security of chameleon-hash in the multi-party
any message 𝑚 ′ using his secret key (this condition holds for the setting.
ElGamal encryption instantiation used in [11]). It implies that the We propose a new generic construction of chameleon-hash, which is
Creator can voluntarily break the IND property based on ℎ. This inspired by our key replacement attack on existing schemes. It is the
kind of insider attack is not considered in the literature. first chameleon-hash that can achieve full indistinguishability and
After defining the roles of the Creator and the Owner, we can full collision-resistance simultaneously. We define different parties
even consider more complicated situations. The Creator or the (creator and owners) involved in chameleon hash, and investigate
Owner may claim the authorship of the randomness 𝑟 or 𝑟 ′ gener- their ability to claim or deny the generation of the chameleon hash.
ated by himself. It implies that either party can voluntarily break We also extend our generic construction to give the first multi-
the IND property based on 𝑟 or 𝑟 ′ . For example in DSS20 [11], the owner chameleon hash.
Creator or the Owner can use the randomness used in the NIZK
proof to claim such authorship. These situations may have different
2 BACKGROUND
implications in real-world applications.
When we consider it from the opposite direction, the Creator 2.1 Chameleon Hash
or the Owner may deny generating the randomness 𝑟 ′ or 𝑟 respec- We show the definition of chameleon hashes [7, 11], which is based
tively. If one party denies generating a randomness, then it must on the work done by [2, 4].
be generated by the other party. It implies that the IND property
• CHPG: It takes a security parameter 𝜆 as input, outputs public
can also be broken by the counterparty. However, it is non-trivial
parameters ppch .
to construct schemes with this deniability property.
• CHKG: It takes public parameters ppch as input, outputs a chameleon
Multi-Owner Chameleon Hash. After defining the roles of the key pair (skch, pkch ).
creator and the owner, it is natural for us to extend CH to a multi- • CHash: It takes the chameleon public key pkch , and a message
owner setting. It means that multiple parties have the ability to 𝑚 ∈ M as input, outputs a chameleon hash ℎ, a randomness 𝑟 .
adapt the hash value ℎ. At first glance, it may look easy to extend Note that M = {0, 1}∗ denotes a general message space.

1078
ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore Kwan Yin Chan, Liqun Chen, Yangguang Tian, and Tsz Hon Yuen

• CHCheck: It takes the chameleon public key pkch , a message 𝑚, Experiment ExpIND
A
(𝜆)
a chameleon hash ℎ and a randomness 𝑟 as input, outputs a bit ppch ← CHPG(𝜆), 𝑏 ← {0, 1}
𝑏 ′ ← A HashOrAdapt(··· ,𝑏) (ppch )
𝑏 ∈ {0, 1}. where HashOrAdapt(· · · , 𝑏 ) on input skch , pkch , 𝑚, 𝑚 ′ , 𝑏 :
• CHAdapt: It takes the chameleon secret key skch , messages 𝑚, 𝑚 ′ , (ℎ 0 , 𝑟 0 ) ← CHash(pkch , 𝑚 ′ )
(ℎ 1 , 𝑟 1′ ) ← CHash(pkch , 𝑚)
chameleon hash ℎ and randomness 𝑟 as input, outputs a new 𝑟 1 ← CHAdapt(skch , 𝑚, 𝑚 ′ , ℎ 1 , 𝑟 1′ )
randomness 𝑟 ′ . return ⊥ if 𝑟𝑏 = ⊥ ∨ 𝑟 1′ = ⊥
return (ℎ𝑏 , 𝑟𝑏 )
Correctness states that a pair (ℎ, 𝑟 ), computed by the CHash algo- if 𝑏 ′ = 𝑏, return 1; else, return 0.

rithm, verifies with overwhelming probability. Also, the CHAdapt

algorithm always verifies if the given chameleon hash ℎ is valid, Figure 1: Full Indistinguishability.
or it outputs ⊥. In the definition above, hashing is assumed to be
randomized. The randomness 𝑟 (or check string) is a public value, Experiment ExpCR
A
(𝜆)
ppch ← CHPG(𝜆), Q ← ∅
and the implicit random coins (or internal randomness) are secret. (skch , pkch ) ← CHKG(ppch )
This definition is a generalization of standard chameleon hashes (𝑚 ∗ , 𝑟 ∗ , 𝑚 ′∗ , 𝑟 ′∗ , ℎ ∗ ) ← A CHAdapt(skch ,··· ) (pkch )
where CHAdapt(skch , · · · ) on input skch , 𝑚, 𝑚 ′ , ℎ, 𝑟 :
[21]. Now, we present two security guarantees: full indistinguisha- return ⊥, if CHCheck(pkch , ℎ, 𝑚, 𝑟 ) ≠ 1
bility [30] and full collision-resistance [11], which will be used in 𝑟 ′ ← CHAdapt(skch , 𝑚, 𝑚 ′ , ℎ, 𝑟 )
Q ← Q ∪ { (ℎ, 𝑚), (ℎ, 𝑚 ′ ) }
the security analysis of our proposed constructions. return 𝑟 ′
if 1 = CHCheck(pkch , 𝑚 ∗ , ℎ ∗ , 𝑟 ∗ ) = CHCheck(pkch , 𝑚 ′∗ , ℎ ∗ , 𝑟 ′∗ )
Full Indistinguishability. Informally, for a chameleon hash, an ∧(ℎ ∗ , 𝑚 ∗ ) ∉ Q ∧ 𝑚 ∗ ≠ 𝑚 ′∗ , return 1;
adversary cannot decide whether its randomness was freshly gen- //(ℎ∗, 𝑚∗) does not appear as first or second pair in CHAdapt query
else, return 0.
erated using CHash algorithm or was created using CHAdapt algo-
rithm. The adversary is allowed to generate the keys which are used
for hashing and adapting. We define a formal experiment between Figure 2: Full Collision-Resistance.
an adversary A and a challenger S in Figure 1. The security ex-
periment allows A to access a HashOrAdapt oracle which ensures
that the randomness does not reveal whether it was obtained from some statement 𝑥 in the language 𝐿. The formal definition is shown
CHash or CHAdapt algorithm. below.
We define the advantage of A as
Definition 2.4. A non-interactive proof system Π for language 𝐿
AdvIND IND
A (𝜆) = |Pr[Exp A (𝜆) → 1] − 1/2|. includes the following three algorithms.
Definition 2.1. A CH scheme is fully indistinguishable if for any • PG: It takes a security parameter 𝜆 as input, outputs public com-
probabilistic polynomial-time PPT A, AdvIND (𝜆) is negligible in 𝜆. mon reference string (CRS) crsΠ .
A
• Pf: It takes the CRS crsΠ , a statement 𝑥 and a witness 𝑤, outputs
Full Collision Resistance. Informally, an adversary attempts to a proof 𝜋.
find valid collisions without using trapdoors. The adversary can ac- • Vfy: It takes the CRS crsΠ , a statement 𝑥 and a proof 𝜋, outputs
cess an CHAdapt oracle: it takes messages (𝑚, 𝑚 ′ ) as input, outputs a bit 𝑏 ∈ {0, 1}.
a collision for the adversarially chosen hash and records (𝑚, 𝑚 ′ ) Non-interactive proof systems typically satisfy three proper-
under a list Q. A wins if it outputs a collision for an adversarially ties: correctness, zero-knowledge, and soundness. Correctness (or
generated chameleon hash ℎ ∗ , while (ℎ ∗, 𝑚 ∗ ) was not previously completeness) says that an honest prover should always be able
queried to the CHAdapt oracle. We define a formal experiment in to convince the verifier that 𝑥 ∈ 𝐿. Zero-knowledge says that the
Figure 2. receiver of the proof 𝜋 cannot learn anything except the validity
We define the advantage of A as of the statement. Soundness says that a malicious prover cannot
AdvCR CR
A (𝜆) = |Pr[Exp A (𝜆) → 1] |.
generate a proof 𝜋 for any element 𝑥 ∉ 𝐿. We use a stronger for-
mulation of the soundness called simulation-sound extractability
Definition 2.2. A CH scheme is fully collision-resistant if for any [11, 13]. It says that every adversary who can generate a proof 𝜋 ∗
PPT A, AdvCRA
(𝜆) is negligible in 𝜆. for a statement 𝑥 ∗ must know the witness 𝑤 ∗ , even when seeing
simulated proofs for adaptively chosen statements not in language
2.2 One-Way Function 𝐿. The distribution of the common reference string crsΠ generated
Definition 2.3. A function 𝐹 : 𝐷 𝐹 → 𝑅𝐹 is one-way, if the advan- by PG and the distribution of the simulated crsΠ by SIM1 or Ext1
tage of PPT A defined in the following equation is negligible in are assumed to be indistinguishable.
𝜆. Definition 2.5 (Correctness). A non-interactive proof system Π
Pr[𝑥 ∈𝑅 𝐷 𝐹 , 𝑥 ′ ∈𝑅 A (𝐹 (𝑥)) : 𝐹 (𝑥) = 𝐹 (𝑥 ′ )]. is correct, if for all 𝜆, for all crsΠ ← PG(𝜆), for all 𝑥 ∈ 𝐿, for all
We assume that the domain 𝐷 𝐹 and range 𝑅𝐹 are defined by 𝐹 . 𝑤 such that 𝑅(𝑥, 𝑤) = 1, for all 𝜋 ← Pf (crsΠ , 𝑥, 𝑤), it holds that
Vfy(crsΠ , 𝑥, 𝜋) = 1.
2.3 Non-Interactive Zero-Knowledge Definition 2.6 (Zero-Knowledge). We define a formal experiment
Let 𝐿 = {𝑥 |∃𝑤 : 𝑅(𝑥, 𝑤) = 1} be an NP-language with a relation between a PPT adversary A and a simulator SIM = (SIM1, SIM2 )
𝑅. A non-interactive proof system allows to prove membership of in Figure 3. Note that 𝜏 denotes a simulation trapdoor. We define

1079
Reconstructing Chameleon Hash: Full Security and the Multi-Party Setting ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore

Experiment ExpZK
A
(𝜆) • CHPG(𝜆): It picks a collision-resistant hash function 𝐻 that maps
(crsΠ , 𝜏 ) ← SIM1 (𝜆), 𝑏 ← {0, 1} the message space to the range 𝑅𝐹 of 𝐹 . It runs crsΠ ← PG(𝜆).
𝑏 ′ ← A 𝑃𝑏 (·,·) (crsΠ )
where 𝑃 0 on input 𝑥, 𝑤 : It outputs public parameters ppch = (𝐹, 𝐻, crsΠ ).
return 𝜋 ← Pf (crsΠ , 𝑥, 𝑤 ), if 𝑅 (𝑥, 𝑤 ) = 1 • CHKG(ppch ): It outputs a random skch (randomly chosen from
return ⊥
where 𝑃 1 on input 𝑥, 𝑤 : the domain of 𝐹 ) and pkch = 𝐹 (skch ).
return 𝜋 ← SIM2 (crsΠ , 𝑥, 𝜏 ), if 𝑅 (𝑥, 𝑤 ) = 1
return ⊥
• CHash(pkch, 𝑚): It picks a random 𝜌 from the domain of 𝐹 and
if 𝑏 ′ = 𝑏, return 1; else, return 0. calculates ℎ = 𝐹 (𝜌) ⊕ 𝐻 (𝑚). It computes a zero-knowledge proof
𝑟 ← Pf (crsΠ , (𝐹, ℎ ⊕ 𝐻 (𝑚), pkch ), 𝜌). It outputs (ℎ, 𝑟 ). Note that
𝑟 is a NIZK proof for the witness 𝜌 such that
Figure 3: Zero-Knowledge.
𝐹 (𝜌) = ℎ ⊕ 𝐻 (𝑚) ∨ 𝐹 (𝜌) = pkch .
Experiment ExpSim
A
(𝜆)
(crsΠ , 𝜏, 𝜌 ) ← Ext1 (𝜆), Q ← ∅ The parameters (𝐹, ℎ ⊕ 𝐻 (𝑚), pkch ) are public in the NIZK proof.
(𝑥 ∗ , 𝜋 ∗ ) ← A SIM(·) (crsΠ ) • CHCheck(pkch, 𝑚, ℎ, 𝑟 ): It outputs 𝑏 ← Vfy(crsΠ , (𝐹, ℎ ⊕ 𝐻 (𝑚),
where SIM on input 𝑥 :
𝜋 ← SIM2 (crsΠ , 𝑥, 𝜏 ) pkch ), 𝑟 ).
Q ← Q ∪ { (𝑥, 𝜋 ) }
return 𝜋
• CHAdapt(skch, 𝑚, 𝑚 ′, ℎ, 𝑟 ): It returns ⊥ if CHCheck(pkch, 𝑚, ℎ, 𝑟 )
𝑤 ∗ ← Ext2 (crsΠ , 𝜌, 𝑥 ∗ , 𝜋 ∗ ) = 0. Otherwise, it outputs another zero-knowledge proof 𝑟 ′ ←
if 1 = Vfy(𝑥 ∗ , 𝜋 ∗ ) ∧ 𝑅 (𝑥 ∗ , 𝑤 ∗ ) = 0 ∧ (𝑥 ∗ , 𝜋 ∗ ) ∉ Q, return 1;
else, return 0. Pf (crsΠ , (𝐹, ℎ ⊕ 𝐻 (𝑚 ′ ), pkch ), skch ).
Note that 𝑟 ′ is a NIZK proof for skch such that

Figure 4: Simulation Sound Extractability. 𝐹 (skch ) = ℎ ⊕ 𝐻 (𝑚 ′ ) ∨ 𝐹 (skch ) = pkch .

3.1.1 Security. We prove the security of our generic construction
under the strong model of full indistinguishability and full collision-
the advantage of A as resistance.
AdvZK ZK
A (𝜆) = |Pr[Exp A (𝜆) → 1] − 1/2|. Theorem 3.1. Our CH scheme is fully indistinguishable if Π has
The non-interactive proof system Π for language 𝐿 is zero-knowledge, the zero-knowledge property and the output of 𝐹 is uniformly dis-
if for any PPT A, AdvZK (𝜆) is negligible in 𝜆. tributed in its range 𝑅𝐹 .
A
Definition 2.7 (Simulation-sound Extractability). We define a for- Proof. The proof is given by a sequence of games. We define
mal experiment between a PPT adversary A and an extractor the following games:
Ext = (Ext1, Ext2 ) in Figure 4. We define the advantage of A as • Game0 : The same as the IND game.
• Game1 : The output 𝑟 0 from CHash(pkch, 𝑚 ′ ) is given by the
AdvSim Sim
A (𝜆) = |Pr[Exp A (𝜆) → 1] |. simulator of Π.
The non-interactive proof system Π for language 𝐿 is simulation- • Game2 : The output 𝑟 1 from CHAdapt(skch, 𝑚, 𝑚 ′, ℎ 1, 𝑟 1′ ) is given
sound extractable, if for any PPT A, AdvSim (𝜆) is negligible in by the simulator of Π.
A
𝜆. • Game3 : The output ℎ 0 from CHash(pkch, 𝑚 ′ ) is replaced by a
random number in 𝑅𝐹 .
3 OUR CONSTRUCTIONS • Game4 : The output ℎ 1 from CHash(pkch, 𝑚) is replaced by a
random number in 𝑅𝐹 .
In this section, we introduce a new generic construction of chameleon
hash from a one-way function (OWF) and a non-interactive zero- By the zero-knowledge property of Π, we can see that no PPT
knowledge (NIZK) proof. adversary can distinguish between Game0 and Game1 (and also
Suppose that 𝐹 is a one-way function with its output uniformly between Game1 and Game2 ) with non-negligible probability.
distributed in the range 𝑅𝐹 2 . We define an efficient NIZK proof of If the output of 𝐹 is uniformly distributed in its range, then
knowledge 𝑥 for the following language: 𝐹 (𝜌) is indistinguishable with a random number chosen from the
range. Hence, no PPT adversary can distinguish 𝐹 (𝜌) ⊕ 𝐻 (𝑚 ′ ) (in
𝐿 := {(𝐹, 𝑦1, 𝑦2 )|𝑥 : 𝐹 (𝑥) = 𝑦1 ∨ 𝐹 (𝑥) = 𝑦2 }. Game2 ) with a random number ℎ (in Game3 ) with non-negligible
This is known as the disjunctive proof. The NIZK proof system Π probability. The same argument applies for Game3 and Game4 .
consists of three algorithms (PG, Pf, Vfy). Denote ⊕ as the bitwise Finally in Game4 , the pairs (ℎ 0, 𝑟 0 ) and (ℎ 1, 𝑟 1 ) are randomly
XOR operation3 . generated. Hence no PPT adversary can win this game with non-
negligible probability. □
3.1 Generic Construction We need a new assumption to prove the full collision-resistance
Our generic CH algorithm is as follows: property.
2 For example, under the discrete logarithm assumption, 𝐹 (𝑥 ) = 𝑔𝑥 is uniformly Definition 3.2 (Assumption 1). Given a one-way function 𝐹 and a
distributed in the group G when 𝑔 is a generator of G. Under the RSA assumption, collision resistant hash function 𝐻 , no PPT adversary can output
𝐹 (𝑥 ) = 𝑥 𝑒 mod 𝑁 is uniformly distributed when given the RSA public key (𝑒, 𝑁 ) . 𝑥 0, 𝑥 1, 𝑚 0, 𝑚 1 with non-negligible probability such that 𝑚 0 ≠ 𝑚 1
3We can replace the bitwise XOR operation with an algebraic operation over the
range of 𝐹 , with some minor modification in the writing of the security proof and the and
assumptions used. See section 3.2. 𝐹 (𝑥 0 ) ⊕ 𝐹 (𝑥 1 ) = 𝐻 (𝑚 0 ) ⊕ 𝐻 (𝑚 1 ).

1080
ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore Kwan Yin Chan, Liqun Chen, Yangguang Tian, and Tsz Hon Yuen

We note that the Assumption 1 should be analyzed in the con- which contradicts the Assumption 1.
crete instantiation. For example in the discrete logarithm(DL)- For case 2b, by the simulation of the CHAdapt query, S already
based setting, if 𝐹 (𝑥) = 𝑔𝑥 and ⊕ is point addition, then the extracts 𝑥ˆ2𝑏 such that 𝐹 (𝑥ˆ2𝑏 ) = ℎ ∗ ⊕ 𝐻 (𝑚). Since (ℎ ∗, 𝑚) ∈ Q and
hard problem becomes outputting 𝑥 0, 𝑥 1, 𝑚 0, 𝑚 1 such that 𝑔𝑥 0 +𝑥 1 = (ℎ ∗, 𝑚 ∗ ) ∉ Q, it implies that 𝑚 ≠ 𝑚 ∗ . Similar to case 1, S can use
𝐻 (𝑚 0 ) · 𝐻 (𝑚 1 ). It can be easily reduced to the DL problem if 𝐻 is the extractor Ext2 to obtain
modeled as a random oracle. In the RSA-based setting, if 𝐹 (𝑥) = 𝑥 𝑒
mod 𝑁 where (𝑒, 𝑁 ) is a RSA public key, and ⊕ is modular multi- 𝑥 0 :𝐹 (𝑥 0 ) = ℎ ∗ ⊕ 𝐻 (𝑚 ∗ ) ∨ 𝐹 (𝑥 0 ) = 𝑦.
plication, the hard problem becomes outputting 𝑥 0, 𝑥 1, 𝑚 0, 𝑚 1 such Hence, S either returns 𝑥 0 as the solution to 𝐹 −1 (𝑦), or obtains
that (𝑥 0𝑥 1 )𝑒 = 𝐻 (𝑚 0 )𝐻 (𝑚 1 ) mod 𝑁 . It can be reduced to the RSA
problem if 𝐻 is modeled as a random oracle. ℎ ∗ = 𝐹 (𝑥 0 ) ⊕ 𝐻 (𝑚 ∗ ) = 𝐹 (𝑥ˆ2𝑏 ) ⊕ 𝐻 (𝑚),
Theorem 3.3. Our CH scheme is fully collision resistant if 𝐹 has which contradicts the Assumption 1 since 𝑚 ≠ 𝑚 ∗ . □
the one-wayness property, Π has simulation-sound extractability and
assumption 1 holds. 3.2 ECC-based Construction
Proof. The simulator S runs as the adversary of breaking one- We instantiate 𝐹 in an ECC group G with prime order 𝑞 and its
wayness property of 𝐹 . S is given 𝑦 and wants to find 𝐹 −1 (𝑦). generator is 𝑔. We define 𝐹 (𝑥) = 𝑔𝑥 for any 𝑥 ∈ Z𝑞 . 𝐹 is a one-way
S runs the extractor Ext1 of Π to obtain (crsΠ , 𝜏, 𝜌). S sets ppch = function if the DL assumption holds in G. We can easily instantiate
(𝐹, 𝐻, crsΠ ), pkch = 𝑦 and returns (ppch, pkch ) to the adversary A. our generic construction with a DL-based OR proof.
For the CHAdapt oracle query with input (𝑚, 𝑚 ′, ℎ, 𝑟 ), S runs the To further simplify the assumption we need, we change ⊕ to the
extractor Ext2 of Π to obtain 𝑥ˆ ← Ext2 (crsΠ , 𝜌, (𝐹, ℎ⊕𝐻 (𝑚), pkch ), 𝑟 ) point addition operation. The scheme has to be modified slightly,
such that by introducing some inverse operation.
The algorithm is as follows:
𝑥ˆ :𝐹 (𝑥)
ˆ = ℎ ⊕ 𝐻 (𝑚) ∨ 𝐹 (𝑥)
ˆ = 𝑦.
• CHPG(𝜆): On input the security parameter 𝜆, it outputs public
ˆ = 𝑦, S simply returns 𝑥ˆ as the solution of 𝐹 −1 (𝑦) and aborts.
If 𝐹 (𝑥) parameters ppch , including the elliptic curve group G of prime
Otherwise, S runs the simulator of the zero-knowledge proof to order 𝑞, a generator 𝑔 ∈ G, and collision-resistant hash function
generate 𝑟 ′ ← SIM2 (crsΠ , 𝜏, (ℎ ⊕ 𝐻 (𝑚 ′ ), pkch )) and return 𝑟 ′ to 𝐻 : {0, 1}∗ → G and 𝐻 ′ : {0, 1}∗ → Z𝑞 .
A. • CHKG(ppch ): It picks 𝑥 ∈ Z𝑞 , and outputs (skch = 𝑥, pkch = 𝑔𝑥 ).
In the output phase, the adversary returns (𝑚 ∗, 𝑟 ∗, 𝑚 ′∗, 𝑟 ′∗, ℎ ∗ ) • CHash(pkch, 𝑚): It picks 𝜌 ∈ Z𝑞 and sets ℎ = 𝑔𝜌 · 𝐻 (𝑚). Then
with 𝑚 ∗ ≠ 𝑚 ′∗ and (ℎ ∗, 𝑚 ∗ ) ∉ Q. We consider two cases: (1) we compute a NIZK proof 𝑟 by:
(ℎ ∗, 𝑚 ′∗ ) ∉ Q; (2)(ℎ ∗, 𝑚 ′∗ ) ∈ Q. (1) It picks 𝑡 2, 𝑧 1 ∈ Z𝑞 and computes𝑇2 = 𝑔𝑡2 , 𝑐 1 = 𝐻 ′ (𝑇2, pkch, 𝑔𝜌 , 𝑚),
We first consider case 1. Since it passes CHCheck, it means that 𝑇1 = 𝑔𝑧1 pk𝑐ch1 .
S can use the extractor Ext2 to obtain (2) It computes 𝑐 2 = 𝐻 ′ (𝑇1, pkch, 𝑔𝜌 , 𝑚).
𝑥 0 :𝐹 (𝑥 0 ) = ℎ ∗ ⊕ 𝐻 (𝑚 ∗ ) ∨ 𝐹 (𝑥 0 ) = 𝑦, (3) It computes 𝑧 2 = 𝑡 2 − 𝑐 2 𝜌. It returns 𝑟 = (𝑧 1, 𝑧 2, 𝑐 1 ).
It outputs (ℎ, 𝑟 ).
𝑥 1 :𝐹 (𝑥 1 ) = ℎ ∗ ⊕ 𝐻 (𝑚 ′∗ ) ∨ 𝐹 (𝑥 1 ) = 𝑦.
• CHCheck(pkch, 𝑚, ℎ, 𝑟 ): It parses 𝑟 = (𝑧 1, 𝑧 2, 𝑐 1 ). It computes
Now we have two possible sub-cases: 𝑦 ′ = ℎ/𝐻 (𝑚). It outputs 1 if
• 1a. 𝐹 (𝑥 0 ) = 𝑦 or 𝐹 (𝑥 1 ) = 𝑦.
𝑇1 = 𝑔𝑧1 pk𝑐ch1 , 𝑐 2 = 𝐻 ′ (𝑇1, pkch, 𝑦 ′, 𝑚),
• 1b. 𝐹 (𝑥 0 ) = ℎ ∗ ⊕ 𝐻 (𝑚 ∗ ) and 𝐹 (𝑥 1 ) = ℎ ∗ ⊕ 𝐻 (𝑚 ′∗ ).
For the case 1a, S simply outputs 𝑥 0 or 𝑥 1 as the solution of 𝐹 −1 (𝑦). 𝑇2 = 𝑔𝑧2 𝑦 ′𝑐 2 , 𝑐 1 = 𝐻 ′ (𝑇2, pkch, 𝑦 ′, 𝑚).
For the case 1b, it implies that Otherwise, it returns 0.
ℎ ∗ = 𝐹 (𝑥 0 ) ⊕ 𝐻 (𝑚 ∗ ) = 𝐹 (𝑥 1 ) ⊕ 𝐻 (𝑚 ′∗ ). • CHAdapt(skch, 𝑚, 𝑚 ′, ℎ, 𝑟 ): It returns ⊥ if CHCheck(pkch, 𝑚, ℎ, 𝑟 ) =
0. Otherwise, it generates another NIZK proof 𝑟 ′ with respect
Since 𝐻 is a collision resistant hash function, 𝐻 (𝑚 ∗ ) ≠ 𝐻 (𝑚 ′∗ ) for
to (pkch , 𝑦 ′ = ℎ/𝐻 (𝑚 ′ )), using the secret key skch = 𝑥 and the
𝑚 ∗ ≠ 𝑚 ′∗ . By assumption 1, this case happens with a negligible
message 𝑚 ′ .
probability. ′
(1) It picks 𝑡 1′ , 𝑧 2′ ∈ Z𝑞 and computes𝑇1′ = 𝑔𝑡1 , 𝑐 2′ = 𝐻 ′ (𝑇1′, pkch, 𝑦 ′, 𝑚 ′ ),
Next, we consider case 2. If (ℎ ∗, 𝑚 ′∗ ) ∈ Q, there are two sub- ′
cases: 𝑇2′ = 𝑔𝑧2 𝑦 ′𝑐 2 .
(2) It computes 𝑐 1′ = 𝐻 ′ (𝑇2′, pkch, 𝑦 ′, 𝑚 ′ ).
• 2a. There was a CHAdapt query with input (𝑚 ′∗, ·, ℎ ∗, ·).
(3) It computes 𝑧 1′ = 𝑡 1′ − 𝑐 1′ 𝑥. It returns 𝑟 ′ = (𝑧 1′ , 𝑧 2′ , 𝑐 1′ ).
• 2b. There was a CHAdapt query with input (𝑚, 𝑚 ′∗, ℎ ∗, 𝑟 ).
It outputs 𝑟 ′ .
For case 2a, by the simulation of the CHAdapt query, S already
extracts 𝑥ˆ2𝑎 such that 𝐹 (𝑥ˆ2𝑎 ) = ℎ ∗ ⊕ 𝐻 (𝑚 ′∗ ). Similar to case 1, S Theorem 3.4. Our ECC-based scheme is fully indistinguishable
can use the extractor Ext2 to obtain in the random oracle model (ROM).
𝑥 0 :𝐹 (𝑥 0 ) = ℎ ∗ ⊕ 𝐻 (𝑚 ∗ ) ∨ 𝐹 (𝑥 0 ) = 𝑦. Theorem 3.5. Our ECC-based scheme is fully collision-resistant if
Hence, S either returns 𝑥 0 as the solution to 𝐹 −1 (𝑦), or obtains the DL assumption in G holds in the random oracle model.

ℎ ∗ = 𝐹 (𝑥 0 ) ⊕ 𝐻 (𝑚 ∗ ) = 𝐹 (𝑥ˆ2𝑎 ) ⊕ 𝐻 (𝑚 ′∗ ), We show the security proofs in the Appendix B.

1081
Reconstructing Chameleon Hash: Full Security and the Multi-Party Setting ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore

3.3 Lattice-based construction Theorem 3.8. Our lattice-based scheme is fully indistinguishable
We define 𝑞 as an odd modulus and 𝑅𝑞 as a ring Z𝑞 [𝑋 ]/(𝑋 𝑑 + 1) if the M-LWE𝑚−𝑘,𝑘,𝑞,𝔘1 assumption holds in the random oracle model.
of dimension 𝑑. Define 𝐼®𝑛 as the identity matrix with size 𝑛, 𝔘𝑘 as Theorem 3.9. Our lattice-based scheme is fully collision-resistant
a set of polynomials in Z[𝑋 ]/(𝑋 𝑑 + 1) with infinity norm at most if the M-SIS𝑘,𝑚+1,𝑞,𝛽SIS assumption and the M-LWE𝑚−𝑘,𝑘,𝑞,𝔘1 as-
𝑘 ∈ Z+ , and U as the uniform distribution. The Euclidean ∥·∥ and sumption hold in the random oracle model, where 𝛽 SIS ≈ 4𝑑 · (2𝑚𝑑 2 +
infinity ∥ · ∥ ∞ norms of a polynomial (or a vector of polynomials) √
𝑚𝑑).
are defined in the standard fashion w.r.t. the coefficient vector of
the polynomial. The symbol 𝑥 ←𝑠 X means randomly picks 𝑥 from The proofs are given in the Appendix C.
X. Define the following challenge space:
C = { 𝑐 ∈ Z[𝑋 ]/(𝑋 𝑑 + 1) : ∥𝑐 ∥ ∞ = 1 }. (1)
3.4 Comparison
Apart from the comparison of IND and CollRes models in Table 1,
Observe that |C| = 3𝑑 . That is, for 𝑑 = 128, we have |C| = 3128 > we further compare various CHs in Table 2. We assume an ECC
2202 . group (G, Z𝑞 ), and RSA modulus Z𝑁 . Let 𝐸 G be an exponentiation
We review the hardness of Module-SIS (M-SIS) and Module-LWE on G, and this notation also applies to Z𝑁 . Let 𝐸𝑐𝑡 denote exponen-
(M-LWE) problems [17]. tiation on an ABE ciphertext 𝑐𝑡, and |𝑐𝑡 | denote its length. We refer
Definition 3.6 (M-SIS𝑛,𝑚,𝑞,𝛽𝑆𝐼 𝑆 Assumption). For all PPT adver- the reader to the listed schemes for explanations on assumptions
saries A, the probability such as DL, DDH, OM-RSA, DLIN and the models like standard
"
𝑛× (𝑚−𝑛)
# model and ROM. We put [12, 30] together as their efficiency and
𝐴®′ ←𝑠 U (𝑅𝑞 ), ®𝑧 = 0® ∈ 𝑅𝑞𝑛 ,
𝐴® assumption are very similar. The RSA-based CH in [7] is similar to
Pr :
𝐴® = [𝐼®𝑛 ||𝐴®′ ], 𝑧® ← A (𝐴)
® 0 < ∥®𝑧 ∥ ≤ 𝛽𝑆𝐼𝑆 the tag-based CH in [4]. We do not put the tag-based CHs [4, 23]
is at most negl(𝜆). for comparison since the security model is different from the nor-
mal CH. According to Table 2, our ECC-based construction is the
Definition 3.7 (M-LWE𝑛,𝑚,𝑞,𝜒 Assumption). Let 𝜒 be a distribu- shortest one and the fastest one except the classical CH. We use
tion over 𝑅𝑞 and 𝑠® ←𝑠 𝜒 𝑛 be a secret key. Define LWE𝑞,𝑠 as the the strongest model of full IND and full CollRes.
distribution obtained by sampling 𝑎® ←𝑠 𝑅𝑞𝑛 , 𝑒 ←𝑠 𝜒 and outputting By following DSS20 [11], Derler et al. [10] introduced a new
(𝑎,
® ⟨®
𝑎, 𝑠®⟩ + 𝑒). For all PPT adversaries A, the probability of dis- framework of chameleon hash scheme with full collision-resistance.
tinguishing between 𝑚 samples from LWE𝑞,𝑠 and U (𝑅𝑞𝑛 , 𝑅𝑞 ) is The idea is to replace PKE used in [11] with a commitment scheme
negl(𝜆). (e.g., Pedersen commitment). They also present a quantum-secure
CH scheme using commitment and zero-knowledge proofs from
The algorithm is as follows:
learning parity with noise [20]. They use a ZK proof with hash
• CHPG(𝜆): On input the security parameter 𝜆, ith sets M-LWE i output size = 3 bit. Hence it needs to repeat many times to achieve
𝑘 × (𝑚−𝑘 ) ®
parameters 𝑘, 𝑚, 𝑑, 𝑞, picks 𝐺® ′ ← 𝑅𝑞 , 𝐺 = 𝐼®𝑘 ∥ 𝐺® ′ and soundness error ≤ 2 −128 . It implies that their ZK proof size is very
collision-resistant hash function 𝐻 : {0, 1}∗ → 𝑅𝑞𝑘 and 𝐻 ′ : large and impractical. In contrast, our lattice-based construction is
very practical (4kB for the hash value ℎ, and 15kB for 𝑟 ), and the
{0, 1}∗ → C. It returns ppch = (𝑘, 𝑚, 𝑑, 𝑞, 𝐺, ® 𝐻, 𝐻 ′ )
running time is mainly a multiplication 𝑀𝑘 ×𝑚 of a matrix with size
• CHKG(ppch ): It picks 𝑥® ← 𝔘1 and computes 𝑦® = 𝐺® · 𝑥.
𝑚 ® It outputs 𝑘 = 9, 𝑚 = 20 and a vector of length 𝑚. The size of parameters are
(skch = 𝑥, ® pkch = 𝑦).
® discussed in the Appendix C.3.
• CHash(pkch, 𝑚): It picks 𝜌® ← 𝔘𝑚 ® ®
1 and computes ℎ = 𝐺 · 𝜌®+𝐻 (𝑚). Lastly, we implement our instantiations and present our source
Then we compute a NIZK proof 𝑟 by: code at https://github.com/kychancf/CCTY24_cham_hash. We run
(1) It picks 𝑡®2 ← 𝔘𝑚𝑑 𝑚 , 𝑧® ← 𝔘𝑚
2 1 𝑚𝑑 2 −𝑑
and computes 𝑇®2 = 𝐺® · 𝑡®2 , our implementation in a Azure standard B2s virtual machines with
′ ® ®
𝑐 1 = 𝐻 (𝑇2, pkch, 𝐺 · 𝜌, ® ®
® 𝑚), 𝑇1 = 𝐺 · 𝑧®1 − pkch · 𝑐 1 . 2vCPUs and 4GB RAM. We implement our ECC-based CH in Rust
(2) It computes 𝑐 2 = 𝐻 ′ (𝑇®1, pkch, 𝐺® · 𝜌, ® 𝑚). using the curve secp256k1 from the Zengo-X curv library and
(3) It computes 𝑧®2 = 𝑡®2 − 𝑐 2 𝜌. ® If ∥𝑧®2 ∥ ∞ > 𝑚𝑑 2 − 𝑑, restart from SHA256 for the hash function. The running time is 0.189ms for
step 1. Else, it returns 𝑟 = (𝑧®1, 𝑧®2, 𝑐 1 ). CHash, 0.202ms for CHCheck, and 0.161ms for CHAdapt (exclud-
It outputs (ℎ, ® 𝑟 ). ing the CHCheck part). We implement our lattice-based CH in
® 𝑟 ): It parses 𝑟 = (𝑧®1, 𝑧®2, 𝑐 1 ). It computes Python3 using the library SymPy and SHA256 for the hash func-
• CHCheck(pkch, 𝑚, ℎ,
tion. The running time is 2.413s for CHash, 1.617s for CHCheck,
𝑦®′ = ℎ® − 𝐻 (𝑚). It outputs 1 if
and 1.653s for CHAdapt (excluding the CHCheck part).
𝑇®1 = 𝐺® · 𝑧®1 − pkch · 𝑐 1, 𝑐 2 = 𝐻 ′ (𝑇®1, pkch, 𝑦®′, 𝑚),
𝑇®2 = 𝐺® · 𝑧®2 + 𝑦®′ · 𝑐 2, 𝑐 1 = 𝐻 ′ (𝑇®2, pkch, 𝑦®′, 𝑚).
3.5 Multi-owner CH
In this subsection, we focus on our generic construction in the
and ∥𝑧®1 ∥ ∞ ≤ 𝑚𝑑 2 − 𝑑, ∥𝑧®2 ∥ ∞ ≤ 𝑚𝑑 2 − 𝑑. Otherwise, it returns 0. multi-owner setting. We assume that the scheme involves a creator
• CHAdapt(skch, 𝑚, 𝑚 ′, ℎ, ® 𝑟 ): It returns ⊥ if CHCheck(pkch, 𝑚, ℎ,
® 𝑟) = and 𝑛 owners. Specifically, the creator generates a chameleon hash,
′
0. Otherwise, it generates another NIZK proof 𝑟 with respect to and any owner can adapt the chameleon hash multiple times. We
(pkch, ℎ® − 𝐻 (𝑚 ′ )), using the secret key skch = 𝑥® and the message only sketch the difference between our generic construction with a
𝑚 ′ . It outputs 𝑟 ′ . single owner.

1082
ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore Kwan Yin Chan, Liqun Chen, Yangguang Tian, and Tsz Hon Yuen

Table 2: The comparison between different CHs.

Scheme |ℎ | |𝑟 | CHash CHAdapt Assumption Model

[21] 1G 1Z𝑞 2𝐸 G 0𝐸 G DL Standard
[2] 1G 12G+7Z𝑞 17𝐸 G 14𝐸 G DDH ROM
[7] 1Z𝑁 1Z𝑁 1𝐸 Z 1𝐸 Z OM-RSA ROM
𝑁 𝑁
[12, 30] 3Z𝑁 + |𝑐𝑡 | 1Z𝑁 2𝐸 Z +𝐸𝑐𝑡
𝑁
8𝐸 Z +𝐸𝑐𝑡
𝑁
DLIN ROM
[11] 2G 4Z𝑞 6𝐸 G 5𝐸 G DDH ROM
[10] 1G 5Z𝑞 6𝐸 G 4𝐸 G DL ROM
Ours (1) 1G 3Z𝑞 4𝐸 G 3𝐸 G DL ROM
Ours (2) 𝑘
1𝑅𝑞 𝑚 + 1| C |
2𝑅𝑞 1𝑀𝑘 ×𝑚 1𝑀𝑘 ×𝑚 M-SIS/LWE ROM

(1) (𝑛)
• CHash((pkch , . . . , pkch ), 𝑚): It picks a random 𝜌 from the do- RSA-based CH scheme fall into Level 0 for all cases. On the other
main of 𝐹 and calculates ℎ = 𝐹 (𝜌) ⊕ 𝐻 (𝑚). It computes a zero- hand, DSS20 [11] (and also DKSS20 [10]) may fall into different
(1) (𝑛)
knowledge proof 𝑟 ← Pf (crsΠ , (𝐹, ℎ⊕𝐻 (𝑚), pkch , . . . , pkch ), 𝜌). levels.
It outputs (ℎ, 𝑟 ). Note that 𝑟 is a NIZK proof for 𝜌 such that
(1) Claimability of creation of ℎ.
(1) (𝑛)
𝐹 (𝜌) = ℎ ⊕ 𝐻 (𝑚) ∨ 𝐹 (𝜌) = pkch ∨ . . . ∨ 𝐹 (𝜌) = pkch . (1) Level 0: The creator cannot claim the creation of the hash value
(1) (𝑛) ℎ. It is because any owner is able to generate the same claim.
• CHCheck((pkch , . . . , pkch ), 𝑚, ℎ, 𝑟 ): It outputs 𝑏 ← Vfy(crsΠ , • e.g., the classical CH scheme ℎ = 𝑔𝑚 pk𝑟ch or RSA-based CH.
(1) (𝑛)
(𝐹, ℎ ⊕ 𝐻 (𝑚), pkch , . . . , pkch ), 𝑟 ). (2) Level 1: The creator can claim the creation of the hash value ℎ,
(𝑖 ) (1)
• CHAdapt(skch , 𝑚, 𝑚 ′, ℎ, 𝑟 ): It returns ⊥ if CHCheck((pkch , . . . , without disclosing 𝑚.
(𝑛) • e.g., in DSS20, the creator can create a NIZK proof of knowing
pkch ), 𝑚, ℎ, 𝑟 ) = 0. Otherwise, it outputs another zero-knowledge (𝑚, 𝜌) such that ℎ = Encpkch (𝑚; 𝜌), where 𝜌 represents an
(1) (𝑛) (𝑖 )
proof 𝑟 ′ ← Pf (crsΠ , (𝐹, ℎ ⊕ 𝐻 (𝑚), pkch , . . . , pkch ), skch ). internal randomness.
(𝑖 )
Note that 𝑟 ′ is a NIZK proof for skch such that (3) Level 2: The creator can claim that the original message is 𝑚
given the hash value ℎ. It also implies creation.
(𝑖 ) (𝑖 ) (1) (𝑖 ) (𝑛)
𝐹 (skch ) = ℎ ⊕ 𝐻 (𝑚 ′ ) ∨ 𝐹 (skch ) = pkch ∨ . . . ∨ 𝐹 (skch ) = pkch . • e.g., in DSS20, the creator can output 𝑚 and create a NIZK
proof of knowing 𝜌 such that ℎ = Encpkch (𝑚; 𝜌).
The concrete construction can be constructed similarly using the
one-out-of-many commitment proof [19], Bulletproof[6]-based OR
(2) Claimability of hash output 𝑟 .
proof [22, 35]. As compared to DSS20 [11] or DKSS20 [10], we
can easily compress the size of 𝑟 to 𝑂 (log 𝑛). It could require addi- (1) Level 0: The creator/the owners cannot claim the authorship of
tional assumptions from the new NIZK proof, such as the discrete 𝑟 . It is because the creator/the owners can generate the same
logarithm relation assumption in Bulletproof[6]. claim.
• e.g., the classical CH scheme or RSA-based CH.
4 CLAIMABILITY AND DENIABILITY FOR CH (2) Level 1: The creator/the owner can claim the authorship of 𝑟 .
• e.g., in DSS20, the creator/the owner can output the internal
As discussed in section 1.3, we define the creator as the party who
randomness 𝜌 used for generating the NIZK proof in 𝑟 to
generates the hash by running CHash, and the owners as the parties
claim the authorship.
who can run the CHAdapt with their secret keys. These parties are
the insider of the chameleon hash function. The existing security
models of indistinguishability and collision-resistant only consider (3) Deniability of hash output 𝑟 .
the attack from the third party, with the corruption of the owners’ (1) Level 0: The creator/the owner cannot deny the authorship of
secret keys. 𝑟.
In this section, we study the ability of the insider, such as break- • e.g., the classical CH scheme or RSA-based CH.
ing the indistinguishability (IND) or collision-resistant (CollRes) (2) Level 1: The creator/the owner can deny the authorship of 𝑟 .
property of his own, or the counterparty. We use different defini- • No known construction achieves Level 1.
tions of IND and CollRes to analyze the existing schemes, and our
classification below is not limited to full security as some properties (4) Deniability of original message 𝑚.
have conflicts. (1) Level 0: The creator cannot deny that the original message is
𝑚, in case the owner outputs a valid hash output (ℎ, 𝑟 ′ ) for a
4.1 Classification message 𝑚 ′ later.
We first classify the ability of the creator or the owners to claim • e.g., the classical CH scheme or RSA-based CH.
or deny the generation of the hash value ℎ or the randomness 𝑟 . (2) Level 1: The creator can deny that the original message is 𝑚, in
Examples are given based on the existing schemes and also our case the owner outputs a valid hash output (ℎ, 𝑟 ′ ) for a message
generic construction. Interestingly, the classical CH scheme and the 𝑚 ′ later.

1083
Reconstructing Chameleon Hash: Full Security and the Multi-Party Setting ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore

• e.g., in DSS20, the creator can create a NIZK proof of knowing 4.2.2 Unclaimable chameleon hashes. Unclaimability requires that
(𝑚, 𝜌) such that ℎ = Encpkch (𝑚; 𝜌) and ℎ ′ = Encpkch (𝑚 ′ ; 𝜌). the creator/owners cannot convince anyone of its identity. That
Everyone can check that ℎ ≠ ℎ ′ . is, for any function that a party can produce an internal random-
ness and a chameleon secret key, another party can compute an
4.2 New Definitions: (un)claimability and indistinguishable function.
(un)deniability Definition 4.4 (Unclaimable chameleon hashes). An unclaimable
Based on the classification described above, we present the formal chameleon hash in the multi-party setting is a chameleon hash (as
definitions of (un)claimability and (un)deniability in the multi-party in Section 2.1) along with an algorithm ExtRand. The algorithm
(𝑖 )
setting, which are inspired by [26]. ExtRand takes a set of public keys pk, a secret key skch , a hash
value ℎ, a message 𝑚 and a randomness 𝑟 as input, outputs an
4.2.1 Claimable chameleon hashes. Claimability requires that the (𝑖 )
creator/owner can claim the creation of ℎ, the authorship of 𝑟 , and internal randomness 𝜌 if skch is one of secret keys for pk and
even the original message 𝑚. CHCheck(pk, ℎ, 𝑚, 𝑟 ) = 1.
ExtRand satisfies computational unclaimability. Let R be the dis-
Definition 4.1 (Claimable chameleon hash). A claimable chameleon tribution of NIZK internal randomness. For any 𝑛, there exists
hash in the multi-party setting is a chameleon hash (as in Section a negligible function 𝜀 such that the following condition holds.
2.1) along with a pair of algorithms (Claim, VerClaim). (𝑖 ) (𝑖 ) (𝑗) (𝑗)
Let (pkch , skch ), (pkch , skch ) ← CHKG(ppch, 𝑛), (ppch, 𝑛) ←
(1) (𝑛) (1) (1)
• Claim: It takes a set of public keys pk = {pkch , · · · pkch }, a CHPG(𝜆), where 𝑖 ≠ 𝑗. For any message 𝑚 and any (skch , pkch )
(𝑖 ) (𝑛) (𝑛) (1) (𝑛) (𝑖 )
secret key skch , a hash value ℎ, a message 𝑚 and a randomness 𝑟 · · · , (skch , pkch ), let pk = {pkch ) · · · , pkch } and S = {(𝑖, skch ,
as input, outputs a claim 𝜁 . The claim 𝜁 indicates the claimability (𝑖 ) (𝑖 )
pkch )}𝑖 ∈𝑛 . Let 𝜌𝑖 ← R, (ℎ𝑖 , 𝑟𝑖 ) ← CHash(pk, 𝑚; skch , 𝜌𝑖 ), and
of any values in (ℎ, 𝑚, 𝑟 ).
(𝑗)
• VerClaim: It takes a set of public keys pk, a hash value ℎ, a mes- 𝜌𝑖 ← ExtRand(pk, skch , ℎ𝑖 , 𝑟𝑖 , 𝑚). Let 𝜌 𝑗 ← R and (ℎ 𝑗 , 𝑟 𝑗 ) ←
(𝑖 ) (𝑗)
sage 𝑚, a randomness 𝑟 , a claim 𝜁 and a public key pkch as input, CHash(pk, 𝑚; skch , 𝜌 𝑗 ). Then
outputs a bit 𝑏 = {0, 1}, indicating that whether or not 𝜁 is a valid
(𝑖 )
(S, 𝜌𝑖 , ℎ𝑖 , 𝑟𝑖 ) ≈𝑐 (S, 𝜌 𝑗 , ℎ 𝑗 , 𝑟 𝑗 ).
claim of (ℎ, 𝑚, 𝑟 ) for public key pkch .
4.2.3 Deniable chameleon hashes. Deniability requires that the
Definition 4.2 (Claim Oracle OClaim). The oracle OClaim takes
creator/owner can deny the authorship of 𝑟 , and even the original
an index 𝑖 ∈ [1, 𝑛], a public-key set pk, and a tuple (ℎ, 𝑚, 𝑟 ) as
Ð (𝑖 ) (𝑖 ) message 𝑚.
input, outputs Claim(pk {pkch }, skch , ℎ, 𝑚, 𝑟 ). The oracle takes
(pk, ℎ, 𝑚, 𝑟 ) as input when it is invoked with a single key pair. Definition 4.5 (Deniable chameleon hash). A deniable chameleon
hash in the multi-party setting is a chameleon hash (as in Section
We define the oracle OClaim(· · · ) to output ⊥ if adversary 2.1) along with a pair of algorithms (Deny, VerDeny).
queries the challenge tuple (ℎ ∗, 𝑚 ∗, 𝑟 ∗ ). Otherwise, the oracle out- (1) (𝑛)
• Deny: It takes a set of public keys pk = {pkch , · · · pkch }, a secret
puts the same response as OClaim(· · · ). Claimability requires that:
(𝑖 )
(1) honest parties can claim the creation of ℎ or the authorship of 𝑟 key skch , a hash value ℎ, a message 𝑚 and a randomness 𝑟 as
on a message 𝑚; (2) adversarial parties cannot claim the creation of input, outputs a denial 𝜗. The denial 𝜗 indicates the deniability
ℎ or the authorship of 𝑟 that they did not produce on a message 𝑚; of 𝑚 or 𝑟 , even both of them.
and (3) adversarial parties cannot produce the creation of ℎ or the • VerDeny: It takes a set of public keys pk, a hash value ℎ, a message
(𝑖 )
authorship of 𝑟 on a message 𝑚 along with a claim 𝜁 that appears 𝑚, a randomness 𝑟 , a denial 𝜗 and a public key pkch as input,
to be produced by an honest party. outputs a bit 𝑏 = {0, 1}, indicating that whether or not 𝜗 is a
(𝑖 )
valid denial of (𝑚, 𝑟 ) for public key pkch .
Definition 4.3 (Claimability). A chameleon hash is claimable if
equipped with Claim and VerClaim such that the following equa- Definition 4.6 (Deny Oracle ODeny). The oracle ODeny takes
tions hold an index 𝑖 ∈ [1, 𝑛], a public-key set pk, and a tuple (ℎ, 𝑚, 𝑟 ) as
Ð (𝑖 ) (𝑖 )
• Equation (1). There exists a negligible function 𝜀 such that for any input, outputs Deny(pk {pkch }, skch , ℎ, 𝑚, 𝑟 ). The oracle takes
(1) (1) (𝑛) (𝑛) (pk, ℎ, 𝑚, 𝑟 ) as input when it is invoked with a single key pair.
(skch , pkch ), · · · , (skch , pkch ) ← CHKG(ppch, 𝑛), (ppch, 𝑛) ←
CHPG(𝜆) and any 𝑖 ∈ [1, 𝑛], it holds for any message 𝑚 that We define the oracle ODeny(· · · ) to output ⊥ if adversary queries
Pr[(ℎ, 𝑟 ) ← CHash(pk, 𝑚) : the challenge values (pk∗, ℎ ∗ ). Otherwise, the oracle outputs the
(𝑖 ) (𝑖 )
same response as ODeny(· · · ). Deniability requires that: (1) hon-
VerClaim(pk, pkch , ℎ, 𝑚, 𝑟, Claim(pk, skch , ℎ, 𝑚, 𝑟 )) = 1] est parties who did not produce message 𝑚 and/or randomness 𝑟
> 1 − 𝜀 (𝜆). can deny; and (2) adversarial parties possessing a subset of secret
(1) (𝑛) (1) (𝑛)
keys cannot deny (𝑚, 𝑟 ) under all public keys in a set. Equation (2)
where sk = {skch , · · · skch } and pk = {pkch · · · , pkch }. captured the following cases: 1) If a party generates all keys in a
• Equation (2) & (3). The advantage of A illustrated in Figure 5 set, s/he may produce denials on {(𝑚, 𝑟 )} under every public key
and 6 is negligible in 𝜆, respectively. Q is the set of queries made in the set. Given denials under every public key in a set, anyone
(𝑖 )
to oracle OClaim(· · · ), and pkch is an honest party in Figure 6. can infer that all keys in the set were generated dishonestly and

1084
ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore Kwan Yin Chan, Liqun Chen, Yangguang Tian, and Tsz Hon Yuen

Experiment ExpA (𝜆) We provide two justifications. First, we show that deniable chameleon
(ppch , 𝑛) ← CHPG(𝜆)
(𝑖 ) (𝑖 ) hashes cannot satisfy full indistinguishability. If an attacker obtains
(skch , pkch ) ← CHKG(ppch , 𝑛)
(𝑖 )
(pk′ , 𝜁 ) ← A OClaim(··· ) (pkch )
all secret keys in the generation of 𝑟 , the attacker can produce
(𝑖 ) denial using each secret key. As a result, the attacker can identify
where OClaim(· · · ) on input pkch , ℎ, 𝑚, 𝑟 :
(𝑖 ) (𝑖 )
𝜁 ← Claim(pk′ {pkch }, skch , ℎ, 𝑚, 𝑟 )
Ð the creator of 𝑟 , as there exists one secret key for which the Deny
return 𝜁 algorithm could not produce a valid denial 𝜗 (i.e., adversarial parties
(𝑖 )
return 1, if CHCheck(pk′ {pkch }, ℎ, 𝑚, 𝑟 ) = 1
Ð
(𝑖 ) (𝑗) (𝑗) (𝑖 )
cannot deny under all public keys in a set, as in Figure 8).
∧VerClaim(pk′ {pkch }, pkch , ℎ, 𝑚, 𝑟, 𝜁 ) = 1 ∧ pkch ≠ pkch
Ð
Second, we show that fully indistinguishable chameleon hashes
else, return 0.
can imply undeniability. We consider a scenario where an owner
Bob should behave indistinguishably from a creator Alice, but the
Figure 5: Equation (2) for Claimability. attackers cannot identify the creation of 𝑟 given their secret keys.
Experiment ExpA (𝜆)
That is, for any protocol that Bob could execute with respect to
(ppch , 𝑛) ← CHPG(𝜆), Q ← 0 a randomness 𝑟 and his public key pkch ′ , Alice should engage in
(𝑖 ) (𝑖 )
(skch , pkch ) ← CHKG(ppch , 𝑛) the same protocol with respect to her own public key pkch and
(𝑖 )
(pk′ , ℎ, 𝑚, 𝑟, 𝜁 ) ← A OClaim(··· ) (pkch ) behave indistinguishably from Bob. In this scenario, we require
(𝑖 )
return 1, if CHCheck(pk′
Ð
{pkch }, ℎ, 𝑚, 𝑟 ) = 1
that if Bob’s secret key skch′ is compromised, the attacker cannot
(𝑖 ) (𝑖 )
∧VerClaim(pk {pkch }, pkch , ℎ, 𝑚, 𝑟, 𝜁 ) = 1 ∧ Q ∩ { (pk′ , ℎ, 𝑚, 𝑟, ·) } = ∅
′ Ð
else, return 0.
decide whether 𝑟 was produced by Bob or by someone else. Besides,
if Bob lends his key to someone else who used it to produce 𝑟 , Bob
could not decide as well. The definition of full indistinguishability
Figure 6: Equation (3) for Claimability. represents this scenario: attackers cannot produce a valid denial 𝜗
Experiment ExpA (𝜆) of 𝑟 even if they access all secret keys corresponding 𝑟 .
(ppch , 𝑛) ← CHPG(𝜆), Q ← 0
(𝑖 ) (𝑖 )
(skch , pkch ) ← CHKG(ppch , 𝑛) Remark. We have so far shown full indistinguishability, full collision-
(𝑖 )
(pk′ , ℎ, 𝑚, 𝑟 ) ← A ODeny(··· ) (pkch ) resistance, (un)claimability and (un)deniablity for chameleon hashes.
(𝑖 )
𝜗 ← Deny(pk′ , skch , ℎ, 𝑚, 𝑟 ) They are not entirely separate properties: one might imply the other
return 1, if CHCheck(pk′ , ℎ, 𝑚, 𝑟 ) = 0 (e.g., full indistinguishability implies undeniability). On the other
(𝑖 )
∨VerDeny(pk′ , pkch , ℎ, 𝑚, 𝑟, 𝜗 ) = 1 ∨ Q ∩ { (pk′ , ℎ, · · · ) } ≠ ∅
else, return 0.
hand, some properties may have conflicts. For example, one can-
not create a deniable CH with full indistinguishability. The natural
question is whether one can create a secure chameleon hash with
Figure 7: Equation (1) for Deniability. a (sub)set of these properties. First, the combination of these prop-
Experiment ExpA (𝜆) erties could be various depending on the application scenarios.
(ppch , 𝑛) ← CHPG(𝜆), Q ← 0 Second, it would be a nice conclusion if we could find the relation-
(1) (1) (𝑛) (𝑛)
(skch , pkch ) · · · , (skch , pkch ) ← CHKG(ppch , 𝑛)
′
ships among these properties. We leave it for future research, as
(pk , ℎ, 𝑚, 𝑟, {𝜗 (𝑖 ) } (𝑖 ) ′
) ← A ODeny(··· ) (pk)
pk pk ∈pk \pk our main focus in this work is full indistinguishability, full collision-
ch ch
return 1, if CHCheck(pk′ , ℎ, 𝑚, 𝑟 ) = 0
(𝑖 ) resistance and multi-party setting.
VerDeny(pk′ , pkch , ℎ, 𝑚, 𝑟, 𝜗 (𝑖 )
Ô
∨ (𝑖 ) )=0
pk ∈pk′ \pk pk ∈pk′ \pk
ch ch
∨pk′ ∩ pk = ∅ ∨ Q ∩ { (pk′ , ℎ, · · · ) } ≠ ∅
else, return 0. 4.3 Our Constructions
4.3.1 Claimability of creation of ℎ. Our scheme is level 2, since the
Figure 8: Equation (2) for Deniability. function 𝐹 is one-way. Also, we do not have an efficient NIZK for
the hash function, so no efficient level 1 (theoretically we can use
zk-SNARK).
all parties in the set colluded to produce each tuple (ℎ, 𝑚, 𝑟 ) under 4.3.2 Claimability of hash output 𝑟 . Our generic construction is
that set. 2) If there exist denials for a subset of public keys in a set, flexible for using different NIZK proofs. We can have a Level 0 or
then anyone can infer that either one of the remaining public keys Level 1 construction.
(𝑖 )
in the set (i.e., pkch ∈ pk′ \pk in Fig 8) produced the values (𝑚, 𝑟 )
or all of the remaining public keys colluded to produce it. Level 0 Construction. We give the multi-owner construction using
(uncompressed) Dual Ring [34] to construct CH with unclaimable
Definition 4.7 (Deniability). A chameleon hash is deniable if the hash output.
advantage of A described in Figure 7 and 8 is non-negligible in
(1) (𝑛)
𝜆, i.e., 1 − 𝜀 (𝜆). Q is the set of chameleon hash tuples involved in • CHash((pkch , . . . , pkch ), 𝑚): It picks random 𝜌 ∈ Z𝑞 and sets
(𝑖 ) ℎ = 𝑔𝜌 · 𝐻 (𝑚). Then we compute a NIZK proof 𝑟 by:
the experiment. pkch ∈ pk′ \pk indicates the parties cannot deny
(𝑚, 𝑟 ) in Fig 8. (1) It picks random 𝑡, 𝑐 1, . . . , 𝑐𝑛 ∈ Z𝑞 and computes
(𝑖 )
𝑇 = 𝑔𝑡 𝑛𝑖=1 (pkch ) −𝑐𝑖 .
Î
4.2.4 Undeniable chameleon hashes. (1) (𝑛)
(2) It computes 𝑐 0 = 𝐻 ′ (𝑇 , 𝑔𝜌 , pkch , . . . , pkch , 𝑚) − 𝑛𝑖=1 𝑐𝑖 .
Í
Claim 1. A chameleon hash in the multi-party setting is undeni- (3) It computes 𝑧 = 𝑡 + 𝑐 0 𝜌, and sets 𝑟 = (𝑧, 𝑐 0, 𝑐 1, . . . , 𝑐𝑛 ).
able if it satisfies full indistinguishability. It outputs (ℎ, 𝑟 ).

1085
Reconstructing Chameleon Hash: Full Security and the Multi-Party Setting ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore

(1) (𝑛)
• CHCheck((pkch , . . . , pkch ), 𝑚, ℎ, 𝑟 ): It parses 𝑟 = (𝑧, 𝑐 0, 𝑐 1, . . . , 𝑐𝑛 ). deny generating it (where 𝑖 ≠ 𝑗), he can compute a zero-knowledge
It computes 𝑦 ′ = ℎ/𝐻 (𝑚). It outputs 1 if (𝑖 )
proof 𝜋 for skch such that:
𝑛
(𝑖 ) (1) (𝑛)
Ö
𝑐 0 + . . . + 𝑐𝑛 = 𝐻 ′ (𝑔𝑧 𝑦 ′−𝑐 0 (pkch ) −𝑐𝑖 , 𝑦 ′, pkch , . . . , pkch , 𝑚). (𝑖 )
(𝑖 ) (𝑖 )
𝐻ˆ (𝑚) skch ≠ 𝑍 ∧ pkch = 𝑔skch .
𝑖=1
Otherwise, it returns 0.
The zero-knowledge proof of inequality of discrete logarithm can
Proof of unclaimability of hash output. For any hash output ℎ ∗ be efficiently instantiated.
(𝑖 )
and 𝑟 ∗ = (𝑧 ∗, 𝑐 1∗, . . . , 𝑐𝑛∗ ), any owner skch can claims that he gener-
ated this pair (ℎ ∗, 𝑟 ∗ ) by reconstructing the value 𝑡𝑖 = 𝑧 ∗ − 𝑐𝑖∗ skch .
(𝑖 ) 5 APPLICATION: REDACTABLE
The creator can also compute 𝑡 0 = 𝑧 ∗ − 𝑐 0∗ 𝜌. The values 𝑡 0, 𝑡 1, . . . , 𝑡𝑛 BLOCKCHAINS
can be used to claim the authorship of (ℎ ∗, 𝑟 ∗ ). Hence this scheme We consider redactable blockchain as an application scenario. Such
is unclaimable. a blockchain allows some after-the-fact modifications of its content.
This is motivated by the illicit content that might be included in
Level 1 Construction. We use the one-out-of-many commitment
the Bitcoin blockchain, which poses a significant challenge for
proof to give a level 1 construction.
law enforcement agencies like INTERPOL and legislations like
Assume that the public parameters include another generator
GDPR (General Data Protection Regulation). The existing solutions
𝑔ˆ ∈ G. Define a commitment scheme for a message 𝑚 ∈ Z𝑞 and
may either work for the permissioned [12] or the permissionless
randomness 𝜌 ∈ Z𝑞 as
setting [14], use cryptographic [2] or non-cryptographic tool [14],
Com(𝑚; 𝜌) = 𝑔ˆ𝑚 𝑔𝜌 . allow block-level [2] or transaction-level rewriting [12]. This work
In our ECC-based construction, all public keys can be viewed as a relies on a cryptographic tool (i.e., a chameleon hash function) to
commitment of zero: Com(0; skch ). We utilize the one-out-of-many redact mutable transactions in the permissionless setting. We do
commitment proof to generate 𝑟 in the chameleon hash. Without not consider block insertions and removals as described in [15].
loss of generality (WLOG), assume that we want to compute 𝑟 by Full indistinguishability and full collision-resistance provide en-
(𝑗) (𝑗) hanced privacy and security guarantees to the redactable blockchains,
using skch . Then we compute a zero-knowledge proof for skch
as discussed in [11, 30]. Here, we justify the multi-party setting,
such that
(𝑗) (𝑗) (un)claimability and (un)deniability. Multiple party setting is more
Com(0; skch ) = pkch ∧ 𝑗 ∈ [0, 𝑛]. desirable for redactable blockchains, especially considering single-
In the one-out-of-many proof [19], they express 𝑗 as a binary point of failure towards a trapdoor holder. Chameleon hashes in the
number (ℓ1, . . . , ℓlog 𝑛 ) and compute commitment Com(ℓ𝑖 ; 𝜌𝑖 ) us- multi-party setting have been studied in the literature. For example,
ing randomness 𝜌𝑖 for 𝑖 ∈ [1, log 𝑛]. A similar idea applies to the a threshold number of parties (or miners) are allowed to execute
Bulletproof-based OR proof [22, 35]. a multi-party computation protocol to redact blocks (or transac-
Proof of claimability of hash output. Since Com is binding, only tions) [2, 28]. Also, the redactable blockchains based on policies
the author can output a valid pair (ℓ𝑖 ; 𝜌𝑖 ). Anyone can validate [12, 32] allow multiple authorized parties to rewrite the mutable
(ℓ𝑖 ; 𝜌𝑖 ), reconstruct 𝑗 from (ℓ1, . . . , ℓlog 𝑛 ) and find the index of the transactions.
author. Claimability allows an owner to prove the authorship of a modi-
fied transaction at a later date, especially in the case of rewriting a
4.3.3 Deniability of hash output 𝑟 . All of the existing constructions mutable transaction containing illicit content to a benign one. De-
are Level 0 in deniability, including our ECC-based construction. niability implies that the creator who created a mutable transaction
Level 1 Construction. We now give a Level 1, multi-owner con- containing illicit content may deny it. The owner also wants to deny
struction, inspired from linkable ring signature [24]. Assume that the malicious rewriting by one of his members. For example, the
there is another collision-resistant hash function 𝐻ˆ : {0, 1}∗ → G owner may suffer serious consequences through no fault of his own,
in the public parameters. or due to the creator adversarially trying to damage his reputation.
We also utilize the one-out-of-many commitment proof to gen- Malicious rewriting means either adding illicit or malicious content
erate a zero-knowledge proof 𝜋 in the chameleon hash. In addition, to mutable transactions, or deleting legitimate or benign mutable
(𝑗) transactions from the blockchain. Unclaimability and undeniability
the creator/owner has to compute an extra value 𝑍 = 𝐻ˆ (𝑚) skch .
(𝑗) are also useful properties. For example, an authority (e.g., an au-
WLOG, we compute a zero-knowledge proof 𝜋 for skch such that thoritarian government) may coerce the creator/owners to provide
(𝑗) proof of authorship or denial for a maliciously written transaction,
(𝑗) (𝑗)
Com(0; skch ) = pkch ∧ 𝑍 = 𝐻ˆ (𝑚) skch ∧ 𝑗 ∈ [0, 𝑛]. the provable inability to do so is desired. Undeniability may also be
The hash output is (ℎ, 𝑟 = (𝜋, 𝑍 )). desirable in accountable redactable blockchains [32].
Observe that the value 𝑍 will not compromise the indistinguisha- Structures. We consider two types of changes are required in redactable
bility if the DDH assumption holds in G. This level of indistinguisha- blockchains: block-level and transaction-level. First, we follow
bility assumes attackers cannot access creator/owner’s secret keys. the notation used in [2, 11], and describe a block in Bitcoin as
Proof of deniability of hash output. Suppose that (ℎ, 𝑟 = (𝜋, 𝑍 )) 𝐵 = ⟨𝑠, 𝑥, 𝑐𝑡𝑟 ⟩, where 𝑠 ∈ {0, 1}𝜆 contains the block header (minus
(𝑗)
is generated by skch for some 𝑗 ∈ [0, 𝑛]. For party 𝑖 who wants to the nonce), 𝑥 ∈ {0, 1}∗ contains all the transactions inside a block,

1086
ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore Kwan Yin Chan, Liqun Chen, Yangguang Tian, and Tsz Hon Yuen

by replacing (𝑚, 𝑟 ) with (𝑚 ′, 𝑟 ′ ). After modification, the key holder

broadcasts (𝑚 ′, 𝑟 ′ ), and 𝑖𝑑 (helps other parties to identify which
transaction needs to be updated) in the blockchain network, each
party will perform the following checks.
• whether the message 𝑚 needs to be modified as 𝑚 ′ according to
some rules like GDPR.
• whether the message-randomness pairs (𝑚, 𝑟 ) and (𝑚 ′, 𝑟 ′ ) are
Figure 9: Changes to transactions. mapping to the same chameleon hash value ℎ and they are valid
under a set of public keys {pkch }.
and 𝑐𝑡𝑟 ∈ N denotes a nonce value, and a block is valid if If the above requirements are met, all parties are required to
update their local copy of the blockchain by replacing (𝑚, 𝑟 ) with
validblock𝑞𝐷 (𝐵) := 𝐻 (𝑐𝑡𝑟, 𝐺 (𝑠, 𝑥)) < 𝐷 ∧ 𝑐𝑡𝑟 < 𝑞.
(𝑚 ′, 𝑟 ′ ). Based on Figure 9, each mutable transaction additionally
Here (𝐻, 𝐺) are two collision-resistant hash functions. To make contains one element in the output field, and three elements in the
a block mutable, we change the description of the block to 𝐵 = auxiliary field. Considering our concrete ECC-based CH instantia-
⟨𝑠, 𝑥, 𝑐𝑡𝑟, (ℎ, 𝑟, 𝐻 ′ (pkch ))⟩, where the new component is a chameleon tion, the elements in the auxiliary field are 162 bytes. The running
hash (ℎ, 𝑟, 𝐻 ′ (pkch )) with a public key pkch , and 𝐻 ′ denotes an- time for hashing and verifying are both around 0.6s, which is quite
other collision-resistant hash function. The validation predicate practical.
changes to
6 CONCLUSION
validblock𝑞𝐷 (𝐵) := 𝐻 (𝑐𝑡𝑟, ℎ, 𝐻 ′ (pkch )) < 𝐷 ∧ 𝑐𝑡𝑟 < 𝑞
In this paper, we proposed a new generic construction of the chameleon
∧CHCheck(pkch, (𝑠, 𝑥), ℎ, 𝑟 ) = 1. hash function supporting enhanced security and usability guaran-
Note that the underlined part is used to prevent the key replacement tees. The proposed scheme achieved full indistinguishability, full
attack. For rewriting a block, a key holder may change (𝑠, 𝑥) to collision-resistance, and multi-party setting simultaneously with
(𝑠 ′, 𝑥 ′ ), and update 𝑟 to 𝑟 ′ . minimal extra overhead. We also discussed (un)claimability and
Second, we show the modifications to a Bitcoin transaction, and (un)deniability properties for chameleon hashes to satisfy broader
we list immutable, mutable and redacted transactions in Figure 9. chameleon hash-based applications. Lastly, we presented practical
The key difference between an immutable transaction and a mutable ECC and quantum-secure instantiations, and our implementation of
one is an auxiliary field. This auxiliary field is used to verify the these two instantiations showed that they are suitable for real-life
chameleon hash only. Its size is constant due to the hashing of applications such as redactable blockchains.
multiple chameleon public keys (i.e., 𝐻 ′ (pkch )). For rewriting a
chameleon-hashed message 𝑚, a key holder changes 𝑚 to 𝑚 ′ , and ACKNOWLEDGEMENT
updates 𝑟 to 𝑟 ′ . This work is supported by the EU’s research and innovation pro-
Modification Process. First, we need to clarify the redacted content gram: 101019645 (SECANT) and 101095634 (ENTRUST). These
inside a mutable block or transaction. For rewriting a block, the key projects are funded by the UK government Horizon Europe guar-
holder can rewrite 𝑠 or 𝑥, or both [2, 11]. But, we argue that it is more antee and administered by UKRI. Yangguang Tian is partially sup-
reasonable to rewrite 𝑥. This is because rewriting some content in ported by the National Natural Science Foundation of China under
a block header 𝑠 may break some rules such as fork. Thus, we focus Grant No. 62072371 and 61872264.
on redacting some (illicit) content inside a mutable transaction like
[14]. We consider two cases in rewriting a mutable transaction. For REFERENCES
a Bitcoin transaction, we slightly modify its structure to make it mu- [1] G. Ateniese, D. H. Chou, B. de Medeiros, and G. Tsudik. Sanitizable signatures.
table. The Bitcoin transaction’s structure mainly includes two fields: In S. d. C. di Vimercati, P. Syverson, and D. Gollmann, editors, Computer Secu-
rity – ESORICS 2005, pages 159–177, Berlin, Heidelberg, 2005. Springer Berlin
1) the input contains a hash of the previous transaction (Pre-Tx), Heidelberg.
and a signature (Sig); 2) the output contains an amount, and a public [2] G. Ateniese, B. Magri, D. Venturi, and E. Andrade. Redactable blockchain – or –
rewriting history in bitcoin and friends. In 2017 IEEE European Symposium on
key (Pub-Key) which is used to verify a (redeemer’s) signature on a Security and Privacy (EuroS&P), pages 111–126, 2017.
transaction. We add a message 𝑚 (i.e., arbitrary data) to the output [3] M. Bellare and G. Neven. Multi-signatures in the plain public-key model and a
field to create a mutable Bitcoin transaction. For transactions in general forking lemma. In Proceedings of the 13th ACM Conference on Computer
and Communications Security, CCS ’06, page 390–399, New York, NY, USA, 2006.
Ethereum, a submitted (regular) transaction contains similar fields Association for Computing Machinery.
as in Bitcoin, except an optional field including arbitrary data [18]. [4] C. Brzuska, M. Fischlin, T. Freudenreich, A. Lehmann, M. Page, J. Schelbert,
Like most redactable blockchain solutions, we do not allow anyone D. Schröder, and F. Volk. Security of sanitizable signatures revisited. In S. Jarecki
and G. Tsudik, editors, Public Key Cryptography – PKC 2009, pages 317–336,
to change transaction amount, public key (or address), otherwise it Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.
may cause transaction inconsistency [14, 28]. [5] C. Brzuska, M. Fischlin, A. Lehmann, and D. Schröder. Unlinkability of sanitizable
signatures. In P. Q. Nguyen and D. Pointcheval, editors, Public Key Cryptography
Third, we assume the message 𝑚 as illicit content, and we take – PKC 2010, pages 444–461, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.
the mutable transaction recording message 𝑚 in Figure 9 to explain [6] B. Bünz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell. Bulletproofs:
the modification process. Since the message 𝑚 is hashed under a Short proofs for confidential transactions and more. In 2018 IEEE Symposium on
Security and Privacy (SP), pages 315–334, 2018.
set of public keys {pkch }, it can be modified by one of the secret [7] J. Camenisch, D. Derler, S. Krenn, H. C. Pöhls, K. Samelin, and D. Slamanig.
key holders. Thus, a key holder can redact the mutable transaction Chameleon-hashes with ephemeral trapdoors. In S. Fehr, editor, Public-Key

1087
Reconstructing Chameleon Hash: Full Security and the Multi-Party Setting ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore

Cryptography – PKC 2017, pages 152–182, Berlin, Heidelberg, 2017. Springer [32] Y. Tian, N. Li, Y. Li, P. Szalachowski, and J. Zhou. Policy-based chameleon hash
Berlin Heidelberg. for blockchain rewriting with black-box accountability. In Annual Computer
[8] S. Canard, A. Jambert, and R. Lescuyer. Sanitizable signatures with several signers Security Applications Conference, ACSAC ’20, page 813–828, New York, NY, USA,
and sanitizers. In A. Mitrokotsa and S. Vaudenay, editors, Progress in Cryptology 2020. Association for Computing Machinery.
- AFRICACRYPT 2012, pages 35–52, Berlin, Heidelberg, 2012. Springer Berlin [33] B. Yu, S. K. Kermanshahi, A. Sakzad, and S. Nepal. Chameleon hash time-lock
Heidelberg. contract for privacy preserving payment channel networks. In R. Steinfeld
[9] S. Canard, F. Laguillaumie, and M. Milhau. Trapdoor sanitizable signatures and T. H. Yuen, editors, Provable Security, pages 303–318, Cham, 2019. Springer
and their application to content protection. In S. M. Bellovin, R. Gennaro, International Publishing.
A. Keromytis, and M. Yung, editors, Applied Cryptography and Network Security, [34] T. H. Yuen, M. F. Esgin, J. K. Liu, M. H. Au, and Z. Ding. Dualring: Generic
pages 258–276, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. construction of ring signatures with efficient instantiations. In T. Malkin and
[10] D. Derler, S. Krenn, K. Samelin, and D. Slamanig. Fully collision-resistant C. Peikert, editors, Advances in Cryptology – CRYPTO 2021, pages 251–281, Cham,
chameleon-hashes from simpler and post-quantum assumptions. In C. Galdi and 2021. Springer International Publishing.
V. Kolesnikov, editors, Security and Cryptography for Networks, pages 427–447, [35] T. H. Yuen, S.-F. Sun, J. K. Liu, M. H. Au, M. F. Esgin, Q. Zhang, and D. Gu. Ringct
Cham, 2020. Springer International Publishing. 3.0 for blockchain confidential transaction: Shorter size and stronger security. In
[11] D. Derler, K. Samelin, and D. Slamanig. Bringing order to chaos: The case of J. Bonneau and N. Heninger, editors, Financial Cryptography and Data Security,
collision-resistant chameleon-hashes. In A. Kiayias, M. Kohlweiss, P. Wallden, pages 464–483, Cham, 2020. Springer International Publishing.
and V. Zikas, editors, Public-Key Cryptography – PKC 2020, pages 462–492, Cham,
2020. Springer International Publishing.
[12] D. Derler, K. Samelin, D. Slamanig, and C. Striecks. Fine-grained and controlled A SECURITY IN THE MULTI-KEY SETTING
rewriting in blockchains: Chameleon-hashing gone attribute-based. In NDSS,
2019. In this section, we show our key replacement attacks for concrete
[13] D. Derler and D. Slamanig. Key-homomorphic signatures: definitions and appli- schemes SS20 [30] and DSS20 [11], and provide a fix.
cations to multiparty signatures and non-interactive zero-knowledge. Designs,
Codes and Cryptography, 87(6):1373–1413, 2019.
[14] D. Deuber, B. Magri, and S. A. K. Thyagarajan. Redactable blockchain in the A.1 Key Replacement Attack on SS20
permissionless setting. In 2019 IEEE Symposium on Security and Privacy (SP),
pages 124–138, 2019. Suppose that the RSA public key is (𝑁 , 𝑒). The RSA-based chameleon
[15] M. S. Dousti and A. Küpçü. Tri-op redactable blockchains with block modification, hash in SS20 [30] is
removal, and insertion. Turkish Journal of Electrical Engineering and Computer
Sciences, 30(2):376–391, 2022.
[16] M. F. Esgin. Practice-Oriented Techniques in Lattice-Based Cryptography. PhD ℎ = 𝐻 (𝑚) · 𝑟 𝑒 mod 𝑁 ,
thesis, Monash University, 5 2020.
[17] M. F. Esgin, R. Steinfeld, J. K. Liu, and D. Liu. Lattice-based zero-knowledge for some randomness 𝑟 . Suppose (𝑁 ′, 𝑒 ′ ) and 𝑑 ′ is the RSA key pair
of the attacker. For any message 𝑚 ′ , he finds 𝑟 ′ such that:
proofs: New techniques for shorter and faster constructions and applications. In
A. Boldyreva and D. Micciancio, editors, Advances in Cryptology – CRYPTO 2019,
pages 115–146, Cham, 2019. Springer International Publishing.
′
[18] ethereum.org. Transactions, 2023. https://ethereum.org/en/developers/docs/transactions/. 𝑟 ′ = (ℎ/𝐻 (𝑚 ′ ))𝑑 mod 𝑁 ′ .
[19] J. Groth and M. Kohlweiss. One-out-of-many proofs: Or how to leak a secret
and spend a coin. In E. Oswald and M. Fischlin, editors, Advances in Cryptology
- EUROCRYPT 2015, pages 253–280, Berlin, Heidelberg, 2015. Springer Berlin It is easy to see that (𝑚 ′, 𝑟 ′ ) is a collision of ℎ with respect to
Heidelberg. (𝑁 ′, 𝑒 ′ ).
[20] A. Jain, S. Krenn, K. Pietrzak, and A. Tentes. Commitments and efficient zero-
knowledge proofs from learning parity with noise. In X. Wang and K. Sako,
editors, Advances in Cryptology – ASIACRYPT 2012, pages 663–680, Berlin, Hei- A.2 Key Replacement Attack on DSS20
delberg, 2012. Springer Berlin Heidelberg.
[21] H. Krawczyk and T. Rabin. Chameleon signatures. In NDSS, 2000. Suppose that the ElGamal public key is 𝑦. The chameleon hash in
[22] R. W. F. Lai, V. Ronge, T. Ruffing, D. Schröder, S. A. K. Thyagarajan, and J. Wang. DSS20 [11] is:
Omniring: Scaling private payments without trusted setup. In Proceedings of the
2019 ACM SIGSAC Conference on Computer and Communications Security, CCS
’19, page 31–48, New York, NY, USA, 2019. Association for Computing Machinery. ℎ = (𝐶 1 = 𝑚 · 𝑦 𝜌 , 𝐶 2 = 𝑔𝜌 ).
[23] Y. Li and S. Liu. Tagged chameleon hash from lattice and application to redactable
blockchain. Cryptology ePrint Archive, 2023. Let (𝑥 ′, 𝑦 ′ ) as another key pair of the attacker. The attacker can
[24] X. Lu, M. H. Au, and Z. Zhang. Raptor: A practical lattice-based (linkable) ring
signature. In R. H. Deng, V. Gauthier-Umaña, M. Ochoa, and M. Yung, editors, calculate
Applied Cryptography and Network Security, pages 110–130, Cham, 2019. Springer ′
International Publishing. 𝑚 ′ = 𝐶 1𝐶 2−𝑥 .
[25] V. Lyubashevsky. Lattice signatures without trapdoors. In D. Pointcheval and ′ ′
T. Johansson, editors, Advances in Cryptology – EUROCRYPT 2012, pages 738–755, Then we can write 𝑚 ′ · (𝑦 ′ ) 𝜌 = 𝐶 1𝐶 2−𝑥 · 𝑔𝑥 𝜌 = 𝐶 1 . Hence ℎ is the
[26]
Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
S. Park and A. Sealfon. It wasn’t me! repudiability and claimability of ring
ElGamal encryption of 𝑚 ′ with respect to 𝑦 ′ . With the knowledge
signatures. In A. Boldyreva and D. Micciancio, editors, Advances in Cryptology – of 𝑥 ′ , the attacker can generate a valid NIZK proof of 𝑟 ′ . Hence
CRYPTO 2019, pages 159–190, Cham, 2019. Springer International Publishing. (𝑚 ′, 𝑟 ′ ) is a collision for ℎ with respect to 𝑦 ′ .
[27] B. Poettering and D. Stebila. Double-authentication-preventing signatures. In
M. Kutyłowski and J. Vaidya, editors, Computer Security - ESORICS 2014, pages
436–453, Cham, 2014. Springer International Publishing. A.3 Solution to the Key Replacement Attack
[28] I. Puddu, A. Dmitrienko, and S. Capkun. 𝜇 chain: How to forget without hard
forks. Cryptology ePrint Archive, Paper 2017/106, 2017. Our solution is to change the hash value as (ℎ, 𝐻 ′ (pkch )), for some
[29] T. Ruffing, A. Kate, and D. Schröder. Liar, liar, coins on fire! penalizing equivoca- collision-resistant hash function 𝐻 ′ . In the multi-owner setting, we
tion by loss of bitcoins. In Proceedings of the 22nd ACM SIGSAC Conference on
Computer and Communications Security, CCS ’15, page 219–230, New York, NY, change the hash value as (ℎ, 𝐻 ′ (pk)), where pk contains a creator
USA, 2015. Association for Computing Machinery. and multiple owners. We also show how to apply such modification
[30] K. Samelin and D. Slamanig. Policy-based sanitizable signatures. In S. Jarecki,
editor, Topics in Cryptology – CT-RSA 2020, pages 538–563, Cham, 2020. Springer
to redactable blockchains in Section 5. We stress that the owners’
International Publishing. public keys must be authenticated by a certificate authority. The
[31] A. Shamir and Y. Tauman. Improved online/offline signature schemes. In J. Kilian, creator must use the authenticated public keys to create H′ (pk),
editor, Advances in Cryptology — CRYPTO 2001, pages 355–367, Berlin, Heidelberg,
2001. Springer Berlin Heidelberg. and anyone is supposed to check H′ (pk) during CHCheck. This
additional check is needed for a secure chameleon hash function.

1088
ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore Kwan Yin Chan, Liqun Chen, Yangguang Tian, and Tsz Hon Yuen

B SECURITY PROOF OF THE ECC-BASED C SECURITY PROOF OF THE LATTICE-BASED

CONSTRUCTION CONSTRUCTION
To prove Theorem 3.4 and 3.5, we first show that the ECC-based Because of the “knowledge-gap" in lattice-based NIZK proof, we
NIZK proof has the desired properties. cannot use the simulation-sound extractability of our lattice-based
Lemma B.1. The ECC-based NIZK proof has zero-knowledge and NIZK proof. We refer the reader to earlier works [17, 25] for expla-
simulation-sound extractability in the random oracle model. nations on this knowledge gap issue. Hence, we give a direct proof
for our lattice-based chameleon hash.
Proof. Simulation-sound extractability. Recall that the rela-
tion 𝑅 of the NIZK proof is to know 𝑥 such that 𝑦1 = 𝑔𝑥 ∨ 𝑦2 = 𝑔𝑥 . C.1 Proof of Theorem 3.8
Denote A as the adversary of breaking the simulation-sound ex- Proof. The proof is given by a sequence of games as defined
tractability. A is given the public parameters. For the SIM oracle in the proof of Theorem 3.1. In the game hopping to Game1 , the
with input (𝑦1, 𝑦2 ) and a message 𝑚, the simulator S picks random simulator S can pick random 𝑐 1 ∈ C, 𝜌® ← 𝔘𝑚 𝑚
1 , 𝑧®1 , 𝑧®2 ← 𝔘𝑚𝑑 2 −𝑑 .
𝑐 1, 𝑧 1, 𝑧 2 ∈ Z𝑞 and computes
It calculates 𝑦®′ = 𝐺® · 𝜌, ® 𝑇®1 = 𝐺® · 𝑧®1 −pkch ·𝑐 1 , 𝑐 2 = 𝐻 ′ (𝑇®1, pkch, 𝑦®′, 𝑚),
𝑇1 = 𝑔𝑧1 𝑦𝑐11 , 𝑐 2 = 𝐻 ′ (𝑇1, 𝑦1, 𝑦2, 𝑚), 𝑇2 = 𝑔𝑧2 𝑦𝑐22 . 𝑇®2 = 𝐺® · 𝑧®2 − 𝑦®′ · 𝑐 2 . It sets 𝑐 1 = 𝐻 ′ (𝑇®2, pkch, 𝑦®′, 𝑚) in the random
S sets 𝑐 1 = 𝐻 ′ (𝑇2, 𝑦1, 𝑦2, 𝑚). With probability 𝜖 ≤ 𝑞𝐻 /𝑞 (𝑞𝐻 is the oracle. With probability 𝜖 ≤ 𝑞𝐻 /|C| (𝑞𝐻 is the number of queries
number of queries to 𝐻 ′ ), the input (𝑇2, 𝑦1, 𝑦2, 𝑚) is already set in to 𝐻 ′ ), the input (𝑇®2, pkch, 𝑦®′, 𝑚) is already set in the random oracle
the random oracle 𝐻 ′ , and S declares failure and exits in this case. 𝐻 ′ , and S declares failure and exits in this case. The game hopping
Otherwise, S returns (𝑧 1, 𝑧 2, 𝑐 1 ). to Game2 is handled similarly.
When A returns (𝑦1∗, 𝑦2∗, 𝑚 ∗ ) and a proof (𝑧 1∗, 𝑧 2∗, 𝑐 1∗ ), S calculates In the game hopping to Game3 , note that we can write 𝐺® · 𝜌® =
∗ ∗ ∗ ∗
𝑇1 = 𝑔𝑧1 𝑦1∗𝑐 1 , 𝑐 2∗ = 𝐻 ′ (𝑇1∗, 𝑦1∗, 𝑦2∗, 𝑚 ∗ ) and 𝑇2∗ = 𝑔𝑧2 𝑦2∗𝑐 2 . Since it is a
∗ 𝜌®0 + 𝐺® ′ · 𝜌®1 for 𝜌®0 ∈ 𝔘1𝑘 and 𝜌®1 ∈ 𝔘𝑚−𝑘 1 . Therefore, by M-
valid proof, we have 𝑐 1∗ = 𝐻 ′ (𝑇2∗, 𝑦1∗, 𝑦2∗, 𝑚 ∗ ). S checks if 𝑐 1∗ or 𝑐 2∗ was ®
LWE𝑚−𝑘,𝑘,𝑞,𝔘1 assumption, 𝐺 · 𝜌® is computationally indistinguish-
queried later to the 𝐻 ′ oracle. WLOG, assume that 𝑐 1∗ was queried able from a random element in 𝑅𝑞𝑘 and so is ℎ® = 𝐺® · 𝜌® + 𝐻 (𝑚 ′ ). The
later and 𝑐 2∗ = 𝐻 ′ (𝑇1∗, 𝑦1∗, 𝑦2∗, 𝑚 ∗ ) was queried before. S rewinds game hopping to Game4 is handled similarly. □
to the point that 𝑐 1∗ was queried with input (𝑇2∗, 𝑦1∗, 𝑦2∗, 𝑚 ∗ ) and
returns a different 𝑐 1′ ≠ 𝑐 1∗ . If A still wins the game by outputting C.2 Proof of Theorem 3.9
(𝑧 1′ , 𝑧 2′ , 𝑐 1′ ) (it happens with a non-negligible probability according
∗ ∗ ′ ′ Proof. Suppose that A is an adversary breaking the h full collision-
to the forking lemma [3]), it means that 𝑇1∗ = 𝑔𝑧1 𝑦1∗𝑐 1 = 𝑔𝑧1 𝑦1∗𝑐 1 .
resistance. Suppose that the simulator S is given 𝐺®ˆ = 𝐼®𝑘 ∥ 𝐺® ′ ∥ 𝑔® ∈
i
∗ ∗ ′ ′
Then S obtains the witness 𝑤 = (𝑧 1 − 𝑧 1 )/(𝑐 1 − 𝑐 1 ) = log𝑔 𝑦1 . ∗ ∗
𝑘 × (𝑚+1)
Hence, it contradicts the winning condition of A. 𝑅𝑞 as the M-SIS matrix where 𝐺® ′ and 𝑔® are sampled uni-
Zero-knowledge. Similar to the simulation of the SIM oracle h i
formly at random. Denote 𝐺® = 𝐼®𝑘 ∥ 𝐺® ′ , which is used as the
above, no PPT adversary can break the zero-knowledge property
with non-negligible probability in the random oracle model. □ public parameter given to A. S sets

Similar to the generic construction, our ECC-based construction pkch = 𝐺® · 𝑥® + 𝑔® (2)

√
 
has full indistinguishability in the random oracle model since the ′ ∥ ≤ 𝑚𝑑 + 1 for 𝑥®′ = ®
𝑥
output of 𝐹 (𝑥) = 𝑔𝑥 is uniformly distributed in G. We can also for 𝑥® ← 𝔘𝑚 1 . Observe that ∥ ®
𝑥 .
1
prove that our ECC-based construction has full collision-resistance Also, note that we can write 𝐺® · 𝑥® = 𝑥®0 + 𝐺® ′ · 𝑥®1 for 𝑥®0 ∈ 𝔘1𝑘 and
in the random oracle model if the DL assumption holds in G, or
𝑥®1 ∈ 𝔘𝑚−𝑘 . Therefore, by M-LWE𝑚−𝑘,𝑘,𝑞,𝔘 assumption, 𝐺® · 𝑥® is
1 1
reduces to the case that the adversary outputs 𝑥 0, 𝑥 1, 𝑚 0, 𝑚 1 such
that computationally indistinguishable from a random element in 𝑅𝑞𝑘
𝐻 (𝑚 1 )/𝐻 (𝑚 0 ) = 𝑔𝑥 0 /𝑔𝑥 1 = 𝑔𝑥 0 −𝑥 1 . and so is pkch = 𝐺® · 𝑥® + 𝑔. ® S gives ppch = (𝑘, 𝑚, 𝑑, 𝑞, 𝐺, ® 𝐻, 𝐻 ′ ) and
It can be further reduced to the following Assumption DL-1. pkch to A. S also picks a random number 𝑗 ∈ [1, 𝑞𝐴 ], where 𝑞𝐴 is
the number of CHAdapt oracle query.
Definition B.2 (Assumption DL-1). Given a generator 𝑔 and a ® 𝑟 ), S firstly
For the CHAdapt oracle query with input (𝑚, 𝑚 ′, ℎ,
collision resistant hash function 𝐻 , no PPT adversary can output ®
𝑥, 𝑚 0, 𝑚 1 with non-negligible probability such that 𝑚 0 ≠ 𝑚 1 and checks if CHCheck(𝑚, ℎ, 𝑟 ) = 1. For the 𝑗-th query, if 𝑟 is not
the previous CHAdapt oracle with input (·, 𝑚, ℎ, ® ·), S additionally
𝑔𝑥 = 𝐻 (𝑚 1 )/𝐻 (𝑚 0 ). rewinds and extracts as follows:
Lemma B.3. The Assumption DL-1 can be reduced to the DL as- • Denote 𝑟 = (𝑧®1, 𝑧®2, 𝑐 1 ). S calculates 𝑦®2 = ℎ® − 𝐻 (𝑚), 𝑇®1 = 𝐺® · 𝑧®1 −
sumption in the random oracle model. pkch · 𝑐 1 , 𝑐 2 = 𝐻 ′ (𝑇®1, pkch, 𝑦®2, 𝑚), 𝑇®2 = 𝐺® · 𝑧®2 − 𝑦®2 · 𝑐 2 . Since 𝑟 is
Proof. Suppose that an algorithm B is given the DL problem a valid proof, we have 𝑐 1 = 𝐻 ′ (𝑇®2, pkch, 𝑦®2, 𝑚). S checks if 𝑐 1 or
(𝑔, 𝑦). If there is a PPT attacker A that breaks the Assumption DL-1, 𝑐 2 was queried later in the 𝐻 ′ oracle.
B first gives 𝑔 to A. When A ask for the hash query 𝐻 (𝑚𝑖 ), B picks • If 𝑐 1 was queried later, S rewinds A to the point that 𝑐 1 was
a random, distinct 𝜇𝑖 and returns 𝑦 𝜇𝑖 . Finally, A returns (𝑥, 𝑚 0, 𝑚 1 ) queried with input (𝑇®2, pkch, 𝑦®2, 𝑚). S returns a different 𝑐 1′ ≠
such that 𝑔𝑥 = 𝐻 (𝑚 1 )/𝐻 (𝑚 0 ). Then we have 𝑔𝑥 = 𝑦 𝜇1 −𝜇0 . Hence 𝑐 1 for the 𝐻 ′ oracle. If A still query the oracle by returning
B can return 𝑥/(𝜇 1 − 𝜇 0 ) as the DL solution of log𝑔 𝑦. □ another proof 𝑟 ′ = (𝑧®1′ , 𝑧®2′ , 𝑐 1′ ) (it happens with a non-negligible

1089
Reconstructing Chameleon Hash: Full Security and the Multi-Party Setting ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore

probability according to the forking lemma [3]), it means that Case (1b): if 𝑐 2∗ was queried later than 𝑐 1∗ , and 𝑐 ′ ∗2 was queried
later than 𝑐 ′ ∗1 , S rewinds A to the point that 𝑐 2∗ and 𝑐 ′ ∗2 was queried.
𝑇®1 = 𝐺® · 𝑧®1 − pkch · 𝑐 1 = 𝐺® · 𝑧®1′ − pkch · 𝑐 1′ .
Similar to the simulation of the CHAdapt oracle, S gets
Hence we get
𝑧®2∗ − 𝑧®˜2
 
𝑦®2∗ · (𝑐 2∗ − 𝑐˜2 ) = 𝐺® · (𝑧®2∗ − 𝑧®˜2 ) = 𝐺®ˆ ·
𝑧®1 − 𝑧®1′
  , (4)
pkch · (𝑐 1 − 𝑐 1′ ) = 𝐺® · (𝑧®1 − 𝑧®1′ ) = 𝐺®ˆ · . 0
0
!
By multiplying equation (2) by (𝑐 1 − 𝑐 1′ ), we have ®
®
𝑦®′ ∗2 · (𝑐 ′ ∗2 − 𝑐˜′ 2 ) = 𝐺® · (𝑧®′ ∗2 − 𝑧˜2′ ) = 𝐺®ˆ · 𝑧®′ ∗2 − 𝑧˜2′ . (5)
0
pkch · (𝑐 1 − 𝑐 1′ ) = 𝐺® · 𝑥® · (𝑐 1 − 𝑐 1′ ) + 𝑔® · (𝑐 1 − 𝑐 1′ )

𝑥®
 S calculates (𝑐 ′ ∗2 − 𝑐˜′ 2 )× Eq. (4) - (𝑐 2∗ − 𝑐˜2 )× Eq. (5):
= 𝐺®ˆ · (𝑐 1 − 𝑐 1′ ) · .  
1 𝜏®
𝐻 (𝑚 ∗ )(𝑐 ′ ∗2 − 𝑐˜′ 2 ) − 𝐻 (𝑚 ′ ∗ )(𝑐 2∗ − 𝑐˜2 ) = 𝐺®ˆ · ,
Therefore, we get 0
𝑧®1 − 𝑧®1′
   
𝑥® ®
𝐺·®
ˆ ® ′
= 𝐺 · (𝑐 1 − 𝑐 1 ) ·
ˆ . where 𝜏® = (𝑧®2∗ − 𝑧®˜2 )(𝑐 ′ ∗2 − 𝑐˜′ 2 ) − (𝑧®′ ∗2 − 𝑧˜2′ )(𝑐 2∗ − 𝑐˜2 ).
0 1 Recall that by the simulation of the 𝐻 oracle, we have 𝐻 (𝑚 ∗ ) =
𝑧®1 − 𝑧®1′ 𝐺® · 𝜇®∗ + 𝑔® and 𝐻 (𝑚 ′ ∗ ) = 𝐺® · 𝜇®′ ∗ + 𝑔® for some 𝜇®∗, 𝜇®′ ∗ ∈ 𝔘1𝑘 . Hence,
   
𝑥®
That is, 𝐺®ˆ · 𝑠® = 0 over 𝑅𝑞 for 𝑠® = (𝑐 1 − 𝑐 1′ ) · − . we have
1 0
′
Observe that 𝑠® cannot be the zero vector as 𝑐 1 ≠ 𝑐 1 and the last 𝐻 (𝑚 ∗ )(𝑐 ′ ∗2 − 𝑐˜′ 2 ) − 𝐻 (𝑚 ′ ∗ )(𝑐 2∗ − 𝑐˜2 )
coordinate of 𝑠® is (𝑐 1 − 𝑐 1′ ). Since ∥® 𝑧 1′ ∥ ∞ ≤ 𝑚𝑑 2 − 𝑑, we
𝑧 1 ∥ ∞ , ∥®
√ =𝐺® · [ 𝜇®∗ (𝑐 ′ ∗2 − 𝑐˜′ 2 ) − 𝜇®′ ∗ (𝑐 2∗ − 𝑐˜2 )] + 𝑔® · [(𝑐 ′ ∗2 − 𝑐˜′ 2 ) − (𝑐 2∗ − 𝑐˜2 )]
also have ∥® 𝑠 ∥ ≤ 2𝑑 𝑚𝑑 + 1 + 2𝑚𝑑 2 . Hence, √ 𝑠® is a solution to the
𝜇®∗ (𝑐 ′ ∗2 − 𝑐˜′ 2 ) − 𝜇®′ ∗ (𝑐 2∗ − 𝑐˜2 )
 
M-SIS𝑘,𝑚+1,𝑞,𝛽SIS for 𝛽 SIS = 4𝑑 · (2𝑚𝑑 2 + 𝑚𝑑). S quits the game =𝐺®ˆ ·
in this case. (𝑐 ′ ∗2 − 𝑐˜′ 2 ) − (𝑐 2∗ − 𝑐˜2 )
• If 𝑐 2 was queried later, S rewinds A to the point that 𝑐 2 was ∗
®ˆ 𝑠 = 0 over 𝑅 for 𝑠® = 𝜇®∗ (𝑐 ′ 2 − 𝑐˜′ 2 ) − 𝜇®′ ∗ (𝑐 2∗ − 𝑐˜2 ) − 𝜏® .
 
queried with input (𝑇®1, pkch, 𝑦®2, 𝑚). S returns a different 𝑐 2′ ≠ 𝑐 2 That is, 𝐺·® ∗
(𝑐 ′ 2 − 𝑐˜′ 2 ) − (𝑐 2∗ − 𝑐˜2 )
𝑞
for the 𝐻 ′ oracle. If A still queries the oracle by another proof
𝑟˜ = (𝑧®˜1, 𝑧®˜2, 𝑐˜2 ), it means that Observe that the last coordinate of 𝑠® is (𝑐 ′ ∗2 − 𝑐˜′ 2 ) − (𝑐 2∗ − 𝑐˜2 ), and
it is equal to zero only with probability 1/𝑞. Hence, 𝑠® cannot be the
𝑇®2 = 𝐺® · 𝑧®2 − 𝑦®2 · 𝑐 2 = 𝐺® · 𝑧®˜2 − 𝑦®2 · 𝑐˜2 . zero vector with overwhelming probability.
Since ∥𝑧®2∗ ∥ ∞ , ∥𝑧®˜2 ∥ ∞ , ∥𝑧®2∗ ∥ ∞ , ∥𝑧®˜2′ ∥ ∞ ≤ 𝑚𝑑 2 − 𝑑, we also have
′
Hence we get
√
𝑧®2 − 𝑧®˜2
 
𝑦®2 · (𝑐 2 − 𝑐˜2 ) = 𝐺® · (𝑧®2 − 𝑧®˜2 ) = 𝐺®ˆ · . (3) ∥®𝑠 ∥ ≤ 4𝑑 𝑚𝑑 + 1 + 8𝑑 · (𝑚𝑑 2 − 𝑑) + 4𝑑
0  √ 
≤ 4𝑑 · 2𝑚𝑑 2 + 𝑚𝑑 .
Afterward, S simulates the CHAdapt oracle using the random
oracle 𝐻 ′ as in the Game1 of the proof of Theorem 3.8. Therefore, 𝑠® gives a solution to M-SIS𝑘,𝑚+1,𝑞,𝛽SIS for 𝛽 sis ≈ 4𝑑 ·
For input 𝑚𝑖 , the 𝐻 oracle returns 𝐺® · 𝜇®𝑖 + 𝑔, ® where 𝜇®𝑖 ← 𝔘1𝑘 . Ob-
 √ 
2𝑚𝑑 2 + 𝑚𝑑 .
√
 
𝜇®𝑖
serve that 𝜇®𝑖 ′ ≤ 𝑚𝑑 + 1 for 𝜇®𝑖 ′ = . Also, note that we Next, we consider case 2. If (ℎ®∗, 𝑚 ′∗ ) ∈ Q, there are two sub-
1
cases:
can write 𝐺® · 𝜇®𝑖 = 𝜇®𝑖 0 + 𝐺® ′ · 𝜇®𝑖 1 for 𝜇®𝑖 0 ∈ 𝔘1𝑘 and 𝜇®𝑖 1 ∈ 𝔘𝑚−𝑘 . There-
1 Case (2a): The 𝑖-th CHAdapt oracle query has input (𝑚 ′∗, ·, ℎ®∗, 𝑟𝑖 )
fore, by M-LWE𝑚−𝑘,𝑘,𝑞,𝔘1 assumption, 𝐺® · 𝜇®𝑖 is computationally for some 𝑟𝑖 . If 𝑖 ≠ 𝑗, S declares failure and exits. If 𝑖 = 𝑗, then the
indistinguishable from a random element in 𝑅𝑞𝑘 and so is 𝐺® · 𝜇®𝑖 + 𝑔. ® extraction of (𝑟𝑖 , 𝑚 ′∗ ) has already been done during the CHAdapt
In the output phase, the adversary returns (𝑚 , 𝑟 , 𝑚 , 𝑟 , ℎ ) ∗ ∗ ′∗ ′∗ ®∗ oracle query. The solution to the M-SIS problem is calculated as in
with 𝑚 ∗ ≠ 𝑚 ′∗ and (ℎ®∗, 𝑚 ∗ ) ∉ Q. We consider two cases: (1) case (1a) and case (1b).
(ℎ®∗, 𝑚 ′∗ ) ∉ Q; (2)(ℎ®∗, 𝑚 ′∗ ) ∈ Q. Case (2b): There was a CHAdapt query with input (𝑚𝑖 , 𝑚 ′∗ ,
®∗
ℎ , 𝑟𝑖 ) for some 𝑚𝑖 , 𝑟𝑖 . If further looks for previous query with input
We first consider case 1. A outputs 𝑟 ∗ = (𝑧®∗, 𝑧®∗, 𝑐 ∗ ). S calculates
1 2 1
(𝑚𝑖 −1, 𝑚𝑖 , ℎ®∗, 𝑟𝑖 −1 ) and output 𝑟𝑖 . It runs recursively until it finds a
𝑦®2∗ = ℎ®∗ − 𝐻 (𝑚 ∗ ), 𝑇®1∗ = 𝐺® · 𝑧®1∗ − pkch · 𝑐 1∗ , 𝑐 2∗ = 𝐻 ′ (𝑇®1∗, pkch, 𝑦®2∗, 𝑚 ∗ ),
query (denoted as the 𝑖 ∗ -th query) with input (𝑚 0, 𝑚 1, ℎ®∗, 𝑟 0 ) and
𝑇®∗ = 𝐺® · 𝑧®∗ − 𝑦®∗ · 𝑐 ∗ . Since 𝑟 ∗ is a valid proof, we have 𝑐 ∗ =
2 2 2 2 1 output 𝑟 1 , such that there is no query with input (·, 𝑚 0, ℎ®∗, ·) and
𝐻 ′ (𝑇®2∗, pkch, 𝑦®2∗, 𝑚 ∗ ). S checks if 𝑐 1∗ or 𝑐 2∗ was queried later in the 𝐻 ′ output 𝑟 0 . If 𝑖 ∗ ≠ 𝑗, S declares failure and exits. If 𝑖 ∗ = 𝑗, then the
oracle. S also performs a similar checking for (𝑟 ′ ∗ = (𝑧®′ ∗, 𝑧®′ ∗, 𝑐 ′ ∗ ), 1 2 1 extraction of (𝑟 0, 𝑚 0 ) has already been done during the CHAdapt
𝑚 ′ ∗ ) and we do not repeat the writing here. oracle query. The solution to the M-SIS problem is calculated as in
Case (1a): if 𝑐 1∗ was queried later than 𝑐 2∗ , or 𝑐 ′ ∗1 was queried later case (1a) and case (1b).
than 𝑐 ′ ∗2 , S rewinds A to the point that 𝑐 1∗ or 𝑐 ′ ∗1 was queried. Similar Apart from the probability of rewinding successfully, the success
to the simulation of the CHAdapt oracle, S can find a solution to probability for case (2a) and (2b) are at least 1/𝑞𝐴 , and the success
the M-SIS𝑘,𝑚+1,𝑞,𝛽SIS problem. probability for case (1b) is at least 1 − 1/𝑞. Also, S has to rewind

1090
ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore Kwan Yin Chan, Liqun Chen, Yangguang Tian, and Tsz Hon Yuen

once for the 𝑗-th CHAdapt oracle query, and twice for case (1b) practical hardness. Following Algorithm 3.1 in [16], we have log 𝑞 =
or case (2b). Hence, S can solve the M-SIS problem in polynomial 28, 𝑑 = 128, 𝑘 = 9, 𝑚 = 20.
time with non-negligible probability. □ Observe that the size of the hash value ℎ® = 𝑑𝑘𝑞 bits, which is
about 4kB. The length of 𝑟 can be approximated by the following
C.3 Parameter Selection formula:
The practical security estimations of M-SIS and M-LWE against |𝑟 | = 2|®
𝑧 | + |𝑐 1 | ≈ 2 ∗ 7541 + 26 = 15108 bytes. (6)
known attacks can be found in [16, Section 3.2.4]. In particular,
The above formula stems from the fact that |𝑐 1 | = 𝑑 log 3/8 bytes
we look for a “Root Hermite Factor” of around 1.0045, which is
𝑧 | = 𝑚𝑑 log(2𝑚𝑑 2 )/8 bytes since 𝑧® ∈ 𝑅𝑚 with ∥®
and |® 𝑧 ∥ ∞ ≤ 𝑚𝑑 2 .
a common metric used in lattice-based cryptography to measure
Plugging in (𝑑, 𝑚) = (128, 20) yields (6).

1091