Feistel Structures for MPC, and More

Abstract

We study approaches to generalized Feistel constructions with low-degree round functions with a focus on x \mapsto x^3. Besides known constructions, we also provide a new balanced Feistel construction with improved diffusion properties. This then allows us to propose more efficient generalizations of the MiMC design (Asiacrypt’16), which we in turn evaluate in three application areas. Whereas MiMC was not competitive at all in a recently proposed new class of PQ-secure signature schemes, our new construction leads to about 30 times smaller signatures than MiMC. In MPC use cases, where MiMC outperforms all other competitors, we observe improvements in throughput by a factor of more than 4 and simultaneously a 5-fold reduction of preprocessing effort, albeit at the cost of a higher latency. Another use case where MiMC already outperforms other designs, in the area of SNARKs, sees modest improvements. Additionally, this use case benefits from the flexibility to use smaller fields.

Keywords: Feistel · Multiplicative Complexity · Algebraic Attack · Secure Multiparty Computation (MPC) · PQ-secure Signature Scheme · SNARKs

1 Introduction

Computing on Encrypted Data

Due to an increasing maturity of secure multi-party computation, there are a couple of companies such as Partisia [Par], Sepior [Sep], Sharemind [BLW08], Unbound [Unb] which try to incorporate MPC frameworks into large projects to offer services where the companies do not need to know the user inputs to be able to compute on them [Arc+18]. Since the complexity of these systems grows, one must be able to incorporate encrypted databases with an MPC system to deal with data in transit or at rest.

Cryptographic primitives such as block ciphers play an important role in storing outputs from the MPC engine into an encrypted database: parties can engage in an MPC protocol to compute an encryption of the share using a shared key. In this way, parties jointly produce a single ciphertext rather than having N ciphertexts per stored share.

If one chooses AES as the underlying primitive for the encryption scheme then the share conversions become the bottleneck of MPC procedures when the underlying engine performs arithmetic modulo p. Hence, for efficient and secure computation of algorithms modulo p we would like a blockcipher over the same field. Grassi et al. [GRR+16] give several constructions for lightweight pseudorandom functions (PRFs) when evaluated in a prime field of large characteristic and concluded that among various other options MiMC [AGR+16] is competitive, which is the starting point of our design as well.

Our Results

In this work, we continue the exploration of construction strategies for symmetric cryptography which benefit MPC applications. In particular, we continue with an old design idea by Nyberg and Knudsen [NK95] from the 1990s, in which the round function of a Feistel network is the mapping x \mapsto x^3. Even though the idea was abandoned soon after [JK97], recently it was shown that it can lead to efficient instantiations for SNARKs [AGR+16] and in MPC protocols [GRR+16]: The MiMC design mentioned above.

In this paper we generalize this design approach. Our generalized MiMC (GMiMC) can cope with prime fields while at the same time work on many field elements at once. For this we draw from old approaches in symmetric cryptography: Generalized Feistel networks which generalize the approach taken by the designers of the DES. Previous works [GRR+16, RSS17] did not take into account how to optimize the number of multiplications for a higher number of blocks and treated the PRF as a black-box when extending to more inputs. This is where our constructions shine the most: if one chooses to encrypt multiple shares at once we can amortize the number of multiplications per share resulting in a more efficient preprocessing phase.

In order to effectively make use of a large number of branches t, we introduce a new variant of the generalized Feistel network, which we call “Multi-Rotating Feistel network”, that provides extremely fast diffusion. It permits the construction of a block cipher operating on t = 2^b branches, which provides full diffusion in 2b = 2 \cdot \log_2(t) rounds rather than t.

We show the performance of GMiMC in MPC applications based on secret sharing techniques such as BDOZa [BDOZ11], SPDZ [DPSZ12] or VIFF [DGKN09]. We show that using our construction one can choose to encrypt multiple shares at once thus amortizing the number of multiplications per share and resulting in a more efficient preprocessing phase. From a theoretical point of view two of our constructions are the first to avoid the linear increase of time and data sent across the parties in the preprocessing phase with the number of encrypted blocks (in \mathbb{F}_p).

Other Applications

Basic cryptographic primitives that require a low number of multiplications without compromising security have many applications. These primitives can reduce the cost of countermeasures against various side-channel attacks [DPVR00, GLS+14], eliminate the ciphertext expansion in homomorphic encryption schemes [ARS+15, MJS+16, Can+16, DSE+14, NLV11], help dealing with encrypted data in secure multi-party computation systems [ARS+15, GRR+16, RSS17], increase throughput or latency in SNARKs [AGR+16], and reduce the signature size of signature schemes and (privacy-preserving) variants based on one-way functions from symmetric-key primitives and non-interactive zero-knowledge proofs [Cha+17a, DRS18b, BEF18, DRS18a, KKW18].

