  Learning from data owned by several parties, as in federated learning, raises
challenges regarding the privacy guarantees provided to participants and the
correctness of the computation in the presence of malicious parties. We tackle
these challenges in the context of distributed averaging, an essential building
block of federated learning algorithms. Our first contribution is a scalable
protocol in which participants exchange correlated Gaussian noise along the
edges of a network graph, complemented by independent noise added by each
party. We analyze the differential privacy guarantees of our protocol and the
impact of the graph topology under colluding malicious parties, showing that we
can nearly match the utility of the trusted curator model even when each honest
party communicates with only a logarithmic number of other parties chosen at
random. This is in contrast with protocols in the local model of privacy (with
lower utility) or based on secure aggregation (where all pairs of users need to
exchange messages). Our second contribution enables users to prove the
correctness of their computations without compromising the efficiency and
privacy guarantees of the protocol. Our verification protocol relies on
standard cryptographic primitives like commitment schemes and zero knowledge
proofs.
