International Association
for Cryptologic Research

We study information-theoretic hiding when an adversary has unrestricted quantum processing but physical access to only one region from a declared family of subsystems. Perfectly hidden classical codewords lie in one fiber of the corresponding marginal map. We organize trace-distance diameter, orthogonal zero-error packing, and exact coherent subspace hiding on this fixed-marginal set, distinguishing equality of basis-state marginals from the cross-term conditions of quantum error correction.

The meet-in-the-middle (MITM) attack framework is one of the most powerful cryptanalytic techniques with broad influence to preimage, key recovery, and collision attacks. In this paper, we present two generic techniques. First, we observe that the constant space in MITM attacks is an exploitable source of degrees of freedom: its value-independence enables MITM-style partition and acceleration of attack subprocesses. With this intuition in mind, we revisit the single-color initial structure technique by Chen et al. at Asiacrypt 2025, and find an improved algorithm that relaxes the canonical optimization objective in automatic search for MITM attacks. Second, we extend the partial-target-preimage-to-collision conversion by Li, Isobe, and Shibutani at FSE 2012 used in MITM-based collision attacks to the settings of chosen-prefix collision and diamond structure construction. We demonstrate the practical relevance of our techniques by presenting a number of improved results in (pseudo-)preimage, (chosen-prefix) collision, and herding attacks on AES-like constructions over the state-of-the-art.

Garbled circuits are fundamental in modern cryptography and secure two- or multi-party computation. For real-world programs that are naturally expressed in the Random-Access Machine (RAM) model, garbled RAM is the RAM counterpart of garbled circuits: they avoid the cost of compiling the entire program into a circuit, with communication complexity serving as the primary efficiency metric. We study the setting in which the RAM program is public, while the input data and memory contents remain secret except for the prescribed output.

We construct a garbled RAM for programs running in time $T$ over memory consisting of $N$ words of $W$ bits each, the scheme achieves \[ O(T \cdot (W + \lambda) \cdot \log N) + \mathrm{poly} (\lambda) \] bits in communication, where $\lambda$ is the security parameter. For sufficiently large word size $W\ge \lambda$ and running time $T\ge\mathrm{poly}(\lambda)$, the communication becomes $O(T W \log N)$, asymptotically matching the bandwidth of an optimal oblivious RAM. Since any secure garbled RAM must hide memory accesses as in oblivious RAMs, our construction can be viewed as compiling an oblivious RAM into a non-interactive analogue, without incurring additional asymptotic communication cost.

Technically, our garbled RAM builds on the recent succinct garbled circuits of Ishai, Li, and Lin (Crypto'25) and Li, Lin, and Lu (Eurocrypt'26), which are in turn based on homomorphic secret sharing. Accordingly, we inherit their circular-power variants of the Decisional Diffie-Hellman or Ring Learning-With-Errors assumptions. We also use techniques from the recent work on garbled arithmetic RAM, called Zebra, by Gu, Ghoshal, and Shi (Eurocrypt'26). Compared to Zebra, which achieves the same $O(TW\log N)$ communication for *arithmetic* RAM programs that only perform arithmetic over large and bounded integers, our work focuses on the standard *boolean* RAM model. Compared to the best garbled RAM in the random oracle model, due to Liu, Liu, Luo, and Heath (ACM CCS'26), we remove a multiplicative factor $\lambda$ in communication.

