Mesmerizing Chameleon Signatures

Photo by Pierre Bamin on Unsplash

Preface

Signature schemes are essential to our daily lives. Before computers have existed, we have been signing off papers and documents with our names for a long time. A proper signature simply represents identity and authenticity. Digital Signature is essentially the same idea but in the world of computers. A signature proves the validity of what we say.

  • Binding: A commitment can only bind to one value. It’s impossible to produce another value that also aliases to the same commitment.
  • Hiding: A commitment should hide its committed value. By just looking at the commitment itself, the observer should have no way to regain knowledge of the committed value.

Chameleon Signatures

Chameleon Signatures are a very special (and beautiful) type of digital signatures. Like its name, these signatures do act like chameleons.

Online Auction

Imagine that Alice participated in an online auction and bid 100 dollars for a painting that she really likes. In order to make sure that she is “committed” to pay 100 dollars when she wins the auction, usually, we would ask Alice to sign a digital signature on her bidding.

sig = Sign(sk, m_bid)
is_valid = Verify(pk, m_bid, sig)

Problems

However, this is just a toy protocol that demonstrates how digital signature works. In the real world, things get dirty real quick.

Signatures destroy secrecy

So what’s wrong with these signatures? The answer is — not only the platform can verify these signatures, but it can also send the signature to anyone else and they can verify the validity of Alice’s bidding.

Photo by Scott Graham on Unsplash

Chameleon Signatures to the rescue

In 1997, Krawczyk and Rabin came up with the Chameleon Signature scheme. It allows the signer to only disclose the validity to the intended recipient. If the recipient tries to send this signature to some other party, the signature itself immediately loses its validity.

The Structure

The overall structure of the Chameleon Signature scheme is like the following:

  1. Both parties go through a Setup phase and it spits out some parameters for the signer and the recipient.
  2. Then the signer uses the public parameters to create a commitment to her message. Since she only has the public parameters to this commitment, it will be impossible for her to break the binding property of this commitment (i.e. aliasing this commitment to a different message).
  3. The signer then signs the commitment using a normal signature scheme. She passes it along with the original message and the verifying key to the recipient.
  4. The recipient verifies the validity of the signature by recomputing the commitment using the message plaintext and using the verify function of the normal signature scheme to check if the signature on the commitment is valid.

Chameleon Hash Function

The secret sauce behind Chameleon Signatures is creating a commitment scheme that satisfies the property that I mentioned before — Alice cannot produce forgeries while the platform can trivially produce arbitrary openings to a given commitment. What the authors came up with was called the Chameleon Hash Function.

Alice() -> (m_0, r_0), (m_1, r_1)
Prob[ChamHash(m_0, r_0) = ChamHash(m_1, r_1)] ~= 0
Photo by Nick Hillier on Unsplash

Claw-free Trapdoor Permutations

Don’t be scare of its name. I’ll explain it shortly.

sizeof(x) == sizeof(y)
1 - 3
2 - 4
3 - 3
4 - 1
1 - 3
2 - 3
3 - 1
4 - 4

Building the Chameleon Hash Function

Once we have the Claw-free pair of Trapdoor Permutations (TDP), we are ready to build our Chameleon Hash Function.

  1. First, we will write m in terms of a sequence of k bits m[1]...m[k].
  2. Then, we sample a random nonce r from the permutation space.
  3. Starting from the first bit of m, if m[1] = 0, then we apply F_0 to r. If m[1] = 1, then we apply F_1 to r. We keep doing this for all the k bits of m and obtain the final Chameleon Hash.
ChamHash(m, r) = F_m[k](...(F_m[2](F_m[1](r)))...)
m_0 = 0 1 1 0 0 ... 0 1 0 1
m_1 = 1 0 1 0 1 ... 1 1 0 1

1 ... i k
F_m0[i](F_m0[i-1](...(r_0)...)) = F_m1[i](F_m1[i-1](...(r_1)...))
F_m0[i](r_0') = F_m1[i](r_1')
r = F_m[k]^-1(F_m[k-1]^-1(...(ChamHash(m, r))...))
r' = F_m'[k]^-1(F_m[k-1]^-1(...(ChamHash(m,r))...))
Photo by Daniel McCullough on Unsplash

The Construction — Factoring based

In order to build a Chamaleon Hash Function, we know that we just need to build a Claw-free pair of Trapdoor Permutations. The paper briefly introduced two candidates that have this property. The first one is factoring based.

F_0(x) = x^2 mod N
F_1(x) = 4x^2 mod N

The Construction — Discrete-log based

If you are familiar with other Crypto algorithms, you should be expecting this section to come.

Group = {0, g, g^2, g^3, ..., g^q}
{0, 3, 3^2 mod 5, 3^3 mod 5, 3^4 mod 5} = {0, 3, 4, 2, 1}
ChamHash(m,r) = g^m * y^r
g^m * h^r = g^m' * h^r'
g^m * (g^x)^r = g^m' * (g^x)^r'
m + xr = m' + xr'

Putting it all together

Since we already discussed how the signature scheme works at a higher level, I’ll briefly recap the signature scheme here. Assume we use the discrete-log based construction.

  1. During the setup phase, Alice and the platform agree on some certain group G and its generator g. Then the platform will randomly sample an element x and pass along y = g^x to Alice. Alice will also generate a signing key and a verifying key for a normal signature scheme (like ECDSA).
  2. Alice will then make her bid (let’s say her bid is 100) and sample some random nonce r. She will produce a Chameleon Hash hash = g^100 * y^r. Then she can sign the hash with a regular signature scheme to obtain the signature sig = Sign(sign_key, hash). Finally, Alice sends the signature along with the hash and the bidding to the platform.
  3. The platform verifies the validity of the hash by running Verify(verify_key, hash, sig).

Further Enhancements

In the original paper, the authors didn’t just stop right here. They also elaborated on how to enhance this protocol even further. I’m going to talk about two interesting ones.

Photo by Matthew Henry on Unsplash

Afterthought

Woah, I didn’t realize that I have written this long in this post. But this was a pretty interesting idea to think and write about.

Potential Use Cases

Privacy-Preserving Auction: This was Alice’s example I gave in the post. We can also extend this to a lot of other scenarios such as in submitting trades in a stock market and participating in a business contract. And of course, this could be written into a smart contract!

What comes after

Chameleon Signature wasn’t the first signature scheme that has this interesting designated-verifier property. In fact, there was this Undeniable Signature in the 90s that has a similar idea but uses a heavier Zero-knowledge construction.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Steven Yue

Steven Yue

Software Engineer & Part-time student. I code and do photography. Instagram: stevenyue. https://higashi.tech