Update ZKPs to use Z*Ns

[marsella]

The scope of work in #40 was originally too large. That issue focuses on designing an interface for using elements of the multiplicative group of integers mod N.

Now that we have a nice Z*N module, we'll integrate it into the Paillier module, the Ring-Pedersen module (if it's merged), and the ZKPs

• [ ] ~Replace all calls to random_bn_in_zkstar with calls to the API~
• [ ] Update types in the ring-Pedersen and Paillier modules ~as well as any "unwrapped" types in the Proof, Input, and Private structs (e.g. those not already defined in terms of rP or Paillier types)~
• [ ] Instantiate and name builders appropriately in each place where we use Z*_Ns
• [ ] If appropriate, replace the builder new() method with from_x methods that derive builders from specific types (e.g. from_decryption_key(key: PaillerDecryptionKey))

[Ra1issa]

@marsella I was looking at where I should replace random_bn_in_zkstar and realized that it was only being used to generate a Paillier nonce which itself relies on the Paillier Encryption key to determine the range to sample from. Is part of the idea here to change the Paillier Encryption key in libpaillier (libpaillier-0.5.0/src/encryptionkey.rs/EncryptionKey) like this?

pub struct EncryptionKey {
    pub(crate) n: ZKStarBuilder, // N = p * q, where p,q are primes
    pub(crate) nn: ZKStarBuilder,    // N^2
}

Where ZKStarBuilder is the wrapper around the multiplicative group's modulus in the new ZKStar API (see PR #129 ). That said, it sounds to me like we are gradually phasing out libpaillier. If that is the case, how do you want me to proceed ? Should I postpone this ?

[marsella]

Ooh. This might be a good time to ditch use of the libpaillier::EncryptionKey completely and replace our own encryption key with your suggestion! We're only using the libpaillier version to access the those two values, so it's not worth keeping it around for longer if it's getting in your way. I think nn doesn't need to be a builder, though, so we could have

pub struct EncryptionKey {
    n: ZkStarBuilder,
    nn: BigNumber
}

Do all operations between Z*_N elements happen in the Paillier module? If so we can update the getter for n to pull out the modulus from the builder, and never reveal the builder outside this module. And I'm pretty sure nn is never accessed outside the Paillier module either.

This does bring up #105 again, since we'd ideally verify on deserialization that n and nn match. I might still put that off since I don't think this change would put us in a worse position than we were in before (I don't think libpaillier did any verification on deserialization).

[Ra1issa]

I think nn doesn't need to be a builder

• Sanity check me here, but I was thinking thatnn can be a builder. if Z_n is a multiplicative group I'd think that Z_n^2 would be to.

I might still put that off since I don't think this change would put us in a worse position than we were in before (I don't think libpaillier did any verification on deserialization).

• Okay, I'll take a look at replacing the other pieces first and then switch to issue #133

[marsella]

I think nn doesn't need to be a builder

• Sanity check me here, but I was thinking thatnn can be a builder. if Z_n is a multiplicative group I'd think that Z_n^2 would be to.

It definitely can be a builder, but I don't think we ever generate elements in that group so it shouldn't need to be one. I'd rather keep the type as simple as possible and only give functionality that is necessary for this use case.

I might still put that off since I don't think this change would put us in a worse position than we were in before (I don't think libpaillier did any verification on deserialization).

• Okay, I'll take a look at replacing the other pieces first and then switch to issue Add operations on Z*_N to the module #133

Sure. To be clear, I think it's fine to remove the libpaillier::EncryptionKey now and update all the types that should be ZStarN. But to complete this issue, you do not have to fix the deserialization of the EncryptionKey type. We'll do that in a separate PR.

[Ra1issa]

Regarding libpaillier: I have been trying to replace libpaillier's EncryptionKey & DecryptionKey but there are several questions that need addressing. Let me list out my findings/concerns:

