The theory of compressed $\Sigma$-protocols [AC20, ACF21] provides a standardized framework for creating efficient $\Sigma$-protocols. This method involves two main phases: first, amortization, which combines multiple instances that satisfy a homomorphic relation into a single instance; and second, Bulletproofs compression [BBB+18], which minimizes communication overhead to a logarithmic scale during the verification of the combined instance. For high-degree polynomial (non-homomorphic)...

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

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

The recent technological advances in Post-Quantum Cryptography (PQC) raise the questions of robust implementations of new asymmetric cryptography primitives in today's technology. This is the case for the lattice-based Module Lattice-Key Encapsulation Mechanism (ML-KEM) algorithm which is proposed by the National Institute of Standards and Technology (NIST) as the first standard for Key Encapsulation Mechanism (KEM), taking inspiration from CRYSTALS-Kyber. We must ensure that the ML-KEM...

In this article, we propose several generic methods for constructing minimal linear codes over the field $\mathbb{F}_p$. The first construction uses the method of direct sum of an arbitrary function $f:\mathbb{F}_{p^r}\to \mathbb{F}_{p}$ and a bent function $g:\mathbb{F}_{p^s}\to \mathbb{F}_p$ to induce minimal codes with parameters $[p^{r+s}-1,r+s+1]$ and minimum distance larger than $p^r(p-1)(p^{s-1}-p^{s/2-1})$. For the first time, we provide a general construction of linear codes from a...

Existing Oblivious RAM protocols do not support the storage of data items of variable size in a non-trivial way. While the study of ORAM for items of variable size is of interest in and of itself, it is also motivated by the need for more performant and more secure Searchable Symmetric Encryption (SSE) schemes. In this article, we introduce the notion of weighted ORAM, which supports the storage of blocks of different sizes. In a standard ORAM scheme, each data block has a fixed size...