2 Description of Generalized MiMC

Notation

In a Feistel network, X_{i-1} denotes the input to the branch i, where 1 \leq i \leq t. X_{t-1} and X_0 denote the inputs to the leftmost and rightmost branches respectively. X_i \in \mathbb{F} for a finite field \mathbb{F}. The block size (in bits) of the keyed Feistel permutation is denoted by N, while n = \lceil \log_2 |\mathbb{F}| \rceil denotes the branch size (in bits). We write \mathbb{F}_p for the finite prime field of order p. We write \mathbb{F}_{2^q} for any finite field of order 2^q. The bit size of the key of a block cipher is denoted by \kappa. In particular, through the paper we work with two different cases:

• the univariate case, for which the key-size is \kappa = n = \lceil \log_2 |\mathbb{F}| \rceil;
• the multivariate case, for which the key-size is \kappa = N = n \cdot t.

2.1 The Block Cipher GMiMC

We construct “Generalized Feistel MiMC” (GMiMC) variants from several generalized (unbalanced and balanced) Feistel networks: with contracting round function (CRF), expanding round function (ERF), Nyberg’s GFN and a new structure which we call Multi-Rotating (MR). Each of the following constructions is a keyed permutation over \mathbb{F}_{2^n} or \mathbb{F}_p. The three main parameters of the block ciphers are denoted by [\kappa, t, n].

2.1.1 GMiMC_{\mathrm{crf}}

An unbalanced Feistel network (UFN) with a contracting round function (CRF) can be written as

where X_i is the input to the i-th branch and F(\cdot) is a key-dependent function in round j. In GMiMC_{\mathrm{crf}} we define the j-th round function as

where c_j and k_j are respectively the round constant and the key of the round j (for 1 \le j \le r).

2.1.2 GMiMC_{\mathrm{erf}}

An unbalanced Feistel network with an expanding round function (ERF) can be written as

In GMiMC_{\mathrm{erf}} the j-th round function is defined as

2.1.3 GMiMC_{\mathrm{Nyb}}

A generalized Feistel network was proposed in [Nyb96] for an even number of branches and can be written as

Each F_i(\cdot) in the j-th round of GMiMC_{\mathrm{Nyb}} is defined as

2.1.4 GMiMC_{\mathrm{mrf}}

In [SM10], Suzaki and Minematsu introduced new variants of the GFN structure where the linear mixing applied after the Feistel functions is a complex permutation rather than a simple rotation. This allowed them to build GFNs operating on t = 2^b branches such that full diffusion is achieved in 2b rounds rather than the 2t rounds needed by a Nyberg-style construction.

Here, we introduce the Multi-Rotating structure for generalized Feistel networks, which provides full diffusion as quickly as a Twine-like structure without the constraint that the number of branches is a power of 2 or lower than a certain threshold. A rotated Feistel round is a permutation \mathcal{R}_s parameterized by a rotation amount s. Like in GMiMC_{\mathrm{Nyb}}, each F_i in the j-th round of GMiMC_{\mathrm{mrf}} is defined as

We build a GMiMC_{\mathrm{mrf}} instance operating on t branches using a sequence of rotations \{s_j\}_{0 \le j \le r} where

We denote by \Lambda(t) the minimum number of rounds to achieve full diffusion, that is \Lambda(t) = 2\lceil \log_2(t) \rceil.

2.1.5 Key Schedule

When |k| = n (i.e. the univariate case), then k_i = k \; \forall i. The key schedule for the multivariate case |k| = t \times n uses a t \times t matrix M with elements in \mathbb{F}_{2^n} or \mathbb{F}_p that satisfies:

• M is invertible;
• for each 1 \le i \le \lceil R/t \rceil where R is the number of rounds, M^i[j,l] \neq 0 for all 0 \le j, l < t.

This condition guarantees that each subkey depends linearly on all the first t subkeys, which allows saving approximately t-1 rounds compared to a cyclic key schedule.

2.2 Hash Function

To construct the hash function GMiMCHash, we use one of the structures (e.g. GMiMC_{\mathrm{erf}}) with fixed subkeys and instantiate a sponge construction [BDPV08]. When the internal permutation \mathcal{P} of an N-bit sponge function (composed of c-bit capacity and r-bit bitrate, N = c + r) is modeled as a randomly chosen permutation, Bertoni et al. [BDPV08] proved it to be indifferentiable from a random oracle up to 2^{c/2} calls to \mathcal{P}.

For GMiMCHash-256 we use a GMiMC permutation with N = n \cdot t = 1024 or 1025. The rate and the capacity are chosen as 512 and 513 respectively, offering collision security and preimage security of 256 bits.

3 Security Analysis

