Mesmerizing Chameleon Signatures

Photo by Pierre Bamin on Unsplash

Preface

  • 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

Online Auction

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

Problems

Signatures destroy secrecy

Photo by Scott Graham on Unsplash

Chameleon Signatures to the rescue

The Structure

  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

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

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

  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

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

The Construction — Discrete-log based

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

  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

Photo by Matthew Henry on Unsplash

Afterthought

Potential Use Cases

What comes after

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

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Help! My AWS Server Has Been Hacked!

HealthCerts — Coda

A New Threat Modeling Trend is Brewing

Threat Modeling Trend

Announcement: HALO Network (HALO Chain) Block Explorer Upgrade

Sappchat Web Staking Platform (Hodl APP) Now Available!

Privacy Policy

Fountain Protocol: A Week in Review

OATH Initiative — the Main Goals, Tasks, Ins & Outs

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

More from Medium

nodemon : File nodemon.ps1 cannot be loaded. The file nodemon.ps1 is not digitally signed.

go-ethereum ethclient provides wrong blockhash on xDai

Upgrading to Yocto Honister release

Ruby on Rails — Migration