STAP use-cases: Multi Party Computation

Multi Party Computation (MPC) is a cryptographic protocol dividing a computation among multiple parties where no single party can see the data of the other parties.

As opposed to traditional ciphers built from linear and non-linear building blocks for applications where these two have roughly similar costs in hardware and software implementations, the situation is radically different for ciphers implemented in an MPC protocol. Linear operations come almost for free since they only incur local computation, whereas the bottleneck is non-linear operations that involve symmetric cryptographic operations and communication between parties.

This cost metric suggests that ciphers that find a use-case in MPC protocols should desirably minimize their use of non-linear operations while most cryptographically relevant work is performed as linear operations. This design philosophy is related to the fundamental theoretical question of the minimal multiplicative complexity (MC) of certain tasks, which is simply the number of multiplications (AND gates) in a circuit. A lower MC allows for a positive impact on latency and throughput of the MPC evaluation of the cipher, making it an essential feature of the circuit.

MPC for Boolean circuits

There are two classes of practically efficient secure MPC protocols for securely evaluating Boolean circuits where XOR gates are considerably cheaper (no communication and less computation) than AND gates. The first has a constant number of rounds, and their total amount of communication depends on the MC of the circuit since each AND gate requires communication. The second has a round complexity that is linear in the multiplicative depth of the evaluated circuit since each AND gate requires interaction, and hence the performance depends on both the MC and multiplicative depth of the circuit.

Applications

Applications include server-side one-time passwords, instantiation of Oblivious Pseudorandom Functions (OPRFs) for privacy-preserving keyword search, and secure storage.

STAP Lounge

The STAP Wiki currently collects information about the following list of STAP primitives used in MPC:

                            ◊ LowMC

  • Designers: Martin Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen and Michael Zohner.
  • Article: Ciphers for MPC and FHE, EUROCRYPT 2015.

LowMC is a family of flexible block ciphers based on an SPN structure defined over F_2. It is designed to be used in the context of an MPC protocol, ZK or HE scheme.

To reduce its multiplicative complexity, LowMC leaves part of the substitution layer as the identity mapping; reducing the number of Sboxes applied in parallel. It then introduces a high degree of diffusion by using pseudorandomly generated binary matrices in the linear layer in order to reach the claimed security.

The authors propose a wide range of different instantiations corresponding to 80, 128, and 256-bit security.

Cryptanalysis

Recent cryptanalysis proposes an algebraic meet-in-the-middle attack on LowMC, reducing the memory and time complexities over previous attacks that retrieve the full key from a differential trail. As a consequence, some LowMC instances could be broken for the first time.

Implementation

The authors report on experiments when evaluating LowMC with MPC protocols and with FHE.

In the case of MPC, they provide GMW benchmarking results in the semi-honest setting for a single block and for multiple blocks in parallel to encrypt 12.8 Mbit of data. The security parameters are set to 80-bit for lightweight security and to 128-bit for long-term security. The experiments are run on two desktop PCs, each equipped with an Intel Haswell i7-4770K CPU with 3.5 GHz and 16GB of RAM, that are connected by Gigabit LAN.

For FHE, they implement LowMC using the holomorphic encryption library HELib.

  • Designers: 
  • Article: 

Description, relations, special features

Sbox, round function, pics

keyboard_arrow_up