The Walsh-Hadamard transform (WHT) computes the correlation of a Boolean function with every input parity function at once. Cryptanalytic workflows transform large arrays repeatedly, in batches. However, available tools specialize in particular datatypes, platforms, or ecosystems, and none combines what a portable search needs. We present LibFWHT, an open-source C library for dense Walsh-Hadamard transforms, with Python bindings and a command-line interface. It includes vectorized, multicore, and graphics-processor backends, batch operations, and Boolean and substitution-box helpers. With one central processing unit (CPU) core, LibFWHT is 2.5 to 3.3 times faster than FFTW and up to 3.7 times faster than sboxU on batched Boolean spectra. On an NVIDIA H200 its device-resident graphics-processor backend reaches 1.8 trillion operations per second and runs the same Boolean workload about 600 times faster than the CPU-only sboxU. We demonstrate LibFWHT in linear and differential-linear cryptanalysis of SIMON-32, KATAN-32, BEANIE, KeeLoq, and RC5-16, all with 32-bit blocks. We report the first exact differential-linear distinguishers for KATAN-32, BEANIE, KeeLoq, and RC5-16, whose correlations are measured over the complete codebook rather than estimated from round-by-round trails. We then analyze how these correlations depend on the key, using the geometric approach to cryptanalysis. Writing a fixed-key correlation as a signed sum over key masks turns key dependence into a question of which masks survive. We address this question by combining a mixed-basis trail search with exact measurement on sampled keys. The search proposes responsible round-key bits, and only the measurement determines whether those bits explain the dependence. The procedure separates three outcomes: dependence concentrated on a few key bits, cancellation at the enumerated leading orders, and dependence only weakly explained by the tested short list. Distinguishers are normally reported as a single correlation, and key-recovery complexities are computed from that number. We show that relying on this summary is unsafe. For one of our distinguishers, a quarter of the keys belong to a weak class. Its root-mean-square correlation implies a data requirement about 40 times that estimated from the overall root-mean-square correlation. Key dependence therefore belongs in the analysis, and we report distributions over keys rather than single numbers.

Repeat--accumulate--accumulate (RAA) codes have minimum distance linear in the block length with probability tending to one, both with and without random coordinate scaling. Sharp results, however, reveal a tradeoff between the two constructions. For block length \(N=rn\) and fixed repetition factor \(r\ge4\), the probability that the minimum distance is at most \(\delta N\) is \(\Theta(N^{2-r})\) for unscaled RAA and \(\Theta(N^{1-r})\) for scaled RAA, on their common proved range \(0<\delta\le1/10\). Thus scaling reduces the failure probability by a factor of order \(N\). This improvement comes at a cost: the scaled result requires \(q=\Omega(N)\) over \(\F_q\), and the encoder uses two length-\(N\) layers of coordinatewise field multiplications. In contrast, unscaled RAA works over a fixed field of characteristic greater than \(r\), and its accumulator stages use only field additions.

In this work, we show that adding a third accumulator provides a substantially larger reliability gain without random scaling. For the unscaled repeat--accumulate--accumulate--accumulate ensemble \[ G_3=R\Pi_1A\Pi_2A\Pi_3A, \] where \(R\) is \(r\)-fold repetition, \(A\) is the accumulator, and the \(\Pi_i\) are independent uniform interleavers, we prove that \[ \Prb[d_{\min}(G_3)\le\delta N] =\Theta_{r,\delta}\!\left(N^{\,2-r-\ceil{r/2}}\right) \] for every fixed \(r\ge4\) and \(0<\delta\le1/10\), uniformly over all finite fields of characteristic greater than \(r\). Hence the field size need not grow with \(N\), and the encoder requires three accumulator passes but no coordinatewise field multiplications. On the common threshold range, its failure probability is smaller by a factor of order \(N^{\ceil{r/2}}\) than that of unscaled RAA and by a factor of order \(N^{\ceil{r/2}-1}\) than that of scaled RAA. For example, when \(r=4\), the respective failure probabilities have orders \(N^{-2}\), \(N^{-3}\), and \(N^{-4}\).

This paper introduces a new polynomial model for the exact variant of the Syndrome Decoding Problem (SDP) in the binary case. The model is based on elementary symmetric polynomials. We estimate the computational complexity of solving the corresponding polynomial system by establishing bounds on the degree of regularity and on the solving degree of the ideal associated to the model. The complexity estimate is lower than for previous polynomial models. We also provide a variant of the model whose complexity depends directly on the specific instance of the SDP and is lower than for the first model. Finally, we discuss how to apply our ap- proach to solve other variants of the SDP.

