# Mesmerizing Chameleon Signatures

## 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)`

## 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`

## Claw-free Trapdoor Permutations

`sizeof(x) == sizeof(y)`
`1 - 32 - 43 - 34 - 1`
`1 - 32 - 33 - 14 - 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 1m_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))...))`

## The Construction — Factoring based

`F_0(x) = x^2 mod NF_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)`.

# Afterthought

## More from Steven Yue

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.

## Steven Yue

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