International Association
for Cryptologic Research

Bootstrapping is the computational bottleneck of BGV/BFV fully homomorphic encryption, scaling particularly poorly with large plaintext primes. Its two dominant stages: digit extraction and linear transforms. Recent work has reduced the digit-extraction polynomial degree via null-polynomial lattices and bounded-support constructions, but both evaluate the reduced polynomial via generic Paterson--Stockmeyer at cost $O(\sqrt{d})$ .

We present two algebraic optimizations that address both stages simultaneously. For digit extraction, we prove that choosing the auxiliary radix $A$ with $A^2\equiv -1\pmod{p}$ induces an order-four character filter, forcing the canonical digit-extraction polynomial to satisfy $P_A(AX)+AP_A(X)=AX$ and eliminating all monomials $X^k$ with $k\not\equiv 1,3\pmod{4}$. The resulting structured decomposition$P_A(X)=\tfrac{1}{2}X+X^3Q(X^4)$ reduces non-scalar multiplications from $O(\sqrt{d})$ to $O(\sqrt{d/r})$. For linear transforms, we provide first concrete instantiation of a Galois-structured mixed-radix butterfly decomposition for non-power-of-two cyclotomics, reducing the automorphism count from $O(\sqrt{D})$ to $O(\log D)$. On the standard NTT-friendly large-prime set ($p=65537$, $m=2^{16}$, $32768$ slots), our single-threaded \HElib{} implementation achieves a $1.85\times$ digit-extraction speedup ($20.06$s to $10.81$s) and a $1.27\times$ total thin-bootstrapping speedup ($42.3$s to $33.3$s) over the state-of-the-art Ma et al.\ baseline, the three stages the method does not touch moving by at most one per cent. All comparisons are made against the Ma et al.\ baselines, run in the identical pipeline at the same auxiliary radix; across nineteen encrypted parameter sets with $1297\le p\le 65537$, the digit-extraction speedup is $1.72$--$1.88\times$ on general cyclotomic rings ($37637\le m\le 65047$) and $1.84$--$2.13\times$ on the power-of-two ring $m=2^{16}$. Every set we recommend is quoted with concrete bit security.

Event date: 16 November to 20 November 2026

The Department of Computer Science at the University of Oxford is seeking to appoint two full-time Associate Professors or Professors of Computer Science to start on 1 September 2027. Each post is associated with a college, one with a Tutorial Fellowship at Wadham, the other with an Official Studentship at Christ Church (the Christ Church equivalent of a Tutorial Fellowship). Duties will include undertaking original research in Computer Science, securing funding to support the Department’s research activities, together with teaching and supervision responsibilities for the Department of Computer Science and the College, and Trustee duties (as a member of the Governing Body) at the College. Applicants should hold a doctoral degree in Computer Science or a closely related discipline, have the ability to teach across a range of Computer Science subjects, and will also have a proven research track record of internationally high quality in Computer Science. Applicants should be able to demonstrate a high standard of research potential and achievement depending on experience, and the ability to enthuse and inspire students at both undergraduate and graduate level through tutorials, classes, lectures, and supervision. The University of Oxford uses the grade of Associate Professor for most of its academic appointments. Appointments to Associate can include those at the start of their careers directly from PhD, as well as more established researchers. The Department and colleges offer an exciting research and teaching environment, and an attractive financial package to the successful applicants. Please refer to the Further Particulars for details of the wider benefits package offered by the University and by each of the two colleges. All applicants will automatically be considered for both posts - please do not mention a particular college in your application. Demonstrating a commitment to provide equality of opportunity, we would particularly welcome applications from women and black and minority ethnic applicants who are currently under-represented within the CS Department. All applicants will be judged on merit, according to the selection criteria.

Closing date for applications:

Contact: HR Team

More information: https://my.corehr.com/pls/uoxrecruit/erq_jobspec_version_4.display_form?p_company=10&p_internal_external=E&p_display_in_irish=N&p_process_type=&p_applicant_no=&p_form_profile_detail=&p_display_apply_ind=Y&p_refresh_search=Y&p_recruitment_id=185766

Employment type: Fixed-term contract, full-time, 2 years
Remuneration: Level A6 $118,467 + leave loading + 17% super
Location: UNSW Canberra, ADFA Campus

