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.

ZK-friendly symmetric primitives are usually classified in 3 types.