Papers updated in last 1 days (14 results)
Impossible Polytopic Cryptanalysis Extended: Attention to Block Ciphers with Oversized Keys
Block ciphers whose key size exceeds their block size, such as the 192- and 256-bit variants of \textsf{AES}, the tweakable block ciphers \textsf{Deoxys-BC-256} and \textsf{Deoxys-BC-384} (standardized by ISO/IEC as \textsf{Deoxys-TBC}), and \textsf{ChiLow-32} (EUROCRYPT 2025), achieve a security level beyond the block size and are becoming increasingly prevalent. This paper extends the impossible polytopic attack (\ipa{}, proposed by Tyge Tiessen at EUROCRYPT 2016) and shows that it yields longer-round distinguishers, enables key recovery on more rounds, and extends to the known-plaintext (KP) setting. To this end, we formalize the bound-estimation-based \ipd{} underlying Tiessen's original work and establish a general framework for distinguisher construction, within which we develop two strategies---the large-Sbox strategy and the subtlety-aware strategy---that substantially reduce the construction cost. For key recovery, we propose the plaintext-grouping technique and the partition-guess-filter technique: the former extends the attack to both sides of the distinguisher and thereby reaches more rounds, while the latter allows the entire master key to be guessed during the attack and substantially lowers the overall complexity. Building on these techniques, we obtain the first key-recovery framework for \ipa{}s, in two complementary variants, the target-table and the candidate-table frameworks. We apply our techniques to \textsf{AES}, \textsf{Deoxys-BC}, \textsf{Joltik-BC}, \textsf{LED-128}, and \textsf{ChiLow-32} in the single-key setting, under both the chosen-plaintext/chosen-ciphertext (CP/CC) and the known-plaintext (KP) scenarios. The main objective of this work is low-data cryptanalysis, i.e., to minimize the data complexity of both \ipd{}s and key-recovery attacks. Notably, 10-round low-data attacks are obtained on \textsf{Deoxys-BC-384} and \textsf{Joltik-BC-192}, which improve upon the best known impossible differential attacks by one round. For \textsf{ChiLow-32}, a full-round \ipa{} in the CP setting requires only $8$ chosen plaintexts, improving upon the best known full-round attack that requires $64$; a full-round \ipa{} in the KP setting requires $107$ known plaintexts, improving upon the best known full-round KP attack that requires $160$ plaintexts.
Universally Composable Almost-Everywhere Secure Computation
Most existing work on secure multi-party computation (MPC) ignores a key idiosyncrasy of modern communication networks, that there are a limited number of communication paths between any two nodes, many of which might even be corrupted. The problem becomes particularly acute in the information-theoretic setting, where the lack of trusted setups (and the cryptographic primitives they enable) makes communication over sparse networks more challenging. The work by Garay and Ostrovsky [EUROCRYPT'08] on almost-everywhere MPC (AE-MPC), introduced ``best-possible security'' properties for MPC over such incomplete networks, where necessarily some of the honest parties may be excluded from the computation.
In this work, we provide a universally composable definition of almost-everywhere security, which allows us to automatically and accurately capture the guarantees of AE-MPC (as well as AE-communication, the analogous ``best-possible security'' version of secure communication) in the Universal Composability (UC) framework of Canetti. Our results offer the first simulation-based treatment of this important but under-investigated problem, along with the first simulation-based proof of AE-MPC. To achieve that goal, we state and prove a general composition theorem, which makes precise the level or ``quality'' of AE-security that is obtained when a protocol's hybrids are replaced with almost-everywhere components.
Is It Even Possible? On the Parallel Composition of Asynchronous MPC Protocols
Despite several known idiosyncrasies separating the synchronous and the asynchronous models, asynchronous secure multi-party computation (MPC) protocols demonstrate high-level similarities to synchronous MPC, both in design philosophy and abstract structure. As such, a coveted, albeit elusive, desideratum is to devise automatic translators (e.g., protocol compilers) of feasibility and efficiency results from one model to the other.
In this work, we demonstrate new challenges associated with this goal. Specifically, we study the case of parallel composition in the asynchronous setting. We provide formal definitions of this composition operation in the UC framework, which, somewhat surprisingly, have been missing from the literature. Using these definitions, we then turn to charting the feasibility landscape of asynchronous parallel composition.
We first prove strong impossibility results for composition operators that do not assume knowledge of the functions and/or the protocols that are being composed. These results draw a grim feasibility picture, which is in sharp contrast with the synchronous model, and highlight the question:
Is asynchronous parallel composition even a realistic goal?
To answer the above (in the affirmative), we provide conditions on the composed protocols that enable a useful form of asynchronous parallel composition, as it turns out to be common in existing constructions.
Concurrent Asynchronous Byzantine Agreement in Expected-Constant Rounds, Revisited
It is well known that without randomization, Byzantine agreement (BA) requires a linear number of rounds in the synchronous setting, while it is flat out impossible in the asynchronous setting. The primitive which allows to bypass the above limitation is known as oblivious common coin (OCC). It allows parties to agree with constant probability on a random coin, where agreement is oblivious, i.e., players are not aware whether or not agreement has been achieved.
The starting point of our work is the observation that no known protocol exists for information-theoretic multi-valued OCC---i.e., OCC where the coin might take a value from a domain of cardinality larger than 2---with optimal resiliency in the asynchronous (with eventual message delivery) setting. This apparent hole in the literature is particularly problematic, as multi-valued OCC is implicitly or explicitly used in several constructions. (In fact, it is often falsely attributed to the asynchronous BA result by Canetti and Rabin [STOC ’93], which, however, only achieves binary OCC and does not translate to a multi-valued OCC protocol.)
In this paper, we present the first information-theoretic multi-valued OCC protocol in the asynchronous setting with optimal resiliency, i.e., tolerating $t<n/3$ corruptions, thereby filling this important gap. Further, our protocol efficiently implements OCC with an exponential-size domain, a property which is not even achieved by known constructions in the simpler, synchronous setting.
We then turn to the problem of round-preserving parallel composition of asynchronous BA. A protocol for this task was proposed by Ben-Or and El-Yaniv [Distributed Computing ’03]. Their construction, however, is flawed in several ways: For starters, it relies on multi-valued OCC instantiated by Canetti and Rabin's result (which, as mentioned above, only provides binary OCC). This shortcoming can be repaired by plugging in our above multi-valued OCC construction. However, as we show, even with this fix it remains unclear whether the protocol of Ben-Or and El-Yaniv achieves its goal of expected-constant-round parallel asynchronous BA, as the proof is incorrect. Thus, as a second contribution, we provide a simpler, more modular protocol for the above task. Finally, and as a contribution of independent interest, we provide proofs in Canetti's Universal Composability framework; this makes our work the first one offering composability guarantees, which are important as BA is a core building block of secure multi-party computation protocols.
Randomized Early-Stopping Byzantine Agreement with Applications to Round-Efficient MPC
We consider two main classes of synchronous round-efficient Byzantine Agreement (BA) protocols: \emph{expected constant rounds} and \emph{early-stopping}. Randomized protocols can terminate in expected constant rounds, and early-stopping protocols' worst-case round complexity depends on the actual number of corrupted parties $f\le t$, with $\min(t+1, f+2)$ being optimal. In this work, we combine the benefits of both classes, proposing a protocol that has constant round-complexity in expectation and $O(f)$ in the worst case. We present our protocol in the form of a compiler that can lift a broad class of expected-constant-round BA protocols, including Feldman--Micali and Katz--Koo, to {\em also} achieve near-optimal $O(f)$ worst-case complexity.
This yields the {\em first} treatment of perfectly secure BA protocols for $t<n/3$ that is both expected constant-round and near-optimal ($O(f)$) early stopping. Assuming a PKI, we show a variant of the compiler with a better round complexity, tolerating $t<n/2$ corruptions.
We also extend our results to parallel broadcast, also known as interactive consistency (IC). We give a compiler that runs $N$ Byzantine agreement instances in parallel while preserving both guarantees, expected constant rounds and $O(f)$ rounds in the worst case. Parallel broadcast then follows with one extra round for $t<n/2$. To the best of our knowledge, this is the first compiler of its kind, and the first IC protocol with such expected and worse round-complexity.
Finally, by combining our protocol with standard (fast) sequential composition techniques, we obtain a valid candidate to execute \emph{multi-party computation protocols} that require broadcast as their hybrid. By running existing MPC constructions using our broadcast protocol, we obtain the first MPC protocol that requires constant rounds of P2P communication in expectation and $O(f)$ rounds in the worst case.
Practical Keyword SPIR with Lightweight Clients: Hintless and Efficient
Keyword private information retrieval (keyword PIR) enables a client to retrieve the value associated with a keyword without revealing the queried keyword, generalizing traditional index PIR. This work advances the state of the art of Hao et al. (USENIX Security 2025) by addressing several key limitations of their constructions, most notably the efficiency bottleneck of their generic framework and the over-revealing nature of their more efficient designs. Although using oblivious PRFs (OPRFs) can solve the over-revealing issue, doing so introduces additional trade-offs that may hinder practical deployment.
We present a practical, hintless keyword PIR framework that natively eliminates over-revelation without relying on OPRFs, achieving symmetric PIR security. Building on KsPIR (CCS 2024) and the linearly homomorphic technique of Peikert and Pepin (TCC 2025), our server homomorphically evaluates key-value store decoding over encrypted queries, retrieving exactly the target record. To accelerate evaluation, we introduce a generalized baby-step giant-step (BSGS) algorithm for coefficient-encoded Galois sums, an offline/online decomposition, and a Horner-style evaluation chain that reduces uploaded evaluation keys to three. For databases up to $2^{22}$ entries, our construction achieves a mean online speedup of $2.65\times$ over their generic framework under the same index-PIR backend. Compared to their specialized design, our scheme attains comparable online time while requiring neither a client-side hint (saving 14.5--143.6 MB) nor an OPRF.
Distributed Key Generation for Efficient Threshold-CKKS
Threshold fully homomorphic encryption provides efficient multi-party computation with low round-complexity. Among fully homomorphic encryption schemes, CKKS (Cheon-Kim-Kim-Song) enables high-throughput computations on both approximate and exact data. As most interesting applications involve deep computations, they require bootstrapping, the most efficient variants of which rely on sparse ternary secret keys. Unfortunately, so far, key generation protocols for threshold-CKKS either assume a trusted dealer, or lead to dense and non-ternary secret keys that severely damage computational throughput. In the latter case, the impact is so large that one often considers off-loading bootstrapping to an interactive protocol [Mouchet et al., PETS'21].
We introduce a novel Distributed Key Generation (DKG) protocol for threshold-CKKS. At a high level, it consists in running the existing distributed key generation algorithm from Mouchet et al. resulting in large secret keys, and using it to homomorphically evaluate the sparse-secret key generation algorithm. At the end, the parties obtain additive shares of a sparse secret key. The main technical challenge is to obtain an algorithm for sampling sparse ternary vectors of prescribed Hamming weight that can be CKKS-evaluated in an efficient manner. In the process, we design a new sampler of one-hot vectors that outperforms the one from~[Boneh et al., AFT'20]. We also design a rejection-sampling algorithm to map several one-hot vectors into a vector of prescribed Hamming weight. The whole process can be performed with only two CKKS bootstraps, even for a significant number of users.
We present several variants of the DKG protocol, with~2 to~4 communication rounds, as well as an extension to key generation delegation. We implemented the 4-round protocol; its computational components run in~under 2s on GPU (RTX4090) for up to 1024 parties.
Extending the Schur--Macaulay Framework for UOV Attacks via Truncated Polynomial Algebras
Building on the ideal-inclusion framework of Ding, Li, and Tao, we reformulate and extend the Schur--Macaulay approach of Merz and Ran using multigraded $p$-truncated polynomial algebras over arbitrary finite fields. The construction admits a reconciliation interpretation involving multiple oil vectors. Combining divided powers with transfer relation spaces, we derive quotient-dimension criteria for recovering graded components of the hidden oil-space ideal. Hilbert-series conjectures and structured rank predictions underpin the complexity estimates. Applications to NIST third-round submissions yield reductions of up to 61 bits in estimated attack costs for selected additional MAYO parameter sets and improvements over the classical wedge attack for selected QR-UOV parameters. Certain alternating parameters provided by authors in MAYO fail to meet the NIST security level III and V.
Twisted Towers: Fully Costed Special Tower NFS Attacks on BLS12-381 and BN254
BLS12-381 is commonly said to offer "126 bits" of security and BN254 "about 100 bits". Both figures are estimates of the special tower number field sieve (STNFS) in the target group $\mathbb{F}_{p^{12}}^*$, and both count abstract operations in models that leave out whole phases of the attack. We replace them by complete ledgers in which every step is priced in machine instructions: relation collection, cofactorisation, filtering, linear algebra, both individual logarithms and all failures. Under explicitly listed heuristics, a complete attack executes $2^{127.5}$ instructions for BLS12-381 and $2^{103.2}$ for the BN254 curve used in Ethereum, with success probability above $0.998$. For BLS12-381 this is $9.6$ bits below Pollard's rho on the curve counted the same way, where operation counts suggested one bit: the target group is clearly the weaker side. It is also $9.8$ bits below what the published design costs when it is completed with standard components and charged in full ($2^{137.3}$ instructions, level with rho). For BN254 our figure confirms the accepted level and gives it a concrete meaning.
The method rests on three ideas and on a systematic reduction of the work per sieved cell. First, a twisted tower: a unit $c$ of the sextic base field with $c\,\sigma(c)=-1$ turns the usual sign symmetry into a symmetry of order four that acts as a Frobenius power, so that relations and ideals come in orbits of four and the linear system has Gaussian-integer entries. Second, counting each relation once: coefficient-cube estimates count unit multiples of a relation as distinct; for the published BLS12-381 design only $2^{-2.8}$ of the counted relations are distinct, and we sieve a fundamental domain instead. Third, a sieve organised around reuse: only the harder side is sieved, tiny primes are handled by batch arithmetic, and the hits of a prime ideal are replayed from lists shared by all slices. A product-form linear algebra and a planned descent complete the method. Each technique is stated for a general special pair of tower shape $(6,2)$ and then instantiated on the two curves. Nothing was run at full size; the final designs assume up to $2^{112}$ bytes of storage, which the cost model does not charge; and the practical security of both curves is unchanged.
Limits of Pseudorandom Codes under Adaptive Corruption
Pseudorandom codes (PRCs) hide messages in strings that look uniformly random
to anyone without the decoder key. If the key may be stolen after some codewords
have been sent, security requires that these codewords and the stolen key be
indistinguishable from uniform strings, chosen independently of the messages,
together with a key that decodes each of them to its message. We call producing
such a key \emph{opening} the codewords, and ask how many key bits it takes.
We first show that every adaptively secure PRC yields a \emph{$q$-use code} with
the same key length, namely its opened key together with the $q$ uniform strings it
opens. Lower bounds for these information-theoretic objects therefore hold
unconditionally and apply to every adaptively secure PRC, including current designs
based on hardness assumptions.
We then show that every opening costs key bits beyond the opened message:
$\omega(\log\lambda)$ without errors, $\frac{1}{\rho^2}\cdot\omega(\log\lambda)$ under random noise of correlation $\rho$, and, for every alphabet, a constant fraction of the codeword if every error pattern up to a constant fraction of the length must be corrected, even when an unbounded adversary chooses it with the key. We call the last cost the robustness tax. As for non-committing encryption, adaptively secure PRCs thus need an a-priori bound on the number of openings, but each opening costs more, because of the tension between soundness and robustness: a sound key must reject almost all strings, yet accept a region around each uniformly random codeword. We show simple stateful codes meet these bounds and yield stateful PRCs with perfect bounded adaptive security.
Finally, unlike for non-committing encryption, a programmable random oracle cannot pay this cost under noise. Errors move the decoder's queries away from any programmed point, so for decoders with non-adaptive oracle queries, every opening must still be paid for in key bits or in programmed points that the decoder reads on a noticeable fraction of inputs.
Blind zkSNARKs for Private Proof Delegation and Verifiable Computation over Encrypted Data
In this paper, we show for the first time it is practical to privately delegate proof generation of zkSNARKs to a single server for computations of up to $2^{20}$ R1CS constraints. We achieve this by computing zkSNARK proof generation over homomorphic ciphertexts, an approach we call blind zkSNARKs. We formalize the concept of blind proofs, analyze their cryptographic properties and show that the resulting blind zkSNARKs remain sound when compiled using BCS compilation. Our work follows the framework proposed by Garg et al. (Crypto’24) and improves the instantiation presented by Aranha et al. (Asiacrypt’24), which implements only the FRI subprotocol. By delegating proof generation, we are able to reduce client computation time from 10 minutes to mere seconds, while server computation time remains limited to 20 minutes. We also propose a practical construction for vCOED supporting constraint sizes four orders of magnitude larger than the current stateof-the-art verifiable FHE-based approaches. These results are achieved by optimizing Fractal for the GBFV homomorphic encryption scheme, including a novel method for making homomorphic NTT evaluation packing-friendly by computing it in two dimensions. Furthermore, we make the proofs publicly verifiable by appending a zero-knowledge Proof of Decryption (PoD). We propose a new construction for PoDs optimized for low proof generation time, exploiting modulus and ring switching in GBFV and using the Schwartz-Zippel lemma for proof batching; these techniques might be of independent interest. Finally, we implement the latter protocol in C and report on execution time and proof sizes.
The Geometry of Zero Knowledge: Tight Masking and Efficient Multilinear Arguments
Zero-knowledge proofs have become a fundamental tool for verifiable computation and privacy-preserving applications, driving growing interest in proof systems that are both succinct and efficient. In polynomial-based arguments, however, achieving zero knowledge introduces additional costs. Random masks must hide the evaluations and intermediate messages revealed during verification while preserving the underlying computation. Existing approaches range from protecting individual messages with cryptographic commitments to constructing small masking polynomials tailored to particular protocols. These techniques raise a more general question: how much randomness is needed when the verifier observes only a structured collection of evaluations and linear combinations?
We present GoZK, a query-aware approach to zero knowledge that constructs masking spaces from the verifier’s conditional joint observations. We characterize these observations through affine images and develop low-degree masks for selected Cartesian strata, witness polynomials, and product-tree relations. In particular, two product trees that reveal eight boundary evaluations and a single root difference admit a nine-dimensional masking space, matching the dimension of their specified uniform observation interface. We integrate these constructions with a causal masking polynomial, a global sumcheck, and a pairing-based polynomial commitment scheme. The resulting protocol admits exact online simulation under the stated setup and private-coin conditions, with classical knowledge soundness established in a registered algebraic-group and random-oracle model. In a Rust implementation over BLS12-381, query-aware masking reduces the number of source-mask coefficients from 390 to 19 relative to an implemented projected arbitrary-point construction, saves 4,128 proof bytes, and improves prover time by factors of 1.40–1.67 on matched eight-column instances. Global sumcheck further reduces communication by 6,752–10,400 bytes, with a modest prover-time tradeoff.
Information-Theoretic Strong Traceable Secret Sharing Schemes
Traceable secret sharing complements traditional schemes by enabling the identification of parties who sell their shares. More precisely, a group of corrupted parties generates a reconstruction box $R$ that, given enough valid shares as input, reconstructs the secret. The goal is to trace $R$ back to at least one of the corrupted parties using only black-box access to it. Recently, two independent works extended traceable secret sharing to general access structures.
Goyal, Jain, and Partap [EC'26] introduced a model in which $R$ is augmented with a label $I \subseteq [n]$ and is only required to distinguish between two secrets when queried with the shares of parties in $I$. Based on how this label relates to the corrupted set $J$ that built the box, they defined two notions of traceability. If $I \cap J = \emptyset$, the model is called $\emptyset$-strong traceability, for which they presented a construction based on indistinguishability obfuscation (iO). Otherwise, their model is called strong traceability, for which they proved an impossibility result.
Farràs and Guiot [EC'26] proposed a different model, which we call hidden traceability, where $R$ has no label and the access structure is hidden from the parties.
In this work, we improve traceable secret sharing for general access structures in three directions. First, we present a fully information-theoretic scheme for the $\emptyset$-strong traceability model, eliminating the need for strong cryptographic assumptions. This resolves an open question posed by Goyal, Jain, and Partap, who asked what are the minimal assumptions needed in the $\emptyset$-strong traceability model.
Second, motivated by the impossibility of strong traceability, we introduce a relaxed notion called hidden mildly strong traceability. This model is relevant in practice and bridges the strong and hidden models. For this setting, we present an information-theoretic scheme for general access structures.
Finally, we consider the more general model of stateful traceability, where reconstruction boxes may keep state across queries, and we prove an impossibility result for this setting.
Improved Differential-Linear Cryptanalysis of Orthros, Gleeok, ZIP-AES, and ZIP-GIFT
We improve differential-linear distinguishers and derive key-recovery attacks on reduced-round versions of the PRFs Orthros, Gleeok, ZIP-AES, ZIP-GIFT-64, and ZIP-GIFT-128. Relative to previous differential-linear analyses, we extend the reported coverage for Orthros from 7 to 9 rounds and for Gleeok-128 from 4 to 5 rounds. For Orthros and Gleeok-128, we obtain estimated correlation magnitudes \(2^{-61.40}\) and \(2^{-31.71}\), respectively. We also obtain distinguishers for 6-round Gleeok-256, \((3,3)\)-round ZIP-AES, \((7,7)\)-round ZIP-GIFT-64, and \((10,10)\)-round ZIP-GIFT-128. For key recovery, we give a \((3,3)\)-round differential-linear attack on ZIP-AES requiring approximately \(2^{122.42}\) chosen plaintexts and \(2^{122.88}\) ZIP-AES evaluations. Our \((10,10)\)-round ZIP-GIFT-128 attack has estimated data, time, and memory complexities of \(2^{93}\) chosen plaintexts, \(2^{117}\) full PRF evaluations, and \(2^{25.01}\) bits. We further obtain weak-key attacks on 9-round Orthros, 5-round Gleeok-128, and 6-round Gleeok-256, with key-space coverages of \(2^{-2.87}\), \(2^{-3}\), and \(2^{-1}\), respectively. The Orthros key-recovery result reaches one round beyond the previous DL key-recovery coverage. These results use automated differential and linear trail search together with existing round-based correlation estimation. We enforce the compatibility constraints between branches and select input-side extensions that make their prescribed differences jointly reachable.