search

plume-sig / zk-nullifier-sig

Implementation of PLUME: nullifier friendly signature scheme on ECDSA
MIT License
132 stars 22 forks source link

alternative security proof #11

Open weikengchen opened 1 year ago

weikengchen commented 1 year ago

Just to add, there is a quick way to prove the PLUME security, in case anyone asks.

This is the GDH undeniable signature with the confirmation protocol replaced with NIZK, and here the NIZK is a classical Chaum-Pedersen protocol.

The GDH undeniable signature can be found here: Tatsuaki Okamoto and David Pointcheval. The gap-problems: A new class of problems for the security of cryptographic schemes. In PKC ’01

This is also discussed in the BLS signature paper. Section 2.2.

Uniqueness comes from hashing to the curve.

weikengchen commented 1 year ago

added that this also nicely explains the separation between the prover and the signer, as this is the same as the original undeniable signature syntax.

weikengchen commented 1 year ago

I think the GDH signature does provide an easy framework to describe PLUME. Interesting that none of the experts in your acknowledgment recalled GDH.

Divide-By-0 commented 1 year ago

I think the GDH signature does provide an easy framework to describe PLUME. Interesting that none of the experts in your acknowledgment recalled GDH.

This is a great observation. We had been looking at it from the angle of a DDH-VRF and corresponding proofs, and the experts likely didn't have the time to recall GDH in the short conversations we had together or the framing that I imposed for the construction and proofs -- the fault for missing that is mine, not theirs (this was in fact my first cryptography paper so I'm not yet familiar with the full landscape).

The GDH undeniable signature can be found here: Tatsuaki Okamoto and David Pointcheval. The gap-problems: A new class of problems for the security of cryptographic schemes. In PKC ’01

I will look at that paper, that's a great find. If you'd be interested in working together to write up a security argument with me for poseidon's proposed v2 version with that argument, I would be happy to :)

EDIT: It seems GDH is similar but not quite what we are looking for.

weikengchen commented 1 year ago

If possible, we can have a call. I am looking into this question a lot recently, and we are working on something for hardware wallet and have something on the go very quickly into production.

We have some thoughts on how to implement it efficiently with zkSNARK.