Work rights required: Visa sponsorship is not available for this position. Candidates must hold full rights to work in Australia to be considered for this position.

Who You Are (skills and experience):

• A PhD in Computer Science or Math or a relevant area/discipline that complements the breadth of expertise of the School.
• Candidates with PhD thesis submissions are also welcome. It is expected the PhD degree will be obtained within a short time before the commencement of the job.
• A demonstrated ability to conduct innovative and independent research in the field.
• A record of publications in high-quality journals and/or conferences in the field. Some typical venues include, Crypto, Eurocrypt, CCS, NDSS, IEEE TIFS and IEEE TPAMI.
• A strong background in post-quantum cryptography or applied cryptography. A strong math background in related areas such as coding theory will also be considered.
• Capability of applying deep learning models and willingness to use them for biometrics research required in the project.

  Eligibility: Visa sponsorship is not available for this position. Candidates must hold full rights to work in Australia to be considered for this position.

  How to Apply:
  Make each day matter with a meaningful career at UNSW. Submit your application online before Monday 28 September 2026 at 11:30pm. In order to view the position description, please ensure that you allow pop-ups for https://www.jobs.unsw.edu.au

  Closing date for applications:

  Contact:
  For role-related queries please contact:
  Jiankun Hu - Professor [email protected]
  
  For recruitment process-related queries please contact:
  Holly Whale – Talent Acquisition Partner [email protected] Applications cannot be accepted if sent directly to the contact listed.

When communication systems are subject to strict external control, a powerful authority may monitor all transmitted messages and compel users to surrender their secret keys, thereby undermining user autonomy and the confidentiality of keys in encrypted communication. Anamorphic encryption (AE) enables covert communication under such surveillance by embedding hidden messages into innocent-looking ciphertexts. However, existing lattice-based AE constructions remain limited and typically rely on lattice trapdoor techniques, which impose restrictive parameter requirements and hinder their deployment in practical post-quantum cryptosystems such as Kyber. Moreover, existing constructions do not address the challenge of enabling covert communication among multiple parties under dictator-controlled environments. In this work, we propose \textbf{Threshold Anamorphic Encryption (TAE)}, a new cryptographic primitive that extends receiver-AE to the \textbf{$N$-out-of-$N$ threshold setting}, where the covert message can be recovered only through the collaboration of all $N$ participants. Then we propose \textbf{TAKyber}, a concrete instantiation of TAE constructed from the KyberPKE framework. TAKyber embeds covert information into the randomness of ciphertexts rather than the public matrix structure, avoiding the large aspect-ratio requirement imposed by lattice trapdoor techniques and enabling deployment on Kyber and other lattice-based encryption schemes whose public matrices do not satisfy such requirements. Furthermore, TAKyber distributes covert information into multiple components during encryption and enables \textbf{all $N$ participants to jointly reconstruct the covert ciphertext}, while preventing any subset of fewer than $N$ participants without the double key from obtaining any information about the covert message. Finally, we apply TAKyber to privacy-preserving federated learning, where participants can securely exchange encrypted model gradients while simultaneously transmitting covert information through the anamorphic channel under dictator-controlled environments.

In this work we present a new variant of the non-interactive key exchange (NIKE) scheme based on the learning with errors (LWE) assumption and prove its security with a security reduction that incurs a security loss that is only linear in the number of users. This improves upon all prior reductions for lattice-based NIKE schemes, which had a security loss that is quadratic in the number of users. Our tight reduction can handle the setting with super-polynomial modulus-to-noise ratio and negligible correctness error as well as the more challenging setting with polynomial modulus-to-noise ratio and inverse polynomial correctness error.