Proton is a popular privacy-focused service vendor, serving over 100,000 organizations. Proton Docs/Sheets supports real-time collaborative document editing, which claims to offer end-to-end security. This is mainly achieved by applying cryptographic protection through users' Web clients so that data outside the user's client remains confidential and intact. We analyze the cryptographic design and the collaborative editing protocol of Proton Docs/Sheets based on the open-source Web client code and the webpage code inspection.

We demonstrate three distinct "integrity" attacks against Proton Docs/Sheets that can cause history rewriting, context manipulation, and censorship, all of which can, in fact, evade detection. The first two can be launched even when the Proton server acts honestly, and the third is mounted by a corrupted Proton server. We also present the corresponding mitigation methods. Our attacks highlight the subtleties of end-to-end security in collaborative settings involving multiple users and constant updates. This state of affairs naturally calls for systematic formal treatment (i.e., design and/or analysis) of the security of such systems.

Verifiable secret sharing (VSS) is a core primitive in multiparty computation (MPC). Bhimrajka et al. [PKC'24, TIT'26] proposed the first computationally network-agnostic VSS and VSS-based MPC, which seamlessly accommodate both synchronous and asynchronous network models. However, their VSS requires Byzantine Agreement (BA) and incurs $O(n^5)$ bits of communication per sharing among $n$ parties, and their MPC requires honest participation from nearly all parties.

We revisit the network-agnostic VSS architecture and propose a more efficient and general network-agnostic VSS structure. Our key technique is a new virtual-party strategy, which introduces more parties for reconstruction. With this technique, network-agnostic VSS is BA-free and performs as efficiently as synchronous VSS. Specifically, in terms of communication, our VSS costs $O(n^2)$ bits in the one-shot case and $O(n)$ bits in the round-by-round case with the dispute-control technique, yielding the first computationally network-agnostic VSS protocols with amortized linear communication complexity. Besides, we further address a series of subtle yet necessary hurdles in adapting existing results to network-agnostic models, including the erasure coding techniques in Reliable Broadcast (RBC), packed secret sharing techniques in VSS, and the correlated polynomial techniques in MPC.

In a widely publicized recent announcement, Google established a formal 2029 deadline for completing its post-quantum cryptography (PQC) migration---one that deliberately preempts the 2035 deadline set by NIST and the US federal government to complete the deprecation of classical public-key algorithms. Google cited faster-than-expected progress across three fronts: quantum computing hardware development; quantum error correction; and revised estimates of the resources required for quantum computers to break current cryptographic schemes; as motivation for setting an ambitious internal target ahead of the regulatory horizon. This tightened deadline places particular pressure on existing Internet protocols that rely on classical key exchange primitives for secure communication. Our work aims to ease this transition by constructing a unified, formally analyzed security framework for migrating classical key exchange constructions to their post-quantum counterparts.

Lattice signatures face a strict trade-off among compactness, implementation simplicity, and reliance on standard lattice assumptions: ML-DSA-44 requires a 2420-byte signature (3732 bytes combined) and HAETAE-120 takes 1474 bytes (2466 bytes combined), while Falcon-512 achieves 555 bytes but relies on complex floating-point arithmetic. We propose SHUTTLE, a compact Fiat–Shamir signature built on a standard MLWE public-key structure with unforgeability bound to MSIS in the random oracle model. At NIST Level I, SHUTTLE achieves a signature size of 1175 bytes (and 2167 bytes combined)—a 51% reduction in signature size over ML-DSA-44 and 20% smaller than HAETAE-120 using purely integer arithmetic. SHUTTLE resolves prior compact schemes’ limitations via three core techniques: (1) replacing secret-dependent rejection in the iterative sampling loop with a deterministic transition bounded by Rényi divergence, relegating restarts solely to public bounds and encoding checks (occurring with negligible probability $\approx 2^{-30}$); (2) reformulating transition logic in the logarithmic domain into simple integer interval comparisons; and (3) employing an asymmetric stretch-and-compress mechanism to offset MLWE parameter expansion. By eliminating secret-dependent rejection from the inner loop, SHUTTLE achieves constant-time execution with fast signing (1406k cycles, about $3\times$ faster than HAETAE-120) and verification faster than ML-DSA-44.