For each proposal we consider the maximum number of rounds that can be attacked by the attacks currently present in the literature. Due to the target applications, the authors limit themselves to providing the number of rounds to guarantee security only in the following two scenarios:

• GMiMC instantiated over \mathbb{F}_p such that the size of the prime is 128 bit or more (used for SNARKs and MPC);
• GMiMC instantiated over \mathbb{F}_{2^n} in the low-data scenario (used for PQ-Signature Schemes).

4 Security Analysis – GMiMC instantiated over \mathbb{F}_p

4.1 Algebraic Attacks

These attacks are particularly relevant to applications which only make a limited number of (plaintext, ciphertext) pairs available to the attacker. A key datum for all these attacks is the degree reached in each construction after r rounds.

Growth of Degree of GMiMC_{\mathrm{crf}}

Consider the t-branch, univariate case. Given a known plaintext, the degree d_i of the key in branch X_i after r rounds is

4.1.1 Greatest Common Divisors

As for the original MiMC [AGR+16], an attack strategy is to compute Greatest Common Divisors (GCD). Given more than one known (plaintext, ciphertext) pair, one can construct their polynomial representations and compute their polynomial GCD to recover a multiple of the key. Since the interpolation attack is more efficient than the GCD attack (from the attacker’s point of view), the GCD attack details are deferred to Section 5.1 and Appendix C.4.

4.1.2 Gröbner Bases

The natural generalization of GCDs to the multivariate case is the notion of a Gröbner basis [CLO97]. For generic systems, the complexity of computing a Gröbner basis for a system of \mathfrak{N} polynomials in \mathfrak{V} variables is

operations over the base field, where D_{\mathrm{reg}} is the degree of regularity and 2 \le \omega < 3 is the linear algebra constant.

4.1.3 Interpolation Attack

One of the most powerful attacks against the GMiMC family is the interpolation attack, introduced by Jakobsen and Knudsen [JK97] in 1997. The strategy is to construct a polynomial corresponding to the encryption function without knowledge of the secret key.

GMiMC_{\mathrm{crf}}. GMiMC_{\mathrm{crf}} is secure against interpolation attack if (3^{r-2t+2})^t \approx 2^N \simeq p^t. Hence,

rounds will be secure. Conservatively, 2r + 2 rounds will be secure against meet-in-the-middle attacks for the case 2^\kappa \simeq p.

4.1.4 Higher-Order Differential

Higher-order differential attacks [Knu95] exploit the fact that \sum_{x \in A} P(x) = 0 if the dimension of A is higher than the degree of P(\cdot). A crucial difference exists between \mathbb{F}_{2^N} and \mathbb{F}_p: while \mathbb{F}_{2^m} is always a subspace of \mathbb{F}_{2^n} for each m \le n, the only subspaces of \mathbb{F}_p are \{0\} and \mathbb{F}_p. This means that a lower degree (and hence fewer rounds) suffices to protect a cipher instantiated over \mathbb{F}_p.

4.2 Statistical Attacks

4.2.1 Classical and Truncated Differential Cryptanalysis

The function f(x) = x^3 is Almost Perfect Non-linear (APN) [NK92] and thus has optimal differential probability bounded above by 2/2^n or 2/|\mathbb{F}_p|.

GMiMC_{\mathrm{crf}}. The following truncated characteristic over t+1 rounds has overall probability 2^{-2n+2}:

By iterating, it is possible to construct a differential characteristic over s \cdot (t+1) with probability at most (2^{-2n+2})^s. Then 2 + t \cdot (t+1) \cdot \lceil \frac{n}{2(n-1)} \rceil rounds suffice for the univariate case.

4.2.2 Impossible Differential Cryptanalysis

Impossible differential cryptanalysis exploits differentials occurring with probability 0. For GMiMC_{\mathrm{crf}}, the number of rounds must be at least 3t - 1 for the case \kappa = n, and 4t - 2 for the case \kappa = t \cdot n.

4.2.3 Linear Cryptanalysis

Linear attacks [Mat94] pose no threat to the GMiMC family instantiated with the same number of rounds defined for differential cryptanalysis. This follows from the fact that the cubic function is almost bent, meaning its maximum square correlation is limited to 2^{-n+1}.

4.2.4 “Generic” (MitM) Attacks

For GMiMC_{\mathrm{crf}}, 5t - 4 rounds can be attacked when the key size equals the block size [GJNS16]. For GMiMC_{\mathrm{erf}}, generic attacks cover 4t - 2 rounds [GJNS16].

4.3 Quantum Improvements

In a post-quantum setting, the cost of exhaustive key search is square-rooted by Grover’s algorithm. Statistical attacks remain unchanged (except perhaps their computational part). The quantum interpolation attack gives no significant advantage since the attack requires d/2 queries, where d is the degree of the polynomial [CVHS16]. It is not clear that Grover’s algorithm can improve the GCD or Gröbner basis attacks.

