International Association
for Cryptologic Research

In their seminal work, Goldreich, Goldwasser, and Micali [CRYPTO 1984] constructed a pseudorandom function (PRF) using a black-box access to a pseudorandom generator (PRG). When combined with Levin's domain extension technique, the GGM construction invokes the PRG $\omega(\log n)$ times, where $n$ denotes the input length to the PRG. To this day, no black-box construction achieving fewer calls is known.

Recently, Beimel, Malkin, and Mazor [CRYPTO 2024] showed that for a certain family of constructions, which they termed \emph{tree constructions}, the GGM construction is optimal. However, the basic challenge of whether a PRF can be built with just \emph{one invocation} of the PRG still remains open.

In this work, we consider fully black-box constructions of PRFs from PRGs, where both the construction and the reduction are required to be black-box, and the number of interactions the reduction makes with the adversary is independent of the number of oracle calls the adversary makes to its underlying function within each interaction.

Our main result shows that no such construction can have $o(n/\log n)$ and $o(\mathsf{in}/\log\mathsf{in})$ \emph{non-adaptive} calls to the PRG, where $\mathsf{in}$ is the input length of the PRF. This impossibility holds even for weak PRFs with one-bit output, where the adversary is restricted to making i.i.d. uniformly random queries. In addition, we prove a lower bound for weak PRFs with sufficiently long outputs that holds even when the construction is allowed to make adaptive queries to the PRG.

In KEM-based TLS 1.3 key establishment, the client generates a fresh KEM key pair for each connection, placing key generation on the handshake critical path. For NTRU+, a KEM based on the NTRU problem selected in the Korean Post-Quantum Cryptography (KpqC) competition, the dominant cost in this path is the polynomial inversion needed to compute the public key. Although NTRU+ uses an NTT-friendly ring and performs this inversion in the NTT domain, the routine still decomposes into many base inversions, each requiring a modular inversion computed by exponentiation.

To accelerate polynomial inversion in the NTT domain, we collect the modular inversions arising from base inversions into a single stage. This makes it possible to apply Montgomery's trick, reducing the number of modular inversions to one at the cost of sequential product and recovery chains. These chains limit instruction-level parallelism (ILP). To address this dependency bottleneck, we apply hierarchical batching to these exposed denominator inversions, splitting the inputs into $k$ groups to expose independent product chains and recursively batching the resulting $k$ group-product inversions. This preserves the arithmetic cost of Montgomery's trick while improving ILP, thereby reducing cycle counts.

We evaluate hierarchical batch inversion across all NTRU+ parameter sets in both C and AVX2. For NTRU+$864$, the parameter set with the largest gains, compared with non-batched polynomial inversion, it reduces polynomial inversion latency by 48.91% in C and 59.57% in AVX2. For key generation, the corresponding speedups are 18.91% in C and 9.34% in AVX2.

CMoSS facilitates modular specifications, design and analysis of cryptographic protocols. Modular design and analysis is achieved by supporting provably-secure compositions of protocols; typically, a protocol uses a blackbox subprotocol, and is proven secure when composed with any subprotocol meeting the blackbox specifications. For modularity of specifications, CMoSS extends the approach of the MoSS framework: protocol specifications are defined modularly, by a set of independent predicates (games) for each model (assumption) and requirement (goal). CMoSS makes it feasible to rigorously specify, develop and analyze realistic applied cryptographic protocols, supporting real-time concurrency and involving different attacker capabilities, delays, faults and synchronization challenges. CMoSS specifications provide a precise formalization of the informal specifications used by practitioners, facilitating provable security for practical protocols.

A key challenge in digital credential systems is revocation, that is, the ability to revoke credentials post-issuance and verify their status upon presentation. While anonymous credentials enhance privacy over classical credentials (e.g., by providing unlinkability), they complicate revocation. Existing revocation schemes for anonymous credentials often suffer from high client or verifier computation, long delays before revocation takes effect (e.g., epoch-based settings), or require updates to all users with each revocation. We present an efficient, real-time revocation system for anonymous credentials with decentralized revocation authorities based on a novel primitive called Private Record Certification (PRC). PRC enables users to obtain a certificate for a record stored in a server-managed database without the servers learning which record was requested. This primitive is of independent interest, and we construct it by combining techniques from private information retrieval and secure multi-party computation. Our revocation scheme outsources its costs to the revocation authorities and has minimal overhead for clients and verifiers, while ensuring the communication costs are sublinear in the number of credentials for the revocation authorities. We build a prototype and demonstrate that our system achieves sub-second real-time latency at a scale of over 1 billion credentials, with an online operational cost of 2.5$ per server for processing 1 million PRC queries.