Side-channel leakage certification aims to quantify what an attacker can learn about a secret variable from observed leakage. Existing information-theoretic estimators, such as perceived information (PI), hypothetical information (HI), and nonparametric mutual information (MI), aim to quantify distributional leakage, but they become unstable in high-dimensional traces and do not provide a finite-sample certificate of the best attacker. We introduce \emph{Bounded Information} (BI), a probably approximately correct (PAC)-style finite-sample certification method that upper-bounds the exact-recovery success of a fixed attacker scope on unseen traces. The attacker suite certificate, $\mathrm{BI}^{\mathrm{suite}}$, applies a KL-binomial confidence interval with a union bound over a fixed suite that contains every trained attacker, preprocessing choice, and hyperparameter. BI therefore turns standard profiled-attack evaluation into an auditable certificate with an explicit attacker scope and confidence level. We further define $\mathrm{BI}^{\mathrm{loc}}(\varepsilon)$ to bound the recovery success of attackers whose normalized scores differ by at most $\varepsilon$ from those of a model in the suite. Across eight side-channel benchmarks with trace dimensions up to $7{,}000$, BI provides stable certificates without density estimation, and its tightness diagnostics tell an evaluator whether a certified value is a genuine measurement of leakage or a conservative bound that more attack traces would tighten.

Does refreshing payload bits hide a fixed geometric watermark carrier when covariance is uninformative? For a Gaussian latent model with independently refreshed fair angular bits, we derive an exact fourth-order signature and a sharp relation between uniform decoding margin and distributional hiding. A fixed-probe operator bound has leading sufficient count O(p^3 log(p)/c(a)^2) at fixed rank, accuracy and confidence, where c(a)=sin(2*pi*a)/(2*pi*a). We then prove a dimension-independent centered fourth-tensor covariance bound whose constant (1+|c(a)|)^2 is attained when there are at least two carrier blocks. This yields a public finite-sample overlap certificate for any candidate subspace frozen before independent validation. The statistic needs no secret key and is computed by streaming projected fourth moments. For all eight archived outputs at p=240, 65,536 new directions per output give positive known- and unknown-scale lower bounds, with at least 95% simultaneous coverage for sixteen statements under the exact model. An exact working-subspace signal criterion and rank-dependent noise formula explain limits of subspace feedback. The main eight-seed training panel attains mean overlap 0.5999 against 0.3282 with a frozen initial frame at equal feature count. A noise-reducing variant improves feature-matched pilots but loses a near-compute-budget comparison; this negative result is retained. A complementary radial model provides directed population witnesses and a conditional certificate for a linear PNG carrier. The results identify and validate latent carrier subspaces; they do not establish adaptive training convergence, bit recovery or a neural watermark attack.

Zero-knowledge proofs (ZKPs) based on vector oblivious linear evaluation (VOLE) excel in prover efficiency but typically require linear communication and verification. Antman (Weng et al., CCS '22) introduced information-theoretic polynomial authentication codes (IT-PACs) to achieve sublinear communication: $O(B + C)$ for SIMD (single-instruction-multiple-data) circuits and $O(B^3 + C)$ for general circuits, where $N=B \cdot C$ is the total circuit size and $B,C$ are batch size and subcircuit size, respectively. Antman++ (Bui et al., J. Cryptol. '25) further reduced the general-case communication to $O(B + C)$. However, these protocols remain interactive and cannot be made non-interactive via traditional techniques like Fiat-Shamir, due to limited functionalities of IT-PACs; also, the verifier of Antman++ is not succinct for processing $N\times N$ public matrices.