5 Security Analysis – GMiMC instantiated over \mathbb{F}_{2^n} in the Low-Data Attacks

Among all attacks present in the literature, only two apply for the case of low-data complexity: the GCD attack and its generalization as a Gröbner Basis attack. Statistical attacks and other algebraic attacks (interpolation, higher-order differential) are not competitive in this setting.

5.1 Security Analysis – GCD Attacks

Two-pair case. Consider two polynomials E(K, p^1) - c^1 and E(K, p^2) - c^2. These polynomials share (K - k) as a factor. By computing their GCD, we can find the value of k.

One-pair case. Since we work with a Feistel construction, we can set up a GCD computation among the branches of the cipher using a single known pair.

Complexity. The complexity for finding the GCD of two polynomials of degree d is \mathcal{O}(d \log_2^2 d). To derive the required number of rounds, we target

GMiMC_{\mathrm{crf}}, case \kappa = n. The number of rounds must be approximately

to thwart the Meet-in-the-Middle variant.

6 Parameter-Space Exploration

GMiMC_{\mathrm{crf}} vs GMiMC_{\mathrm{erf}}. GMiMC_{\mathrm{erf}} is always more efficient than GMiMC_{\mathrm{crf}}, since it always requires a lower number of rounds to be secure.

GMiMC_{\mathrm{Nyb}} vs GMiMC_{\mathrm{mrf}}. GMiMC_{\mathrm{mrf}} is always more efficient than GMiMC_{\mathrm{Nyb}}, since it always requires a lower number of rounds to be secure.

The minimum number of rounds is obtained by choosing the number of branches t not too small and not too big (e.g. 6 \le t \le 18). For this range, GMiMC_{\mathrm{erf}} is as competitive as MiMC or even more so.

6.1 MPC/SNARK/PQ Signature Applications

The two selected GMiMC ciphers are optimized with respect to different metrics:

• SNARK: minimize total number of operations – case \kappa = \log_2 p (using the hash function GMiMCHash).
• PQ Signature: minimize total number of multiplications \times field size – case \kappa = N in low-data scenario.
• MPC: minimize/optimize both the total number of operations and the total number of (parallel) multiplications.

7 Application and Implementation

7.1 MPC Setting

The authors benchmarked the protocols using the SPDZ framework, which provides active security against multiple malicious parties [KSS13]. Protocols ran across two computers with Intel i7-4790 CPUs at 3.60GHz and 16GB of RAM connected via a 1 GB/s LAN network and an average round-trip time of 0.3 ms.

Table 4: Two-party costs for MiMC and GMiMC over a LAN network.

GMiMC_{\mathrm{crf}} and GMiMC_{\mathrm{erf}} have a very fast preprocessing phase because they perform a low number of multiplications. These two constructions are the first to avoid the linear increase of preprocessing data with the number of blocks. For 16 blocks, the preprocessing time for GMiMC_{\mathrm{erf}} is 5.5 times smaller than MiMC: 0.86ms vs. 4.86ms.

7.2 SNARKs

The rank-1 constraints in a SNARK are defined [BCG+13] as a system of bilinear equations over a field \mathbb{F}. For GMiMC_{\mathrm{erf}}, the rank-1 constraints per round are:

Table 5: Comparison of MiMC with GMiMC_{\mathrm{erf}} in SNARK when block size is 1024 bits.

For N \approx 1024-bit block size, GMiMC_{\mathrm{erf}} with t = 8 shows improvement over MiMC. For hashing a single message block, GMiMCHash-256 is more than 1.2 times faster than MiMCHash-256 and significantly (> 12 times) faster than SHA-256. The primary advantage is the flexibility to be used over 256-bit or smaller field sizes.

7.3 Post-Quantum Signatures

Picnic [Cha+17a] is a new class of digital signature schemes which derive their security entirely from the security of symmetric-key primitives. The construction is based on a one-way function f, where for the secret key x the image y = f(x) is published as the public key. A signature on a message is obtained from a non-interactive zero-knowledge proof using ZKB++.

Table 6: Comparison of MiMC with GMiMC_{\mathrm{erf}} and LowMC when block size is ≈ 256 bits (ZKB++ context).

Even for very small fields with the smallest view sizes, GMiMC_{\mathrm{erf}} performs significantly better in terms of view size and runtime than MiMC. Compared to LowMC, choosing an instance over \mathbb{F}_{2^3} allows beating the smallest signature sizes obtainable using LowMC with one S-Box by 306 bits in terms of view size.

Ring Signatures

