STAP block ciphers

Given a key k, a block cipher E_k is a family of permutations that takes a fixed-sized block as input and returns an encrypted message of the same size.

Block ciphers are usually built by iterating a round function; a process that is repeated r times (sub-keys might optionally be derived from a key schedule algorithm applied to the master key), where r is chosen such that the cipher offers a good security margin and efficiency when evaluating the function.

A block cipher is said to be secure if E_k, with a randomly chosen key, is indistinguishable from a random permutation. Thus, each round in the iterated construction must bring some confusion (such that changing the input has an unpredictable effect on the output) and diffusion (such that changing a few entries in the input changes many entries in the output).

The most common round function constructions are Feistel networks and Substitution Permutation Networks (SPNs).

Constructions

Feistel networks

In a Feistel network, the input x is divided into two parts: x_L and x_R, each of size n/2 bits.

A well-known Feistel cipher is the Data Encryption Standard (DES), which is no longer used because of its small key space, allowing a systematic attack in a reasonable amount of time.

SPNs

An SPN comprises three components: an S-box layer S, a diffusion layer M, and a sub-key addition AddK.

The most widely used block cipher (and best-known symmetric encryption) is the Advanced Encryption Standard (AES), considered the most secure in the community.

STAP Lounge

The STAP Wiki currently collects information about the following list of STAP block ciphers:

                            ◊ 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