algebraic
-
arXiv:2502.07284v1 Announce Type: new Abstract: Lattice-based cryptography is a foundation for post-quantum security, with the Learning with Errors (LWE) problem as a core component in key exchange, encryption, and homomorphic computation. Structured variants like Ring-LWE (RLWE) and Module-LWE (MLWE) improve efficiency using polynomial rings but remain constrained by traditional polynomial multiplication rules, limiting their ability…
-
One-more problems like One-More Discrete Logarithm (OMDL) and One-More Diffie–Hellman (OMDH) have found wide use in cryptography, due to their ability to naturally model security definitions for interactive primitives like blind signatures and oblivious PRF. Furthermore, a generalization of OMDH called Threshold OMDH (TOMDH) has proven useful for building threshold versions of interactive protocols. However,…
-
Javier Gomez-Martinez, Dimitrios Vasilopoulos, Pedro Moreno-Sanchez, Dario Fiore ePrint Report In this work, we introduce Modular Algebraic Proof Contingent Payment (MAPCP), a novel zero-knowledge contingent payment (ZKCP) construction. Unlike previous approaches, MAPCP is the first that simultaneously avoids using zk-SNARKs as the tool for zero-knowledge proofs and HTLC contracts to atomically exchange a secret for…
-
Cong Ling, Andrew Mendelsohn ePrint Report In Noncommutative Ring Learning With Errors From Cyclic Algebras, a variant of Learning with Errors from cyclic division algebras, dubbed ‘Cyclic LWE’, was developed, and security reductions similar to those known for the ring and module case were given, as well as a Regev-style encryption scheme. In this work,…
-
Emanuele Bellini, Mohamed Rachidi, Raghvendra Rohit, Sharwan K. Tiwari ePrint Report This paper reveals a critical flaw in the design of ARADI, a recently proposed low-latency block cipher by NSA researchers — Patricia Greene, Mark Motley, and Bryan Weeks. The weakness exploits the specific composition of Toffoli gates in the round function of ARADI’s nonlinear…
-
Arnab Roy, Matthias Johann Steiner ePrint Report In recent years a new class of symmetric-key primitives over $\mathbb{F}_p$ that are essential to Multi-Party Computation and Zero-Knowledge Proofs based protocols has emerged. Towards improving the efficiency of such primitives, a number of new block ciphers and hash functions over $\mathbb{F}_p$ were proposed. These new primitives also…
-
The Doubly-Efficient Private Information Retrieval (DEPIR) protocol of Lin, Mook, and Wichs (STOC’23) relies on a Homomorphic Encryption (HE) scheme that is algebraic, i.e., whose ciphertext space has a ring structure that matches the homomorphic operations. While early HE schemes had this property, modern schemes introduced techniques to manage noise growth. This made the resulting…
-
Hossein Arabnezhad, Babak Sadeghiyan ePrint Report The aim of an algebraic attack is to find the secret key by solving a collection of relations that describe the internal structure of a cipher for observations of plaintext/cipher-text pairs. Although algebraic attacks are addressed for cryptanalysis of block and stream ciphers, there is a limited understanding of…
-
Threshold signatures have recently seen a renewed interest due to applications in cryptocurrency while NIST has released a call for multi-party threshold schemes, with a deadline for submission expected for the first half of 2025. So far, all lattice-based threshold signatures requiring less than two-rounds are based on heavy tools such as (fully) homomorphic encryption…
-
The Alternating Trilinear Form Equivalence (ATFE) problem was recently used by Tang et al. as a hardness assumption in the design of a Fiat-Shamir digital signature scheme ALTEQ. The scheme was submitted to the additional round for digital signatures of the NIST standardization process for post-quantum cryptography.
-
Fukang Liu, Abul Kalam, Santanu Sarkar, Willi Meier ePrint Report Fully homomorphic encryption (FHE) is an advanced cryptography technique to allow computations (i.e., addition and multiplication) over encrypted data. After years of effort, the performance of FHE has been significantly improved and it has moved from theory to practice. The transciphering framework is another important…
-
The LowMC family of SPN block cipher proposed by Albrecht et al. was designed specifically for MPC-/FHE-/ZKP-friendly use cases. It is especially used as the underlying block cipher of PICNIC, one of the alternate third-round candidate digital signature algorithms for NIST post-quantum cryptography standardization. The security of PICNIC is highly related to the difficulty of…
-
Helger Lipmaa, Roberto Parisella, Janno Siim ePrint Report In the algebraic group model (AGM), an adversary has to return with each group element a linear representation with respect to input group elements. In many groups, it is easy to sample group elements obliviously without knowing such linear representations. Since the AGM does not model this,…
-
Picnic is a NIST PQC Round 3 Alternate signature candidate that builds upon symmetric primitives following the MPC-in-the-head paradigm. Recently, researchers have been exploring more secure/efficient signature schemes from conservative one-way functions based on AES, or new low complexity one-way functions like Rain (CCS 2022) and AIM (CCS 2023). The signature schemes based on Rain…
-
I recently returned from Eindhoven, where I had the pleasure of giving a talk on some recent progress in isogeny-based cryptography at the SIAM Conference on Applied Algebraic Geometry (SIAM AG23). Firstly, I want to thank Tanja Lange, Krijn Reijnders and Monika Trimoska, who orgainsed the mini-symposium on the application of isogenies in cryptography, as…