Ring signatures solely relying on symmetric-key primitives can be constructed by proving an authentication path in a Merkle tree in zero-knowledge [DRS18b, BEF18]. MiMC based hashes incur a view size of more than a million bits per hash function evaluation, which is larger than a LowMC based hash by a factor of about 1000. With GMiMC we can change the field size and obtain much better numbers.

8 Discussion

One key take-away of this work is that, when it comes to building structures in symmetric cryptography with low multiplicative complexity, balanced Feistel networks are not the best strategy. The authors provided a new and optimal (in some sense) variant of the GFN and yet still cannot beat the ERF variant.

This observation is surprising: Unbalanced Feistel networks do not have a great track record in the academic literature and in recent designs. Among all lightweight block cipher designs listed on the CryptoLux wiki, 7 are Type-II GFNs and 10 are balanced Feistel networks, whereas none is of the UFN or ERF type.

And yet exactly those types turn out to be the best in this setting. The work parallels MiMC itself: its structure builds on a design from the mid 1990s, which in recent textbooks [KR11, Section 8.4] was shown as an example of how not to design a cipher. Despite this, it has turned out to be very good in many applications where multiplicative complexity matters.

This raises the question: What are other known but out-of-fashion structures which might be very suitable for MPC, SNARKs, PQ signatures or related applications?

References