• Small question: What should each of these structs derive and how should the ZKStarN API be updated? Currently, EncryptionKey & DecryptionKey in libpaillierboth derive Clone, Debug, Serialize, Deserialize. I don't see a reason why ZStarNBuilder (i.e. the modulus) shouldn't be update to derive all of them.
• Observation: Phasing out libpaillier's EncryptionKey to the API I had suggested is straightforward because paillier.rs doesn't really use libpaillier.
• Concern: Phasing out libpaillier's DecryptionKey is more complicated because now we would additionally need to write (or export) the decryption algorithm thats called in libpaillier along with several smaller methods/macros like modpow, modin, l (which computes the residuosity class of N^2). We can export these as they are from libpaillier into utils.rs and paillier.rs for now. But is this the right way to go ?

[Ra1issa]

InProof: Is the idea here to change Proof's API ? Because I am not sure I understand why you would do that. I'd have expected that we'd be changing parameters in individual proofs like for instance C,D,Y in PiAffgProof.

In Private: This comment is in vain of the previous one. Why would we want to change the type of rho and nu in this case from Nonce to ZStarN ? Do you think its more descriptive and less error prone?

[marsella]

• Small question: What should each of these structs derive and how should the ZKStarN API be updated? Currently, EncryptionKey & DecryptionKey in libpaillierboth derive Clone, Debug, Serialize, Deserialize. I don't see a reason why ZStarNBuilder (i.e. the modulus) shouldn't be update to derive all of them.

All of these are fine to derive! Feel free to derive anything that you need to get stuff to compile; I'll flag anything weird in the PR, but I don't expect you'll do anything unreasonable.

• Observation: Phasing out libpaillier's EncryptionKey to the API I had suggested is straightforward because paillier.rs doesn't really use libpaillier.

:+1:

• Concern: Phasing out libpaillier's DecryptionKey is more complicated because now we would additionally need to write (or export) the decryption algorithm thats called in libpaillier along with several smaller methods/macros like modpow, modin, l (which computes the residuosity class of N^2). We can export these as they are from libpaillier into utils.rs and paillier.rs for now. But is this the right way to go ?

Removing libpaillier::DecryptionKey seems out of scope for this PR. I'll link to this comment in #84 and we can decide later whether to take it out or not.

InProof: Is the idea here to change Proof's API ? Because I am not sure I understand why you would do that. I'd have expected that we'd be changing parameters in individual proofs like for instance C,D,Y in PiAffgProof.

You're correct! I meant to change the fields if they should be ZKStarN, but leave the overall structure the same. See e.g. the type changes in the piaffg module from adding Ring-Pedersen parameters.

In Private: This comment is in vain of the previous one. Why would we want to change the type of rho and nu in this case from Nonce to ZStarN ? Do you think its more descriptive and less error prone?

No, I'd like to keep those as Nonce and maybe just change the internal type of Nonce to ZStarN. I'd rather treat ZStarN as a lower-level API than Paillier or Ring-Pedersen.

Actually, these last two questions raise a good point: I'm not sure that there will be any "free-floating" ZStarN types in the proofs. They might be fully contained in the Paillier module (as Nonces) and the RingPedersen module (the parameters s and t and the commitment type). You can definitely handle the Paillier changes now but since @amaloz is actively working on abstracting RingPedersen (#144), I don't want you to, say, change all the ZKSetupParameters and things that are actually commitments only for them to get removed as soon as that PR is merged.

[marsella]

See note in https://github.com/boltlabs-inc/tss-ecdsa/pull/144#issuecomment-1416253097 about updating types in that module.

[Ra1issa]

To add to the prior discussion, replacing the field of Nonce with ZKStarN instead of BigNumber will also lead to discussion of whether or not Nonce should derive Deserialize, something we explicitly do not want ZKStarN to do for correctness.

The second question to consider is whether or not MaskedNonce should also be a ZKStarN or not.

[marsella]

We decided to deprioritize this ticket. When we come back to it, the goals will be to simplify the API of the ZStar type, since it's only used in the paillier and ring-pedersen modules now. We'll aim for confidence in generation, but depending on the use case, we might decide not to use the builder struct.

[marsella]

ING Bank has an audited implementation of the Goldfeder-Gennaro scheme (the precursor to our implementation). In their audit report, they noted that they didn't recommend validation of Z*_N elements because in that setting, it wasn't a security issue (see report S4.1).