NIST standardised a lattice-based key-encapsulation mechanism (ML-KEM) and a lattice-based digital signature scheme (ML-DSA) in 2024 as post-quantum replacements for classical key establishment and digital signatures. Both compute a forward number-theoretic transform (NTT) over secret-bearing polynomials; the NTT's twiddle constants are a documented fault-attack surface. Published attacks zero every twiddle with a single glitch on ML-KEM key generation, or zero individual twiddles on ML-DSA signing. Countermeasures detect or mask such faults, but none bounds the information that survives when an attacker perturbs twiddles one at a time. This paper supplies that bound as an exact per-layer rank ladder, for arbitrary perturbations $\zeta_k \mapsto \zeta_k^{'}$ with bit-flips included. A single twiddle fault leaks exactly the butterfly length of its layer in secret coefficients, a count attained rather than merely bounded, so one fault per layer pins all but two coefficients for ML-KEM and all but one for ML-DSA. The surviving ambiguity is identical whichever twiddle is hit in each layer: $\mathrm{span}(e_0, e_1)$ for ML-KEM's incomplete NTT, $\mathrm{span}(e_0)$ for ML-DSA's complete NTT. No combination of twiddle-perturbation faults, however large, shrinks it further, and this rank-and-kernel characterisation is machine-checked in Lean 4. The per-layer leakage rate it exposes gives countermeasure designers a closed-form budget for allocating protection.

While FHE enables computation on encrypted data, protecting the program itself remains a theoretical and practical challenge, often forcing practitioners to choose between exposing proprietary logic or suffering impractical performance penalties. This paper introduces HEGIDE, an oblivious processor based on the (discrete) Cheon-Kim-Kim-Song (CKKS) scheme that bridges the gap between theoretical Private Function Evaluation (PFE) and its practical realization. Central to our contribution is OSReM (Oblivious Shift Register Memory), a novel memory architecture that circumvents the linear complexity of standard FHE-RAM writes. By treating memory as a shift register, OSReM enables low-latency, constant-time writes without the need for expensive full-memory bootstrapping. HEGIDE leverages a MIMD (Multiple Instruction, Multiple Data) design, utilizing CKKS packing to evaluate distinct program threads in parallel, thus maximizing throughput. While the processor architecture natively supports arbitrary word sizes and instructions, we provide a compiler that manages memory scheduling to abstract the complexity of the shift-register design. We provide a proof-of-concept full implementation of HEGIDE using the OpenFHE library. Experimental results demonstrate the efficiency of our approach, achieving an amortized cycle time of just 6.4 ms for a 16-bit processor - two orders of magnitude faster in throughput than comparable approaches - offering a viable path for the secure execution of proprietary algorithms on encrypted data.

The Learning with Errors (LWE) problem is a fundamental hardness assumption underlying most fully homomorphic encryption (FHE) schemes. Given the close relationship between the Learning with Rounding (LWR) and LWE problems, several cryptographic constructions have also been developed based on LWR. In particular, LWR-based schemes often benefit from simpler and more efficient implementations, as they eliminate the need for explicit Gaussian error sampling. Despite these advantages, relatively few FHE constructions in the literature are based on the LWR assumption.

At AsiaCCS 2025, Goyal and Gangopadhyay proposed a multi-key FHE (MKFHE) scheme based on LWR that adopts a public-key extension mechanism rather than the conventional ciphertext-extension paradigm. The authors also identified the development of a ring-based analogue as an open future direction.

