[Cryptography] pseudo-homomorphic encryption ??

[Benjamin Kreuter]

On Mon, 2019-01-14 at 10:01 -0800, Henry Baker wrote:
> 
> The following link was suggested to me, but
> I don't know enough about AI/ML to fully
> appreciate it:
> 
> "Federated Learning: Collaborative Machine Learning without
> Centralized Training Data"
> 
> https://ai.googleblog.com/2017/04/federated-learning-collaborative.html

Coauthor of the relevant cryptography paper here (link below).  The
project does not use homomorphic encryption; it is an interactive
protocol based on secret sharing (MPC).  The basic idea is that if
Alice has X, Bob has Y, and Catherine has Z, then we can do this:

Alice and Bob agree on a random A.

Bob and Catherine agree on a random B.

Catherine and Alice agree on a random C.

Alice sends X+A+C to the server.

Bob sends Y-A+B

Catherine sends Z-B-C

The server can now compute the sum:  (X+A+C)+(Y-A+B)+(Z-B-C)=X+Y+Z

If we can compute sums we can compute linear combinations, which is
what we need for Federated ML (basically, the training is divided into
a non-linear step that can be done on a single device, and a linear
step that requires inputs from many devices).  Most of the work that
went into the design involved optimizing for communication and dealing
with a large fraction of devices failing to complete the protocol.  Our
paper has the details (this was also published at CCS):

https://eprint.iacr.org/2017/281

HE could be used here (additive homomorphic schemes are already being
used in practice in other settings), but it would still require an
interactive protocol because a threshold scheme would needed.  Our
protocol is more communication efficient than a threshold HE approach
would be according to our analysis.

We were working in a "single server" setting i.e. all the servers are
under a single party's control.  If there are servers controlled by
multiple parties you can get an even more efficient system; for
example, Prio, which is being deployed by Mozilla for gathering usage
statistics about Firefox:

https://crypto.stanford.edu/prio/

-- Ben

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: This is a digitally signed message part
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20190116/86b23bd1/attachment.sig>