What a lovely hat

Privacy-preserving Transformer inference (PPTI) is essential for deploying large language models (LLMs) such as BERT and LLaMA in sensitive domains. In these models, the attention mechanism is both the main source of expressiveness and the dominant performance bottleneck under fully homomorphic encryption (FHE), due to large ciphertext matrix multiplications and the softmax nonlinearity. This paper presents Arion, a non-interactive FHE-based PPTI protocol that specifically optimizes the...

Cube attack is one of the most powerful approaches for recovering keys of stream ciphers. Practical cube attacks generate several superpolys first and solve the system constructed by these superpolys afterward. Unlike previous practical attacks, we propose a new cube attack that transfers the difficulty of generating easy-solving superpolys to solving the system built by numerous nonlinear ones. In the offline phase, we recovered lots of nonlinear superpolys by improving the approach...

The butterfly structures were introduced by Perrin et al. as a generalization of the Dillon's APN permutation operated in 6 bits. It was proved by several authors independently that such butterflies are differentially 4-uniform and have best known nonlinearity among functions over $\mathbb{F}_{2^{2k}}$. In [LLHQ21, LHXZ22] authors provided sufficient coefficient conditions such that the closed butterfly is a permutation and they further prove that such functions have boomerang uniformity 4...

The study of cryptographic criteria for Boolean functions with restricted domains has been an important topic over the last 20 years. A revived interest has sparked after the work of Carlet, Méaux and Rotella in 2017, where the authors studied cryptographic properties of restricted-domain functions and introduced the concept of weightwise perfectly balanced functions as part of the analysis of the FLIP stream cipher. Weightwise (almost) perfectly balanced functions are defined as Boolean...

The first contribution of the paper is to put forward an abstract definition of the Grain family of stream ciphers which formalises the different components that are required to specify a particular member of the family. Our second contribution is to provide new and strengthened definitions of the components. These include definining new classes of nonlinear Boolean functions, improved definition of the state update function during initialisation, choice of the tap positions, and the...

Side-channel attacks can uncover sensitive data by analyzing information leakages of cryptographic hardware devices caused by the power consumption, timing, electromagnetic, glitches, etc. An attack exploiting these leakages is the differential power analysis (DPA). Threshold Implementation (TI), introduced by Nikova et al. [JoC 24(2):292-321, 2011], was proposed to resist DPA on hardware implementations of block ciphers and eliminate information leakage due to glitches. TI is based on...

The machine learning problem of model extraction was first introduced in 1991 and gained prominence as a cryptanalytic challenge starting with Crypto 2020. For over three decades, research in this field has primarily focused on ReLU-based neural networks. In this work, we take the first step towards the cryptanalytic extraction of PReLU neural networks, which employ more complex nonlinear activation functions than their ReLU counterparts. We propose a raw output-based parameter...