We also give a matching lower bound on the tightness for a natural class of lattice-based NIKE schemes (that captures all existing variants of lattice-based NIKE), showing that our security loss is optimal (up to constant factors). This generalizes a lower bound by Hesse, Hofheinz and Kohl (Crypto 2018) and is the first lower bound for the tightness of lattice-based NIKE schemes. Several previous lower bounds for the tightness of NIKE exist, but none of them can be applied to lattice-based schemes.

Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS) gave a $2^{n+o(n)}$ time algorithm for the Shortest Vector Problem (SVP) based on discrete Gaussian sampling (DGS), together with an honest sampler producing $2^{n/2}$ samples above the smoothing parameter in $2^{n/2+o(n)}$ time and space. Gao, Feng, and Hu (GFH) subsequently introduced DGS on random prime-index superlattices, making this sampler available at the shortest vector scale and obtaining a $2^{0.7314n+o(n)}$ time algorithm. In a different direction, the Becker--Ducas--Gama--Laarhoven (BDGL) sieve uses spherical product codes to find correlated pairs and runs in $2^{0.2925n+o(n)}$ time under the random list heuristic.

We combine the random superlattice DGS framework with a single BDGL product code decoding layer. The algorithm splits the DGS output into two lists. For a fixed shortest vector $v$, the Gaussian midpoint identity turns the event $X-Y=v$ into a birthday event, while equal quotient labels certify that the reported difference belongs to the input lattice. The product code decoder locates the corresponding pair without enumerating all pairwise differences.

Our analysis makes no random list assumption. For a fixed shortest vector $v$, once the retained lists contain a pair $x,y$ with $x-y=v$, the BDGL product code finds that pair with high probability. We extend the product code analysis so that this guarantee is compatible with the claimed time and space bounds. A centered quotient line gives a $2^{0.5822n+o(n)}$ time algorithm. We then replace the line through the zero residue with a random affine translate. This lets us target a rarer midpoint shell. As a result, we obtain a randomized classical algorithm for SVP that runs in $2^{0.5596n+o(n)}$ time and uses $2^{n/2+o(n)}$ space.

ARX-based cryptographic primitives have received considerable attention for their efficient software implementations. For a long time, however, constructing ARX primitives with provable resistance against single-trail differential and linear cryptanalysis remained an open problem. Dinu et al. addressed this problem by introducing the Long Trail Strategy (LTS), the first general design strategy for establishing such bounds for ARX symmetric-key primitives. A remaining challenge in applying LTS is the systematic design and analysis of large-state S-boxes that combine efficient implementation with strong multi-iteration differential and linear bounds. More recently, Yan et al. introduced a general framework for designing and analyzing such S-boxes, with the AFS family serving as a concrete instantiation. Given their excellent multi-iteration security bounds and outstanding software implementation efficiency, AFS boxes offer a viable solution to the core challenging problem in ARX cryptography—systematic design, accurate analysis, and the pursuit of an extreme and compact balance between cryptographic security and implementation performance. We thus argue that the potential of AFS boxes as nonlinear components in LTS-based primitives has long been undervalued. To demonstrate this potential and address the broader design challenge, we use AFS-64 to construct APEX, an efficient and extensible family of cryptographic permutations spanning state widths from 64 to 1536 bits.

We then instantiate APEX in a broad range of symmetric primitives to demonstrate its extensibility and translate the security and implementation advantages of AFS into complete cryptographic designs. These include small-state hash functions and extendable-output functions, authenticated encryption with associated data (AEAD) schemes, an ultralightweight block cipher, large-state block and tweakable block ciphers, and large-state hash functions based on the Sponge-F mode and designed for China's Next-Generation Commercial Cryptographic Algorithms program. We derive differential and linear long-trail bounds for the underlying permutations and adapt the long-trail analysis to rate-restricted, same-capacity, and related-tweak settings. Together with analyses of other major attack classes, these results support the selected step counts and the stated security claims.