• [AABL12] M. A. Abdelraheem, M. Ågren, P. Beelen, and G. Leander, “On the distribution of linear biases: Three instructive examples,” in CRYPTO 2012, LNCS vol. 7417, Springer, 2012, pp. 50–67.
• [AMMR18] S. Agrawal, P. Mohassel, P. Mukherjee, and P. Rindal, “Dise: Distributed symmetric-key encryption,” ePrint 2018/727, accepted at CCS 2018.
• [ARS+16a] M. Albrecht, C. Rechberger, T. Schneider, T. Tiessen, and M. Zohner, “Ciphers for MPC and FHE,” ePrint 2016/687.
• [AGR+16] M. R. Albrecht, L. Grassi, C. Rechberger, A. Roy, and T. Tiessen, “MiMC: Efficient encryption and cryptographic hashing with minimal multiplicative complexity,” in ASIACRYPT 2016, LNCS vol. 10031, Springer, 2016, pp. 191–219.
• [ARS+15] M. R. Albrecht, C. Rechberger, T. Schneider, T. Tiessen, and M. Zohner, “Ciphers for MPC and FHE,” in EUROCRYPT 2015, LNCS vol. 9056, Springer, 2015, pp. 430–454.
• [Aly+18] A. Aly et al., “SCALE-MAMBA v1.3: Documentation,” 2018.
• [NA19] N. Analytics, “MP-SPDZ,” 2019.
• [AHI+17] B. Applebaum, N. Haramaty, Y. Ishai, E. Kushilevitz, and V. Vaikuntanathan, “Low-Complexity Cryptographic Hash Functions,” in ITCS 2017, LIPIcs vol. 67, pp. 7:1–7:31.
• [AIK06] B. Applebaum, Y. Ishai, and E. Kushilevitz, “Cryptography in NC0,” SIAM J. Comput., vol. 36, no. 4, pp. 845–888, 2006.
• [Arc+18] D. W. Archer et al., “From keys to databases – real-world applications of secure multi-party computation,” ePrint 2018/450.
• [AM09] J.-P. Aumasson and W. Meier, “Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi,” 2009.
• [BFSY05] M. Bardet, J. Faugere, B. Salvy, and B. Yang, “Asymptotic behaviour of the index of regularity of quadratic semi-regular polynomial systems,” in MEGA 2005, pp. 1–14.
• [BS+14] E. Ben-Sasson et al., “Zerocash: Decentralized anonymous payments from bitcoin,” in 2014 IEEE S&P, pp. 459–474.
• [BCG+13] E. Ben-Sasson, A. Chiesa, D. Genkin, E. Tromer, and M. Virza, “SNARKs for C: Verifying program executions succinctly and in zero knowledge,” in CRYPTO 2013, LNCS vol. 8043, Springer, 2013, pp. 90–108.
• [BDOZ11] R. Bendlin, I. Damgård, C. Orlandi, and S. Zakarias, “Semi-homomorphic encryption and multiparty computation,” in EUROCRYPT 2011, LNCS vol. 6632, Springer, 2011, pp. 169–188.
• [BDPV] G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche, “Note on zero-sum distinguishers of Keccak-f.”
• [BDPV08] G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche, “On the indifferentiability of the sponge construction,” in EUROCRYPT 2008, LNCS vol. 4965, Springer, 2008, pp. 181–197.
• [BFP09] L. Bettale, J.-C. Faugere, and L. Perret, “Hybrid approach for solving multivariate systems over finite fields,” J. Math. Cryptology, vol. 3, no. 3, pp. 177–197, 2009.
• [BFP12] L. Bettale, J. Faugère, and L. Perret, “Solving polynomial systems over finite fields: improved analysis of the hybrid approach,” in ISSAC’12, ACM, 2012, pp. 67–74.
• [BAK98] E. Biham, R. Anderson, and L. Knudsen, “Serpent: A new block cipher proposal,” in FSE 1998, pp. 222–238.
• [BBS99] E. Biham, A. Biryukov, and A. Shamir, “Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials,” in EUROCRYPT’99, LNCS vol. 1592, Springer, 1999, pp. 12–23.
• [BLW08] D. Bogdanov, S. Laur, and J. Willemson, “Sharemind: A framework for fast privacy-preserving computations,” in ESORICS 2008, LNCS vol. 5283, Springer, 2008, pp. 192–206.
• [BEF18] D. Boneh, S. Eskandarian, and B. Fisch, “Post-quantum group signatures from symmetric primitives,” ePrint, vol. 2018, p. 261, 2018.
• [BIP+18] D. Boneh, Y. Ishai, A. Passelègue, A. Sahai, and D. J. Wu, “Exploring crypto dark matter,” in TCC 2018, Springer, pp. 699–729.
• [BC10] C. Boura and A. Canteaut, “A zero-sum property for the Keccak-f permutation with 18 rounds,” in ISIT, IEEE, 2010, pp. 2488–2492.
• [BCC11] C. Boura, A. Canteaut, and C. De Cannière, “Higher-Order Differential Properties of Keccak and Luffa,” in FSE 2011, LNCS vol. 6733, Springer, pp. 252–269.
• [BNS14] C. Boura, M. Naya-Plasencia, and V. Suder, “Scrutinizing and improving impossible differential attacks: Applications to CLEFIA, Camellia, LBlock and Simon,” in ASIACRYPT 2014, LNCS vol. 8873, Springer, pp. 179–199.
• [BPP00] J. Boyar, R. Peralta, and D. Pochuev, “On the multiplicative complexity of Boolean functions over the basis (∩, +, 1),” Theor. Comput. Sci., 2000.
• [Can+16] A. Canteaut et al., “Stream ciphers: A practical solution for efficient homomorphic-ciphertext compression,” in FSE 2016, LNCS vol. 9783, Springer, pp. 313–333.
• [CGT19] V. Cauchois, C. Gomez, and G. Thomas, “General diffusion analysis: How to find optimal permutations for generalized type-II Feistel schemes,” ToSC, vol. 2019, no. 1, pp. 264–301, 2019.
• [Cha+17a] M. Chase et al., “Post-quantum zero-knowledge and signatures from symmetric-key primitives,” in ACM CCS 17, pp. 1825–1842.
• [Cha+17b] M. Chase et al., “The Picnic Signature Algorithm Specification,” 2017.
• [CVHS16] A. M. Childs, W. van Dam, S. Hung, and I. E. Shparlinski, “Optimal quantum algorithm for polynomial interpolation,” in ICALP, LIPIcs vol. 55, pp. 16:1–16:13.
• [CLO97] D. A. Cox, J. Little, and D. O’Shea, Ideals, Varieties, and Algorithms, 2nd ed., Springer, 1997.
• [DPVR00] J. Daemen, M. Peeters, G. Van Assche, and V. Rijmen, “Nessie Proposal: NOEKEON,” 2000.
• [DGKN09] I. Damgård, M. Geisler, M. Krøigaard, and J. B. Nielsen, “Asynchronous multiparty computation: Theory and implementation,” in PKC 2009, LNCS vol. 5443, Springer, pp. 160–179.
• [DPSZ12] I. Damgård, V. Pastro, N. P. Smart, and S. Zakarias, “Multiparty computation from somewhat homomorphic encryption,” in CRYPTO 2012, LNCS vol. 7417, Springer, pp. 643–662.
• [DRS18a] D. Derler, S. Ramacher, and D. Slamanig, “Generic double-authentication preventing signatures and a post-quantum instantiation,” in ProvSec 2018, LNCS vol. 11192, Springer, pp. 258–276.
• [DRS18b] D. Derler, S. Ramacher, and D. Slamanig, “Post-Quantum Zero-Knowledge Proofs for Accumulators with Applications to Ring Signatures from Symmetric-Key Primitives,” in PQCrypto 2018, LNCS vol. 10786, Springer, pp. 419–440.
• [DKP+19] I. Dinur, D. Kales, A. Promitzer, S. Ramacher, and C. Rechberger, “Linear equivalence of block ciphers with partial non-linear layers: Application to LowMC,” in EUROCRYPT 2019.
• [DLW17] X. Dong, Z. Li, and X. Wang, “Quantum cryptanalysis on some generalized Feistel schemes,” ePrint 2017/1249.
• [DSE+14] Y. Doröz, A. Shahverdi, T. Eisenbarth, and B. Sunar, “Toward practical homomorphic evaluation of block ciphers using Prince,” in FC 2014 Workshops, LNCS vol. 8438, Springer, pp. 208–220.
• [DL12a] M. Duan and X. Lai, “Improved zero-sum distinguisher for full round Keccak-f permutation,” Chinese Sci. Bull., vol. 57, no. 6, pp. 694–697, 2012.
• [DL12b] M. Duan and X. Lai, ibid.
• [GRR+16] L. Grassi, C. Rechberger, D. Rotaru, P. Scholl, and N. P. Smart, “MPC-friendly symmetric key primitives,” in ACM CCS 16, pp. 430–443.
• [GLS+14] V. Grosso, G. Leurent, F.-X. Standaert, and K. Varici, “LS-designs: Bitslice encryption for efficient masked software implementations,” in FSE 2014, LNCS vol. 8540, Springer, pp. 18–37.
• [GJNS16] J. Guo, J. Jean, I. Nikolic, and Y. Sasaki, “Meet-in-the-middle attacks on classes of contracting and expanding Feistel constructions,” ToSC, vol. 2016, no. 2, pp. 307–337.
• [HMV03] D. Hankerson, A. J. Menezes, and S. Vanstone, Guide to Elliptic Curve Cryptography, Springer, 2003.
• [JK97] T. Jakobsen and L. R. Knudsen, “The interpolation attack on block ciphers,” in FSE’97, LNCS vol. 1267, Springer, pp. 28–40.
• [KKW18] J. Katz, V. Kolesnikov, and X. Wang, “Improved non-interactive zero knowledge with applications to post-quantum signatures,” in ACM CCS 18, pp. 525–537.
• [KPR18] M. Keller, V. Pastro, and D. Rotaru, “Overdrive: Making SPDZ Great Again,” in EUROCRYPT 2018, LNCS vol. 10822, Springer, pp. 158–189.
• [KSS13] M. Keller, P. Scholl, and N. P. Smart, “An architecture for practical actively secure MPC with dishonest majority,” in ACM CCS 13, pp. 549–560.
• [Knu95] L. R. Knudsen, “Truncated and higher order differentials,” in FSE’94, LNCS vol. 1008, Springer, 1995, pp. 196–211.
• [Knu98] L. R. Knudsen, “DEAL – A 128-bit Block Cipher,” Technical Report, 1998.
• [KR11] L. R. Knudsen and M. J. B. Robshaw, The Block Cipher Companion, Springer, 2011.
• [Mat94] M. Matsui, “Linear cryptanalysis method for DES cipher,” in EUROCRYPT’93, LNCS vol. 765, Springer, 1994, pp. 386–397.
• [MJS+16] P. Méaux, A. Journault, F.-X. Standaert, and C. Carlet, “Towards stream ciphers for efficient FHE with low-noise ciphertexts,” in EUROCRYPT 2016, LNCS vol. 9665, Springer, pp. 311–343.
• [MJ16] N. E. Mrabet and M. Joye, Guide to Pairing-Based Cryptography, Chapman & Hall/CRC, 2016.
• [NLV11] M. Naehrig, K. E. Lauter, and V. Vaikuntanathan, “Can homomorphic encryption be practical?” in CCSW 2011, pp. 113–124.
• [Nyb96] K. Nyberg, “Generalized Feistel networks,” in ASIACRYPT’96, LNCS vol. 1163, Springer, pp. 91–104.
• [NK92] K. Nyberg and L. R. Knudsen, “Provable Security Against Differential Cryptanalysis,” in CRYPTO 1992, LNCS vol. 740, Springer, pp. 566–574.
• [NK95] K. Nyberg and L. R. Knudsen, “Provable security against a differential attack,” J. Cryptology, vol. 8, no. 1, pp. 27–37, 1995.
• [ISM] I. S. M. S. Overview.
• [Par] Partisia.
• [PNB06] J. Patarin, V. Nachef, and C. Berbain, “Generic attacks on unbalanced Feistel schemes with contracting functions,” in ASIACRYPT 2006, LNCS vol. 4284, Springer, pp. 396–411.
• [QSL+17] K. Qiao, L. Song, M. Liu, and J. Guo, “New Collision Attacks on Round-Reduced Keccak,” in EUROCRYPT 2017, LNCS vol. 10212, pp. 216–243.
• [RSS17] D. Rotaru, N. P. Smart, and M. Stam, “Modes of operation suitable for computing on encrypted data,” ToSC, vol. 2017, no. 3, pp. 294–324.
• [SC12] R. Safavi-Naini and R. Canetti, Eds., CRYPTO 2012, LNCS vol. 7417, Springer, 2012.
• [Sco07] M. Scott, “Optimal irreducible polynomials for GF(2^m) arithmetic,” ePrint 2007/192.
• [Sep] Sepior.
• [Sho] V. Shoup, “Number Theory Library 5.5.2 (NTL).”
• [Sol99] J. A. Solinas, “Generalized Mersenne numbers,” NSA, Tech. Rep., 1999.
• [Ste+17] W. Stein et al., Sage Mathematics Software Version 8.0, 2017.
• [SM10] T. Suzaki and K. Minematsu, “Improving the generalized Feistel,” in FSE 2010, LNCS vol. 6147, Springer, pp. 19–39.
• [SMM+12] T. Suzaki, K. Minematsu, S. Morioka, and E. Kobayashi, “Twine: A lightweight block cipher for multiple platforms,” in SAC 2012, LNCS vol. 7707, Springer, pp. 339–354.
• [Tod15] Y. Todo, “Structural Evaluation by Generalized Integral Property,” in EUROCRYPT 2015, LNCS vol. 9056, Springer, pp. 287–314.
• [Unb] Unbound.
• [WGR18] Q. Wang, L. Grassi, and C. Rechberger, “Zero-Sum Partitions of PHOTON Permutations,” in CT-RSA 2018, LNCS vol. 10808, pp. 279–299.

