Chameleon hash function
A chameleon hash function is a keyed, randomized hash function that is collision-resistant for every efficient adversary given only the hash key , while the holder of a trapdoor can, for any and any , find with — KR00.
Syntax
A chameleon hash function is a tuple of efficient algorithms with message space , randomness space , and range — KR00:
- , a randomized algorithm outputting a public hash key and a trapdoor ,
- , a deterministic algorithm which takes the hash key, a message and randomness , outputting ; hashing samples ,
- , an algorithm which takes the trapdoor, a message–randomness pair and a second message , outputting .
Properties
Correctness
A chameleon hash function is correct if for all , all output by , all and all , the output satisfies . The stronger requirement that be uniform in whenever is holds for both constructions under Other results, since there is a bijection of .
Collision resistance
The adversary, given only , must find two message–randomness pairs with distinct messages and the same hash value — KR00.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{cr}}_{\mathsf{CH},\calA}(\secpar)$}
\begin{algorithmic}
\State $(\mathit{hk}, \td) \gets \KeyGen(1^\secpar)$
\State $(m, r, m', r') \gets \calA(1^\secpar, \mathit{hk})$
\Return $[m, m' \in \calM \wedge r, r' \in \calR \wedge m \ne m' \wedge \mathsf{CH}(\mathit{hk}, m; r) = \mathsf{CH}(\mathit{hk}, m'; r')]$
\end{algorithmic}
\end{algorithm}
A chameleon hash function is collision-resistant if for all efficient ,
is negligible. The trapdoor holder wins with probability by computing , which is why receives only .
Uniformity
For uniform , the hash value is distributed independently of the message, even given the trapdoor.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{unif}}_{\mathsf{CH},\calA}(\secpar)$}
\begin{algorithmic}
\State $(\mathit{hk}, \td) \gets \KeyGen(1^\secpar)$; $b \getsr \bits$
\State $(m_0, m_1, \stA) \gets \calA(1^\secpar, \mathit{hk}, \td)$
\Comment{$m_0, m_1 \in \calM$}
\State $r \getsr \calR$
\State $b' \gets \calA(\mathsf{CH}(\mathit{hk}, m_b; r), \stA)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
Let
A chameleon hash function is uniform if for every , efficient or not, that is, if for every hash key output by the distribution of over is the same for all .
Variations
Key exposure
In the discrete-logarithm construction over a group of prime order (DLOG ⇒ Chameleon hash (Krawczyk–Rabin)), any collision with reveals the trapdoor , so a trapdoor holder who publishes one collision lets anyone compute further collisions; AdM04 study this key exposure problem and chameleon hashes in which published collisions do not expose the trapdoor.
Chameleon encryption
Chameleon encryption extends a chameleon hash with an encryption algorithm keyed by a hash value , a position and a bit , whose ciphertexts can be decrypted with any such that and — DG17a. DG17a build it from CDH and use it to construct IBE (CDH ⇒ IBE (Döttling–Garg)).
Other results
- If DLOG is hard in prime-order groups, with trapdoor is a uniform chameleon hash function (DLOG ⇒ Chameleon hash (Krawczyk–Rabin)) — KR00.
- A claw-free pair of trapdoor permutations gives a uniform chameleon hash function on a prefix-free message space (Claw-free TDP ⇒ Chameleon hash (Krawczyk–Rabin)) — KR00.
- A uniform chameleon hash function is a non-interactive trapdoor commitment: the commitment to is and the opening is ; uniformity makes it perfectly hiding, collision resistance makes it computationally binding, and equivocates — standard.
- Chameleon signatures: the signer signs with an ordinary signature scheme, under the hash key of the recipient ; can turn a signature on into one on any by computing , so the signature does not convince a third party, while the signer can deny a forged signature by exhibiting a collision — KR00.
- Online/offline signatures (hash-sign-switch): offline, the signer signs for random with any EUF-CMA-secure signature scheme; online, it computes and outputs with the precomputed signature. The scheme is EUF-CMA-secure if the signature scheme is EUF-CMA-secure, the chameleon hash is collision-resistant, and for all the map sends uniform to an that is uniform (the stronger requirement under Correctness) or computationally indistinguishable from uniform — ST01.
- HW09 turn a weakly secure RSA-based signature scheme into an EUF-CMA-secure one with a chameleon hash (RSA ⇒ DS (Hohenberger–Waters, short and stateless)).
- Chameleon hash functions are distinct from trapdoor hash functions, whose trapdoor recovers a bit of the input from a short hint — DGI+19.
Participates in
Produces Chameleon hash function