A central challenge in quantum algorithm analysis and cryptography is reasoning about algorithms with oracle access to a random group element (e.g. a random function, a random permutation, a random unitary). Can we efficiently simulate such algorithms? Can we determine what they know after $t$ queries? Classically, an important tool for this is lazy sampling, where the oracle does not commit to the full group element at the beginning, but rather samples partial information about it on the...

Design of hash functions and pseudo-random permutations over Galois extensions of $\mathbb Z_q$ for prime powers $q$ has recently gained some interest in relation to recent directions in advanced cryptography, such as multiparty computation and zero-knowledge protocol design. Thus investigating optimality of cryptographic properties of S-boxes defined by polynomials over Galois rings is of interest. Of particular interest is the differential uniformity of such functions. To our knowledge,...

For many applications of SNARKs, a key bottleneck is proving large batches of standard cryptographic hash evaluations, such as SHA-256, Keccak, or BLAKE3. We introduce Flock, a hash-based SNARK for extremely fast proving of such batched Boolean computations. Flock proves batches of the same R1CS circuit (plus input/output relations between them), can prove hash-chains and Merkle path openings, and in principle can be extended to full-fledged hash-based signature verification. At its core,...

The increasing usage of Zero-knowledge proof protocols has raised the need for cryptographic primitives that are efficient in that setting, called Arithmetization-oriented primitives. The security of such permutations is commonly evaluated with the CICO-$k$ problem. The best known CICO-$1$ attack against ZK-Friendly permutations over $\mathbb{F}_q^t$ based on $\alpha$-inversions $x\mapsto x^{1/\alpha}$ exploits resultants (ASIACRYPT 2024, CRYPTO 2025). It starts from one input variable $x$...

Distributed shuffling is a core primitive underlying mix-nets, electronic voting, and, more recently, single secret leader election (SSLE) protocols for proof-of-stake blockchains. In these settings, a collection of resource-constrained parties jointly permutes a list of ciphertexts or commitments in order to conceal the correspondence between inputs and outputs. Existing security analyzes of such protocols typically rely on heuristic anonymity measures or implicitly assume honest behavior;...

Poseidon is one of the most widely deployed arithmetization-oriented cryptographic permutations and plays a central role in modern zero-knowledge proof systems. Although several algebraic attacks on reduced-round variants have been proposed, the security of the recommended parameter sets remains intact. A central difficulty in such attacks is controlling the degree growth of the polynomial representations induced by the permutation. In this work, we introduce degree annihilation, a new...

Advances in quantum computing technology have motivated the development of post-quantum cryptography (PQC) algorithms. HAWK is a new post-quantum digital signature scheme and the only lattice-based candidate selected for Round 3 of the "Additional Digital Signatures" phase of the NIST PQC Standardization process. HAWK offers compact key and signature sizes compared to NIST standard ML-DSA (Dilithium), and its simple design avoids the use of floating-point arithmetic unlike NIST standard...

