Mastodawn

#eprint Revision of Public-Key Quantum Fire and Key-Fire From Classical Oracles by Alper Çakan, Vipul Goyal, Omri Shmueli (https://ia.cr/2025/726)

Public-Key Quantum Fire and Key-Fire From Classical Oracles

Quantum fire is a distribution of quantum states that can be efficiently cloned, but cannot be efficiently converted into a classical string. First considered by Nehoran and Zhandry (ITCS'24) and later formalized by Bostanci, Nehoran, Zhandry (STOC'25), quantum fire has strong applications and implications in cryptography, along with important connections to physics and complexity. However, constructing and proving the security of quantum fire so far has been elusive. Nehoran and Zhandry showed how to construct quantum fire relative to an inefficient quantum oracle (which cannot be instantiated even heuristically). Later, Bostanci, Nehoran, Zhandry gave a candidate construction based on group actions, however, even in the classical oracle model they could only conjecture the security of their scheme, and were not able to give a security proof or argue security. In this work, for the first time, we give a construction of public-key quantum fire relative to a classical oracle and prove its security unconditionally. Going further, we introduce two stronger notions that generalize quantum fire, and we give secure constructions for these notions. *** We introduce a notion called quantum key-fire where the clonable fire states serve as keys: They can be used to evaluate a functionality (such as a signing or decryption key), and for security we require unbounded leakage-resilience, which means that given the fire state, the key cannot be efficiently converted into a classical string. *** We consider the notion of interactive (i.e. LOCC) security for quantum (key-)fire. In this setting, instead of trying to convert the state or key into a classical string; the adversary, given the flame state, attempts to transfer it to another adversary interactively over a classical channel. We give a construction of quantum key-fire relative to a classical oracle and unconditionally prove that it satisfies interactive security for any unlearnable functionality. As a result, we also obtain the first classical oracle separations between various notions in physics and cryptography: *** A separation in the computational universe between two fundamental principles of quantum mechanics: No-cloning and no-teleportation, which are equivalent in the information-theoretic setting. *** A separation between copy-protection security (Aaronson, CCC'09) and unbounded/LOCC leakage-resilience security (Cakan, Goyal, Liu-Zhang, Ribeiro, TCC'24). *** A separation between computational no-cloning security and computational no-learning security, two notions introduced recently by Fefferman, Ghosh, Sinha, Yuen (ITCS'26). In all our constructions, the oracles can be implemented efficiently using one-way functions. Thus, our schemes can be heuristically instantiated in the plain model using one-way functions and indistinguishability obfuscation, which gives us the first constructions in the plain model with concrete evidence for their security.

IACR Cryptology ePrint Archive

eprint-revision 5d ago

#eprint Revision of A proof of P≠NP (New symmetric encryption algorithm against any linear attacks and differential attacks) by Gao Ming (https://ia.cr/2025/445)

A proof of P≠NP (New symmetric encryption algorithm against any linear attacks and differential attacks)

P vs NP problem is the most important unresolved problem in the field of computational complexity. Its impact has penetrated into all aspects of algorithm design, especially in the field of cryptography. The security of cryptographic algorithms based on short keys depends on whether P is equal to NP. In fact, the security requirements for cryptographic keys are much stricter than those for P$\neq$NP, the security of the key must ensure not only a sufficiently high computational complexity to crack it, but also consider the security of each bit of the key, while fully avoiding the effectiveness of various attack methods. In this paper, we innovatively propose a new encoding mechanism and develop a novel block symmetric encryption algorithm, whose encryption and decryption can be completed in linear time. For the attacker, in the case where only the plaintext-ciphertext correspondence is known, the problem of cracking the key is equivalent to solving a system of equations which contains at least one free variable that cannot be eliminated, and the number of possible values for each variable is exponentially to the length of the key. To solve this system of equations, it is necessary to exhaustively search for at least one variable, thus proving that the computational complexity of cracking the key is exponential. So the decryption is a one-way function, and according to "the existence of one-way function means P$\neq$NP", thus solving the unsolved problem of P vs NP. In addition, this paper delves into the underlying mathematical laws of this new encoding mechanism, and develops a right multiplication operation to binary. Based on this right multiplication operation, we further constructed a nonlinear operation and designed another block symmetric encryption algorithm that is resistant to all forms of linear and differential attacks.

IACR Cryptology ePrint Archive

eprint-revision 5d ago

#eprint Revision of Post-Quantum Anonymous Signatures from the Lattice Isomorphism Group Action by Chris van Noorden, Paola de Perthuis (https://ia.cr/2026/436)

Post-Quantum Anonymous Signatures from the Lattice Isomorphism Group Action

Post-quantum assumptions may not rely on the difficulty of finding secret subgroups as many classical schemes did. Instead, several assumptions make use of more general group actions, with the belief that quantum algorithms are not helpful in this less structured setting. Famously, some isogeny constructions use the action of an ideal class group on elliptic curves, but equivalence problems in error-correcting codes and lattices also exhibit such structures. Previous works hence presented anonymity-preserving constructions in a generic group action framework; however, they were not general enough to encompass the group action underlying the Lattice Isomorphism Problem (LIP), for which the acting group is infinite (in fact, not even compact) and non-commutative. We bridge this gap by, from zero-knowledge proofs of OR statements, building generic blind signature and strong designated-verifier signature with non-delegability constructions from standard assumptions corresponding to a generalised group action inverse problem.

IACR Cryptology ePrint Archive

eprint-revision 5d ago

#eprint Revision of EFFICIENT QUATERNION ALGORITHMS FOR THE DEURING CORRESPONDENCE, AND APPLICATION TO THE EVALUATION OF MODULAR POLYNOMIALS by Antonin Leroux (https://ia.cr/2026/185)

EFFICIENT QUATERNION ALGORITHMS FOR THE DEURING CORRESPONDENCE, AND APPLICATION TO THE EVALUATION OF MODULAR POLYNOMIALS

This work presents several algorithms to perform operations in the quaternion ideals and orders stemming from the Deuring correspondence. While most of the desired operations can be solved with generic linear algebra, we show that they can be performed much more efficiently while maintaining a strict control over the size of the integers involved. This allows us to obtain a very efficient implementation with fixed sized integers of the effective Deuring correspondence. We apply our new algorithms to improve greatly the practical performances of a recent algorithm by Corte-Real Santos, Eriksen, Leroux, Meyer and Panny to evaluate modular polynomials. Our new implementation, including several other improvements, runs 20 times faster than before for the level ℓ = 11681. The Deuring correspondence also plays a central role in the most recent developments in isogeny-based cryptography, and in particular in the SQIsign signature scheme submitted to the NIST PQC competition. After the latest progresses, it appears that fixed-sized efficient quaternion operations is one of the main missing feature of the most recent implementations of SQIsign. We believe that several of our new algorithms could be very useful for that.

IACR Cryptology ePrint Archive

eprint-revision 5d ago

#eprint Revision of UFOs: An Ultra-fast Toolkit for Multiparty Computation of Small Elements by Jiacheng Gao, Moyang Xie, Yuan Zhang, Sheng Zhong (https://ia.cr/2025/2281)

UFOs: An Ultra-fast Toolkit for Multiparty Computation of Small Elements

In many secure multiparty computation (MPC) applications, the data to be processed are much smaller than the underlying field or ring size. The encoding domain is typically chosen to be large enough to guarantee security (e.g., a 128-bit prime field for 128-bit security), whereas the actual data may consist of only a few bits, such as 4-bit values in a 16-category classification task. This mismatch can lead to substantial communication and computation overhead in existing MPC protocols, which typically treat data of different ranges uniformly. We introduce UFO$_\mathrm{s}$, an ultra-fast toolkit for MPC on small elements. UFO$_\mathrm{s}$ provides highly optimized protocols for three fundamental primitives: one-hot encoding, comparison, and digit decomposition. While these primitives are designed for small elements, they can also be used to construct higher-level protocols; as an example, we develop a radix sort protocol for sorting large field elements. Experimental results show significant performance improvements over state-of-the-art MPC implementations. In particular, our sorting protocol achieves up to a $58\times$ speedup in the online phase when sorting $2^{16}$ elements among five parties.

IACR Cryptology ePrint Archive

eprint-revision 5d ago

#eprint Revision of The HyperFrog Cryptosystem: High-Genus Voxel Topology as a Trapdoor for Post-Quantum KEMs by Victor Duarte Melo (https://ia.cr/2026/195)

The HyperFrog Cryptosystem: High-Genus Voxel Topology as a Trapdoor for Post-Quantum KEMs

We present HyperFrog, a lattice-based Key Encapsulation Mechanism (KEM) targeting post-quantum security levels. The construction instantiates a variant of the Learning With Errors (LWE) problem in which the secret vector is derived from high-genus topological structures embedded in a three-dimensional grid. Unlike standard LWE schemes that draw secrets from uniform or Gaussian distributions, HyperFrog uses a topology-mining procedure to generate sparse binary secret keys corresponding to connected subgraphs with cyclomatic number (genus) >= 8, introducing geometric constraints while preserving combinatorial hardness. To achieve practical robustness, the scheme applies the Fujisaki-Okamoto (FO) transform, attaining IND-CCA2 security under standard assumptions. The reference implementation, internally codenamed "Topological Obsidian", includes a constant-time decoding routine based on branchless arithmetic to eliminate secret-dependent control flow during decryption and re-encryption. We provide benchmark results on an AMD Ryzen 9 5950X implementation using AVX2 vectorization for polynomial arithmetic, and demonstrate the integration of the KEM into a high-performance AES-256-GCM hybrid encryption pipeline.

IACR Cryptology ePrint Archive

eprint-revision 5d ago

#eprint Revision of Vision: A Modular Framework for Anonymous Credential Systems by Anja Lehmann, Andrey Sidorenko, Alexandros Zacharakis (https://ia.cr/2025/1981)

Vision: A Modular Framework for Anonymous Credential Systems

Anonymous credentials enable the unlinkable presentation of previously attested information, or even only predicates thereof. They are a versatile tool and currently enjoy attention in various real-world applications, ranging from the European Digital Identity project to Privacy Pass. While each application usually requires their own tailored variant of anonymous credentials, they all share the same common blueprint. So far, this has not been leveraged though, and currently several proposals either targeting monolithic variants of core components such as BBS signatures, or application-speciﬁc protocols undergo standardization. This is clearly not optimal, as the same work gets repeated multiple times, while still risking ending up with many slight modiﬁcations of the same main idea and protocols. In this work we present our vision to use a modular approach to build anonymous credential systems: they are built from a core component – consisting of a commitment, signature and NIZK scheme – that can be extended with additional commitment-based modules in a plug-and-play manner. We sketch modules for pseudonyms, range proofs and device binding. Importantly, apart from the committed input, all modules are entirely independent of each other. We use this modularity to propose a concrete instantiation that uses BBS signatures for the core component and ECDSA signatures for device binding, addressing the need to bind modern credential schemes to legacy signatures in secure hardware elements.

IACR Cryptology ePrint Archive

eprint-revision 5d ago

#eprint Revision of Query-Optimal IOPPs for Linear-Time Encodable Codes by Anubhav Baweja, Pratyush Mishra, Tushar Mopuri, Matan Shtepel (https://ia.cr/2025/1588)

Query-Optimal IOPPs for Linear-Time Encodable Codes

We present the first Interactive Oracle Proof of Proximity (IOPP) for linear-time encodable codes that achieves $\lambda$-bit security with linear prover time and optimal $O(\lambda)$ query complexity. This implies (via standard techniques) the first IOP for NP with $O(n)$ prover time and $O(\lambda)$ query complexity, and hence also the first SNARK for NP in the random oracle model with linear prover time and $O(\lambda^2 \log n)$ proof size. The technical core of our result is a novel IOPP for tensor codes. Our tensor IOPP leverages error correction in a novel way to reduce checking proximity of a purported codeword to the tensor code to checking the proximity of $\Theta(\lambda)$-many of its columns to the column code. Our key insight is that it in fact suffices to just prove that a constant fraction of these new proximity claims hold (as opposed to all of them). We devise a new lossy batching protocol that provides the foregoing guarantee with just $O(\lambda)$ query complexity. By combining this tensor IOPP with prior "codeswitching" reductions, we obtain IOPPs for a large class of linear-time encodable codes. We complement our IOPP construction with a lower bound that shows that, when proving proximity to constant-rate codes, one cannot construct IOPPs with query complexity better than $O(\lambda)$. This establishes the optimality of our IOPP's query complexity.

IACR Cryptology ePrint Archive

eprint-revision 5d ago

#eprint Revision of On the design of Survivable Distributed Passwordless Authentication and Single Sign-On by Luca Ferretti, Federico Magnanini, Mauro Andreolini, Mattia Trabucco, Michele Colajanni (https://ia.cr/2026/028)

On the design of Survivable Distributed Passwordless Authentication and Single Sign-On

Single Sign-On (SSO) protocols allow an identity provider to authenticate users and report the outcome by issuing identity attestations. Recent attacks show that breaching the identity provider infrastructure enables adversaries to issue arbitrary identity attestations and impersonate users. Survivable SSO protocols limit the risks of similar intrusions, but they have only been defined for password-based authentication, inheriting their limitations against powerful attacks such as credential phishing. While phishing-resistant passwordless authentication protocols have been standardized, they are not designed to guarantee intrusion tolerance. We initiate the research for Survivable Passwordless SSO (SPS) and propose a modular approach which includes the novel definition of Survivable Passwordless Challenge-response (SPC) protocols for authentication as a sub-routine of SSO. We give the first frameworks and game-based security definitions both for SPC and SPS which capture both novel attack classes, such as session injection attacks in a decentralized setting, and existing but not yet formalized attack classes, such as detection of cloned authenticators. The design of the models includes novel strategies to capture proactive security in survivable protocols within security definitions and to compose authentication and SSO through a modular approach. Our strategies and models may also be applied with minor modifications to non-survivable protocols, possibly providing a novel approach to assess the security of existing SSO protocols.

IACR Cryptology ePrint Archive

eprint-revision 6d ago

#eprint Revision of „One More Time”: Security of One-time Signature Scheme Using Run-length Encoding Under Two-message Attacks by Viktória I. Villányi (https://ia.cr/2026/142)

„One More Time”: Security of One-time Signature Scheme Using Run-length Encoding Under Two-message Attacks

In this paper, we examine the One-time signature scheme using run-length encoding, as proposed by Steinwandt et al., under the scenario where an adversary is allowed to obtain signatures on two messages before attempting to forge a signature on a third message. Our analysis follows the line of security discussion presented by Groot Bruinderink et al. in their paper “Oops, I Did It Again – Security of One-Time Signatures under Two-Message Attacks.” By considering various attack models and different strategies, we estimate both the attack complexity and the probability of forging a signature. Our results indicate that the signature scheme performs well under a two-message attack, making it an interesting candidate for a few-time signature scheme. Few-time signature schemes such as HORS are a fundamental building block of stateless hash-based signature schemes.

IACR Cryptology ePrint Archive