In this work, we present a succinct non-interactive ZKP system $\mathsf{Wasp}$. Specifically, (1) we enhance the IT-PAC primitive to a fully functional polynomial commitment scheme (PCS) with the support of generic evaluation openings. With this PCS, we construct $\mathsf{Wasp^S}$, a non-interactive ZKP for SIMD circuits based on Antman; also, we build $\mathsf{Wasp^G}$, a general zkSNARK with constant verifier time and proof size based on the Plonkish constraint system. (2) We optimize the SIMD-to-general compiler from Antman++ by exploiting sparse representation of matrices and extending preprocessing techniques to the SIMD setting, and achieve a sublinear verifier. All our protocols achieve non-interactivity in the VOLE-hybrid model (i.e., given preprocessed VOLE correlations).

Experiments show the non-interactive verifier of our SIMD zkSNARK $\mathsf{Wasp^S}$ is $1\sim 2$ orders of magnitude faster than the interactive one of Antman; when compiled with our compiler, the general-case verifier is $2\sim 3$ orders of magnitude faster than the one in Antman++. Our general zkSNARK $\mathsf{Wasp^G}$ has a $1\sim 2$ orders of magnitude faster prover than pairing-based, coding-based and lattice-based zkSNARKs, with less than 1 ms verifier time and 122 KB proof size; compared to the non-succinct VOLE-based ZKP, $\mathsf{Wasp^G}$ is $3\sim22\times$ slower in proving but can be 4 orders of magnitude faster in verification with $3$ orders of magnitude smaller proof size.

Virtually all deployed private payment systems publish a nullifier for every transaction to prevent double spending. At a million transactions per second, the nullifier set grows by a petabyte each year. In this work, we tackle the question of sustaining massive throughput in private payments while ensuring the system can be run on commodity hardware.

We construct Bonsai, an account-based private payment scheme where validators store a single commitment per account and never store any nullifiers. Instead, each user privately maintains the nullifiers of the payments it has received, and can prune older nullifiers to cold storage so that its active state remains small. An external observer only learns that an account performed some action (send/receive) but never learns the amount or counterparty of a payment.