A fully shuffled permutation of four cards suffices to implement 1-of-2 Oblivious Transfer at a rate of one transfer per shuffle. After dealing two cards to Alice and one to Bob, Alice deterministically selects item from a threefold partition of the edges of a tetrahedron, at which point OT is established. Unlike decades of 2-player computation results employing restricted permutations (as in den Boer's groundbreaking Five Card Trick) and artificial decks with repeated symbols, the...

Linearization is a cryptanalysis technique in which a nonlinear function (an S-box) is represented by an affine mapping on a certain subset of inputs. Its variants were applied to analyze Keccak, LowMC, RAIN and AIM. In these primitives, the S-boxes are either very small (up to 5 bits) or are very specific monomial functions over a binary field. Linearization of arbitrary S-boxes was never practically explored due to the lack of theoretic, algorithmic, and cryptanalytic understanding. ...

Substitution-permutation networks (SPNs) are the most popular construction method for block ciphers and sponge permutations. Basically, we can divide SPNs into two groups by considering their diffusion layer profiles: bit-wise versus byte-wise (or nibble-wise) diffusion. In this paper, we suitably combine both approaches and present a more efficient and flexible construction that achieves a combination of small S-boxes, linear layers consisting only of XOR operations and bit permutations,...

We introduce MERIDIAN, a 128-bit block cipher designed for resource-constrained environments as a lightweight alternative to AES-128. MERIDIAN retains the AES-128 interface, including a 128-bit block, 128-bit key, and 4×4 byte state, while reusing the standard AES S-box. This enables compatibility with existing AES-128 modes such as ECB, CBC, CFB, OFB, CTR, XTS, CMAC, CCM, and GCM, and allows implementations to reuse established S-box ROMs and GF(28) inverse circuits. The cipher is based on...

We present CLAASP-MP, a monomial prediction (MP) tool based on the three-subset division property without unknown subset (3SDP-woU), integrated into CLAASP, a library for automated analysis of symmetric key cryptographic primitives. The propagation rules of 3SDP-woU are encoded as a Mixed Integer Linear Programming (MILP) model generated directly from the CLAASP component graph, covering the main building blocks used in modern symmetric designs, including S-boxes, linear layers, Boolean word...

Designing cryptographic hash functions that simultaneously achieve high throughput and strong provable security remains a fundamental challenge in symmetric cryptography. Traditional constructions, such as the Merkle-Damg\aa rd (MD) and SPONGE paradigms, inherently suffer from structural limitations: they either expose internal chaining values to length-extension attacks or impose a rigid trade-off between security (capacity) and efficiency (rate), bounding their architectural...

We propose the \emph{Alternating Sponge} (ASP), a permutation-based hashing mode that explores how to obtain beyond-birthday-bound security without duplicating the full capacity state. The main design idea is to replace spatial state duplication by temporal alternation: ASP keeps two \(r\)-bit rate branches but lets them share a single \(c\)-bit capacity chain, and updates the two branches through alternating calls to two independent \((r+c)\)-bit permutations. This yields a state size of...

In this paper we study the cryptographic complexity of non-trivial witness-indistinguishable (WI) arguments of knowledge. We establish that: - Assuming that $NP\not\subseteq P/poly$, the existence of a constant-round computational WI argument of knowledge for $NP$ implies that (infinitely-often) auxiliary-input one-way functions exist. - Assuming that $ NP\nsubseteq P^{Sam}/poly$, there is no black-box construction of a constant-round (unbounded-verifier) statistical WI argument of...

Randomly permuting secret data vectors is a core building block in many privacy-preserving protocols, including those for analytics, advertising, and communication. Existing approaches either rely on computation-heavy public key cryptography and zero-knowledge proofs or scale poorly for large vectors due to use of a quasilinear-sized permutation network. This work presents a preprocessing approach to enable fast linear-time online shuffles in the malicious-secure two-party computation (2PC)...

In this paper, we propose Dialga, a family of low-latency tweakable block ciphers designed to support 128/256-bit tweaks and 256-bit keys. Dialga achieves significantly small latency by leveraging multiple novel strategies. These include the use of multiple linear layers with efficient cell permutations, which enhance security against differential and linear attacks with negligible hardware overhead. We also identify the optimal choice of S-boxes for these permutations using state-of-the-art...

The rapid advancement of quantum computing poses significant challenges to the security of existing cryptographic constructions. Several constructions that are provably secure in the classical setting, e.g., the $3$-round Luby–Rackoff, Even–Mansour, Keyed Sum of Permutations, become vulnerable when the adversary is granted quantum oracle access (the Q2 model). In contrast, when the adversary is restricted to classical oracle queries while retaining the ability to perform quantum computations...

We introduce CRISP (\underline{C}ircuit-p\underline{R}ivate Single-\underline{I}mage \underline{S}teganog\\raphy with \underline{P}ermutations), a provably secure homomorphic steganography scheme that addresses key limitations in existing approaches to private outsourced computation. CRISP operates under an explicit threat model: the cloud provider knows steganography is in use, knows the scheme, and knows the channel-assignment permutations; the only secret is the per-execution pixel...

Poseidon[GKR+19 ] and its successor Poseidon2[GKS23] are arithmetization-oriented permutations proposed for hashing inside algebraic proof systems. While there is extensive prior work on cryptanalysis of reduced-round Poseidon/Poseidon2 and theoretical and practical weaknesses of the Fiat-Shamir transform, these two attacks are typically studied in isolation. This work asks whether combining them i.e., instantiating Fiat-Shamir with Poseidon can enable new attacks. We design and...

Current industry-standard block cipher modes of operation, such as CBC and GCM, are fundamentally limited by the birthday bound $O(2^{n/2})$, a constraint that has evolved from a theoretical concern into a practical security bottleneck in contemporary high-throughput, high-data-volume environments. To address this, the cryptographic community and NIST are prioritizing Beyond Birthday Bound (BBB) security to extend the operational security margin toward the full block size $O(2^n)$. Achieving...

A vast body of work studies how to build a pseudorandom function (PRF) from a pseudorandom permutation (PRP) with beyond-the-birthday-bound (BBB) security. Often, such constructions are also expected to offer some security in keyless settings, for example in the context of committing security or to substitute a parallelizable short-input random oracle (RO) if used in counter mode. This has spurred several works on keyless variants of PRP-to-PRF constructions. However, recent works (Gunsing...

We present multi-query attacks on key-then-hash (KTH) functions in the blinded keyed hash model that achieve an advantage growing quadratically in the number of queries up to a small constant factor from the information-theoretic upper bound. We introduce three families of attacks. Catch attacks exploit the group structure of the digest space and achieve deterministic success with $2\sqrt{\varepsilon^{-1}}$ queries. Group attacks embed high-probability differentials into subgroups of the...

We present the first general upper bound on permutation-based pseudorandom functions in the information-theoretic setting. We show that any non-compressing PRF, with input and output domain at least \([N]\), making \(t\) black-box calls to any \(t\) public permutations on \([N]\), can be distinguished from a random function over the output domain with at most \(\widetilde{O}\big(N^{t/(t+1)}\big)\) total queries to the PRF and the permutations. Our results suggest that the designs of Chen et...

Compressing correlated randomness is a key component of secure computation protocols in the silent preprocessing model and has received significant attention in recent years. However, to date, all known constructions are restricted to generating additive correlations, where the parties receive additive shares of a relation. The only known exceptions are constructions from indistinguishability obfuscation. In this work, we initiate the study of compressing useful forms of correlated...

The mapping $\chi_n$ from $\mathbb{F}_{2}^{n}$ to itself defined by $y=\chi_n(x)$ with $y_i=x_i+x_{i+2}(1+x_{i+1})$, where the indices are computed modulo $n$, has been widely studied for its applications in lightweight cryptography. However, $\chi_n $ is bijective on $\mathbb{F}_2^n$ only when $n$ is odd, restricting its use to odd-dimensional vector spaces over $\mathbb{F}_2$. To address this limitation, we introduce and analyze the generalized mapping $\chi_{n, m}$ defined by...

In recent years, neural network extraction has been studied with cryptographic techniques, since Carlini et al.'s pioneering work proposed at CRYPTO 2020. Most research has focused on simple fully connected network (FCN) models, with limited attention given to more complicated recurrent neural network (RNN) models. However, RNN models are dominant in fields such as natural language processing and speech recognition. Exploring the vulnerability of RNN models to extraction attacks is not only...

Homomorphic Encryption (HE) provides strong data privacy for cloud services but at the cost of prohibitive computational overhead. While GPUs have emerged as a practical platform for accelerating HE, there remains an order-of-magnitude energy-efficiency gap compared to specialized (but expensive) HE ASICs. This paper explores an alternate direction: leveraging existing AI accelerators, like Google's TPUs with coarse-grained compute and memory architectures, to offer a path toward ASIC-level...

This paper presents a unified framework for generic attacks on Generalized Feistel Ciphers, with a primary focus on Type 1, Type 2, and unbalanced contracting (U-Type 1) Feistel constructions with non-invertible round functions. In recent work, authors reveal a class of vulnerabilities exploitable via key independent multidimensional linear trails for Feistel Ciphers, yielding efficient generic distinguishing and key-recovery attacks. We extend the extended work by formalizing the...

The construction of building beyond-birthday-bound secure pseudorandom functions (PRFs) from the Xor-sum of 2 pseudorandom permutations (PRPs) has been known since EUROCRYPT 1998. However, the first concrete instance was only published recently at FSE 2022: the low-latency PRF Orthros. Subsequently, at ASIACRYPT 2024, Flórez-Gutiérrez et al. proposed the general framework of ZIP ciphers, where a block cipher $E_{1} \circ E_{0}$ is used to construct the PRF $E_{0} \oplus E_{1}^{-1}$. They...

Over the past two decades, several works have used (almost) $k$-wise independence as a proxy for pseudorandomness in block ciphers, since it guarantees resistance against broad classes of statistical attacks. For example, even the case $k = 2$ already implies security against differential and linear cryptanalysis. Hoory, Magen, Myers, and Rackoff (ICALP ’04; TCS ’05) formulated an appealing conjecture: if the sequential composition of $T$ independent local randomized permutations is...

The Sum of Even-Mansour (SoEM) construction, introduced at Crypto 2019, implements a pseudorandom function via the XOR sum of independent Even-Mansour structures and serves as the core design for symmetric schemes like CENCPP* and nEHTm. This paper establishes the tight post-quantum security of the single-key, two-permutation variant, SoEM21, under the Q1 adversarial model. We prove that when an adversary makes classical queries to the keyed construction and quantum superposition queries...

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

Key-dependent attacks are effective only for specific weak-key classes, limiting their practical impact. We present a generic statistical framework that combines multiple key-dependent distinguishers into universal attacks covering the full key space. Using log-likelihood ratio statistics, our framework tests the secret key against multiple weak-key distinguishers, aggregates their evidence to determine whether the key is weak or strong for each distinguisher, and exploits this...

Permutation and multiset checks underpin many SNARKs, yet existing techniques either incur superlinear prover time or rely on auxiliary commitments with soundness error that grows linearly in the input size. We present new arguments with linear-time provers and logarithmic soundness, without auxiliary commitments. Prior work achieving logarithmic soundness error arithmetizes the permutation as a product of several multilinear polynomials, a formulation chosen for compatibility with the...

Over the past decades, extensive research has been conducted on lightweight cryptographic primitives. The linear layer plays an important role in their security. In this paper, we propose a family of linear layers consisting of XORs and rotations, which is called multiple rows mixers (MRM). It is a family designed for LS-type ciphers, but mixing elements from several rows. We investigate the impact of the linear layers on the 3-round trail weight of permutations and explore the properties...

Private Simultaneous Messages (PSM) and Conditional Disclosure of Secrets (CDS) are two fundamental primitives in information-theoretic cryptography. In a PSM protocol, each party sends a single message to a referee, who can then compute a function $f$ of their private inputs but learns nothing else. A CDS protocol follows the same model as PSM, but the goal is to disclose a secret shared among all parties to the referee if and only if the function $f$ evaluates to $1$. Minimizing the...

Poseidon and Poseidon2 are cryptographic hash functions crafted for efficient zero-knowledge proof systems and have seen wide adoption in practical applications. We introduce the use of the Graeffe transform in univariate polynomial solving within this line of work. The proposed method streamlines the root recovery process in interpolation attacks and achieves several orders of magnitude acceleration in practical settings, enabling a new and more efficient class of attacks against Poseidon...

Mental Poker enables two players to play card games at a distance without having a physical deck of cards at hand, as long as they have reliable trapdoor permutations or access to Oblivious Transfer (OT). OT itself can be stored and extended using just a one-way function. We examine whether Mental Poker can be extended from initial hands of ordinary physical poker. On the theoretical side, this work establishes OT amplification/extraction as a cryptographic primitive using...

Let $1$ be the all-one vector and $\odot$ denote the component-wise multiplication of two vectors in $\mathbb F_2^n$. We study the vector space $\Gamma_n$ over $\mathbb F_2$ generated by the functions $\gamma_{2k}:\mathbb F_2^n \to \mathbb F_2^n, k\geq 0$, where $$ \gamma_{2k} = S^{2k}\odot(1+S^{2k-1})\odot(1+S^{2k-3})\odot\ldots\odot(1+S) $$ and $S:\mathbb F_2^n\to\mathbb F_2^n$ is the cyclic left shift function. The functions in $\Gamma_n$ are shift-invariant and the well known $\chi$...

Keccak, the hash function at the core of the Ethereum ecosystem, is computationally expensive to reason about in SNARK circuits, creating a critical bottleneck in the ability of the ZK ecosystem to reason about blockchain state. The recent state-of-the-art in proving Keccak permutations relies on proof systems that can perform lookup arguments, which—while exhibiting better performance than directly proving the hash operations in circuit—still typically require tens of thousands of...

Designing practically secure masked circuits remains a central problem in the field of cryptographic implementation. While most masking schemes have been proven secure in the classical probing model, this model fails to capture more advanced side-channel attacks such as horizontal attacks. In recent years, the community has shifted toward the more realistic random probing model, which offers stronger guarantees. Yet, balancing strong security with practical efficiency continues to be a...

The analysis of quantum algorithms which query random, invertible permutations has been a long-standing challenge in cryptography. Many techniques which apply to random oracles fail, or are not known to generalize to this setting. As a result, foundational cryptographic constructions involving permutations often lack quantum security proofs. With the aim of closing this gap, we develop and prove soundness of a compressed permutation oracle. Our construction shares many of the attractive...

The ARX structure plays a crucial role in symmetric-key primitives, with differential-linear (DL) attacks being among the most effective cryptanalysis techniques against ARX ciphers. In this paper, we present a systematic re-decomposition technique for DL distinguishers of ARX ciphers and identify for the first time the hourglass(-like) structural commonalities among optimal DL distinguishers searched out by various deduction techniques, also supported through comprehensive experiments,...

Since Kuwakado and Morii's work (ISIT 2010 & ISITA 2012), it is known that the classically secure 3-round Luby-Rackoff PRP and Even-Mansour cipher become insecure against an adversary equipped with quantum query access. However, while this query model (the so-called Q2 model) has led to many more attacks, it seems that restricting the adversary to classical query access prevents such breaks (the so-called Q1 model). Indeed, at EUROCRYPT 2022, Alagic et al. proved the Q1-security of the...

The Iterated Even-Mansour (IEM) construction was introduced by Bogdanov et al. at EUROCRYPT 2012 and can be seen as an abstraction or idealization of blockciphers like AES. IEM provides insights into the soundness of this blockcipher structure and the best possible security for any number of rounds. IEM with $r$ permutations on $n$-bit blocks is secure up to $q \approx 2^{rn/(r+1)}$ queries to the cipher and each permutation. Forkciphers, introduced at ASIACRYPT 2019 as expanding...

The notion of indifferentiability was proposed by Maurer et al. to bound the distinguishing advantage of a construction built on a public primitive, from a public random function. In Indocrypt'10, Mandal et al. have shown that the sum of two independent permutations is indifferentiable from a public random function up to $2^{2n/3}$ queries. Later in ACNS'15, Mennink and Preneel identified an analytical flaw of Mandal et al's result and revised the security bound to $2^{2n/3}/n$. In...

Construction of efficient and provably-secure (T)PRPs and (fixed/variable input-length) PRFs has been one of the central open problem in modern symmetric-key cryptography. Many Feistel-based constructions has been proposed and analysed to solve this problem. Inspired by some recent works, in this paper, we revisit the problem of constructing provably secure Feistel constructions using permutations as the round functions. More specifically, following the idea of Naor and Reingold, we try to...

In this paper, we present an optimized construction of the Homomorphic Polynomial Public Key (HPPK) cryptosystem, a novel framework designed to provide enhanced security and efficiency in the post-quantum era. Our work introduces a layered cryptographic design that combines modular arithmetic permutations with an innovative additive random masking technique. This approach effectively obscures the underlying factorizable structure of the public key, thereby mitigating vulnerabilities to known...

In electronic voting systems, guaranteeing voter anonymity is essential. One primary method to ensure this is the use of a mix-net, in which a set of mix-servers sequentially shuffle a set of encrypted votes, and generate proofs that a correct permutation has been applied. Whilst mix-nets offer advantages over alternative approaches, their traditional use during the tallying phase introduces a significant robustness bottleneck: the process is inherently sequential and critically depends on...

Understanding the minimal assumptions necessary for constructing non-interactive zero-knowledge arguments (NIZKs) for NP and placing it within the hierarchy of cryptographic primitives has been a central goal in cryptography. Unfortunately, there are very few examples of ``generic'' constructions of NIZKs or any of its natural relaxations. In this work, we consider the relaxation of NIZKs to the designated-verifier model (DV-NIZK) and present a new framework for constructing (reusable)...

A rugged pseudorandom permutation (RPRP) is a security notion for variable-length tweakable ciphers that is strictly weaker than the traditional notion of a strong pseudorandom permutation. Being a weaker security notion it admits more efficient constructions. Yet the notion is strong enough so that any such construction can lend itself to a number of practical applications. It can be used to construct onion encryption, misuse-resistant AEAD, and AEAD secure under the release of unverified...

Given two linear codes, the Code Equivalence Problem asks to find (if it exists) an isometry mapping one code into the other. A special case is the Permutation Equivalence Problem (PEP), where the isometry must be a permutation. The hardness of PEP is crucially dependent on the hull of a code, that is, the intersection between a code and its dual. Indeed, most of the known algorithms have running time that grows exponentially with the hull dimension. Since random codes have very small...

RIPEMD-128 is an ISO/IEC standard hash function based on a double-branch Merkle-Damgård structure. Its compression function includes two branches with distinct Boolean functions and message expansion permutations. To perform a collision attack, differential characteristics must be constructed simultaneously for both branches under the same message word difference, and the message modification order must align with conditions in both branches. These factors make collision attacks on (reduced)...

Vistrutah is a block cipher with block sizes of 256 and 512 bits. It iterates a step function consisting of two AES rounds applied to each 128-bit block of the state, followed by a state-wide cell permutation. Building upon established design principles from Simpira, Haraka, Pholkos, and ASURA, Vistrutah leverages AES instructions to achieve high performance. For each component of Vistrutah, we conduct a systematic evaluation of functions that can be efficiently implemented on both Intel...

The sponge is a popular construction of hash function design. It operates with a $b$-bit permutation on a $b$-bit state, that is split into a $c$-bit inner part and an $r$-bit outer part. However, the security bounds of the sponge are most often dominated by the capacity $c$: if the length of the digest is $n$ bits, the construction tightly achieves $\min\{n/2,c/2\}$-bit collision resistance, $\min\{n,c/2\}$-bit second preimage resistance, and $\min\{n,\max\{n-r,c/2\}\}$-bit preimage...

In this work, we study the quantum security of key-alternating ciphers (KAC), a natural multi-round generalization of the Even–Mansour (EM) cipher underlying many block cipher constructions, including AES. While the classical security of KAC and the quantum security of the $1$-round KAC (i.e. Even-Mansour) cipher are well understood, the quantum resistance of multi-round KAC remains largely unexplored. We focus on the $2$-round KAC construction, defined using public $n$-bit permutations...

This paper explores the algebraic structure of the Poseidon and Poseidon2 permutations over NTT-friendly finite fields, with a focus on preimage recovery via root-finding techniques. We introduce an algorithm for efficiently identifying single roots of high-degree univariate polynomials that emerge from these constructions, based on the Graeffe transform and the tangent Graeffe method. Our approach is evaluated on reduced-round bounty instances of these permutations at various security...

Liskov, Rivest, and Wagner, in their seminal work, formulated tweakable blockciphers and proposed two blockcipher-based design paradigms, LRW1 and LRW2, where the basic design strategy is to xor the masked tweak to the input and output of a blockcipher. The 2-round cascaded LRW2 and 4-round cascaded LRW1 have been proven to be secure up to $\mathcal{O}(2^{3n/4})$ queries, but $n$-bit optimal security still remains elusive for these designs. In their paper, Liskov also posed an open challenge...

The security of block ciphers such as AES-128, AES-192, and AES-256 relies on the assumption that their ciphertext outputs are computationally indistinguishable from random permutations. While distinguishers have been proposed for reduced-round variants or under non-standard models such as known-key or chosen-key settings, no effective distinguisher has been demonstrated for the full-round AES ciphers in the standard secret-key model. This work introduces FESLA (Feature Enhanced...

The power of adaptivity in algorithms has been intensively studied in diverse areas of theoretical computer science. In this paper, we obtain a number of sharp lower bound results which show that adaptivity provides a significant extra power in cryptanalytic time-space tradeoffs with (possibly unlimited) preprocessing time. Most notably, we consider the discrete logarithm (DLOG) problem in a generic group of $N$ elements. The classical `baby-step giant-step' algorithm for the...

In this work, we derive the first lifting theorems for establishing security in the quantum random permutation and ideal cipher models. These theorems relate the success probability of an arbitrary quantum adversary to that of a classical algorithm making only a small number of classical queries. By applying these lifting theorems, we improve previous results and obtain new quantum query complexity bounds and post-quantum security results. Notably, we derive tight bounds for the quantum...

The sponge is a cryptographic construction that turns a public permutation into a hash function. When instantiated with the Keccak permutation, the sponge forms the NIST SHA-3 standard. SHA-3 is a core component of most post-quantum public-key cryptography schemes slated for worldwide adoption. While one can consider many security properties for the sponge, the ultimate one is \emph{indifferentiability from a random oracle}, or simply \emph{indifferentiability}. The sponge was proved...

Truncation of cryptographic outputs is a technique that was recently introduced in Baldimtsi et al. [BCCK22]. The general idea is to try out many inputs to some cryptographic algorithm until the output (e.g. a public-key or some hash value) falls into some sparse set and thus can be compressed: by trying out an expected $2^k$ different inputs one will find an output that starts with $k$ zeros. Using such truncation one can for example save substantial gas fees on Blockchains where...

We present concrete techniques for adapting the protocols of Mohassel et al (CCS 2020) and Badrinarayanan et al (CCS 2022) for compute SQL-like querying operations on secret shared database tables to the two party setting. The afore mentioned protocols are presented in a generic setting with access to certain idealized functionalities, e.g. secret shared permutations. However, they only instantiate their protocols in the honest majority three party setting due to other settings being...

We analyze a variant of the Fiat–Shamir transformation based on an ideal permutation. The transformation relies on the popular duplex sponge paradigm, and minimizes the number of calls to the permutation (given the information to absorb/squeeze). This closely models deployed variants of the Fiat–Shamir transformation, and our analysis provides concrete security bounds to guide security parameters in practice. Our results contribute to the ongoing community-wide effort to achieve rigorous,...

One-shot signatures (OSS) were defined by Amos, Georgiou, Kiayias, and Zhandry (STOC'20). These allow for signing exactly one message, after which the signing key self-destructs, preventing a second message from ever being signed. While such an object is impossible classically, Amos et al observe that OSS may be possible using quantum signing keys by leveraging the no-cloning principle. OSS has since become an important conceptual tool with many applications in decentralized settings and for...

The most fundamental performance metrics of secure multi-party computation (MPC) protocols are related to the number of messages the parties exchange (i.e., round complexity), the size of these messages (i.e., communication complexity), and the overall computational resources required to execute the protocol (i.e., computational complexity). Another quality metric of MPC protocols is related to the black-box or non-black-box use of the underlying cryptographic primitives. Indeed, the design...

The Sum of Even-Mansour (SoEM) construction, proposed by Chen et al. at Crypto 2019, has become the basis for designing some symmetric schemes, such as the nonce-based MAC scheme $\text{nEHtM}_{p}$ and the nonce-based encryption scheme $\text{CENCPP}^{\ast}$. In this paper, we make the first attempt to study the quantum security of SoEM under the Q1 model where the targeted encryption oracle can only respond to classical queries rather than quantum ones. Firstly, we propose a quantum...

We revisit the post-quantum security of Password-Authenticated Key Ex- change (PAKE) from Key Encapsulation Mechanisms (KEM), focusing on (O)CAKE. Despite extensive study, these protocols still lack a security proof against quantum adversaries. We pinpoint exactly why by identifying the precise remaining obstacle. Most game-hopping arguments extend to the quantum setting via standard QROM techniques. The difficulty lies with ideal ciphers: adaptive programming and query recording are well...

The Pointer Authentication Code ($\textsf{PAC}$) feature in the Arm architecture is used to enforce the Code Flow Integrity ($\textsf{CFI}$) of running programs. It does so by generating a short $\textsf{MAC}$ - called the $\textsf{PAC}$ - of the return address and some additional context information upon function entry, and checking it upon exit. An attacker that wants to overwrite the stack with manipulated addresses now faces an additional hurdle, as they now have to guess,...

In the last decade, the introduction of advanced cryptographic protocols operating on large finite fields $\mathbb{F}_q$ has raised the need for efficient cryptographic primitives in this setting, commonly referred to as Arithmetization-Oriented (AO). The cryptanalysis of AO hash functions is essentially done through the study of the CICO problem on the underlying permutation. Two recent works at Crypto 2024 and Asiacrypt 2024 managed to solve the CICO problem much more efficiently than...

We revisit shuffle protocols for Shamir secret sharing. Existing constructions either produce a non-uniform shuffle or incur high communication and round complexity, in some cases exponential in the number of parties. We propose two new shuffle protocols that achieve uniform shuffle with communication complexity $O\!\left(\frac{k + l}{\log k} \, n^2 m \log m\right)$ for shuffling rows of an $m\times l$ matrix shared among $n$ parties, where $k\leq m$ is a tunable parameter that balances...

We propose efficient, post-quantum threshold ring signatures constructed from one-wayness of AES encryption and the VOLE-in-the-Head zero-knowledge proof system. Our scheme scales efficiently to large rings and extends the linkable ring signatures paradigm. We define and construct key-binding deterministic tags for signature linkability, that also enable succinct aggregation with approximate lower bound arguments of knowledge; this allows us to achieve succinct aggregation of our signatures...

In this paper, we present a general framework for constructing SNARK-friendly post-quantum signature schemes based on minimal assumptions, specifically the security of an arithmetization-oriented family of permutations. The term "SNARK-friendly" here refers to the efficiency of the signature verification process in terms of SNARK constraints, such as R1CS constraints. Within the CAPSS framework, signature schemes are designed as proofs of knowledge of a secret preimage of a one-way function,...

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

Arithmetization-Oriented (AO) cryptographic algorithms operate on large finite fields. The most threatening attack on such designs is the Gröbner basis attack, which solves the equation system encoded from the cryptanalysis problem. However, encoding a primitive as a system of equations is not unique, and finding the optimal one with low solving complexity is a challenge. This paper introduces an automatic tool that converts the CICO problem into a Mixed-Integer Quadratic Constraint...

We introduce a new approach between classical security proofs of modes of operation and dedicated security analysis for known cryptanalysis families: General Practical Cryptanalysis. This allows us to analyze generically the security of the sum of two keyed permutations against known attacks. In many cases (of course, not all), we show that the security of the sum is strongly linked to that of the composition of the two permutations. This enables the construction of beyond-birthday bound...

Shuffling is a fundamental operation in secure multiparty computation (MPC). However, the best-known maliciously secure $n$-party $m$-element shuffle protocols still incur at least $n^2 m$ online communication and computation, which exceeds the best-known $O(nm)$ result for the semi-honest additive secret sharing setting. In this paper, we formalize the permute-in-turn paradigm for building MPC shuffle protocols from MPC permutation protocols, which captures the methodology implicitly...

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 circulant twin column parity mixer (TCPM) is a type of mixing layer for the round function of cryptographic permutations designed by Hirch et al. at CRYPTO 2023. It has a bitwise differential branch number of 12 and a bitwise linear branch number of 4, which makes it competitive in applications where differential security is required. Hirch et al. gave a concrete instantiation of a permutation using such a mixing layer, named Gaston, and showed the best 3-round differential and linear...

This paper partly solves the open problem of tight trade-off of client storage and server time in the client preprocessing setting of private information retrieval (PIR). In the client preprocessing setting of PIR, the client is allowed to store some hints generated from the database in a preprocessing phase and use the hints to assist online queries. We construct a new single-server client preprocessing PIR scheme. For a database with $n$ entries of size $w$, our protocol uses $S=O((n/T)...

We establish a one-to-one correspondence between Dembowski-Ostrom (DO) polynomials and upper triangular matrices. Based on this correspondence, we give a bijection between DO permutation polynomials and a special class of upper triangular matrices, and construct a new batch of DO permutation polynomials. To the best of our knowledge, almost all other known DO permutation polynomials are located in finite fields of $\mathbb{F}_{2^n}$, where $n$ contains odd factors (see Table 1). However,...

A Timed Commitment (TC) with time parameter $t$ is hiding for time at most $t$, that is, commitments can be force-opened by any third party within time $t$. In addition to various cryptographic assumptions, the security of all known TC schemes relies on the sequentiality assumption of repeated squarings in hidden-order groups. The repeated squaring assumption is therefore a security bottleneck. In this work, we give a black-box construction of TCs from any time-lock puzzle (TLP) by...

Since designing a dedicated secure symmetric PRF is difficult, various works studied optimally secure PRFs from the sum of independent permutations (SoP). At CRYPTO'20, Gunsing and Mennink proposed the Summation-Truncation Hybrid (STH). While based on SoP, STH releases additional $a \leq n$ bits of the permutation calls and sums $n-a$ bits of them. Thus, it produces $n+a$ bits at $O(n-a/2)$-bit PRF security. Both SoP or STH can be used directly in encryption schemes or MACs in place of...

We construct the first multi-input functional encryption (MIFE) and indistinguishability obfuscation (iO) schemes for pseudorandom functionalities, where the output of the functionality is pseudorandom for every input seen by the adversary. Our MIFE scheme relies on LWE and evasive LWE (Wee, Eurocrypt 2022 and Tsabary, Crypto 2022) for constant arity functions, and a strengthening of evasive LWE for polynomial arity. Thus, we obtain the first MIFE and iO schemes for a nontrivial...

Recently, Baudrin et al. analyzed a special case of Wagner's commutative diagram cryptanalysis, referred to as commutative cryptanalysis. For a family $(E_k)_k$ of permutations on a finite vector space $G$, commutative cryptanalysis exploits the existence of affine permutations $A,B \colon G \rightarrow G$, $I \notin \{A,B\}$ such that $E_k \circ A (x) = B \circ E_k(x)$ holds with high probability, taken over inputs $x$, for a significantly large set of weak keys $k$. Several attacks...

We develop and implement AlgoROM, a tool to systematically analyze the security of a wide class of symmetric primitives in idealized models of computation. The schemes that we consider are those that can be expressed over an alphabet consisting of XOR and function symbols for hash functions, permutations, or block ciphers. We implement our framework in OCaml and apply it to a number of prominent constructions, which include the Luby–Rackoff (LR), key-alternating Feistel (KAF), and...

The problem of reliable/secure all-to-all communication over low-degree networks has been essential for communication-local (CL) n-party MPC (i.e., MPC protocols where every party directly communicates only with a few, typically polylogarithmic in n, parties) and more recently for communication over ad hoc networks, which are used in blockchain protocols. However, a limited number of adaptively secure solutions exist, and they all make relatively strong assumptions on the ability of parties...

We study those $(n,n)$-permutations, and more generally those balanced $(n,m)$-functions, whose component functions all admit a derivative equal to constant function 1 (this property itself implies balancedness). We call these functions quadratic-like permutations (resp. quadratic-like balanced functions) since all quadratic balanced functions have this property. We show that all Feistel permutations, all crooked permutations and (more generally) all balanced strongly plateaued functions...

The Feistel construction is a fundamental technique for building pseudorandom permutations and block ciphers. This paper shows that a simple adaptation of the construction is resistant, even to algorithm substitution attacks---that is, adversarial subversion---of the component round functions. Specifically, we establish that a Feistel-based construction with more than $337n/\log(1/\epsilon)$ rounds can transform a subverted random function---which disagrees with the original one at a small...

Forward-Secure Key-Encapsulation Mechanism (FS-KEM; Canetti et al. Eurocrypt 2003) allows Alice to encapsulate a key $k$ to Bob for some time $t$ such that Bob can decapsulate it at any time $t'\leq t$. Crucially, a corruption of Bob's secret key after time $t$ does not reveal $k$. In this work, we generalize and extend this idea by also taking Post-Compromise Security (PCS) into account and call it Interval Key-Encapsulation Mechanism (IKEM). Thus, we do not only protect confidentiality...

In recent years a new class of symmetric-key primitives over $\mathbb{F}_p$ that are essential to Multi-Party Computation and Zero-Knowledge Proofs based protocols has emerged. Towards improving the efficiency of such primitives, a number of new block ciphers and hash functions over $\mathbb{F}_p$ were proposed. These new primitives also showed that following alternative design strategies to the classical Substitution-Permutation Network (SPN) and Feistel Networks leads to more efficient...

In this paper, we propose quantum key recovery attacks on 4-round iterated Even-Mansour (IEM) with a key schedule that applies two keys alternately. We first show that a conditional periodic function such that one of the secret keys appears as a period conditionally can be constructed using the encryption function and internal permutations. By applying the offline Simon's algorithm to this function, we construct a key recovery attack with a complexity of $O(\sqrt{N} \log N)$ for $N = 2^n$,...

A prominent countermeasure against side channel attacks, the hiding countermeasure, typically involves shuffling operations using a permutation algorithm. Especially in the era of Post-Quantum Cryptography, the importance of the hiding coun- termeasure is emphasized due to computational characteristics like those of lattice and code-based cryptography. In this context, swiftly and securely generating permutations has a critical impact on an algorithm’s security and efficiency. The widely...

We investigate shift-invariant transformations, also known as rotation-symmetric vectorial Boolean functions, on $n$ bits that are induced from Boolean functions on $k$ bits, for $k\leq n$. We consider such transformations that are not necessarily permutations, but are, in some sense, almost bijective, and study their cryptographic properties. In this context, we define an almost lifting as a Boolean function for which there is an upper bound on the number of collisions of its induced...

We propose a generalization of Zhandry’s compressed oracle method to random permutations, where an algorithm can query both the permutation and its inverse. We show how to use the resulting oracle simulation to bound the success probability of an algorithm for any predicate on input-output pairs, a key feature of Zhandry’s technique that had hitherto resisted attempts at generalization to random permutations. One key technical ingredient is to use strictly monotone factorizations to...

We develop a distributed service for generating correlated randomness (e.g. permutations) for multiple parties, where each party’s output is private but publicly verifiable. This service provides users with a low-cost way to play online poker in real-time, without a trusted party. Our service is backed by a committee of compute providers, who run a multi-party computation (MPC) protocol to produce an (identity-based) encrypted permutation of a deck of cards, in an offline phase well ahead...

Cryptographic hash functions are said to be the work-horses of modern cryptography. One of the strongest approaches to assess a cryptographic hash function's security is indifferentiability. Informally, indifferentiability measures to what degree the function resembles a random oracle when instantiated with an ideal underlying primitive. However, proving the indifferentiability security of hash functions has been challenging due to complex simulator designs and proof arguments. The Sponge...

Side channel attacks, and in particular timing attacks, are a fundamental obstacle to obtaining secure implementation of algorithms and cryptographic protocols, and have been widely researched for decades. While cryptographic definitions for the security of cryptographic systems have been well established for decades, none of these accepted definitions take into account the running time information leaked from executing the system. In this work, we give the foundation of new cryptographic...