Optimized implementations on 8-bit AVR, 32-bit ARMv7-M, and x86-64 demonstrate the practical software efficiency of APEX across diverse processor architectures. For 64-byte (resp. 1536-byte) messages, the small-state APEX-HASH functions achieve $1.14\text{--}1.37\times$ (resp. $1.14\text{--}1.17\times$) and $1.15\text{--}1.16\times$ (resp. $1.18\text{--}1.20\times$) the throughput of the corresponding Esch instances on AVR and ARM, respectively. The small-state APEX-AEAD schemes similarly achieve $1.17\text{--}1.48\times$ (resp. $1.14\text{--}1.19\times$) and $1.15\text{--}1.19\times$ (resp. $1.12\text{--}1.15\times$) the throughput of the corresponding Schwaemm instances. For the large-state hash functions targeting the NGCC program, $\mathrm{APEX}_{1536}^{12}\text{-HASH-F-512}$ achieves $2.09\times$ and $2.88\times$ the throughput of the fastest listed SHA3-512 implementations on x86-64 and ARM, respectively, for a 1-MiB message. The higher-security $\mathrm{APEX}_{1536}^{16}\text{-HASH-F-768}$ and $\mathrm{APEX}_{1536}^{20}\text{-HASH-F-1024}$ profiles achieve 6.02 and 11.82 cycles/byte on x86-64, and 123.72 and 239.63 cycles/byte on ARM, respectively. For block-cipher applications, the ultralightweight $\mathrm{APEX}_{64}^{8}\text{-BC-128}$ achieves encryption and decryption speedups of $1.18\text{--}1.21\times$ over CRAX-S across AVR and ARM, while the large-state $\mathrm{APEX}_{256}^{15}\text{-BC-256}$ achieves $1.77\times$ and $1.65\times$ speedups over SATURNIN-256/256 for encryption and decryption on ARM, respectively. The tweakable block cipher $\mathrm{APEX}_{256}^{15}\text{-TBC-256/128}$ achieves $1.38\times$ and $1.39\times$ speedups over TRAX-L for encryption and decryption, respectively. Taken together, these results show that APEX combines extensibility across state sizes and primitive classes with efficient software implementations on markedly different processor architectures.

We propose the arithmetization-oriented (AO) hash function Arion, following a permutation-based design approach. We first define the permutation Arion-π over the finite field F_p, where (p > 2) is prime. The design of Arion-π is based on the recently introduced generalized triangular polynomial system, a novel algebraic framework for constructing cryptographic permutations using polynomials over finite fields. Using this permutation, we define the hash function Arion in two modes: the well-established Sponge construction and a feed-forward truncation mode (Trunc). Secure parameter sets are specified for prime fields commonly used in zero-knowledge proof applications, including the scalar fields of the BLS12-381 and BN254 elliptic curves.

We provide an extensive security analysis of Arion, with particular emphasis on algebraic techniques — including interpolation and polynomial system solving (PoSSo) based techniques, such as Gröbner basis computations, and resultants — which are especially relevant for cryptographic primitives defined over prime fields. To the best of our knowledge, Arion is the first hash function whose security analysis is explicitly based on the algebraic invariant of the underlying ideal - the quotient ring dimension. In particular, we explicitly determine the dimension of the quotient ring associated with the CICO problem induced by the hashing modes. Furthermore, our analysis of the CICO-t problem applies to any t ≥ 1 and covers both the Sponge and feed-forward constructions.

We evaluate the efficiency of Arion across several arithmetization frameworks — R1CS, Plonk, and AIR — and compare it with prominent AO hash functions, including Poseidon, Poseidon2, Anemoi, Griffin, and Rescue. Our results show that Arion is frequently the best-performing design in the Plonk setting and remains highly competitive, often ranking second, in both RoneCS and AIR. In terms of native performance, Arion is the only construction based on high-degree power maps that achieves performance comparable to Poseidon/Poseidon2. This makes it an attractive choice for applications where both zero-knowledge proving efficiency and native evaluation costs are important considerations.

Coordinate-wise extraction in lattice folding naturally produces source openings normalized by challenge differences, while an inconsistency branch must ultimately yield a short integral SIS relation. Branchwise polynomial integralization converts each extracted tuple under one common multiplier before comparing the tuples; this collects the local challenge slacks into a global product and can push the resulting relation outside the useful shortness regime.

We retain each local normalization until the two extracted tuples are compared. The resulting integral kernel relation depends only on local slack factors. In the sequential interactive setting, we realize this comparison by synchronizing two successful coordinate stars at the same numerical folding challenge. The remaining difficulty is probabilistic: the common challenge is inherited from a successful execution and is therefore success-biased. Acceptance-weighted shared-root synchronization gives additive raw extraction loss and linear unconditional expected retry-invocation complexity.

