Robust multiparty computation with linear communication complexity
M Hirt, JB Nielsen - Annual International Cryptology Conference, 2006 - Springer
M Hirt, JB Nielsen
Annual International Cryptology Conference, 2006•SpringerWe present a robust multiparty computation protocol. The protocol is for the cryptographic
model with open channels and a poly-time adversary, and allows n parties to actively
securely evaluate any poly-sized circuit with resilience t< n/2. The total communication
complexity in bits over the point-to-point channels is O(Snκ+nBC), where S is the size of the
circuit being securely evaluated, κ is the security parameter and BC is the communication
complexity of one broadcast of a κ-bit value. This means the average number of bits sent …
model with open channels and a poly-time adversary, and allows n parties to actively
securely evaluate any poly-sized circuit with resilience t< n/2. The total communication
complexity in bits over the point-to-point channels is O(Snκ+nBC), where S is the size of the
circuit being securely evaluated, κ is the security parameter and BC is the communication
complexity of one broadcast of a κ-bit value. This means the average number of bits sent …
Abstract
We present a robust multiparty computation protocol. The protocol is for the cryptographic model with open channels and a poly-time adversary, and allows n parties to actively securely evaluate any poly-sized circuit with resilience t < n/2. The total communication complexity in bits over the point-to-point channels is , where S is the size of the circuit being securely evaluated, κ is the security parameter and is the communication complexity of one broadcast of a κ-bit value. This means the average number of bits sent and received by a single party is , which is almost independent of the number of participating parties. This is the first robust multiparty computation protocol with this property.
Springer