In this work, we present two Ring-LWR-based MKFHE constructions that can be viewed as ring analogues of the LWR-based MKFHE scheme of Goyal and Gangopadhyay. To the best of our knowledge, these are the first MKFHE schemes based on the Ring-LWR assumption. Compared with existing Ring-LWE-based multi-key constructions, our schemes achieve improved compactness in terms of storage and communication costs. We provide concrete parameterizations supporting circuits of varying multiplicative depths and present a proof-of-concept implementation to validate our claims.

We show that the data deduplication scheme [IEEE Trans. Cloud Comput., 11(1), 156-167, 2023] is flawed due to some inconsistent computations. The scheme tries to propose a hybrid encryption and authentication mechanism based on RSA cryptosystem and pairing cryptosystem, but it has confused the different group operations. In the data sharing phase, the cloud service provider cannot determine which stored tag matches the temporary tag, and fails to return the stored data to the requester. To fix, it should explicitly specify which is randomized by modular exponentiation with an RSA modulus, and which is randomized by point multiplication over the underlying elliptic curve.

Pseudorandom codes (PRCs), introduced at Crypto 2024 by Christ and Gunn, are encryption schemes with pseudorandom ciphertexts and error-correction guarantees. PRCs are useful as a tool to obtain watermarking for generative models, in particular ensuring that a watermark is hard to remove against an attacker that can modify up to a given fraction of the watermarked output (a.k.a. the robustness property). A PRC is public-key if the encoding procedure is public (whereas detection requires the corresponding secret key).

In this paper, we provide the first construction of public-key PRCs for the binary alphabet satisfying robustness in the presence of a constant fraction of substitutions ($1/6 - \varepsilon$, for arbitrary $\varepsilon > 0$) and at the same time achieving pseudorandomness against sub-exponential-time distinguishers. The pseudorandomness property relies on a new family of distorted McEliece assumptions that we introduce, instantiated with a class of expanded subcodes of Reed-Solomon codes, called Raw Reed-Solomon codes, for which we provide heuristic evidence of (plausible) sub-exponential hardness.

Our construction is obtained by revisiting the original blueprint by Christ and Gunn to obtain public-key PRCs based on McEliece assumptions. Along the way, we also uncover that their blueprint does not work directly with Raw Reed-Solomon codes. In particular, we show that a generating matrix of a permuted Raw Reed-Solomon code is distinguishable in polynomial time from a uniformly random generating matrix. To circumvent that difficulty, we propose to distort the public key by multiplication with a sparse invertible matrix of constant row Hamming weight.

Byzantine Agreement (BA) protocols must ensure not only agreement and termination, but also validity: the value agreed upon should meaningfully reflect the honest parties' inputs. The choice of validity condition can change the exact resilience threshold at which BA is solvable. Tight characterizations for BA with general validity conditions are known in the partially synchronous model (PODC'23), in the synchronous model (PODC'24), and in the network-agnostic model (DISC'25). We focus on general validity for synchronous BA with responsive termination. Such protocols remain secure against up to $t_s$ byzantine corruptions, but incur a running time that depends on the actual network delay $\delta$, rather than the conservative delay bound $\Delta \gg \delta$, whenever at most $t_r \leq t_s$ parties are corrupted.

We present a tight characterization of the validity properties solvable in this setting. We prove that every non-trivial validity property requires $n>2 t_r+t_s$ in authenticated settings, where a public-key infrastructure and digital signatures are available, and $n>3 t_s$ in unauthenticated settings. These threshold conditions are accompanied by a validity-dependent requirement, the responsive similarity condition: roughly, for any concrete configuration of honest inputs, there is a value that is valid for any view that a protocol could obtain from this initial configuration. We then present matching protocols in both settings, showing that these conditions are sufficient.

The main technical contribution is an authenticated responsive Core-Set Agreement protocol requiring $n>2 t_r+t_s$. This threshold may place the protocol in an honest-minority regime, where prior constructions for general validity do not apply and where standard Synchronous Broadcast is not responsive.

Finally, we instantiate the characterization for several standard validity notions -- weak validity, strong unanimity, convex validity, and honest-input validity.

We continue the study of fast functions, computable by linear-size circuits, that share useful properties of random functions. Motivated by cryptographic applications, we generalize and improve on previous results in this area, obtaining the following results:

