I'm working on an ECC-based system.

There's a Schnorr's signature, by which the prover may prove a knowledge of a preimage (i.e. scalar, private key) of an EC point (i.e. public key).

It can be generalized to multiple NUMS (nothing-up-my-sleeve) generators, this is (AFAIK) generalized Schnorr's signature.

Now, in my particular case the prover needs to prove the knowledge of multiple sets of private keys, which are openings of several Pedersen commitments known to the verifier, in terms of the same generators.

Note: I'm not talking about Schnorr's multisignature, where all the public keys are aggregated. In my specific case it's important to prove each key individually.

A straightforward solution would be creating several Schnorr's signatures, but I think I've figured-out a better way. I'd like to ask the community if it's safe.

So, I think this can be proven by a modified Schnorr's multi-signature, with the following modification: instead of sampling a single challenge, the verifier should sample a separate challenge for each commitment, and then modify the verification appropriately: summarize all the commitments, each multiplied by the appropriate challenge, add the nonce image, and check if the revealed preimages commit to the same value.

I think it's a straight-forward generalization, its soundness can be proven by the same technique with extractor by sampling several challenges with 4the same nonce. The extractor first varies the last challenge, this will extract the opening for the last commitment, then it varies the previous challenge, and etc.

So, it looks like a good scheme: many signatures are compressed into one, without loosing the soundness. Does this look safe?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.