Joint encryption and message-efficient secure computation (Q2563544)

The article is about message complexity for \(n\) parties to evaluate a circuit privately, i.e. in such a way that no subset of participants can extract useful information about the other participant's input. To solve the problem ideas from group-oriented cryptography are used in a novel way. Particularly a new ``joint'' encryption scheme having some desirable properties not found in previously published schemes is proposed. Subsequently the scheme is used in a circuit evaluation protocol using only \(O(nC)\) encrypted bits of communication for size \(C\) circuit. Previously known circuit evaluation protocols used \(O(n^2 C)\) encrypted bits of communication, thus the new result represents significant improvement. In the final section of the paper this improvement is discussed in the light of a model used particularly with respect to ``writer'' vs. ``reader'' measure (for reading a single broadcasted encrypted bit by \(m\) parties the protocol is charged one vs. \(m\) encrypted bits).