Lattice-based key-homomorphic encodings introduced by Boneh et al.~(Eurocrypt'14)---known as BGG+ encodings---underpin many primitives, including key-policy attribute-based encryption (KP-ABE). Many applications beyond KP-ABE require simulating the homomorphic evaluation of FHE ciphertexts over BGG+ encodings, which involves nonlinear operations on integers of magnitude up to the ciphertext modulus $q$. However, due to noise growth incurred by multiplication, the encodable integers must be...

The protection of executable code in embedded systems requires efficient mechanisms that ensure confidentiality and integrity. Belkheyar et al. recently proposed the Authenticated Code Encryption (ACE) framework, with ChiLow-(32 + $\tau$) as the first instantiation of ACE2 at EUROCRYPT 2025. The design of ChiLow-(32 + $\tau$) is based on a 32-bit tweakable block cipher with a quadratic nonlinear layer, known as ChiChi (denoted by $\chi\!\!\chi$), and a nested tweak key schedule optimized...

We describe several families of efficiently implementable Boolean functions achieving provable trade-offs between resiliency, nonlinearity, and algebraic immunity. In particular, the following statement holds for each of the function families that we propose. Given integers $m_0\geq 0$, $x_0\geq 1$, and $a_0\geq 1$, it is possible to construct an $n$-variable function which has resiliency at least $m_0$, linear bias (which is an equivalent method of expressing nonlinearity) at most...

Physical attacks pose serious challenges to the secure implementation of cryptographic algorithms. While side-channel analysis (SCA) has received significant attention, leading to well-established countermeasures, fault attacks and especially their combination with SCA (i.e., combined attacks) remain less researched. Addressing such combined attacks often requires a careful integration of masking and redundancy techniques to resist the reciprocal effects of faults and probes. Recent research...

Zero-knowledge proofs of training (zkPoT) enable a prover to certify that a model was trained on a committed dataset under a prescribed algorithm without revealing the model or data. Proving recurrent neural network (RNN) training is challenging due to hidden-state recurrence and cross-step weight sharing, which require proofs to enforce recurrence, gradients, and nonlinear activations across time. We present SUMMER (SUMcheck and MERkle tree), a recursive zkPoT for scalable RNNs. SUMMER...

Proposed in EUROCRYPT~2025, \chilow is a family of tweakable block ciphers and a related PRF built on the novel nonlinear $\chichi$ function, designed to enable efficient and secure embedded code encryption. The only key-recovery results of \chilow are from designers which can reach at most 4 out of 8 rounds, which is not enough for a low-latency cipher like \chilow: more cryptanalysis efforts are expected. Considering the low-degree $\chichi$ function, we present three kinds of cube-like...

Secure two-party machine learning has made substantial progress through the use of mixed-mode protocols. Despite these advancements, existing approaches often suffer from efficiency bottlenecks due to the inherent mismatch between the optimal domains of various cryptographic primitives, such as Homomorphic Encryption and Oblivious Transfer. In response to these challenges, we introduce the \tNAME{} framework, which features an efficient modulus conversion protocol. This breakthrough...

Symmetric cryptography is confronting threats posed by quantum computing, including Grover's search algorithm and Simon's algorithm. In the fault-tolerant quantum computation, the limited qubit count, connectivity constraints, and error rates of quantum hardware impose stringent requirements on the implementation of cryptographic quantum circuits. Constructing low-resource quantum circuit models forms the foundation for evaluating algorithmic resistance to quantum threats. At CRYPTO 2019,...

The growing adoption of Large Language Models in privacy-sensitive domains necessitates secure inference mechanisms that preserve data confidentiality. Homomorphic encryption offers a promising pathway by enabling computation on encrypted inputs, yet existing approaches struggle to scale efficiently to full transformer models due to limitations in packing schemes, which must efficiently support a wide range of operations, including matrix multiplications, row-wise nonlinear operations, and...

Sorting encrypted values is an open research problem that plays a crucial role in the broader objective of providing efficient and practical privacy-preserving online services. The current state of the art work by Mazzone, Everts, Hahn and Peter (USENIX Security '25) proposes efficient algorithms for ranking, indexing and sorting based on the CKKS scheme, which deviates from the compare-and-swap paradigm, typically used by sorting networks, using a permutation-based approach. This allows...

Three-party secret sharing-based computation has emerged as a promising approach for secure deep learning, benefiting from its high throughput. However, it still faces persistent challenges in computing complex operations such as secure Sign-Bit Extraction, particularly in high-latency and low-bandwidth networks. A recent work, Aegis (Lu et al., Cryptology ePrint'2023), made significant strides by proposing a constant-round DGK-style Sign-Bit Extraction protocol with GPU acceleration on...

Conventional hash functions are often inefficient in zero-knowledge proof settings, leading to design of several ZK-friendly hash functions. On the other hand, lookup arguments have recently been incorporated into zero-knowledge protocols, allowing for more efficient handling of ``ZK-unfriendly'' operations, and hence ZK-friendly hash functions based on lookup tables. In this paper, we propose a new ZK-friendly hash function, dubbed $\mathsf{Polocolo}$, that employs an S-box constructed...

There is rising interest in combining Differential Privacy (DP) and Secure Multiparty Computation (MPC) techniques to protect distributed database query evaluations from both adversaries taking part in the computation and those observing the outputs. This requires implementing both the query evaluation and noise generation parts of a DP mechanism directly in MPC. While query evaluation can be done using existing highly optimized MPC techniques for secure function evaluation, efficiently...

Fully Homomorphic Encryption (FHE) enables arbitrary computation directly on encrypted data. The TFHE scheme supports encryption of bits or small integers, evaluating any univariate function via programmable bootstrapping (PBS), which also refreshes ciphertext noise. Since both linear and nonlinear functions can be expressed with PBS, arbitrary circuits of unlimited depth can be computed without accuracy loss, aside from a negligible failure probability. However, a key limitation of TFHE is...

The increased popularity of large language models (LLMs) raises serious privacy concerns, where users' private queries are sent to untrusted servers. Many cryptographic techniques have been proposed to provide privacy, such as secure multiparty computation (MPC), which enables the evaluation of LLMs directly on private data. However, cryptographic techniques have been deemed impractical as they introduce large communication and computation. On the other hand, many obfuscation techniques have...

This paper presents new results that establish connections between isogeny graphs and nonlinear recurrences over finite fields. Specifically, we prove several theorems that link these two areas, offering deeper insights into the structure of isogeny graphs and their relationship with nonlinear recurrence sequences. We further provide two related conjectures which may be worth of further research. These findings contribute to a better understanding of the endomorphism ring of a curve,...

In this paper, we propose a new 10-bit S-box generated from a Feistel construction. The subpermutations are generated by a 5-cell cellular automaton based on a unique well-chosen rule and bijective affine transformations. In particular, the cellular automaton rule is chosen based on empirical tests of its ability to generate good pseudorandom output on a ring cellular automaton. Similarly, Feistel's network layout is based on empirical data regarding the quality of the output S-box. We...

Advanced Encryption Standard (AES) is one of the most widely used and extensively studied encryption algorithms globally, which is renowned for its efficiency and robust resistance to attacks. In this paper, three quantum circuits are designed to implement the S-box, which is the sole nonlinear component in AES. By incorporating a linear key schedule, we achieve a quantum circuit for implementing AES with the minimum number of qubits used. As a consequence, only 264/328/398 qubits are needed...

Differential cryptanalysis is a powerful technique for attacking block ciphers, wherein the Markov cipher assumption and stochastic hypothesis are commonly employed to simplify the search and probability estimation of differential trails. However, these assumptions often neglect inherent algebraic constraints, potentially resulting in invalid trails and inaccurate probability estimates. Some studies identified violations of these assumptions and explored how they impose constraints on key...

S-boxes are the most popular nonlinear building blocks used in symmetric-key primitives. Both cryptographic properties and implementation cost of an S-box are crucial for a good cipher design, especially for lightweight ones. This paper aims to determine the exact minimum area of optimal 4-bit S-boxes (whose differential uniform and linearity are both 4) under certain standard cell library. Firstly, we evaluate the upper and lower bounds upon the minimum area of S-boxes, by...

Syndrome decoding (SD), and equivalently Learning Parity with Noise (LPN), is a fundamental problem in cryptography, which states that for a field $\mathbb{F}$, some compressing public matrix $\mathbf{G} \in \mathbb{F}^{k\times n}$, and a secret sparse vector $\mathbf{e} \in\mathbb{F}^{n}$ sampled from some noise distribution, $\mathbf{G}\mathbf{e}$ is indistinguishable from uniform. Recently, the SD has gained significant interest due to its use in pseudorandom correlation generators...

With the rapid development of quantum computers, optimizing the quantum implementations of symmetric-key ciphers, which constitute the primary components of the quantum oracles used in quantum attacks based on Grover and Simon's algorithms, has become an active topic in the cryptography community. In this field, a challenge is to construct quantum circuits that require the least amount of quantum resources. In this work, we aim to address the problem of constructing quantum circuits with the...

It is shown that the stream cipher proposed by Carlet and Sarkar in ePrint report 2025/160 is insecure. More precisely, one bit of the key can be deduced from a few keystream bytes. This property extends to an efficient key-recovery attack. For example, for the proposal with 80 bit keys, a few kilobytes of keystream material are sufficient to recover half of the key.

The nonlinear filter model is an old and well understood approach to the design of secure stream ciphers. Extensive research over several decades has shown how to attack stream ciphers based on this model and has identified the security properties required of the Boolean function used as the filtering function to resist such attacks. This led to the problem of constructing Boolean functions which provide adequate security and at the same time are efficient to implement. Unfortunately, over...

This paper introduces new protocols for secure multiparty computation (MPC) leveraging Discrete Wavelet Transforms (DWTs) for computing nonlinear functions over large domains. By employing DWTs, the protocols significantly reduce the overhead typically associated with Lookup Table-style (LUT) evaluations in MPC. We state and prove foundational results for DWT-compressed LUTs in MPC, present protocols for 9 of the most common activation functions used in ML, and experimentally evaluate the...

The construction of Boolean functions with good cryptographic properties over subsets of vectors with fixed Hamming weight is significant for lightweight stream ciphers like FLIP. In this article, we propose a general method to construct a class of Weightwise Almost Perfectly Balanced (WAPB) Boolean functions using the action of a cyclic permutation group on $\mathbb{F}_2^n$. This class generalizes the Weightwise Perfectly Balanced (WPB) $2^m$-variable Boolean function construction by Liu...

The impossible differential (ID) attack is crucial for analyzing the strength of block ciphers. The critical aspect of this technique is to identify IDs, and the researchers introduced several methods to detect them. Recently, the researchers extended the mixed-integer linear programming (MILP) approach by partitioning the input and output differences to identify IDs. The researchers proposed techniques to determine the representative set and partition table of a set over any nonlinear...

This paper studies an extension of the Linear Approximation Table (LAT) of vectorial Boolean mappings (also known as Substitution boxes) used in Linear Cryptanalysis (LC). This extended table is called NonLinear Approximation Table (NLAT).

The Hidden Weight Bit Function (HWBF) has drawn considerable attention for its simplicity and cryptographic potential. Despite its ease of implementation and favorable algebraic properties, its low nonlinearity limits its direct application in modern cryptographic designs. In this work, we revisit the HWBF and propose a new weightwise quadratic variant obtained by combining the HWBF with a bent function. This construction offers improved cryptographic properties while remaining...

In many lightweight cryptography applications, low area and latency are required for efficient implementation. The gate count in the cipher and the circuit depth must be low to minimize these two metrics. Many optimization strategies have been developed for the linear layer, led by the Boyar-Peralta (BP) algorithm. The Advanced Encryption Standard (AES) has been a focus of extensive research in this area. However, while the linear layer uses only XOR gates, the S-box, which is an essential...

A new design strategy for ZK-friendly hash functions has emerged since the proposal of $\mathsf{Reinforced Concrete}$ at CCS 2022, which is based on the hybrid use of two types of nonlinear transforms: the composition of some small-scale lookup tables (e.g., 7-bit or 8-bit permutations) and simple power maps over $\mathbb{F}_p$. Following such a design strategy, some new ZK-friendly hash functions have been recently proposed, e.g., $\mathsf{Tip5}$, $\mathsf{Tip4}$, $\mathsf{Tip4}'$ and the...

The analytical perspective employed in the study classifies the theoretical research on dependencies in differential characteristics into two types. By categorising all dependence representations from the value restrictions and the theory of quasidifferential trails, we pinpoint a specific set of nonlinear constraints, which we term linearised nonlinear constraints. We aim to establish a method that utilises value restrictions to identify these constraints, as the current method based on...

Yu et al. described an algorithm for conducting computational searches for quadratic APN functions over the finite field $\mathbb{F}_{2^n}$, and used this algorithm to give a classification of all quadratic APN functions with coefficients in $\mathbb{F}_{2}$ for dimensions $n$ up to 9. In this paper, we speed up the running time of that algorithm by a factor of approximately $\frac{n \times 2^n}{n^3}$. Based on this result, we give a complete classification of all quadratic APN functions...

In two recent papers, we introduced and studied the notion of $k$th-order sum-freedom of a vectorial function $F:\mathbb F_2^n\to \mathbb F_2^m$. This notion generalizes that of almost perfect nonlinearity (which corresponds to $k=2$) and has some relation with the resistance to integral attacks of those block ciphers using $F$ as a substitution box (S-box), by preventing the propagation of the division property of $k$-dimensional affine spaces. In the present paper, we show that this...

We show that the outsourcing algorithm for the case of linear constraints [IEEE Trans. Cloud Comput., 2023, 11(1), 484-498] cannot keep output privacy, due to the simple translation transformation. We also suggest a remedy method by adopting a hybrid transformation which combines the usual translation transformation and resizing transformation so as to protect the output privacy.

This paper reveals a critical flaw in the design of ARADI, a recently proposed low-latency block cipher by NSA researchers -- Patricia Greene, Mark Motley, and Bryan Weeks. The weakness exploits the specific composition of Toffoli gates in the round function of ARADI's nonlinear layer, and it allows the extension of a given algebraic distinguisher to one extra round without any change in the data complexity. More precisely, we show that the cube-sum values, though depending on the secret key...

It is well known that estimating a sharp lower bound on the second-order nonlinearity of a general class of cubic Booleanfunction is a difficult task. In this paper for a given integer $n \geq 4$, some values of $s$ and $t$ are determined for which cubic monomial Boolean functions of the form $h_{\mu}(x)=Tr( \mu x^{2^s+2^t+1})$ $(n>s>t \geq 1)$ possess good lower bounds on their second-order nonlinearity. The obtained functions are worth considering for securing symmetric...

Cryptography is a crucial method for ensuring the security of communication and data transfers across networks. While it excels on devices with abundant resources, such as PCs, servers, and smartphones, it may encounter challenges when applied to resource-constrained Internet of Things (IoT) devices like Radio Frequency Identification (RFID) tags and sensors. To address this issue, a demand arises for a lightweight variant of cryptography known as lightweight cryptography (LWC). In...

Privacy-Preserving Machine Learning (PPML) is one of the most relevant use cases for Secure Multiparty Computation (MPC). While private training of large neural networks such as VGG-16 or ResNet-50 on state-of-the-art datasets such as ImageNet is still out of reach, given the performance overhead of MPC, GPU-based MPC frameworks are starting to achieve practical runtimes for private inference. However, we show that, unlike plaintext machine learning, using GPU acceleration for both linear...

We describe a new class of Boolean functions which provide the presently best known trade-off between low computational complexity, nonlinearity and (fast) algebraic immunity. In particular, for $n\leq 20$, we show that there are functions in the family achieving a combination of nonlinearity and (fast) algebraic immunity which is superior to what is achieved by any other efficiently implementable function. The main novelty of our approach is to apply a judicious combination of simple...

The SHA-3 standard consists of four cryptographic hash functions, called SHA3-224, SHA3-256, SHA3-384 and SHA3-512, and two extendable-output functions (XOFs), called SHAKE128 and SHAKE256. In this paper, we study the collision resistance of the SHA-3 instances. By analyzing the nonlinear layer, we introduce the concept of maximum difference density subspace, and develop a new target internal difference algorithm by probabilistic linearization. We also exploit new strategies for optimizing...

Homomorphic encryption (HE) is a powerful technology that solves key privacy concerns in cloud computing by enabling computation on encrypted data. However, it has not seen widespread adoption due to high latencies resulting from extensive operations over high-degree polynomials with large coefficients. In this paper, we identify polynomial multiplication as a bottleneck and investigate alternative algorithms to accelerate encrypted computing. Most popular open-source HE implementations...

We reduce the number of bit operations required to implement AES to a new minimum, and also compute improvements to elements of some other ciphers. Exploring the algebra of AES allows choices of basis and streamlining of the nonlinear parts. We also compute a more efficient implementation of the linear part of each round. Similar computational optimizations apply to other cryptographic matrices and S-boxes. This work may be incorporated into a hardware AES implementation using minimal...

We study the behavior of the multiplicative inverse function (which plays an important role in cryptography and in the study of finite fields), with respect to a recently introduced generalization of almost perfect nonlinearity (APNness), called $k$th-order sum-freedom, that extends a classic characterization of APN functions, and has also some relationship with integral attacks. This generalization corresponds to the fact that a vectorial function $F:\mathbb F_2^n\mapsto \mathbb F_2^m$...

Almost perfect nonlinear (in brief, APN) functions are vectorial functions $F:\mathbb F_2^n\rightarrow \mathbb F_2^n$ playing roles in several domains of information protection, at the intersection of computer science and mathematics. Their definition comes from cryptography and is also related to coding theory. When they are used as substitution boxes (S-boxes, which are the only nonlinear components in block ciphers), APN functions contribute optimally to the resistance against...

The discourse herein pertains to a directional encryption cryptosystem predicated upon logarithmic signatures interconnected via a system of linear equations (we call it LINE). A logarithmic signature serves as a foundational cryptographic primitive within the algorithm, characterized by distinct cryptographic attributes including nonlinearity, noncommutativity, unidirectionality, and factorizability by key. The confidentiality of the cryptosystem is contingent upon the presence of an...

This work proposes a new white-box attack technique called filtering, which can be combined with any other trace-based attack method. The idea is to filter the traces based on the value of an intermediate variable in the implementation, aiming to fix a share of a sensitive value and degrade the security of an involved masking scheme. Coupled with LDA (filtered LDA, FLDA), it leads to an attack defeating the state-of-the-art SEL masking scheme (CHES 2021) of arbitrary degree and number of...

he unique design of the FLIP cipher necessitated a generalization of standard cryptographic criteria for Boolean functions used in stream ciphers, prompting a focus on properties specific to subsets of $\mathbb{F}_2^n$ rather than the entire set. This led to heightened interest in properties related to fixed Hamming weight sets and the corresponding partition of $\mathbb{F}_2^n$ into n+1 such sets. Consequently, the concept of Weightwise Almost Perfectly Balanced (WAPB) functions emerged,...

Nonlinear complexity is an important measure for assessing the randomness of sequences. In this paper we investigate how circular shifts affect the nonlinear complexities of finite-length binary sequences and then reveal a more explicit relation between nonlinear complexities of finite-length binary sequences and their corresponding periodic sequences. Based on the relation, we propose two algorithms that can generate all periodic binary sequences with any prescribed nonlinear complexity.

The substitution box (S-box) is often used as the only nonlinear component in symmetric-key ciphers, leading to a significant impact on the implementation performance of ciphers in both classical and quantum application scenarios by S-box circuits. Taking the Pauli-X gate, the CNOT gate, and the Toffoli gate (i.e., the NCT gate set) as the underlying logic gates, this work investigates the quantum circuit implementation of S-boxes based on the SAT solver. Firstly, we propose encoding methods...

A Boolean function with good cryptographic properties over a set of vectors with constant Hamming weight is significant for stream ciphers like FLIP [MJSC16]. This paper presents a construction weightwise almost perfectly balanced (WAPB) Boolean functions by perturbing the support vectors of a highly nonlinear function in the construction presented in [DM]. As a result, the nonlinearity and weightwise nonlinearities of the modified functions improve substantially.

In the linear garbling model introduced by Zahur, Rosulek, and Evans (Eurocrypt 2015), garbling an AND gate requires at least \(2\kappa\) bits of ciphertext, where $\kappa$ is the security parameter. Though subsequent works, including those by Rosulek and Roy (Crypto 2021) and Acharya et al. (ACNS 2023), have advanced beyond these linear constraints, a more comprehensive design framework is yet to be developed. Our work offers a novel, unified, and arguably simple perspective on garbled...

We suggest the family of ciphers s^E^n, n=2,3,.... with the space of plaintexts (Z*_{2^s})^n, s >1 such that the encryption map is the composition of kind G=G_1A_1G_2A_2 where A_i are the affine transformations from AGL_n(Z_{2^s}) preserving the variety (Z*_{2^s)}^n , Eulerian endomorphism G_i , i=1,2 of K[x_1, x_2,...., x_n] moves x_i to monomial term ϻ(x_1)^{d(1)}(x_2)^{d(2)}...(x_n)^{d(n)} , ϻϵ Z*_{2^s} and act on (Z*_{2^s})^n as bijective transformations. The cipher is...

Symmetric cryptography primitives are constructed by iterative applications of linear and nonlinear layers. Constructing efficient circuits for these layers, even for the linear one, is challenging. In 1997, Paar proposed a heuristic to minimize the number of XORs (modulo 2 addition) necessary to implement linear layers. In this study, we slightly modify Paar’s heuristics to find implementations for nonlinear Boolean functions, in particular to homogeneous Boolean functions. Additionally, we...

New ideas to build homomorphic encryption schemes based on rational functions have been recently proposed. The starting point is a private-key encryption scheme whose secret key is a rational function $\phi/\phi'$. By construction, such a scheme is not homomorphic. To get homomorphic properties, nonlinear homomorphic operators are derived from the secret key. In this paper, we adopt the same approach to build HE. We obtain a multivariate encryption scheme in the sense that the knowledge of...

We present a new construction of cryptographically significant Boolean functions defined over a large number of variables, with an emphasis on efficient circuit realizability. Our method is based on a variant of the well-known Maiorana-McFarland (MM) construction, adapted to enable circuit structures with less than $6n$ gates on the number of input bits $n$. We evaluate the circuit efficiency in terms of the total number of logic gates (for example AND, OR, NOT, and XOR, each with a maximum...

Private computation of nonlinear functions, such as Rectified Linear Units (ReLUs) and max-pooling operations, in deep neural networks (DNNs) poses significant challenges in terms of storage, bandwidth, and time consumption. To address these challenges, there has been a growing interest in utilizing privacy-preserving techniques that leverage polynomial activation functions and kernelized convolutions as alternatives to traditional ReLUs. However, these alternative approaches often suffer...

In this work we introduce algebraic transition matrices as the basis for a new approach to integral cryptanalysis that unifies monomial trails (Hu et al., Asiacrypt 2020) and parity sets (Boura and Canteaut, Crypto 2016). Algebraic transition matrices allow for the computation of the algebraic normal form of a primitive based on the algebraic normal forms of its components by means of well-understood operations from linear algebra. The theory of algebraic transition matrices leads to better...

The advent of transformers has brought about significant advancements in traditional machine learning tasks. However, their pervasive deployment has raised concerns about the potential leakage of sensitive information during inference. Existing approaches using secure multiparty computation (MPC) face limitations when applied to transformers due to the extensive model size and resource-intensive matrix-matrix multiplications. In this paper, we present BOLT, a privacy-preserving inference...

Nonlinear feedback shift registers (NFSRs) are used in many stream ciphers as their main building blocks. One security criterion for the design of a stream cipher is to assure its keystream has a long period. To meet this criterion, the NFSR used in a stream cipher must have a long state cycle. Further, to simultaneously avoid equivalent keys, the keystream's period is not compressed compared to the NFSR's state cycle length, which can be guaranteed if the NFSR is observable in the sense...

Fully homomorphic encryption (FHE) is an advanced cryptography technique to allow computations (i.e., addition and multiplication) over encrypted data. After years of effort, the performance of FHE has been significantly improved and it has moved from theory to practice. The transciphering framework is another important technique in FHE to address the issue of ciphertext expansion and reduce the client-side computational overhead. To apply the transciphering framework to the CKKS FHE scheme,...

The LowMC family of SPN block cipher proposed by Albrecht et al. was designed specifically for MPC-/FHE-/ZKP-friendly use cases. It is especially used as the underlying block cipher of PICNIC, one of the alternate third-round candidate digital signature algorithms for NIST post-quantum cryptography standardization. The security of PICNIC is highly related to the difficulty of recovering the secret key of LowMC from a given plaintext/ciphertext pair, which raises new challenges for security...

Weightwise degree-d functions are Boolean functions that take the values of a function of degree at most d on each set of fixed Hamming weight. The class of weightwise affine functions encompasses both the symmetric functions and the Hidden Weight Bit Function (HWBF). The good cryptographic properties of the HWBF, except for the nonlinearity, motivates to investigate a larger class with functions that share the good properties and have a better nonlinearity. Additionally, the homomorphic...

Elisabeth-4 is a stream cipher tailored for usage in hybrid homomorphic encryption applications that has been introduced by Cosseron et al. at ASIACRYPT 2022. In this paper, we present several variants of a key-recovery attack on the full Elisabeth-4 that break the 128-bit security claim of that cipher. Our most optimized attack is a chosen-IV attack with a time complexity of $2^{88}$ elementary operations, a memory complexity of $2^{54}$ bits and a data complexity of $2^{41}$ bits. Our...

Recently, the FinTracer algorithm was introduced as a versatile framework for detecting economic crime typologies in a privacy-preserving fashion. Under the hood, FinTracer stores its data in a structure known as the ``FinTracer tag’’. One limitation of FinTracer tags, however, is that because their underlying cryptographic implementation relies on additive semi-homomorphic encryption, all the system's oblivious computations on tag data are linear in their input ciphertexts. This allows a...

Designing novel symmetric-key primitives for advanced protocols like secure multiparty computation (MPC), fully homomorphic encryption (FHE) and zero-knowledge proof systems (ZK), has been an important research topic in recent years. Many such existing primitives adopt quite different design strategies from conventional block ciphers. Notable features include that many of these ciphers are defined over a large finite field, and that a power map is commonly used to construct the nonlinear...

We investigate the concept of $\mathcal{S}_0$-equivalent class, $n$-variable Boolean functions up to the addition of a symmetric function null in $0_n$ and $1_n$, as a tool to study weightwise perfectly balanced functions. On the one hand we show that weightwise properties, such as being weightwise perfectly balanced, the weightwise nonlinearity and weightwise algebraic immunity, are invariants of these classes. On the other hand we analyze the variation of global parameters inside the...

Hash functions are a crucial component in incrementally verifiable computation (IVC) protocols and applications. Among those, recursive SNARKs and folding schemes require hash functions to be both fast in native CPU computations and compact in algebraic descriptions (constraints). However, neither SHA-2/3 nor newer algebraic constructions, such as Poseidon, achieve both requirements. In this work we overcome this problem in several steps. First, for certain prime field domains we propose a...

The substitution box (S-box) is an important nonlinear component in most symmetric cryptosystems and thus should have good properties. Its difference distribution table (DDT) and linear approximation table (LAT) affect the security of the cipher against differential and linear cryptanalysis. In most previous work, differential uniformity and linearity of an S-box are two primary cryptographic properties to impact the resistance against differential and linear attacks. In some cases, the...

This note shows that there exists a nontrivial invariant for the unkeyed round function of QARMAv2-64. It is invariant under translation by a set of $2^{32}$ constants. The invariant does not extend over all rounds of QARMAv2-64 and probably does not lead to full-round attacks. Nevertheless, it might be of interest as it can be expected to give meaningful weak-key attacks on round-reduced instances when combined with other techniques such as integral cryptanalysis.

Given three positive integers $n<N$ and $M$, we study those vectorial Boolean $(N,M)$-functions $\mathcal{F}$ which map an $n$-dimensional affine space $A$ into an $m$-dimensional affine space where $m<M$ and possibly $m=n$. This provides $(n,m)$-functions $\mathcal{F}_A$ as restrictions of $\mathcal{F}$. We show that the nonlinearity of $\mathcal{F}$ must not be too large for allowing this, and we observe that if it is zero, then it is always possible. In this case, we show that the...

Masking is considered to be an essential defense mechanism against side-channel attacks, but it is challenging to be adopted for hardware cryptographic implementations, especially for high security orders. Recently, Knichel et al. proposed an automated tool called AGEMA that enables the generation of masked implementations in hardware for arbitrary security orders using composable gadgets. This accelerates the construction and practical application of masking schemes. This article proposes a...

Designing symmetric-key primitives for applications in Fully Homomorphic Encryption (FHE) has become important to address the issue of the ciphertext expansion. In such a context, cryptographic primitives with a low-AND-depth decryption circuit are desired. Consequently, quadratic nonlinear functions are commonly used in these primitives, including the well-known $\chi$ function over $\mathbb{F}_2^n$ and the power map over a large finite field $\mathbb{F}_{p^n}$. In this work, we study the...

The construction of invertible non-linear layers over $\mathbb F_p^n$ that minimize the multiplicative cost is crucial for the design of symmetric primitives targeting Multi Party Computation (MPC), Zero-Knowledge proofs (ZK), and Fully Homomorphic Encryption (FHE). At the current state of the art, only few non-linear functions are known to be invertible over $\mathbb F_p$, as the power maps $x\mapsto x^d$ for $\gcd(d,p-1)=1$. When working over $\mathbb F_p^n$ for $n\ge2$, a possible way to...

Fully Homomorphic Encryption (FHE) is a cryptographic method that guarantees the privacy and security of user data during computation. FHE algorithms can perform unlimited arithmetic computations directly on encrypted data without decrypting it. Thus, even when processed by untrusted systems, confidential data is never exposed. In this work, we develop new techniques for accelerated encrypted execution and demonstrate the significant performance advantages of our approach. Our current focus...

The graphs ${\cal G}_F=\{(x,F(x)); x\in \mathbb{F}_2^n\}$ of those $(n,n)$-functions $F:\mathbb{F}_2^n\mapsto \mathbb{F}_2^n$ that are almost perfect nonlinear (in brief, APN; an important notion in symmetric cryptography) are, equivalently to their original definition by K. Nyberg, those Sidon sets (an important notion in combinatorics) $S$ in $({\Bbb F}_2^n\times {\Bbb F}_2^n,+)$ such that, for every $x\in {\Bbb F}_2^n$, there exists a unique $y\in {\Bbb F}_2^n$ such that $(x,y)\in S$....

In this article we study the Algebraic Immunity (AI) of Weightwise Perfectly Balanced (WPB) functions. After showing a lower bound on the AI of two classes of WPB functions from the previous literature, we prove that the minimal AI of a WPB $n$-variables function is constant, equal to $2$ for $n\ge 4$ . Then, we compute the distribution of the AI of WPB function in $4$ variables, and estimate the one in $8$ and $16$ variables. For these values of $n$ we observe that a large majority of...

At Eurocrypt 2016, Méaux et al. presented FLIP, a new family of stream ciphers {that aimed to enhance the efficiency of homomorphic encryption frameworks. Motivated by FLIP, recent research has focused on the study of Boolean functions with good cryptographic properties when restricted to subsets of the space $\mathbb{F}_2^n$. If an $n$-variable Boolean function has the property of balancedness when restricted to each set of vectors with fixed Hamming weight between $1$ and $n-1$, it is a ...

Over the years, a large number of attacks have been proposed against substitution boxes used in symmetric ciphers such as differential attacks, linear attacks, algebraic attacks, etc. In the Advanced Encryption Standard (AES) Block cipher, the substitution box is the only nonlinear component and thus it holds the weight of the cipher. This basically means that if an attacker is able to mount a successful attack on the substitution box of AES, the cipher is compromised. This research work...

In this paper we propose Differential Fault Attack (DFA) on two Fully Homomorphic Encryption (FHE) friendly stream ciphers Rasta and $\text {FiLIP} _ {\text {DSM}} $. Design criteria of Rasta rely on affine layers and nonlinear layers, whereas $\text {FiLIP} _ {\text {DSM}} $ relies on permutations and a nonlinear fil- ter function. Here we show that the secret key of these two ciphers can be recovered by injecting only 1 bit fault in the initial state. Our DFA on full round (# rounds = 6)...

In this article we realize a general study on the nonlinearity of weightwise perfectly balanced (WPB) functions. First, we derive upper and lower bounds on the nonlinearity from this class of functions for all $n$. Then, we give a general construction that allows us to provably provide WPB functions with nonlinearity as low as $2^{n/2-1}$ and WPB functions with high nonlinearity, at least $2^{n-1}-2^{n/2}$. We provide concrete examples in $8$ and $16$ variables with high nonlinearity given...

Cryptanalysts have been looking for differential characteristics in ciphers for decades and it remains unclear how the subkey values and more generally the Markov assumption impacts exactly their probability estimation. There were theoretical efforts considering some simple linear relationships between differential characteristics and subkey values, but the community has not yet explored many possible nonlinear dependencies one can find in differential characteristics. Meanwhile, the...

In data-intensive private computing applications various relations appear as or can be reduced to matrix relations. In this paper we investigate two problems related to constructing the zero-knowledge argument (ZKA) protocols for matrix relations (in commit-and-prove paradigm). In the first part, we establish the ZKA for some bilinear matrix relations over Fp. The relations in consideration include (1) general forms of bilinear relations with two witness matrices and some most important...

Various systematic modifications of vectorial Boolean functions have been used for finding new previously unknown classes of S-boxes with good or even optimal differential uniformity and nonlinearity. Recently, a new method was proposed for modification a component of a bijective vectorial Boolean function by using a linear function. It was shown that the modified function remains bijective under the assumption that the inverse of the function admits a linear structure. A previously known...

Various systematic modifications of vectorial Boolean functions have been used for finding new previously unknown classes of S-boxes with good or even optimal differential uniformity and nonlinearity. In this paper, a new general modification method is given that preserves the bijectivity property of the function in case the inverse of the function admits a linear structure. A previously known construction of such a modification based on bijective Gold functions in odd dimension is a...

The cube attack is one of the most important cryptanalytic techniques against Trivium. As the method of recovering superpolies becomes more and more effective, another problem of cube attacks, i.e., how to select cubes corresponding to balanced superpolies, is attracting more and more attention. It is well-known that a balanced superpoly could be used in both theoretical and practical analyses. In this paper, we present a novel framework to search for valuable cubes whose superpolies have an...

The design of FLIP stream cipher presented at Eurocrypt $2016$ motivates the study of Boolean functions with good cryptographic criteria when restricted to subsets of $\mathbb F_2^n$. Since the security of FLIP relies on properties of functions restricted to subsets of constant Hamming weight, called slices, several studies investigate functions with good properties on the slices, i.e. weightwise properties. A major challenge is to build functions balanced on each slice, from which we get...

Recently, new ideas to build homomorphic noise-free encryption schemes have been proposed. The starting point of these schemes deals with private-key encryption schemes whose secret key is a rational function. By construction, these schemes are not homomorphic. To get homomorphic properties, nonlinear homomorphic operators are derived from the secret key. In this paper, we adopt the same approach to build a HE. We obtain a multivariate encryption scheme in the sense that the knowledge...

A *functional commitment* scheme enables a user to concisely commit to a function from a specified family, then later concisely and verifiably reveal values of the function at desired inputs. Useful special cases, which have seen applications across cryptography, include vector commitments and polynomial commitments. To date, functional commitments have been constructed (under falsifiable assumptions) only for functions that are essentially *linear*, with one recent exception that works...

The security of the post-quantum signature scheme Picnic is highly related to the difficulty of recovering the secret key of LowMC from a single plaintext-ciphertext pair. Since Picnic is one of the alternate third-round candidates in NIST post-quantum cryptography standardization process, it has become urgent and important to evaluate the security of LowMC in the Picnic setting. The best attacks on LowMC with full S-box layers used in Picnic3 were achieved with Dinur's algorithm. For LowMC...

In recent years, several MILP models were introduced to search automatically for boomerang distinguishers and boomerang attacks on block ciphers. However, they can only be used when the key schedule is linear. Here, a new model is introduced to deal with nonlinear key schedules as it is the case for AES. This model is more complex and actually it is too slow for exhaustive search. However, when some hints are added to the solver, it found the current best related-key boomerang attack on...

In this paper, we study the class of those Boolean functions that are coset leaders of first order Reed-Muller codes. We study their properties and try to better understand their structure (which seems complex), by studying operations on Boolean functions that can provide coset leaders (we show that these operations all provide coset leaders when the operands are coset leaders, and that some can even produce coset leaders without the operands being coset leaders). We characterize those...

Lightweight cryptography algorithms are increasing in value because they can enhance security under limited resources. National Institute of Standards and Technology is working on standardising lightweight authenticated encryption with associated data. Thirty-two candidates are included in the second round of the NIST selection process, and their specifications differ with respect to various points. Therefore, for each algorithm, the differences in specifications are expected to affect the...