- For any constant $t$, we construct a fast $t$-wise independent hash function with algebraic degree $\log_2 t$ (over $\mathbb F_2$), simultaneously optimizing both asymptotic circuit size and degree. - We simplify and improve a recent construction (ITCS 2026) of a family of fast codes with fast duals, both meeting the Gilbert-Varshamov bound. Unlike the previous construction, our construction has negligible failure probability, can accommodate general fields and rates, supports a systematic encoding, and admits fast universal encoders. - We strengthen the above to support stronger random-like properties, such as optimal combinatorial list-decoding. This is achieved by constructing, for any constant $t$, a family of fast linear functions that map any $t$ linearly independent inputs to uniform and statistically independent outputs. Prior to our work, this was only known for $t=1$.

We demonstrate the usefulness of the above results to cryptography. This includes the first nontrivial protocols for perfectly secure multiparty computation whose circuit complexity scales linearly with the number of parties, as well as protocols for computing encrypted matrix-vector products with optimal asymptotic circuit complexity.

Heterogeneous computing platforms increasingly rely on high-throughput data paths spanning CPUs and accelerators, yet most high-speed software ciphers are optimized primarily for CPU-centric execution models. We present AICE, an arithmetic-oriented stream cipher over \(\mathbb{Z}/2^{16}\mathbb{Z}\) with a 37-word (592-bit) internal state, a nonlinear feedback combining modular addition, multiplication, bitwise OR, and rotation, a 370-round initialization with post-initialization key feed-forward, and periodic blank updates. We analyze AICE under several cryptanalytic models, including differential trail screening, linear approximation over the abelian group \(\mathbb{Z}/2^{16}\mathbb{Z}\), guess-and-determine state recovery, and exact SMT-based cube evaluation, and find that all observable structural phenomena remain confined to reduced-round settings far below the full initialization. On the AI Cores of Huawei Ascend accelerators, AICE reaches a single-core peak throughput of $114.13$ Gbps on the Ascend 950 and $55.36$ Gbps on the Ascend 910B4, and scales to $1.59$ Tbps on $32$ Ascend 910B4 cores, roughly $54\times$ the throughput of AES-CTR and $107\times$ that of SM4-CTR on the same $32$-core configuration; on the ARM Kunpeng 920 it remains in the same throughput class as hardware instruction accelerated AES-CTR.

Modern cryptography relies on the intractability of computational problems. We present an approach to building cryptography from a new source of hardness: \emph{proving mathematical theorems}.

Our main result is a construction of succinct non-interactive arguments (SNARGs) for NP under a new, but natural, assumption on the hardness of proving lower bounds in proof complexity. Specifically, our assumption states that it is impossible to prove, within a weak bounded arithmetic theory, the correctness of certifying hard tautologies against Extended Frege. This assumption is inspired by an informal mathematical challenge proposed by Razborov [Ann. Math. '15], and can be viewed as a generalization of an unconditional unprovability result due to Krajíček and Pudlák [J. Symb. Log. '89].