Appendices

A   Variants of the GMiMC Family of Ciphers

A.1 A Permutation Round Function. A permutation round function is chosen to prevent attacks due to internal collisions. If internal collisions occur, a truncated trail with only one active branch per round would be possible, which is particularly undesirable in GMiMC_{\mathrm{erf}}.

A.2 Different Round Functions. One may consider a round function of the form F(x) = (x \oplus k \oplus c)^d for generic exponents d. The best choices for exponents seem to be d = 2^r - 1 for integer r. However, since the number of multiplications per round increases, the total number of multiplications does not change, making d = 3 the optimal choice.

B   Diffusion in GMiMC_{\mathrm{mrf}}

The number of rounds needed to achieve full diffusion for a t-branch Multi-Rotating Feistel network is equal to 2\log_2 t - 1, proving Theorem 1. Using the notation where I^i denotes the set of indices j such that V_j^i depends on V_0^0, the induction

shows that all elements of \{0, \ldots, t/2 - 1\} are in I^{2\lceil \log(t/2) \rceil + 1}. Thus 2\lceil \log(t/2) \rceil + 2 = 2\lceil \log_2(t) \rceil rounds provide full diffusion.

C   Security Analysis (Algebraic Attacks)

Appendix C provides detailed analyses for the interpolation attack, higher-order differential, Gröbner basis, and GCD attacks for all four GMiMC variants (GMiMC_{\mathrm{erf}}, GMiMC_{\mathrm{Nyb}}, GMiMC_{\mathrm{mrf}}) in both the general and low-data scenarios. A key result for GMiMC_{\mathrm{erf}} in the low-data GCD attack is that the number of rounds must be incremented by t - 3 to account for a degree-reduction attack based on computing \mathrm{GCD}(X_{t-1} \oplus X_{t-2}, X_{t-2} \oplus X_{t-3}).