For a Cyclo-compatible instantiation, this changes the concrete extraction regime. At arity two, the coefficient radii for local comparison and branchwise integralization have base-two logarithms 25.04 and 49.63, respectively, while the coefficientwise centered-modulus threshold is about 49. We also instantiate the required short unit-difference challenge interface and give a one-fold classical-ROM compilation.

Arithmetic logic unit (ALU) can combine word-level arithmetic with bit-level logic on encrypted machine words. Triangle encoding provides a CKKS-based representation for leveled word arithmetic, but its existing arithmetic-to-Boolean (A2B) conversion recovers only one window per bootstrapping. Consequently, converting an \(\ell\)-bit message requires \(\Theta(\ell)\) sequential functional-bootstrapping on the critical path of each input ciphertext.

We first extend Triangle encoding from binary to general digit bases, allowing a larger base to shorten each Triangle word and increase the number of packed words per ciphertext. We then introduce shared overflow cancellation. For block modulus \(B=d^\omega\) and bounded overflow \(\lvert I_k\rvert
We implement the proposed A2B conversion in OpenFHE and evaluate it for 64-, 128-, and 256-bit words. In a same-machine, single-threaded comparison with Gao--Zheng, base \(d=2\) achieves the lowest single ciphertext latency, yielding \(2.55\times\)--\(6.25\times\) speedups. Base \(d=4\) packs more words into each ciphertext and achieves the best amortized performance, yielding \(4.00\times\)--\(8.71\times\) speedups.

Polynomial commitment schemes (PCSs) are fundamental building blocks of modern zkSNARKs and often dominate their concrete prover and verifier costs. We introduce $\mathsf{Quasar}$, a field-agnostic PCS for multilinear polynomials that combines Quasi-Abelian (QA) codes with BaseFold (Zeilberger et al., CRYPTO 2024) through code switching (Ron-Zewi and Rothblum, JACM 2024). For a polynomial of length $N$ and security parameter $\lambda$, $\mathsf{Quasar}$ achieves concretely fast $O(N\log N)$ commitment, $O(N)$ evaluation time, and $O(\lambda\log^2 N)$ proof size and verifier time.

Our starting point is a recent work of Li et al. (CRYPTO 2026), which shows that QA codes have fast encoding and strong concrete distance. This opens the door to building efficient PCSs from QA codes via Brakedown's paradigm (Golovnev et al., CRYPTO 2023). However, a direct instantiation, called QAPCS, inherits square-root proof size and verifier time, falling short of practical efficiency when $N$ is as large as $2^{25}$. We overcome this crucial limitation by showing that QA codes are essentially code-switchable. In contrast to existing code-switching arguments that utilize algebraic structures of either generator matrices or parity-check matrices, we look into QA encoding algorithms and propose an efficient encoding-oriented argument. Consequently, $\mathsf{Quasar}$ simultaneously enjoys fast proving from QAPCS, and polylogarithmic verification of BaseFold.

We implement $\mathsf{Quasar}$ over the 127-bit Mersenne prime field with rate $1/2$ and 100-bit security. Under the 32-thread CPU setting, $\mathsf{Quasar}$ accelerates commitment and evaluation over BaseFold by $13.6\times$--$20.6\times$ and $5.2\times$--$63.8\times$, respectively. It is also $2.2\times$--$6.0\times$ faster in commitment than Brakedown and $2.1\times$--$4.0\times$ faster in commitment and $17.4\times$--$237.6\times$ faster in evaluation than BrakingBase, while providing smaller proofs and faster verification than both. Compared with QAPCS, it achieves up to $4.3\times$ faster verification and $2.9\times$ smaller proofs. Moreover, we observe that QA encoding naturally exposes massive parallelism, enabling a GPU acceleration strategy that is not directly available to the other code families. Across message lengths from $2^{12}$ to $2^{25}$, the GPU encoder is $32.9\times$--$148.3\times$ faster than the 32-thread CPU implementation. Over polynomial sizes $2^{20}$--$2^{29}$, the commitment with GPU acceleration further achieve a $3.4\times$--$16.7\times$ speedup relative to its 32-thread CPU implementation.

The Fiat--Shamir (FS) transformation is a technique that converts interactive protocols into non-interactive ones. FS is secure in idealized models such as the random oracle model (ROM) (if the interactive protocol satisfies a condition known as state-restoration soundness).

It is known that there are protocols whose FS transformation is secure in the ROM, yet insecure when instantiated with any concrete hash function. Historically, these protocols were contrived (as in, they were designed so their FS transformation would be unsound). Khovratovich, Rothblum and Soukhanov (CRYPTO 2025) showed that a class of natural (and practically deployed) protocols based on a protocol of Goldwasser, Kalai and Rothblum (JACM 2015) was also unsound when compiled with FS and any concrete hash function.

We extend the attack to a different class of protocols: those whose instances are generated by running a program.

This setting covers concrete trends in modern proof systems, in which the computation to be proven is described by a program (often adversarialy generated) which is then either compiled or autonomously converted into an instance of target relation such as rank-1 constraint satisfaction (R1CS). We show that, when the conversion process is "expressive enough", an adversary controlling the program code can break soundness of the non-interactive proof system.

The attacks generalize to a wide class of protocols: any protocol in which a cheating prover can prepare an accepting transcript before the statement is bound. We show that variants of the Spartan (CRYPTO 2020) and Aurora (EUROCRYPT 2019) proof systems for R1CS fall in this class.

Complementing the attacks, we formalize a mitigation: deriving the first Fiat--Shamir challenge from the generated statement, rather than from the program that generates it, provably reduces the soundness of the compiled protocol to that of the underlying protocol for the non-generated relation.

ChaCha is one of the most extensively deployed symmetric ciphers. The security margin of ChaCha is directly related to the safety of many widely used lightweight security protocols and operating systems for constrained devices, such as TLS 1.3, SSH, Noise, WireGuard, S/MIME 4.0, Linux, Android, Chromium/Chrome, Firefox and Safari. This paper introduces a novel \textit{guessed key covering technique}. The objective of this technique is to identify partitioning-based functions whose required key bits are covered by those guessed for bit puncturing-based functions, enabling them to be processed jointly. Building on this, we propose a refined framework for differential-linear cryptanalysis of ChaCha called \texttt{ReBitP}, which combines the ideas of the bit puncturing technique, the partitioning technique and a two-phase distillation strategy. The key insight of \texttt{ReBitP} is to incorporate a carefully selected set of functions that are evaluated using the partitioning technique with different tail lengths into the first phase, without requiring additional key bits to be guessed. This early filtering via parity checks simultaneously lowers the time cost of the first phase and the time complexity of constructing the distillation table in the second phase. As applications, enhanced key recovery attacks on 7- and 7.5-round ChaCha256 are presented, achieving time complexities of $2^{142.08}$ and $2^{242.02}$, respectively. The cryptanalytic results are $2^{6.12}$ and $2^{1.58}$ times faster than the existing attacks, respectively. So far as we know, these are the best known key recovery attacks on 7- and 7.5-round ChaCha256. This definitely demonstrates the superiority of the refined framework \texttt{ReBitP}.

Efficiently supporting both arithmetic operations and logic operations in Fully Homomorphic Encryption (FHE) is an essential step towards general-purpose privacy-preserving computation. Recently, Gao and Zheng (Crypto'26) introduced a triangle encoding for arithmetic computation over $n$-bit machine words, with the refreshing cost of $O(1)$ CKKS bootstrapping operations. Notably, the triangle encoding can be converted to the discrete-CKKS encoding for supporting logic operations, with the cost of amortized $O(1)$ CKKS bootstrapping for $O(n)$ input ciphertexts, or $O(n)$ CKKS bootstrapping operations for a single input ciphertext. It remains open whether there is a cheaper conversion method for a single input ciphertext. In this work, we propose a new conversion method to discrete-CKKS encoding for a single ciphertext in triangle encoding, with the cost of $O(1)$ CKKS bootstrapping and additional $O(\log n)$ level consumption. When combined with existing refreshing and conversion methods in Gao-Zheng, we obtain an FHE scheme for SIMD Arithmetic Logic Unit (ALU) with $O(1)$ bootstrapping.

Wagner's $k$-tree algorithm solves the generalized birthday problem and underlies preimage attacks on randomize-then-combine incremental hashes (EUROCRYPT '97) such as iSHAKE, LtHash, and AdHash. In its full-index execution, the $2^{k-1}$ index entries dominate peak memory at large $k$, and index trimming narrows each entry but leaves their number intact. Tang et al. (TCHES '26) introduced post-retrieval for the single-chain algorithm and left the $2^k$ exponent of the $k$-tree setting as an open problem. We resolve it by extending post-retrieval to the $k$-tree algorithm. This cuts the peak working memory to $P_k\ell N = O(k^2 \ell N)$, removing the $2^{k-1}$ index entries from the forward pass at the cost of a $\Theta(k)$ time overhead. Free $\delta$-level caching shrinks this time factor at no memory cost. The trade-off is starkly asymmetric: it removes an exponential number of index entries for only a linear recovery-time overhead.

As a practical application, we revisit the list-item-reduction landscape for the $k$-tree algorithm under the memory-time product metric, $\mathsf{MT} = M \cdot T$. The gain is regime-dependent: for small $k$ the index entries do not yet dominate, so the recovery overhead outweighs the saving. For large $k$ the saving dominates, lowering the optimized $\log_2 \mathsf{MT}$ from $4\sqrt{n}$ to $2\sqrt{2n}$ at leading order. For fixed-size iSHAKE preimage attacks, we save approximately $51$ and $122$ bits over state-of-the-art index trimming for iSHAKE-128 and iSHAKE-256, respectively, in the unlimited-block setting, narrowing to roughly $6$ and $8$ bits under block-count caps.

Pessiland is a world where NP is hard on average but one-way functions (OWFs) do not exist [Impagliazzo 1995]. Because almost all classical cryptographic primitives imply OWFs [Impagliazzo and Luby 1989], there is almost no classical cryptography in Pessiland. On the other hand, quantum cryptography can exist even when OWFs do not [Kretschmer 2021; Morimae and Yamakawa 2022; Ananth, Qian and Yuen 2022]. Is there a quantum analogue of Pessiland where NP is hard on average but even quantum cryptography does not exist? In this paper, we show that such a miserable world, Quantum Pessiland, exists: there is a quantum oracle relative to which $UP\cap coUP$ is hard on average against quantum polynomial-time algorithms with quantum advice, yet auxiliary-input EFI pairs do not exist. We also show that there is a classical oracle relative to which $UP\cap coUP$ is hard on average against quantum polynomial-time algorithms with quantum advice, yet classically-secure auxiliary-input one-way puzzles (OWPuzzs) do not exist. Almost all quantum cryptographic primitives imply EFI pairs or OWPuzzs, and therefore these results mean that there is almost no quantum cryptography relative to these oracles. We further show that relative to the classical oracle, SampBQP = SampBPP, and therefore there is no sampling-based quantum advantage in Quantum Pessiland. Finally, because our average-case hardness of $UP\cap coUP$ implies $P^{\#P}\not\subseteq i.o.BQP/qpoly$, our result also implies that a non-relativizing proof technique is necessary to construct OWPuzzs solely from $P^{\#P}\not\subseteq i.o.BQP/qpoly$, which gives a partial negative answer to the open problem of [Khurana and Tomer 2025].

White-box security settings assume an extremely powerful adversary having full visibility and control of the software implementation and internal computations. Leakage-based attacks extract secret information via a local passive attacker (e.g., malware) and transmit it to a remote server. However, an active adversary, who can perform fault injections in a white box setting, has received limited attention, especially in the symmetric-key setting. In this paper, we initiate a formal study of active data-only adversaries in the white-box setting. Such adversaries preserve the control flow of the implementation but corrupt a bounded number of key-embedded lookup-table entries, enabling precise and repeatable manipulation of table values. Unlike leakage-based attacks, which are constrained by the bandwidth and existence of firewalls, such fault attacks can operate entirely locally. We focus on a data-only tampering adversary that preserves the control flow of the white-box implementation, but corrupts a bounded number of key-embedded lookup-table entries. Even under this stealth-preserving restriction, the adversary can cryptographically weaken the implementation and make faulty ciphertexts significantly easier to decrypt. We formalize such an active adversary by defining a new security notion and studying its impact on contemporary table-based white-box implementations. Our analyses reveal a structural disparity between two major design paradigms: Feistel-based white-box ciphers appear significantly more vulnerable to fault injection than SPN-based designs. Finally, we propose a software-based fault detection mechanism that detects fault injections with high probability, strengthening resilience. We provide detailed analysis of the SPN-based cipher WEM (the same analyses also work for other SPN-based ciphers like SPNbox), and two Feistel-based ciphers SPACE and Galaxy. Our analyses reveal that SPACE and Galaxy are significantly more vulnerable than WEM, under our fault-based security setting. Precisely, we show that WEM achieves high security under all the adversarial models, whereas SPACE and Galaxy instances can be attacked with a very high message recovery probability of $2^{-8}$, when the adversary can choose the fault positions and the values and corrupts up to one fourth of the implementation table entries.

We present a hybrid password-authenticated key exchange (PAKE) protocol that is secure against harvest-now-decrypt-later (HNDL) attacks by quantum adversaries, and is universally composable under the parallel composition framework of Lyu and Liu (EUROCRYPT 2025). Existing hybrid PAKE constructions combine a classical PAKE with a post-quantum (PQ) PAKE, with the overall security intended to rely on the stronger of the two. However, identifying which PAKE is stronger is non-trivial, given the limited maturity of post-quantum PAKE designs. Recognizing that the immediate quantum threat is passive, we propose a different hybrid compiler: rather than combining two PAKEs, we encapsulate a classical PAKE within a standard post-quantum Key Encapsulation Mechanism (KEM). This modular separation avoids the fragility of post-quantum password handling while neutralizing HNDL attacks. Our compiler works with any two-pass or three-pass PAKEs. As a concrete instantiation, we construct a three-pass protocol that combines J-PAKE and a post-quantum KEM. We also implement the resulting protocol and provide performance results demonstrating that the hybrid construction remains practical, with the complete handshake executing in $2.81\text{ ms}$. This construction has the distinctive advantage that it does not require any ideal cipher, (constant-time) hash-to-curve, or trusted setup assumptions. Within the Lyu-Liu framework, we show that J-PAKE satisfies the notion of a Full DH-type PAKE. We model the KEM as a password-independent Simulatable DH-type component satisfying the minimal simulation properties required for parallel composition. To capture the prospective quantum threat, we formalize a stronger variant of the standard HNDL threat model—where the quantum adversary is explicitly granted the plaintext password—and prove that our protocol achieves Session Key Security and Post-Quantum Forward Secrecy. Our construction relies solely on standardized and widely deployed primitives, yielding a hybrid PAKE that is UC-secure, efficient, and well-suited for real-world deployment during the post-quantum transition.

Matchmaking encryption (ME) enables bilateral access control with private policies, but existing pairing-based constructions tie receiver-side authorization cost to the policy size. This is especially problematic when one party holds a large hidden policy while the other holds only a small attribute set.

We present Silent-Share, a bilateral hidden-policy threshold access-control protocol that decouples policy representation from pairing-based authorization. The construction combines a one-sided hidden-threshold policy-based key encapsulation mechanism (PB-KEM) with a sparse group-valued oblivious key-value store (GOKVS). The GOKVS compactly encodes policy-dependent group elements, so a receiver holding attribute set $\mathcal{A}$ performs exactly $2|\mathcal{A}|$ pairings, independent of the policy size $|\mathcal{P}|$ and threshold $d$. Total decapsulation additionally incurs a hidden-threshold reconstruction cost, characterized separately. Two independent one-sided instances are composed and bound with AES-GCM to realize bilateral authorization.

We prove one-sided KEM confidentiality and policy hiding in the random-oracle model under a hidden common exponent assumption, and extend these guarantees to the bilateral composition. Our implementation on BN254 shows that, when the correct $d$-subset is provided, one-sided decapsulation for $|\mathcal{A}|=10$ takes about $394$ ms, dominated by pairing operations. The pairing-based authorization layer remains flat as $|\mathcal{P}|$ grows from $50$ to $800$, confirming the policy-size independence. The hidden-threshold reconstruction cost is reported separately and can dominate when $|\mathcal{A}|$ is large. Encapsulation is approximately $2$--$3\times$ faster than fuzzy matchmaking encryption across the tested parameter range.