Our construction is a simple variant of the SNARG construction of Jin, Kalai, Lombardi, and Vaikuntanathan [STOC '24]. While the soundness of their construction was proven only for a subclass of NP, we prove its soundness for all of NP under our assumption. At the heart of our result is the observation that cryptographic reasoning is simple in a formal sense: the security proof of most cryptographic primitives can be formalized in a weak theory. In particular, we show how to formalize the scheme of Jin et al. in Jeřábek's theory $\mathsf{APC}_1$ [J. Symb. Log. '07], a weak theory of bounded arithmetic.

Permissionless consensus enables parties to perform Byzantine agreement without any a priori knowledge about who is participating, except for an upper bound on the number of participants running the protocol (no PKI, etc.). Since Nakamoto’s Bitcoin paper, it has been widely believed that permissionless consensus is feasible provided the (Byzantine) adversary only controls a fraction of the collective computational power. However, all known protocols, including Nakamoto’s, rely on idealized assumptions (or ad hoc instantiations).

Is permissionless consensus possible without such assumptions? Surprising little progress had been made towards solving this open question until the recent result by Ball et al. (Crypto 2024), which showed how to achieve permissionless consensus from proofs of work (PoWs) based on fine-grained complexity assumptions in a setting where a randomness beacon is available to all parties running the protocol. Their work left open whether it is possible to remove the beacon assumption; this question is the focus of our work, which we resolve via a new consensus protocol construction that relies on a novel class of distributed samplers and a common random string (that does not need to be structured or sampled precisely at the onset of the protocol execution).

To prove our protocol secure, we revisit the concept of distributed samplers and adapt it to a setting where multiple sampler executions need to be simultaneously secure. To address this challenge we introduce the primitive we call d-wise independent distributed samplers and put forward constructions for such samplers based on DDH and LWE. We then present our consensus protocol via a modular design that utilizes a new moderately hard cryptographic primitive we call multi-verifier signatures of work, a sort of “time-based signature” we construct by composing distributed samplers and (fine-grained complexity-based) PoWs, and which may be of independent interest.

Censorship has always existed, serving both to prevent harms and to inflict them by chilling speech, suppressing organizing, and withholding inconvenient facts and ideas; most technical work aims to prevent all forms of censorship --- the "good", the "bad", and everything in between. We study the complementary, rarely explored goal of making any censorship attempt transparent. We formalize censorship-evident publishing systems (CEPS), protocols that force both overt and covert takedowns to yield transferable evidence. We also provide a CEPS instantiation with Streisand, a proof-of-concept deployment that combines a blockchain-backed timestamp oracle, private information retrieval (PIR)-based anonymous queries to prevent extraction attempts from being conspicuous, and probabilistic Merkle-witness retrieval to produce compact censorship proofs. We present performance evaluations on a 1.3 GiB Enron-derived dataset with regex-based PII redaction to model realistic censorship, and demonstrate that a background daemon can detect heavy censorship after a small number of post-censorship queries, making Streisand an effective auditing mechanism rather than interactive file retrieval. We also discuss design trade-offs (proof size vs. computation, PIR sufficiency vs. necessity), scalability limits, and how CEPS complements existing transparency practices, with Streisand as a starting point for CEPS deployments.

This paper presents high-performance Advanced Vector Extensions 512 (AVX-512) implementations of two Korean standard cryptographic algorithms: the Lightweight Secure Hash (LSH) hash function and Lightweight Encryption Algorithm-Galois/Counter Mode (LEA-GCM) authenticated encryption.

For LSH, we apply three optimization strategies: single-message processing using AVX-512 512-bit vector registers, dual-message parallel processing through register interleaving, and multi-core parallelization using a dynamic queue-based pthread thread pool.

For LEA-GCM, we propose an end-to-end optimization that replaces scalar Counter mode (CTR) encryption with 16-block AVX-512 parallel processing and Streaming SIMD Extensions (SSE)-based Galois Hash (GHASH) authentication with VPCLMULQDQ-based 4-block parallel processing.

Performance evaluation on an Intel Core i7-1165G7 (Tiger Lake) processor shows that LSH-256 achieves an average 1.16× throughput improvement and LSH-512 achieves an average 1.61× improvement over the Korea Internet and Security Agency (KISA) AVX2 reference implementation. Dual-message interleaving achieves an average superlinear speedup of 2.28× driven by instruction-level parallelism (ILP), and the 8-core thread pool delivers speedups of 3.50× to 5.12×.

The optimized LEA-GCM implementation achieves a 3.26× throughput improvement over the KISA SSE-based reference and a 12.1× improvement over the pure software implementation for 4096-byte inputs, with correctness verified against KISA official test vectors.

Electronic voting systems inherently encompass a structural tension among ballot secrecy, verifiability, and coercion resistance. Voters must be able to verify whether their votes have been included; however, if such verification information can serve as evidence presentable to a third party, it becomes a basis for post-election intimidation.

Existing studies have focused primarily on performance evaluation or data separation, and have not comprehensively addressed the structural tension between verifiability and coercion resistance. This study defines this tension as the verification paradox and designs and implements an electronic voting prototype on a three-organization consortium based on Hyperledger Fabric 2.5, combining a 2-of-3 endorsement policy, nullifier-based anonymity, Exponential ElGamal homomorphic tallying, zero-knowledge proof (ZKP)-based ballot validity verification, panic password-based deniable verification, and Private Data Collection (PDC)-based coerced vote separation.

Quantitative evaluation results confirm a server latency overhead of +0.9% for ElGamal relative to the AES performance baseline, statistical indistinguishability between normal and panic responses (p > 0.05), and a peak throughput of approximately 40.7 TPS (with an error rate of 0%) under 1,000 concurrent voters.

This study demonstrates that permissioned blockchains can provide practical mitigation of the verification paradox through implementation and quantitative evaluation.

The Korean Cryptographic Module Validation Program (KCMVP) is a national certification system that verifies the security and conformity of cryptographic modules deployed in government and public institutions. The current process typically takes about one and a half years, during which frequent supplement requests and the resulting retesting cycles substantially raise costs and delay schedules.

To address this, we propose an AI-based pre-certification framework that combines rule-based deterministic detection (L1), RAG-based guideline-evidence retrieval (L2), and LLM-based final decision (L3) into a funnel-shaped pipeline that progressively reduces false positives.

L1 applies more than 170 YAML inspection rules across four pattern types (missing, regex, semantic, ast) to perform deterministic detection. L2 retrieves and attaches KCMVP guideline evidence to each violation through multi-stage RAG search, and L3 employs Gemini 2.5 Flash-Lite to make context-aware decisions on false-positive candidates.

In an initial evaluation on 128 Ground Truth cases derived from the KISA LEA code, the system detected all 128 cases, achieving 100% recall, while L3 correctly removed 9 of 46 FP candidates (19.6%) without inducing any false negatives (FN), confirming the stepwise refinement effect of the funnel structure.

A blind verification on a certified commercial cryptographic module (~14.5 KLOC) yielded a low detection frequency of 0.58 cases per 1,000 lines of code, supporting the system’s practicality in real environments.

The advancement of quantum computing threatens public-key cryptographic algorithms used in TLS connections, such as RSA and ECDHE. The Harvest Now, Decrypt Later (HNDL) attack exposes long-term confidential data to risk even before quantum computers are practically realized, yet a systematic methodology for immediately quantifying the quantum vulnerability of individual TLS connections remains absent.

This paper proposes a layered risk scoring model that quantifies the quantum threat exposure of TLS connections on a 0–100 scale. The model decomposes risk into five independent layers—TLS protocol exposure (L1), legacy public-key vulnerability (L2a), AES-128 Grover weakening (L2b), PQC Level-1 vulnerability (L2c), and certificate expiration urgency (L3)—and incorporates an HNDL global multiplier M that reflects the confidentiality retention period of transmitted data.

Applied to 502 real-world TLS sessions across four industry sectors with M = 1.50, the domestic average risk score (16.0) is approximately 34% higher than the global average (11.9), with domestic legacy key exchange usage at 77.4% versus 53.5% globally and PQC adoption at 22.6% versus 46.5%.

These results quantitatively confirm the elevated quantum risk of domestic network infrastructure, underscoring the urgency of PQC transition.

The “Harvest Now, Decrypt Later (HNDL)” attack—which intercepts and stores encrypted communications before quantum computers become practical and decrypts them afterward—poses a long-term threat to TLS communication channels. Following the completion of NIST PQC standardization, organizations must pursue a phased migration of their TLS layers; however, existing approaches are limited by late detection of configuration errors, absence of cryptographic asset tracking, and insufficient automated response.

This paper proposes an 11-Step DevSecOps pipeline grounded in Policy as Code. The pipeline automatically validates and deploys a 3-Stage TLS migration—Classical ECC (Stage 1), Hybrid PQC (Stage 2), and Advanced Hybrid PQC (Stage 3)—through 11 steps per execution, integrating OQS-Nginx custom builds, security scanning, CBOM Diff, and matrix CI regression detection.

In our evaluation against six PQC toolchain pitfalls, standard SCA/SAST/SBOM pre-detected 0/6, whereas custom builds pre-prevented 5/6 and matrix CI detected 6/6 at runtime. In an evaluation of LLM-based code migration across 80 trials (55 responses received), even with static AST validation applied, 24 failures due to signature/argument hallucination (43.6% of response trials) were only caught at runtime, quantitatively confirming that semantic execution validation is an essential component of multi-layered defense.