Missing proof of correctness of N_tilde

[omershlo]

https://github.com/ing-bank/threshold-signatures/blob/master/src/algorithms/zkp.rs#L303 At the setup of the range proofs the verifier must generated N_tilde, h1,h2 and prove their correctness in zk (as stated in GG18). In the code there is a proof for h1,h2 but not for N_tilde. The zk proof for correctness of Paillier key already exist in the code and being used elsewhere, so the fix should be easy. I did not look for specific attacks that uses this lack of proof. However, in the paper https://eprint.iacr.org/2020/1052 an attack is described in the case where h1,h2 are also not proven and my intuition tells me that similar attack might exist here as well (albeit harder)

[RustMania]

Thanks for the feedback, Omer, To our best knowledge, NIZKP for Paillier [used in the code] proves that N is relatively prime to Fi(N), as explained well in GRSB19. The setup in FO97 is different, it is based on safe primes, and it requires proofs of alpha and alpha^-1 only in original work. From this standpoint it makes more sense to look into the "proof of N being the product of two safe primes" proposed by Camenish et al in CM99. Do you agree?

[omershlo]

Few points: 1) in FO97 N (which is N_tilde in our protocol) is a system parameter, given by a trusted third party (or by a trusted verifier), in GG18 we do not have a trusted authority and therefore this parameter must be delivered with a proof 2) about safe primes: GG18 requires Paillier N to be a multiplication of two safe primes as well. For both cases I claim : a) for all practical concerns, using large enough primes is enough (see https://crypto.stackexchange.com/questions/47729/safe-primes-in-rsa for example) b) proving N and phi(N) are co-primes its enough for correctness

[gtillem]

Hi Omer, We agree with you about the validation of N_tilde. But we are not clear about what do you mean by the correctness of N_tilde. How does 'proving N and phi(N) are co-primes' contribute to this given that N_tilde is the product of two safe primes?

[omershlo]

Hi @gtillem ! maybe I am missing something here. focusing on the validation of N_tilde : it is required to certify N_tilde is a valid RSA key. Why not use the same trick suggested in https://eprint.iacr.org/2018/987.pdf 6.2.3 ? my previous answer was more focused on choosing safe primes vs choosing regular primes - while the former is obviously better, it is often the case that the latter is being used, and in both cases the RSA key certification proof should be enough, no ?