search

tuneinsight / lattigo

A library for lattice-based multiparty homomorphic encryption in Go
Apache License 2.0
1.2k stars 178 forks source link

Documentation for Refresh protocol #30

Closed jon-chuang closed 4 years ago

jon-chuang commented 4 years ago

I don't understand what is being done in: https://github.com/ldsec/lattigo/blob/bb095f1d82cd5c532171b138cd0ad83ecd785103/dckks/public_refresh.go

There is no documentation on this, including here: https://eprint.iacr.org/2019/961.pdf.

Also, I don't understand how it is possible to perform CKKS refreshing in a multiparty manner. Does it do so in a way that none of the parties learn any of the intermediate outputs?

Reading the implementation, it seems that additive secret sharing is used. One decrypts their own portion of the CKKS/BFV secret ct[1].s_i, wrt to modulus 0, and adds their share of a shared secret mod q_0 to it. Then, as long as q_0 is larger than q_i for all i larger than 0, one can reduce this number mod q_i for each i, and for each i, each party removes their portion of the shared secret, and encrypts with their portion of the CKKS secret wrt to the modulus q_i. I believe this is correct.

I don't think this library has solved the problem of premature decryption, before the required computation on the server has been performed, which is a problem faced by any MPC approach, besides client-server, since in the client-server case the client is the sole stakeholder of the component secrets, hence if I am not wrong, it is thinking of implementing ZK proofs, although I don't know how this can be done.

ChristianMct commented 4 years ago

The reference for the refresh protocol is part of an ongoing submission which we should soon be able to reference here (at least as an eprint).

I'm not sure what you are referring to as the "premature decryption problem".

jon-chuang commented 4 years ago

Would you at least be able to comment if my description is essentially correct?

With regards to premature decryption, for instance, a malicious server colluding with one of the parties may fool the rest of the parties that it has performed a computation, when in fact it has just added a 0 ciphertext. Then, when the parties collectively decrypt the ciphertext, the encrypted data or model parameters for instance would be revealed.

Pro7ech commented 4 years ago

I am not sure I can follow your explanation on the refresh protocol. And like Christian said, it is part of an ongoing submission so its full description will be available in the near future. I can however give you a high level description. This protocol enables the parties to decrypt a ciphertext to a secret shared plaintext, and re-encrypt it with a lower noise (BFV) or at higher modulus (CKKS).

The adversarial model that the library supports is currently limited to honest but curious. It is not aimed a providing a solution against parties who could arbitrary deviate from the protocol.

jon-chuang commented 4 years ago

@Pro7ech while honest but curious makes sense for the client-server two party case, since decryption results in either garbage or results that the client themselves could compute on their data, the multi party case in my opinion requires stronger assumptions than honest but curious. For instance, in the malicious setting, the server could get hijacked by one of the parties. Hence my suggestion is to add a zero knowledge layer.

ChristianMct commented 4 years ago

As for issue #32, we would be happy to discuss the proposal of a ZK layer with all the Lattigo team on the mailing list: lattigo@listes.epfl.ch.

ChristianMct commented 4 years ago

Closing: discussion taken offline.