To verify proofs at this rate, we add zero-knowledge to Pari [USENIX '26] with no increase in proof size and negligible prover overhead, and use it with a batch verification strategy. Our prototype verifies over a million operations per second on an M5 MacBook Pro.

We report on the solution to the TII-254 McEliece key recovery challenge -- currently the hardest solved challenge under the original brute-force metric ($2^{254}$). The parameters of TII-254 are $(m,t,n) = (8,12,223)$, defining a binary $[223,127]$ code specified by a full-rank $(96 \times 223)$ parity-check matrix. We state the method as a thirteen-step process, separating heuristic and non-heuristic choices. At a high level, we computed two complete $121$-dimensional relation kernels conditioned at distinct public coordinates, combined them to isolate a certified $80$-dimensional pair core, removed a $64$-dimensional common nuisance space, and identified the remaining $16$ dimensions as an $\mathbb{F}_{2^8}$ projective-line geometry. This yielded all $87$ visible locators, after which a deterministic completion search recovered the full support and polynomial. The two final Krylov sequences alone used $27.2$ GPU-hours on NVIDIA GH200s, excluding GPU reconstruction and CPU processing. We provide a self-contained artifact with compact recovery inputs and code, an independent key verifier, and Lean proofs of the reusable linear-algebraic steps.

Are private set intersection (PSI) protocols ready for the post-quantum future? We focus on the PSI protocol of Rosulek \& Trieu (``RT21'', ACM CCS 2021), which is the current state-of-the-art for PSI on small sets (less than a thousand items). The RT21 protocol presents some fundamental barriers to post-quantum security. First, although it is written in terms of an arbitrary KEM, it requires certain properties of Diffie-Hellman KEM that simply are not satisfied by any post-quantum candidates. Second, even if adapted to post-quantum KEMs, it would require an ideal permutation with blocklength larger than any known viable candidate.

We show how to modify the RT21 to make it compatible with post-quantum KEM candidates like ML-KEM. We also describe a direct domain-extension construction for ideal permutations, showing how to construct a huge-block ideal permutation directly from one with smaller blocklength, such as the Keccak permutation family. Along the way, we also introduce new abstractions for \emph{oblivious key-value stores} (Garimella et al., Crypto 2021) that make the analysis of these kinds of PSI protocols more modular.

We implemented our protocol and evaluated its performance across different network settings and instantiations. We achieve PSI from standardized post-quantum primitives with latency as low as $0.25$ ms/item and communication as low as $1.67$ KiB/item. We find that the performance penalty for post-quantum security ranges from 1.25$\times$ to 5.92$\times$ in latency and is 16.7$\times$ in communication, depending on the instantiation.

Ghoshal, Ishai, Jain and Sun (GIJS) recently gave the first distinguisher for Classic McEliece public keys that is cheaper than generic decoding. They estimate its cost at $2^{114}$ to $2^{124}$ bit operations for the five NIST candidate parameter sets, and have since extended it to a key-recovery algorithm. The distinguisher is one large sparse linear-algebra computation. We show that this computation already contains the secret key, and we give two ways to extract it.

The first method uses the polynomials that the distinguisher computes. For each column of the public key, their gradients span a subcode of the public code, and we prove which subcode this is. Once the subcode is known for every column, the support and the Goppa polynomial follow by linear algebra. The cost is that of about $100$ to $1400$ runs of the distinguisher, depending on the parameter set. The second method builds on the key-recovery algorithm of GIJS and reads the whole support from a single run.

We also lower the cost estimate of the distinguisher itself by about $20$ bits. This uses two facts about binary Goppa codes that we prove and two heuristic assumptions that we test. In the cost model of GIJS, key recovery then costs $2^{94}$ to $2^{102}$ bit operations, or $2^{114}$ to $2^{124}$ if every condition and formula of GIJS is kept unchanged. Information-set decoding costs $2^{151}$ to $2^{287}$.

As a demonstration, we ran the single-run attack on the highest-numbered instance of the TII McEliece key-recovery challenges (label 253: $m=8$, $t=9$, $n=214$), which had not been solved, and recovered its secret key. This took two sparse kernel computations with about $10^7$ unknowns each, at about $700$ core-hours each on one server.

None of the Classic McEliece computations is close to practical, and several ingredients are heuristic. We state each heuristic as an explicit assumption. We test each one by running the attacks end to end on small keys and, for the parts that do not need the expensive run, at full Classic McEliece size.

Lattice-based polynomial commitment schemes (PCSs) promise post-quantum SNARKs with two properties that elliptic curves provide and hash-based schemes, today's deployed post-quantum default, do not: concretely small proofs and commitment time proportional to the number of nonzero entries in the committed polynomial rather than its length. The second property is essential to Twist and Shout (CRYPTO 2026), the fastest known memory-checking arguments and a core component of the Jolt zero-knowledge virtual machine (zkVM): their prover commits to enormous polynomials that are almost entirely zero. Yet despite a wave of recent work, existing lattice-based PCSs achieve at most two of the three properties that deployment demands: small proof size, fast verification, and soundness from standard assumptions such as Module-SIS.

We present Akita, a lattice-based PCS that achieves all three. We improve on the square-root-time verifier of Hachi (ePrint 2026), our direct predecessor, through a new setup offloading technique: the public setup matrices are committed ahead of time, and the verifier's work in processing them is deferred and proved against these commitments. For any fixed $k\ge2$, this reduces verification time to $\widetilde O_{k,\lambda}(N^{1/k})$ while preserving $\widetilde O_{k,\lambda}(\log N)$ proof size, $\widetilde O_{k,\lambda}(N)$ prover time, and security from standard Module-SIS. We also optimize every fold from root to tail and iterate the fold to completion. This includes an optimized digit range check, relation-specific ring dimensions and subring challenges, complementary methods for embedding field evaluations and checking ring relations, commitments compressed to $128$bytes each, and exact Euclidean norm checks for tighter Module-SIS parameters.

Beyond the core protocol, Akita provides the capabilities needed for deployment in a zkVM: batched openings of separately committed polynomials, low-communication distributed proving, and an offline planner for selecting secure parameters under configurable cost objectives. We implement Akita in Rust and benchmark it against existing lattice-based and hash-based PCSs. Across these benchmarks, Akita produces proofs of only $61$-$70$KB, matching Greyhound's when both schemes are calibrated to the same security level, while verifying $10\times$ to $94\times$ faster. Akita's prover uses the least memory: beyond storing the polynomial itself, its memory overhead grows sublinearly in the polynomial size. We also integrate Akita into Jolt. For every program size we evaluate, Jolt-with-Akita achieves a $1.3\times$ to $2.2\times$ prover speedup and $2.2\times$ to $7.4\times$ verifier speedup over Jolt-with-Dory, while matching it in proof size, with every proof remaining below $100$KB.

The alternative mod-$2$/mod-$3$ function is one of the most widely used weak PRF constructions in modern cryptographic protocols. Despite its practical importance, its security has received relatively limited attention, with the main cryptanalytic results consisting of two distinguishing attacks due respectively to Cheon et al. and Johansson et al. In this work, we revisit the cryptanalysis of this primitive by analyzing the output distribution of the weak PRF under fixed Hamming weights for both the secret key and the inputs. This refined analysis allows us to isolate and amplify statistical biases that were averaged out in previous works. Using this approach, we derive a new distinguishing attack with asymptotic data and time complexity $\mathcal O(2^{0.099n})$. We implemented the attack for the original parameter set $n=384$, thereby obtaining the first practical attack against this instance of the construction. We then introduce a generic technique, called the splitting strategy, which consists in partially fixing or guessing part of the secret key in order to amplify the biases while introducing an additional computational cost that can be efficiently handled using Fast Fourier Transform-like techniques. This leads to the currently best known attack against the construction, with asymptotic data, time, and memory complexities $\widetilde{\mathcal O}(2^{0.09n})$. This last technique also provides a useful time-memory trade-off for estimating the security of real-world constructions when the available data is bounded: we show that the weak PRF offers less than $128$-bit security for $n = 510$ when the data is limited to $2^{45}$. Finally, we revisit the attack of Johansson et al. and provide a corrected and refined analysis of the underlying bias, showing that the statistical behavior of the attack differs significantly once the Hamming weight of the secret key is taken into account. This new analysis explains phenomena previously observed experimentally but left unexplained. Thanks to this approach we are able to identify a large class of keys for which the attack performs much better asymptotically than anticipated by Johansson et al.

When looking at authenticated encryption schemes, we have schemes that process the input data by having serial calls to their underlying building blocks, like duplex-based constructions, and schemes that allow for parallel calls to their underlying building blocks, like the Galois Counter Mode (GCM). Naturally, one can parallelize a serial scheme by distributing the data to encrypt over different calls to the serial scheme. However, there are many different choices to be made, like how to choose the nonce for the different instances, or if and how to combine the multiple tags into a single one. In this paper, we investigate different possible choices providing proofs for their security. Interestingly, we see a huge variance in the provable properties and hence, the security in making a serial scheme parallel. Or, motivating the problem more generally, we are investigating tag combiners, where the single tags to be combined are secret to the adversary.