Two main secondary constructions of bent functions are the direct and indirect sum methods. We show that the direct sum, under more relaxed conditions compared to those in \cite{PolujanandPott2020}, can generate bent functions provably outside the completed Maiorana-McFarland class ($\mathcal{MM}^\#$). We also show that the indirect sum method, though imposing certain conditions on the initial bent functions, can be employed in the design of bent functions outside $\mathcal{MM}^\#$....

In this work, we define and study equivalence problems for sum-rank codes, giving their formulation in terms of tensors. Moreover, we introduce the concept of generating tensors of a sum-rank code, a direct generalization of the generating matrix for a linear code endowed with the Hamming metric. In this way, we embrace well-known definitions and problems for Hamming and rank metric codes. Finally, we prove the TI-completeness of code equivalence for rank and sum-rank codes, and hence, in...

This paper provides the first analysis of reflection ciphers such as PRINCE from a provable security viewpoint. As a first contribution, we initiate the study of key-alternating reflection ciphers in the ideal permutation model. Specifically, we prove the security of the two-round case and give matching attacks. The resulting security bound takes form \(O(qp^2/2^{2n}+q^2/2^n)\), where \(q\) is the number of construction evaluations and \(p\) is the number of direct adversarial queries to...

We present a much-improved practical protocol, based on the hardness of Module-SIS and Module-LWE problems, for proving knowledge of a short vector $s$ satisfying $As=t\bmod q$. The currently most-efficient technique for constructing such a proof works by showing that the $\ell_\infty$ norm of $s$ is small. It creates a commitment to a polynomial vector $m$ whose CRT coefficients are the coefficients of $s$ and then shows that (1) $A\cdot \mathsf{CRT}(m)=t\bmod\,q$ and (2) in the case that...

We present two tweakable wide block cipher modes from doubly-extendable cryptographic keyed (deck) functions and a keyed hash function: double-decker and docked-double-decker. Double-decker is a direct generalization of Farfalle-WBC of Bertoni et al. (ToSC 2017(4)), and is a four-round Feistel network on two arbitrarily large branches, where the middle two rounds call deck functions and the first and last rounds call the keyed hash function. Docked-double-decker is a variant of double-decker...

We improve upon the security of (tweakable) correlation-robust hash functions, which are essential components of garbling schemes and oblivious-transfer extension schemes. We in particular focus on constructions from permutations, and improve upon the work by Guo et al. (IEEE S&P '20) in terms of security and efficiency. We present a tweakable one-call construction which matches the security of the most secure two-call construction -- the resulting security bound takes form O((p+q)q/2^n),...

In this paper, we study sufficient conditions to improve the lower bound on the algebraic immunity of a direct sum of Boolean functions. We exhibit three properties on the component functions such that satisfying one of them is sufficient to ensure that the algebraic immunity of their direct sum exceeds the maximum of their algebraic immunities. These properties can be checked while computing the algebraic immunity and they allow to determine better the security provided by functions central...

The notion of almost perfect nonlinear (APN) function is important, mathematically and cryptographically. Much still needs to be understood on the structure and the properties of APN functions. For instance, finding an APN permutation in an even number of variables larger than 6 would be an important theoretical and practical advance. A way to progress on a notion is to introduce and study generalizations making sense from both theoretical and practical points of view. The introduction and ...

Minimal codes are characterized by the property that none of the codewords is covered by some other linearly independent codeword. We first show that the use of a bent function $g$ in the so-called direct sum of Boolean functions $h(x,y)=f(x)+g(y)$, where $f$ is arbitrary, induces minimal codes. This approach gives an infinite class of minimal codes of length $2^n$ and dimension $n+1$ (assuming that $h: \F_2^n \rightarrow \F_2$), whose weight distribution is exactly specified for certain...

Improved filter permutators are designed to build stream ciphers that can be efficiently evaluated homomorphically. So far the transciphering with such ciphers has been implemented with homomorphic schemes from the second generation. In theory the third generation is more adapted for the particular design of these ciphers. In this article we study how suitable it is in practice. We implement the transciphering of different instances of the stream cipher family FiLIP with homomorphic...

Physical Unclonable Functions (PUFs) are used in various key-generation schemes and protocols. Such schemes are deemed to be secure even for PUFs with challenge-response behavior, as long as no responses and no reliability information about the PUF are exposed. This work, however, reveals a pitfall in these constructions: When using state-of-the-art helper data algorithms to correct noisy PUF responses, an attacker can exploit the publicly accessible helper data and challenges. We show that...

Internet of Things is developing at a very fast rate. In order to ensure security and privacy, end-devices (e.g. smartphones, smart sensors, or any connected smartcards) shall be protected both against cyber attacks (coming down from the network) and against physical attacks (arising from attacker low-level interaction with the device). In this context, proactive protections shall be put in place to mitigate information theft from either side-channel monitoring or active computation/data...

In ICISC-05, and in the ePrint $2010/287$, Patarin claimed a lower bound on the number of $2q$ tuples of $n$-bit strings $(P_1, \ldots, P_{2q}) \in (\{0,1\}^{n})^{2q}$ satisfying $P_{2i - 1} \oplus P_{2i} = \lambda_i$ for $1 \leq i \leq q$ such that $P_1, P_2, \ldots$, $P_{2q}$ are distinct and $\lambda_i \in \{0,1\}^n \setminus \{0^n\}$. This result is known as {\em Mirror theory} and widely used in cryptography. It stands as a powerful tool to provide a high-security guarantee for many...

We propose two polynomial memory collision finding algorithms for the low Hamming weight discrete logarithm problem in any abelian group $G$. The first one is a direct adaptation of the Becker-Coron-Joux (BCJ) algorithm for subset sum to the discrete logarithm setting. The second one significantly improves on this adaptation for all possible weights using a more involved application of the representation technique together with some new Markov chain analysis. In contrast to other low weight...

We give Proofs of Work (PoWs) whose hardness is based on well-studied worst-case assumptions from fine-grained complexity theory. This extends the work of (Ball et al., STOC '17), that presents PoWs that are based on the Orthogonal Vectors, 3SUM, and All-Pairs Shortest Path problems. These, however, were presented as a `proof of concept' of provably secure PoWs and did not fully meet the requirements of a conventional PoW: namely, it was not shown that multiple proofs could not be generated...

This note was originally written under the name ``On the Security of HMFEv'' and was submitted to PQCrypto 2018. The author was informed by the referees of his oversight of an eprint work of the same name by Hashimoto, see eprint article /2017/689/, that completely breaks HMFEv, rendering the result on HMFEv obsolete. Still, the author feels that the technique used here is interesting and that, at least in principal, this method could contribute to future cryptanalysis. Thus, with a...

Side Channel Attacks (SCA) and Fault Injection Attacks (FIA) allow an opponent to have partial access to the internal behavior of the hardware. Since the end of the nineties, many works have shown that this type of attacks constitute a serious threat to cryptosystems implemented in embedded devices. In the state of the art, there exist several countermeasures to protect symmetric encryption (especially AES-128). Most of them protect only against one of these two attacks (SCA or FIA). A...

In this paper, we analyze the security of round-reduced versions of the Keccak hash function family. Based on the work pioneered by Aumasson and Meier, and Dinur et al., we formalize and develop a technique named linear structure, which allows linearization of the underlying permutation of Keccak for up to 3 rounds with large number of variable spaces. As a direct application, it extends the best zero-sum distinguishers by 2 rounds without increasing the complexities. We also apply linear...

At EUROCRYPT 2015, Todo proposed the division property. Since then, many researches about the division property had occurred in succession. Inspired by the bit-based division property on SIMON introduced by Todo and Morri at FSE 2016, we give a further understanding of bit-based division property and come up with a new method to reconsider the \textbf{Substitution} rule given by Todo. By integrating the method of division property with the concrete boolean function expressions of S-box, this...

In this paper, we study the Learning With Errors problem and its binary variant, where secrets and errors are binary or taken in a small interval. We introduce a new variant of the Blum, Kalai and Wasserman algorithm, relying on a quantization step that generalizes and fine-tunes modulus switching. In general this new technique yields a significant gain in the constant in front of the exponent in the overall complexity. We illustrate this by solving p within half a day a LWE instance with...

Secure elements, such as smartcards or trusted platform modules (TPMs), must be protected against implementation-level attacks. Those include side-channel and fault injection attacks. We introduce ODSM, Orthogonal Direct Sum Masking, a new computation paradigm that achieves protection against those two kinds of attacks. A large vector space is structured as two supplementary orthogonal subspaces. One subspace (called a code $\mathcal{C}$) is used for the functional computation, while the...

In the setting of cryptographic protocols, the corruption of a party has traditionally been viewed as a simple, uniform and atomic operation, where the adversary decides to get control over a party and this party immediately gets corrupted. In this paper, motivated by the fact that different players may require different resources to get corrupted, we put forth the notion of {\em resource-based corruptions}, where the adversary must invest some resources in order to do so. If the adversary...

In this paper, we construct generalized bent Boolean functions in $n+ 2$ variables from $4$ generalized Boolean functions in $n$ variables. We also show that the direct sum of two generalized bent Boolean functions is generalized bent. Finally, we identify a set of affine functions in which every function is generalized bent.

A leakage resilient encryption scheme is one which stays secure even against an attacker that obtains a bounded amount of side information on the secret key (say $\lambda$ bits of ``leakage''). A fundamental question is whether parallel repetition amplifies leakage resilience. Namely, if we secret share our message, and encrypt the shares under two independent keys, will the resulting scheme be resilient to $2\lambda$ bits of leakage? Surprisingly, Lewko and Waters (FOCS 2010) showed that...

We propose a semantically-secure public-key encryption scheme whose security is polynomial-time equivalent to the hardness of solving random instances of the subset sum problem. The subset sum assumption required for the security of our scheme is weaker than that of existing subset-sum based encryption schemes, namely the lattice-based schemes of Ajtai and Dwork (STOC '97), Regev (STOC '03, STOC '05), and Peikert (STOC '09). Additionally, our proof of security is simple and direct. We also...

This paper considers the construction and analysis of pseudo-random functions (PRFs) with specific reference to modes of operations of a block cipher. In the context of message authentication codes (MACs), earlier independent work by Bernstein and Vaudenay show how to reduce the analysis of relevant PRFs to some probability calculations. In the first part of the paper, we revisit this result and use it to prove a general result on constructions which use a PRF with a ``small'' domain to...

We consider the construction and analysis of pseudorandom functions (PRF) for message authentication. Earlier work due to Bernstein and Vaudenay show how to reduce the analysis of PRFs to some probability calculations. We revisit this result and use it to prove some general results on constructions which use a PRF with ``small'' domain to build a PRF with ``large'' domain. These results are then used to analyse several existing and new constructions. Important among them is a...

Prof. Claude Carlet has pointed out an error in Theorem 1 of the paper. The error could not be recovered for the time being. Thus the statement presented in the title of the paper is not proved.

We give the first simple and efficient construction of {\em verifiable random functions} (VRFs). VRFs, introduced by Micali et al. [MRV99], combine the properties of regular pseudorandom functions (PRFs) [GGM86] (i.e., indistinguishability from a random function) and digital signatures [GMR88] (i.e., one can provide an unforgeable proof that the VRF\ value is correctly computed). The efficiency of our VRF construction is only slightly worse than that of a regular PRF construction of Naor and...