D   Security Analysis (Statistical Attacks)

Appendix D gives detailed truncated differential, impossible differential, and linear cryptanalysis for all variants. A notable result (Proposition 1) is that there cannot be any truncated differential trail covering i \geq 4 rounds of GMiMC_{\mathrm{mrf}} with less than i active S-Boxes.

E   Field Arithmetic

Appendix E presents an example of how Generalized Mersenne primes (Solinas primes) are used to implement the signature scheme. For example, with p_{64} = 2^{64} - 2^8 - 1, the reduction method exploits p_{64} = f(t) = t^8 - t - 1 where t = 2^8.

F   GMiMC_{\mathrm{erf}} – Number of Rounds in Low-Data Scenario

The formula for the number of rounds in the low-data scenario is:

The parameter “Total Number of Multiplications \times Field Size” is minimal when the branch size n is minimized (i.e., n = 3).

Table 7: Number of rounds for GMiMC_{\mathrm{erf}} in the low-data scenario.

G   Low-Data Gröbner Basis Attack

Appendix G provides SageMath code for estimating the complexity of the Gröbner Basis attack on GMiMC. The estimate function takes as parameters the bit-size of the base field (n), the number of key elements (l), the number of branches (t), and the degree of the meet-in-the-middle polynomials (d), and returns the estimated cost of breaking GMiMC using Gröbner basis computations, including the hybrid approach that combines exhaustive search with Gröbner basis computation.