When completing this ticket, we should also consider whether these checks are security critical or not in our implementation. An initial talk-through with @indomitableSwan suggested that the selection of ring-Pedersen parameters do require the check, but the selection of nonces for Paillier encryption (by the party who does not hold the decryption key) does not need it.

Aside: The report says GCD checks are expensive, but we don't think they are. Maybe benchmark this to see if it's worth optimizing away at all?

[indomitableSwan]

ING Bank has an audited implementation of the Goldfeder-Gennaro scheme (the precursor to our implementation). In their audit report, they noted that they didn't recommend validation of Z*_N elements because in that setting, it wasn't a security issue (see report S4.1).

When completing this ticket, we should also consider whether these checks are security critical or not in our implementation. An initial talk-through with @indomitableSwan suggested that the selection of ring-Pedersen parameters do require the check, but the selection of nonces for Paillier encryption (by the party who does not hold the decryption key) does not need it.

Aside: The report says GCD checks are expensive, but we don't think they are. Maybe benchmark this to see if it's worth optimizing away at all?

Looking at the audit report, they are addressing particular NIZKs that prove the Paillier parameters are correct. Someone needs to look more carefully at the actual proofs we are using for Paillier parameters, but it's plausible that we don't need the extra checks there if we're currently doing them. (Some of the proof specifications don't appear to include these checks, e.g., Pi_mod.)

In any case, I find myself repeatedly confused by the scope of this ticket. I can't tell easily from the description which NIZKs we're talking about here. I recommend closing this ticket and opening separate design tickets for each NIZK of concern to examine this issue and determine whether group membership checks are required or not. An outcome of that ticket can then be implementation tasks that reflect our understanding of the theory and our desire to use Z*N types where appropriate.

[marsella]

I recommend closing this ticket and opening separate design tickets for each NIZK of concern to examine this issue and determine whether group membership checks are required or not. An outcome of that ticket can then be implementation tasks that reflect our understanding of the theory and our desire to use Z*N types where appropriate.

We've developed some abstractions that make it harder to take this approach. Specifically, we made ring-Pedersen and Paillier modules that handle generation of commitment randomness and nonces (respectively). Those two types are the only types in the whole repo that use elements in Z*N. They're created in multiple NIZKs (piaffg, pienc, pifac, and pilog). However, actual generation of the Z*N elements happens behind the ring-Pedersen and Paillier abstraction layers.

If we want to make decisions for each NIZK about whether or not to do group membership checks, we'll have to change the ring-Pedersen and Paillier layers to explicitly allow the caller to make that decision. If we're changing the abstraction, I want to look at all the usages at once to figure out what an appropriate new abstraction is.

[indomitableSwan]

I recommend closing this ticket and opening separate design tickets for each NIZK of concern to examine this issue and determine whether group membership checks are required or not. An outcome of that ticket can then be implementation tasks that reflect our understanding of the theory and our desire to use Z*N types where appropriate.

We've developed some abstractions that make it harder to take this approach. Specifically, we made ring-Pedersen and Paillier modules that handle generation of commitment randomness and nonces (respectively). Those two types are the only types in the whole repo that use elements in ZN. They're created in multiple NIZKs (piaffg, pienc, pifac, and pilog). However, actual generation of the ZN elements happens behind the ring-Pedersen and Paillier abstraction layers.

If we want to make decisions for each NIZK about whether or not to do group membership checks, we'll have to change the ring-Pedersen and Paillier layers to explicitly allow the caller to make that decision. If we're changing the abstraction, I want to look at all the usages at once to figure out what an appropriate new abstraction is.

I believe we have a slight misunderstanding here. I imagine we can make these decisions within the ring-Pedersen and Paillier module abstractions, i.e., I do not believe there is any problem. The NIZK-specific reasoning above is about the general shape of the proofs and the purpose of Z*Ns in those proofs, i.e., it should boil down to "are you proving something about Paillier encryption being well-formed or are you proving something using ring-pedersen commitments"? In any case, my main point is that a general ticket that lumps all NIZKs together, without any specifics, makes it very difficult to make reasonable progress on this issue. It's just not amenable to giving concrete answers efficiently.