STAP use-cases: Zero Knowledge

Zero Knowledge Proofs (ZKPs) allow one party – the prover – to prove to another party – the verifier – that a statement is true without disclosing any information beyond the statement’s validity.

ZKPs use arithmetic circuits, which reduce computational problems to algebraic problems involving low-degree polynomials over a finite field. In several ZKP protocols, XOR relations can be proven for free, and the complexity essentially depends on the number of AND gates of the relation to be proven.

This cost metric suggests that ciphers that find a use-case in ZK 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 AND gates in a circuit. A lower MC allows for a positive impact on latency and throughput of the ZK evaluation of the cipher. Classical symmetric algorithms become inappropriate in this context, and new cryptographic protocols must then be combined with symmetric primitives whose proposed constructions use non-linear functions whose algebraic representations remain very simple on a large finite field F_q where q is either a large prime integer or a power of 2 greater than 2^128, such as a sparse polynomial of F_q[X].


ZKPs are used in many different applications, including authentication protocols, digital signatures, electronic voting, and cryptocurrency transactions.

STAP Lounge

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

                            ◊ 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.


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.


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