338 results sorted by ID
Lifting approach against the SNOVA scheme
Shuhei Nakamura, Yusuke Tani, Hiroki Furue
Attacks and cryptanalysis
In 2022, Wang et al. proposed the multivariate signature scheme SNOVA as a UOV variant over the non-commutative ring of $\ell \times \ell $ matrices over $\mathbb{F}_q$.
This scheme has small public key and signature size and is a first round candidate of NIST PQC additional digital signature project.
Recently, Ikematsu and Akiyama, and Li and Ding show that the core matrices of SNOVA with $v$ vinegar-variables and $o$ oil-variables are regarded as the representation matrices of UOV with...
Quantum Security of a Compact Multi-Signature
Shaoquan Jiang
Cryptographic protocols
With the rapid advance in quantum computing, quantum security is now an indispensable property for any cryptographic system. In this paper, we study how to prove the security of a complex cryptographic system in the quantum random oracle model. We first give a variant of Zhandry's compressed quantum random oracle (${\bf CStO}$), called compressed quantum random oracle with adaptive special points ({\bf CStO}$_s$). Then, we extend the on-line extraction technique of Don et al...
FELIX (XGCD for FALCON): FPGA-based Scalable and Lightweight Accelerator for Large Integer Extended GCD
Sam Coulon, Tianyou Bao, Jiafeng Xie
Implementation
The Extended Greatest Common Divisor (XGCD) computation is a critical component in various cryptographic applications and algorithms, including both pre- and post-quantum cryptosystems. In addition to computing the greatest common divisor (GCD) of two integers, the XGCD also produces Bezout coefficients $b_a$ and $b_b$ which satisfy $\mathrm{GCD}(a,b) = a\times b_a + b\times b_b$. In particular, computing the XGCD for large integers is of significant interest. Most recently, XGCD computation...
EagleSignV3 : A new secure variant of EagleSign signature over lattices
Abiodoun Clement Hounkpevi, Sidoine Djimnaibeye, Michel Seck, Djiby Sow
Public-key cryptography
With the potential arrival of quantum computers, it is essential to build cryptosystems resistant to attackers with the computing power of a quantum computer. With Shor's algorithm, cryptosystems based on discrete logarithms and factorization become obsolete. Reason why NIST has launching two competitions in 2016 and 2023 to standardize post-quantum cryptosystems (such as KEM and signature ) based on problems supposed to resist attacks using quantum computers. EagleSign was prosed to NIT...
Erebor and Durian: Full Anonymous Ring Signatures from Quaternions and Isogenies
Giacomo Borin, Yi-Fu Lai, Antonin Leroux
Public-key cryptography
We construct two efficient post-quantum ring signatures with anonymity against full key exposure from isogenies, addressing limitations of existing isogeny-based ring signatures.
First, we present an efficient concrete distinguisher for the SQIsign simulator when the signing key is provided using one transcript. This shows that turning SQIsign into an efficient full anonymous ring signature requires some new ideas.
Second, we propose a variant of SQIsign that is resistant to the...
Fast computation of 2-isogenies in dimension 4 and cryptographic applications
Pierrick Dartois
Implementation
Dimension 4 isogenies have first been introduced in cryptography for the cryptanalysis of Supersingular Isogeny Diffie-Hellman (SIDH) and have been used constructively in several schemes, including SQIsignHD, a derivative of SQIsign isogeny based signature scheme. Unlike in dimensions 2 and 3, we can no longer rely on the Jacobian model and its derivatives to compute isogenies. In dimension 4 (and higher), we can only use theta-models. Previous works by Romain Cosset, David Lubicz and Damien...
Designated-Verifier zk-SNARKs Made Easy
Chen Li, Fangguo Zhang
Cryptographic protocols
Zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) is a kind of proof system that enables a prover to convince a verifier that an NP statement is true efficiently. In the last decade, various studies made a lot of progress in constructing more efficient and secure zk-SNARKs. Our research focuses on designated-verifier zk-SNARKs, where only the verifier knowing some secret verification state can be convinced by the proof. A natural idea of getting a designated-verifier...
DualRing-PRF: Post-Quantum (Linkable) Ring Signatures from Legendre and Power Residue PRFs
Xinyu Zhang, Ron Steinfeld, Joseph K. Liu, Muhammed F. Esgin, Dongxi Liu, Sushmita Ruj
Cryptographic protocols
Ring signatures are one of the crucial cryptographic primitives used in the design of privacy-preserving systems. Such a signature scheme allows a signer to anonymously sign a message on behalf of a spontaneously formed group. It not only ensures the authenticity of the message but also conceals the true signer within the group. An important extension of ring signatures is linkable ring signatures, which prevent a signer from signing twice without being detected (under some constraints)....
Signer Revocability for Threshold Ring Signatures
Da Teng, Yanqing Yao
Public-key cryptography
t-out-of-n threshold ring signature (TRS) is a type of anonymous signature designed for t signers to jointly sign a message while hiding their identities among n parties that include themselves. However, can TRS address those needs if one of the signers wants to revoke his signature or, additively, sign separately later? Can non-signers be revoked without compromising anonymity? Previous research has only discussed opposing situations. The present study introduces a novel property for...
Simple Logarithmic-size LSAG signature
Edsger Hughes
Cryptographic protocols
A number of existing cryptosystems use the well-known linear-size LSAG signature concept, extending it in many ways. This article presents a simple logarithmic-size signature LS-LSAG which, despite a radical reduction in size, retains the basic code block of LSAG. Therefore, substituting LS-LSAG for LSAG requires minimal changes to almost any existing LSAG/CLSAG-based solution, making it logarithmic instead of linear.
Ring Signatures for Deniable AKEM: Gandalf's Fellowship
Phillip Gajland, Jonas Janneck, Eike Kiltz
Public-key cryptography
Ring signatures, a cryptographic primitive introduced by Rivest, Shamir and Tauman (ASIACRYPT 2001), offer signer anonymity within dynamically formed user groups. Recent advancements have focused on lattice-based constructions to improve efficiency, particularly for large signing rings. However, current state-of-the-art solutions suffer from significant overhead, especially for smaller rings.
In this work, we present a novel NTRU-based ring signature scheme, Gandalf, tailored towards...
Loquat: A SNARK-Friendly Post-Quantum Signature based on the Legendre PRF with Applications in Ring and Aggregate Signatures
Xinyu Zhang, Ron Steinfeld, Muhammed F. Esgin, Joseph K. Liu, Dongxi Liu, Sushmita Ruj
Cryptographic protocols
We design and implement a novel post-quantum signature scheme based on the Legendre PRF, named Loquat. Prior to this work, efficient approaches for constructing post-quantum signatures with comparable security assumptions mainly used the MPC-in-the-head paradigm or hash trees. Our method departs from these paradigms and, notably, is SNARK-friendly, a feature not commonly found in earlier designs. Loquat requires significantly fewer computational operations for verification than other...
Physical Ring Signature
Xavier Bultel
Cryptographic protocols
Ring signatures allow members of a group (called "ring") to sign a message anonymously within the group, which is chosen ad hoc at the time of signing (the members do not need to have interacted before). In this paper, we propose a physical version of ring signatures. Our signature is based on one-out-of-many signatures, a method used in many real cryptographic ring signatures. It consists of boxes containing coins locked with padlocks that can only be opened by a particular group member. To...
Isotropic Quadratic Forms, Diophantine Equations and Digital Signatures
Martin Feussner, Igor Semaev
Public-key cryptography
This work introduces DEFI - an efficient hash-and-sign digital signature scheme based on isotropic quadratic forms over a commutative ring of characteristic 0. The form is public, but the construction is a trapdoor that depends on the scheme's private key. For polynomial rings over integers and rings of integers of algebraic number fields, the cryptanalysis is reducible to solving a quadratic Diophantine equation over the ring or, equivalently, to solving a system of quadratic Diophantine...
Interactive Threshold Mercurial Signatures and Applications
Masaya Nanri, Octavio Perez Kempner, Mehdi Tibouchi, Masayuki Abe
Public-key cryptography
Equivalence class signatures allow a controlled form of malleability based on equivalence classes defined over the message space. As a result, signatures can be publicly randomized and adapted to a new message representative in the same equivalence class. Notably, security requires that an adapted signature-message pair looks indistinguishable from a random signature-message pair in the space of valid signatures for the new message representative. Together with the decisional Diffie-Hellman...
Improved Alternating-Moduli PRFs and Post-Quantum Signatures
Navid Alamati, Guru-Vamsi Policharla, Srinivasan Raghuraman, Peter Rindal
Cryptographic protocols
We revisit the alternating-moduli paradigm for constructing symmetric-key primitives with a focus on constructing efficient protocols to evaluate them using secure multi-party computation (MPC). The alternating-moduli paradigm of Boneh, Ishai, Passelègue, Sahai, and Wu (TCC 2018) enables the construction of various symmetric-key primitives with the common characteristic that the inputs are multiplied by two linear maps over different moduli.
The first contribution focuses on...
Efficient Linkable Ring Signatures: New Framework and Post-Quantum Instantiations
Yuxi Xue, Xingye Lu, Man Ho Au, Chengru Zhang
Public-key cryptography
In this paper, we introduce a new framework for constructing linkable ring signatures (LRS). Our framework is based purely on signatures of knowledge (SoK) which allows one to issue signatures on behalf of any NP-statement using the corresponding witness. Our framework enjoys the following advantages: (1) the security of the resulting LRS depends only on the security of the underlying SoK; (2) the resulting LRS naturally supports online/offline signing (resp. verification), where the output...
LLRing: Logarithmic Linkable Ring Signatures with Transparent Setup
Xiangyu Hui, Sid Chi-Kin Chau
Cryptographic protocols
Linkable ring signatures are an important cryptographic primitive for anonymized applications, such as e-voting, e-cash and confidential transactions. To eliminate backdoor and overhead in a trusted setup, transparent setup in the discrete logarithm or pairing settings has received considerable attention in practice. Recent advances have improved the proof sizes and verification efficiency of linkable ring signatures with a transparent setup to achieve logarithmic bounds. Omniring (CCS '19)...
Plover: Masking-Friendly Hash-and-Sign Lattice Signatures
Muhammed F. Esgin, Thomas Espitau, Guilhem Niot, Thomas Prest, Amin Sakzad, Ron Steinfeld
Public-key cryptography
We introduce a toolkit for transforming lattice-based hash-and-sign signature schemes into masking-friendly signatures secure in the t-probing model. Until now, efficiently masking lattice-based hash-and-sign schemes has been an open problem, with unsuccessful attempts such as Mitaka. A first breakthrough was made in 2023 with the NIST PQC submission Raccoon, although it was not formally proven.
Our main conceptual contribution is to realize that the same principles underlying Raccoon...
On the cryptosystems based on two Eulerian transfor-mations defined over the commutative rings $Z_{2^s}, s>1$.
Vasyl Ustimenko
Cryptographic protocols
We suggest the family of ciphers s^E^n, n=2,3,.... with the space of plaintexts (Z*_{2^s})^n, s >1 such that the encryption map is the composition of kind G=G_1A_1G_2A_2 where A_i are the affine transformations from AGL_n(Z_{2^s}) preserving the variety (Z*_{2^s)}^n , Eulerian endomorphism G_i , i=1,2 of K[x_1, x_2,...., x_n] moves x_i to monomial term ϻ(x_1)^{d(1)}(x_2)^{d(2)}...(x_n)^{d(n)} , ϻϵ Z*_{2^s} and act on (Z*_{2^s})^n as bijective transformations.
The cipher is...
Aggregating Falcon Signatures with LaBRADOR
Marius A. Aardal, Diego F. Aranha, Katharina Boudgoust, Sebastian Kolby, Akira Takahashi
Public-key cryptography
Several prior works have suggested to use non-interactive arguments of knowledge with short proofs to aggregate signatures of Falcon, which is part of the first post-quantum signatures selected for standardization by NIST. Especially LaBRADOR, based on standard structured lattice assumptions and published at CRYPTO’23, seems promising to realize this task. However, no prior work has tackled this idea in a rigorous way. In this paper, we thoroughly prove how to aggregate Falcon signatures...
Don’t Use It Twice! Solving Relaxed Linear Code Equivalence Problems
Alessandro Budroni, Jesús-Javier Chi-Domínguez, Giuseppe D'Alconzo, Antonio J. Di Scala, Mukul Kulkarni
Attacks and cryptanalysis
The Linear Code Equivalence (LCE) Problem has received increased attention in recent years due to its applicability in constructing efficient digital signatures. Notably, the LESS signature scheme based on LCE is under consideration for the NIST post-quantum standardization process, along with the MEDS signature scheme that relies on an extension of LCE to the rank metric, namely the Matrix Code Equivalence (MCE) Problem. Building upon these developments, a family of signatures with...
On Security Proofs of Existing Equivalence Class Signature Schemes
Balthazar Bauer, Georg Fuchsbauer
Public-key cryptography
Equivalence class signatures (EQS), introduced by Hanser and Slamanig (AC'14), sign vectors of elements from a bilinear group. Signatures can be ``adapted'', meaning that anyone can transform a signature on a vector to a (random) signature on any multiple of that vector. (Signatures thus authenticate equivalence classes.) A transformed signature/message pair is then indistinguishable from a random signature on a random message. EQS have been used to efficiently instantiate (delegatable)...
QPP and HPPK: Unifying Non-Commutativity for Quantum-Secure Cryptography with Galois Permutation Group
Randy Kuang
Cryptographic protocols
In response to the evolving landscape of quantum computing and the heightened vulnerabilities in classical cryptographic systems, our paper introduces a comprehensive cryptographic framework. Building upon the pioneering work of Kuang et al., we present a unification of two innovative primitives: the Quantum Permutation Pad (QPP) for symmetric key encryption and the Homomorphic Polynomial Public Key (HPPK) for Key Encapsulation Mechanism (KEM) and Digital Signatures (DS). By harnessing...
K-Waay: Fast and Deniable Post-Quantum X3DH without Ring Signatures
Daniel Collins, Loïs Huguenin-Dumittan, Ngoc Khanh Nguyen, Nicolas Rolin, Serge Vaudenay
Cryptographic protocols
The Signal protocol and its X3DH key exchange core are regularly used by billions of people in applications like WhatsApp but are unfortunately not quantum-secure. Thus, designing an efficient and post-quantum secure X3DH alternative is paramount. Notably, X3DH supports asynchronicity, as parties can immediately derive keys after uploading them to a central server, and deniability, allowing parties to plausibly deny having completed key exchange. To satisfy these constraints, existing...
Cryptanalysis of the SNOVA signature scheme
Peigen Li, Jintai Ding
Attacks and cryptanalysis
SNOVA is a variant of a UOV-type signature scheme over a noncommutative ring. In this article, we demonstrate that certain
parameters provided by authors in SNOVA fail to meet the NIST security level, and the complexities are lower than those claimed by SNOVA.
Revisiting the security analysis of SNOVA
Yasuhiko Ikematsu, Rika Akiyama
Attacks and cryptanalysis
SNOVA is a multivariate signature scheme submitted to the ad- ditional NIST PQC standardization project started in 2022. SNOVA is con- structed by incorporating the structure of the matrix ring over a finite field into the UOV signature scheme, and the core part of its public key is the UOV public key whose coefficients consist of matrices. As a result, SNOVA dramatically reduces the public key size compared to UOV. In this paper, we recall the construction of SNOVA, and reconsider its...
Short Code-based One-out-of-Many Proofs and Applications
Xindong Liu, Li-Ping Wang
Public-key cryptography
In this work, we propose two novel succinct one-out-of-many proofs from coding theory, which can be seen as extensions of the Stern's framework and Veron's framework from proving knowledge of a preimage to proving knowledge of a preimage for one element in a set, respectively. The size of each proof is short and scales better with the size of the public set than the code-based accumulator in \cite{nguyen2019new}. Based on our new constructions, we further present a logarithmic-size ring...
Foundations of Anonymous Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions
Jan Bobolz, Jesus Diaz, Markulf Kohlweiss
Public-key cryptography
In today's systems, privacy is often at odds with utility: users that reveal little information about themselves get restricted functionality, and service providers mistrust them. In practice, systems tip to either full anonymity (e.g. Monero), or full utility (e.g. Bitcoin). Well-known cryptographic primitives for bridging this gap exist: anonymous credentials (AC) let users disclose a subset of their credentials' attributes, revealing to service providers "just what they need"; group...
Security analysis and improvements on a semi-quantum electronic voting protocol
Qiu Shujing, Xin Xiangjun, Zheng Qian, Li Chaoyang, Li Fagen
Cryptographic protocols
Recently, Qiu et al. proposed a semi-quantum voting scheme based on the ring signature (International Journal of Theoretical Physics, 60: 1550–1555(2021)), in which the signer and verifier only need measure the received particles with Z-basis and perform some classical simple encryption/decryption operations on the classical message. Although their scheme is very efficient, it cannot resist against the eavesdropping attacks and forgery attack. In this paper, first, the eavesdropping attacks...
Benchmark Performance of Homomorphic Polynomial Public Key Cryptography for Key Encapsulation and Digital Signature Schemes
Randy Kuang, Maria Perepechaenko, Dafu Lou, Brinda Tank
Public-key cryptography
This paper conducts a comprehensive benchmarking analysis of the performance of two innovative cryptographic schemes: Homomorphic Polynomial Public Key (HPPK)-Key Encapsulation Mechanism (KEM) and Digital Signature (DS), recently proposed by Kuang et al. These schemes represent a departure from traditional cryptographic paradigms, with HPPK leveraging the security of homomorphic symmetric encryption across two hidden rings without reliance on NP-hard problems. HPPK can be viewed as a...
On short digital signatures with Eulerian transformations
Vasyl Ustimenko
Foundations
Let n stands for the length of digital signatures with quadratic multivariate public rule in n variables. We construct postquantum secure procedure to sign O(n^t), t ≥1 digital documents with the signature of size n in time O(n^{3+t}). It allows to sign O(n^t), t <1 in time O(n^4). The procedure is defined in terms of Algebraic Cryptography. Its security rests on the semigroup based protocol of Noncommutative Cryptography referring to complexity of the decomposition of the collision...
Evaluating the security of CRYSTALS-Dilithium in the quantum random oracle model
Kelsey A. Jackson, Carl A. Miller, Daochen Wang
Public-key cryptography
In the wake of recent progress on quantum computing hardware, the National Institute of Standards and Technology (NIST) is standardizing cryptographic protocols that are resistant to attacks by quantum adversaries. The primary digital signature scheme that NIST has chosen is CRYSTALS-Dilithium. The hardness of this scheme is based on the hardness of three computational problems: Module Learning with Errors (MLWE), Module Short Integer Solution (MSIS), and SelfTargetMSIS. MLWE and MSIS have...
Exploring SIDH-based Signature Parameters
Andrea Basso, Mingjie Chen, Tako Boris Fouotsa, Péter Kutas, Abel Laval, Laurane Marco, Gustave Tchoffo Saah
Public-key cryptography
Isogeny-based cryptography is an instance of post-quantum cryptography whose fundamental problem consists of finding an isogeny between two (isogenous) elliptic curves $E$ and $E'$. This problem is closely related to that of computing the endomorphism ring of an elliptic curve. Therefore, many isogeny-based protocols require the endomorphism ring of at least one of the curves involved to be unknown. In this paper, we explore the design of isogeny based protocols in a scenario where one...
Lattice Based Signatures with Additional Functionalities
Swati Rawal, Sahadeo Padhye, Debiao He
Public-key cryptography
Digital signatures is a cryptographic protocol that can provide the added assurances of identity, status, proof of origin of an electronic document, and can acknowledge informed consent by the signer. Lattice based assumptions have seen a certain rush in recent years to fulfil the desire to expand the hardness assumption beyond factoring or discrete logarithm problem on which digital signatures can rely. In this article, we cover the recent progress made in digital signatures based on...
Blockchain Governance via Sharp Anonymous Multisignatures
Wonseok Choi, Xiangyu Liu, Vassilis Zikas
Applications
Electronic voting has occupied a large part of the cryptographic protocols literature. The recent reality of blockchains---in particular their need for online governance mechanisms---has put new parameters and requirements to the problem. We identify the key requirements of a blockchain governance mechanism, namely correctness (including eliminative double votes), voter anonymity, and traceability, and investigate mechanisms that can achieve them with minimal interaction and under...
Rectangular Attack on VOX
Gilles Macario-Rat, Jacques Patarin, Benoit Cogliati, Jean-Charles Faugère, Pierre-Alain Fouque, Louis Gouin, Robin Larrieu, Brice Minaud
Public-key cryptography
VOX has been submitted to the NIST Round 1 Additional Signature of the Post-Quantum Signature Competition in June 2023. VOX is a strengthened variant of UOV which uses the Quotient-Ring (QR) setting to reduce the public-key size.
At the end of August 2023, Furue and Ikamatsu posted on the NIST mailing-list a post, indicating that the parameters of VOX can be attacked efficiently using the rectangular attack in the QR setting.
In this note, we explain the attack in the specific case of...
Homomorphic Polynomial Public Key Cryptography for Quantum-secure Digital Signature
Randy Kuang, Maria Perepechaenko, Mahmoud Sayed, Dafu Lou
Cryptographic protocols
In their 2022 study, Kuang et al. introduced the Multivariable Polynomial Public Key (MPPK) cryptography, a quantum-safe public key cryptosystem leveraging the mutual inversion relationship between multiplication and division. MPPK employs multiplication for key pair construction and division for decryption, generating public multivariate polynomials. Kuang and Perepechaenko expanded the cryptosystem into the Homomorphic Polynomial Public Key (HPPK), transforming product polynomials over...
Predicate Aggregate Signatures and Applications
Tian Qiu, Qiang Tang
Public-key cryptography
Motivated by applications in anonymous reputation systems and blockchain governance, we initiate the study of predicate aggregate signatures (PAS), which is a new primitive that enables users to sign multiple messages, and these individual signatures can be aggregated by a combiner, preserving the anonymity of the signers. The resulting PAS discloses only a brief description of signers for each message and provides assurance that both the signers and their description satisfy the specified...
On Gaussian sampling, smoothing parameter and application to signatures
Thomas Espitau, Alexandre Wallet, Yang Yu
Foundations
We present a general framework for polynomial-time lattice Gaussian
sampling. It revolves around a systematic study of the discrete
Gaussian measure and its samplers under extensions of lattices;
we first show that given lattices $\Lambda'\subset \Lambda$ we can sample
efficiently in $\Lambda$ if we know how to do so in $\Lambda'$ and the
quotient $\Lambda/\Lambda'$, \emph{regardless} of the primitivity of
$\Lambda'$. As a direct application, we...
One-time and Revocable Ring Signature with Logarithmic Size in Blockchain
Yang Li, Wei Wang, Dawei Zhang, Xu Han
Public-key cryptography
Ring signature (RS) allows users to demonstrate to verifiers their membership within a specified group (ring) without disclosing their identities. Based on this, RS can be used as a privacy protection technology for users' identities in blockchain. However, there is currently a lack of RS schemes that are fully applicable to the blockchain applications: Firstly, users can only spend a UTXO once, and the current RS schemes are not yet perfect in a one-time manner. At the same time, the...
Improved algorithms for finding fixed-degree isogenies between supersingular elliptic curves
Benjamin Benčina, Péter Kutas, Simon-Philipp Merz, Christophe Petit, Miha Stopar, Charlotte Weitkämper
Public-key cryptography
Finding isogenies between supersingular elliptic curves is a natural algorithmic problem which is known to be equivalent to computing the curves' endomorphism rings.
When the isogeny is additionally required to have a specific known degree $d$, the problem appears to be somewhat different in nature, yet its hardness is also required in isogeny-based cryptography.
Let $E_1,E_2$ be supersingular elliptic curves over $\mathbb{F}_{p^2}$. We present improved classical and quantum...
Designing Efficient and Flexible NTT Accelerators
Ahmet MALAL
Implementation
The Number Theoretic Transform (NTT) is a powerful mathematical tool with a wide range of applications in various fields, including signal processing, cryptography, and error correction codes. In recent years, there has been a growing interest in efficiently implementing the NTT on hardware platforms for lattice-based cryptography within the context of NIST's Post-Quantum Cryptography (PQC) competition. The implementation of NTT in cryptography stands as a pivotal advancement,...
Threshold Computation in the Head: Improved Framework for Post-Quantum Signatures and Zero-Knowledge Arguments
Thibauld Feneuil, Matthieu Rivain
Cryptographic protocols
The MPC-in-the-Head paradigm is instrumental in building zero-knowledge proof systems and post-quantum signatures using techniques from secure multi-party computation. In this work, we extend and improve the recently proposed framework of MPC-in-the-Head based on threshold secret sharing, here called Threshold Computation in the Head. We first address some limitations of this framework, namely its overhead in the communication cost, its constraint on the number of parties and its degradation...
A Total Break of the Scrap Digital Signature Scheme
Daniel Smith-Tone
Public-key cryptography
Recently a completely new post-quantum digital signature scheme was proposed using the so called ``scrap automorphisms''. The structure is inherently multivariate, but differs significantly from most of the multivariate literature in that it relies on sparsity and rings containing zero divisors. In this article, we derive a complete and total break of Scrap, performing a key recovery in not much more time than verifying a signature. We also generalize the result, breaking unrealistic...
Antrag: Annular NTRU Trapdoor Generation
Thomas Espitau, Thi Thu Quyen Nguyen, Chao Sun, Mehdi Tibouchi, Alexandre Wallet
Public-key cryptography
In this paper, we introduce a novel trapdoor generation technique for
Prest's hybrid sampler over NTRU lattices. Prest's sampler is used in
particular in the recently proposed Mitaka signature scheme
(Eurocrypt 2022), a variant of the Falcon signature scheme, one of the
candidates selected by NIST for standardization. Mitaka was introduced
to address Falcon's main drawback, namely the fact that the lattice
Gaussian sampler used in its signature generation is highly...
On the Black-Box Separation Between Ring Signatures and Public Key Encryptions
Kyosuke Yamashita, Keisuke Hara
Foundations
In this paper, we show that it is impossible to construct a public key encryption scheme (PKE) from a ring signature scheme in a black-box fashion in the standard model. Such an impossibility is highly non-trivial because, to the best of our knowledge, known generic constructions of ring signature scheme are based on public key cryptosystems or in the random oracle model. Technically, we introduce a new cryptographic primitive named indistinguishable multi-designated verifiers signature...
A New RSA Variant Based on Elliptic Curves
Maher Boudabra, Abderrahmane Nitaj
Public-key cryptography
We propose a new scheme based on ephemeral elliptic curves over the ring $\mathbb{Z}/n\mathbb{Z}$ where $n=pq$ is an RSA modulus with $p=u_p^2+v_p^2$, $q=u_q^2+v_q^2$, $u_p\equiv u_q\equiv 3\pmod 4$. The new scheme is a variant of both the RSA and the KMOV cryptosystems. The scheme can be used for both signature and encryption. We study the security of the new scheme and show that is immune against factorization attacks, discrete logarithm problem attacks, sum of two squares attacks, sum of...
On the Black-Box Impossibility of Multi-Designated Verifiers Signature Schemes from Ring Signature Schemes
Kyosuke Yamashita, Keisuke Hara
Foundations
From the work by Laguillaumie and Vergnaud in ICICS'04, it has been widely believed that multi-designated verifier signature schemes (MDVS) can be constructed from ring signature schemes in general.
However in this paper, somewhat surprisingly, we prove that it is impossible to construct an MDVS scheme from a ring signature scheme in a black-box sense (in the standard model).
The impossibility stems from the difference between the definitions of unforgeability.
To the best of our...
CSI-Otter: Isogeny-based (Partially) Blind Signatures from the Class Group Action with a Twist
Shuichi Katsumata, Yi-Fu Lai, Jason T. LeGrow, Ling Qin
Public-key cryptography
In this paper, we construct the first provably-secure isogeny-based (partially) blind signature scheme.
While at a high level the scheme resembles the Schnorr blind signature, our work does not directly follow from that construction, since isogenies do not offer as rich an algebraic structure.
Specifically, our protocol does not fit into the "linear identification protocol" abstraction introduced by Hauck, Kiltz, and Loss (EUROCYRPT'19), which was used to generically construct...
DualDory: Logarithmic-Verifier Linkable Ring Signatures through Preprocessing
Jonathan Bootle, Kaoutar Elkhiyaoui, Julia Hesse, Yacov Manevich
Public-key cryptography
A linkable ring signature allows a user to sign anonymously on behalf of a group while ensuring that multiple signatures from the same user are detected. Applications such as privacy-preserving e-voting and e-cash can leverage linkable ring signatures to significantly improve privacy and anonymity guarantees. To scale to systems involving large numbers of users, short signatures with fast verification are a must. Concretely efficient ring signatures currently rely on a trusted authority...
Mask Compression: High-Order Masking on Memory-Constrained Devices
Markku-Juhani O. Saarinen, Mélissa Rossi
Implementation
Masking is a well-studied method for achieving provable security against side-channel attacks. In masking, each sensitive variable is split into $d$ randomized shares, and computations are performed with those shares. In addition to the computational overhead of masked arithmetic, masking also has a storage cost, increasing the requirements for working memory and secret key storage proportionally with $d$.
In this work, we introduce mask compression. This conceptually simple technique is...
Zero-Value Filtering for Accelerating Non-Profiled Side-Channel Attack on Incomplete NTT based Implementations of Lattice-based Cryptography
Tolun Tosun, Erkay Savas
Attacks and cryptanalysis
Lattice-based cryptographic schemes such as Crystals-Kyber and Dilithium are post-quantum algorithms selected to be standardized by NIST as they are considered to be secure against quantum computing attacks. The multiplication in polynomial rings is the most time-consuming operation in many lattice-based cryptographic schemes, which is also subject to side-channel attacks. While NTT-based polynomial multiplication is almost a norm in a wide range of implementations, a relatively new method,...
SoK: Privacy-Preserving Signatures
Alishah Chator, Matthew Green, Pratyush Ranjan Tiwari
Public-key cryptography
Modern security systems depend fundamentally on the ability of users to authenticate their communications to other parties in a network. Unfortunately, cryptographic authentication can substantially undermine the privacy of users. One possible solution to this problem is to use privacy-preserving cryptographic authentication. These protocols allow users to authenticate their communications without revealing their identity to the verifier. In the non-interactive setting, the most common...
Short Signatures from Regular Syndrome Decoding in the Head
Eliana Carozza, Geoffroy Couteau, Antoine Joux
Cryptographic protocols
We introduce a new candidate post-quantum digital signature scheme from the regular syndrome decoding (RSD) assumption, an established variant of the syndrome decoding assumption which asserts that it is hard to find $w$-regular solutions to systems of linear equations over $\mathbb{F}_2$ (a vector is regular if it is a concatenation of $w$ unit vectors). Our signature is obtained by introducing and compiling a new 5-round zero-knowledge proof system constructed using the MPC-in-the-head...
Generating Supersingular Elliptic Curves over $\mathbb{F}_p$ with Unknown Endomorphism Ring
Youcef Mokrani, David Jao
Public-key cryptography
A number of supersingular isogeny based cryptographic protocols require the endomorphism ring of the initial elliptic curve to be either unknown or random in order to be secure. To instantiate these protocols, Basso et al. recently proposed a secure multiparty protocol that generates supersingular elliptic curves defined over
$\mathbb{F}_{p^2}$ of unknown endomorphism ring as long as at least one party acts honestly. However, there are many protocols that specifically require curves defined...
Design of Blockchain-Based Many-to-Many Anonymous Data Sharing Scheme
Esra Günsay, Burcu E. Karakaş, N. Gamze Orhon Kılıç, Oğuz Yayla
Applications
Many to many data sharing in the group setting in a cloud environment is a challenging problem that is crucial for numerous schemes. To our best knowledge, there is no generic study to allow sharing of confidential information in many to many pattern between different groups. Thus we propose a novel data sharing scheme enabling many to many sharing of encrypted data between different groups with using cryptographic techniques such as traceable ring signatures, multiple receiver key...
More Efficient Post-Quantum Electronic Voting from NTRU
Patrick Hough, Caroline Sandsbråten, Tjerand Silde
Cryptographic protocols
In recent years, there has been much focus on developing core cryptographic primitives based on lattice assumptions, driven by the NIST cal for post-quantum key encapsulation and digital signature algorithms. However, more work must be conducted on efficient privacy-preserving protocols with post-quantum security.
Electronic voting is one such privacy-preserving protocol whose adoption is increasing across the democratic world. E-voting offers both a fast and convenient alternative to...
A New Formulation of the Linear Equivalence Problem and Shorter LESS Signatures
Edoardo Persichetti, Paolo Santini
Public-key cryptography
The Linear Equivalence Problem (LEP) asks to find a linear isometry between a given pair of linear codes; in the Hamming weight this is known as a monomial map. LEP has been used in cryptography to design the family of LESS signatures, which includes also some advanced schemes, such as ring and identity-based signatures. All of these schemes are obtained applying the Fiat-Shamir transformation to a Sigma protocol, in which the prover's responses contain a description of how the monomial map...
Lattice-based Commit-Transferrable Signatures and Applications to Anonymous Credentials
Qiqi Lai, Chongshen Chen, Feng-Hao Liu, Anna Lysyanskaya, Zhedong Wang
Cryptographic protocols
Anonymous Credentials are an important tool to protect user's privacy for proving possession of certain credentials.
Although various efficient constructions have been proposed based on pre-quantum assumptions, there have been limited accomplishments in the post-quantum and especially practical settings. This research aims to derive new methods that enhance the current state of the art.
To achieve this, we make the following contributions.
By distilling prior design insights, we...
On Sustainable Ring-based Anonymous Systems
Sherman S. M. Chow, Christoph Egger, Russell W. F. Lai, Viktoria Ronge, Ivy K. Y. Woo
Applications
Anonymous systems (e.g. anonymous cryptocurrencies and updatable anonymous credentials) often follow a construction template where an account can only perform a single anonymous action, which in turn potentially spawns new (and still single-use) accounts (e.g. UTXO with a balance to spend or session with a score to claim). Due to the anonymous nature of the action, no party can be sure which account has taken part in an action and, therefore, must maintain an ever-growing list of potentially...
Compact Lattice Gadget and Its Applications to Hash-and-Sign Signatures
Yang Yu, Huiwen Jia, Xiaoyun Wang
Public-key cryptography
Lattice gadgets and the associated algorithms are the essential building blocks of lattice-based cryptography. In the past decade, they have been applied to build versatile and powerful cryptosystems. However, the practical optimizations and designs of gadget-based schemes generally lag their theoretical constructions.
For example, the gadget-based signatures have elegant design and capability of extending to more advanced primitives, but they are far less efficient than other lattice-based...
MPC in the head for isomorphisms and group actions
Antoine Joux
Cryptographic protocols
In this paper, we take inspiration from an invited talk presented at CBCrypto'23 to design identification protocols and signature schemes from group actions using the MPC-in-the-head paradigm. We prove the security of the given identification schemes and rely on the Fiat-Shamir transformation to turn them into signatures.
We also establish a parallel with the technique used for the MPC-in-the-head approach and the seed tree method that has been recently used in some signature and ring...
A Holistic Security Analysis of Monero Transactions
Cas Cremers, Julian Loss, Benedikt Wagner
Cryptographic protocols
Monero is a popular cryptocurrency with strong privacy guarantees for users’ transactions. At the heart of Monero’s privacy claims lies a complex transaction system called RingCT, which combines several building blocks such as linkable ring signatures, homomorphic commitments, and range proofs, in a unique fashion. In this work, we provide the first rigorous security analysis for RingCT (as given in Zero to Monero, v2.0.0, 2020) in its entirety. This is in contrast to prior works that only...
Fusion One-Time Non-Interactively-Aggregatable Digital Signatures From Lattices
Brandon Goodell, Aaron Feickert
Cryptographic protocols
We present Fusion, a post-quantum one-time digital signature scheme with non-interactive aggregation with security resting on the short integer solution problem over ideal lattices. Fusion is structurally similar to CRYSTALS-Dilithium, but Fusion is based upon the aggregatable one-time lattice-based scheme by Boneh and Kim. Fusion parameters conservatively target at least $128$ bits of security against forgery, taking tightness gaps into account, and with tighter bounds than the BK scheme....
Deuring for the People: Supersingular Elliptic Curves with Prescribed Endomorphism Ring in General Characteristic
Jonathan Komada Eriksen, Lorenz Panny, Jana Sotáková, Mattia Veroni
Constructing a supersingular elliptic curve whose endomorphism ring is isomorphic to a given quaternion maximal order (one direction of the Deuring correspondence) is known to be polynomial-time assuming the generalized Riemann hypothesis [KLPT14; Wes21], but notoriously daunting in practice when not working over carefully selected base fields.
In this work, we speed up the computation of the Deuring correspondence in general characteristic, i.e., without assuming any special form of the...
Lattice-Based Blind Signatures: Short, Efficient, and Round-Optimal
Ward Beullens, Vadim Lyubashevsky, Ngoc Khanh Nguyen, Gregor Seiler
Public-key cryptography
We give a construction of a 2-round blind signature scheme based on the hardness of standard lattice problems (Ring/Module-SIS/LWE and NTRU) with a signature size of 22 KB. The protocol is round-optimal and has a transcript size that can be as small as 60 KB. This blind signature is around $4$ times shorter than the most compact lattice-based scheme based on standard assumptions of del Pino and Katsumata (Crypto 2022) and around $2$ times shorter than the scheme of Agrawal et al. (CCS 2022)...
Key-and-Signature Compact Multi-Signatures for Blockchain: A Compiler with Realizations
Shaoquan Jiang, Dima Alhadidi, Hamid Fazli Khojir
Cryptographic protocols
Multi-signature is a protocol where a set of signatures jointly sign a message so that the final signature is significantly shorter than concatenating individual signatures together. Recently, it finds applications in blockchain, where several users want to jointly authorize a payment through a multi-signature. However, in this setting, there is no centralized authority and it could suffer from a rogue key attack where the attacker can generate his own keys arbitrarily. Further, to...
Ring Verifiable Random Functions and Zero-Knowledge Continuations
Jeffrey Burdges, Oana Ciobotaru, Handan Kılınç Alper, Alistair Stewart, Sergey Vasilyev
Cryptographic protocols
We introduce a new cryptographic primitive, named ring verifiable random function (ring VRF). Ring VRF combines properties of VRF and ring signatures, offering verifiable unique, pseudorandom outputs while ensuring anonymity of the output and message authentication. We design its security in the universal composability (UC) framework and construct two protocols secure in our model. We also formalize a new notion of zero-knowledge (ZK) continuations allowing for the reusability of proofs by...
Ring Signatures with User-Controlled Linkability
Dario Fiore, Lydia Garms, Dimitris Kolonelos, Claudio Soriente, Ida Tucker
Public-key cryptography
Anonymous authentication primitives, e.g., group or ring signatures, allow one to realize privacy-preserving data collection applications, as they strike a balance between authenticity of data being collected and privacy of data providers. At PKC 2021, Diaz and Lehmann defined group signatures with User-Controlled Linkability (UCL) and provided an instantiation based on BBS+ signatures. In a nutshell, a signer of a UCL group signature scheme can link any of her signatures: linking evidence...
A Simple Noncommutative UOV Scheme
Lih-Chung Wang, Po-En Tseng, Yen-Liang Kuan, Chun-Yen Chou
Public-key cryptography
In this paper, we propose a simple noncommutative-ring based UOV signature scheme with key-randomness alignment: Simple NOVA, which can be viewed as a simplified version of NOVA[48]. We simplify the design of NOVA by skipping the perturbation trick used in NOVA, thus shortens the key generation process and accelerates the signing and verification. Together with a little modification accordingly, this alternative version of NOVA is also secure and may be more suitable for practical uses. We...
LightSwap: An Atomic Swap Does Not Require Timeouts At Both Blockchains
Philipp Hoenisch, Subhra Mazumdar, Pedro Moreno-Sanchez, Sushmita Ruj
Cryptographic protocols
Security and privacy issues with centralized exchange services have motivated the design of atomic swap protocols for decentralized trading across currencies. These protocols follow a standard blueprint similar to the 2-phase commit in databases: (i) both users first lock their coins under a certain (cryptographic) condition and a timeout; (ii-a) the coins are swapped if the condition is fulfilled; or (ii-b) coins are released after the timeout. The quest for these protocols is to minimize...
Division of Regulatory Power: Collaborative Regulation for Privacy-Preserving Blockchains
Tianyu Zhaolu, Zhiguo Wan, Huaqun Wang
Applications
Decentralized anonymous payment schemes may be exploited for illicit activities, such as money laundering, bribery and blackmail. To address this issue, several regulatory friendly decentralized anonymous payment schemes have been proposed. However, most of these solutions lack restrictions on the regulator’s authority, which could potentially result in power abuse and privacy breaches. In this paper, we present a decentralized anonymous payment scheme with collaborative regulation (DAPCR)....
Extendable Threshold Ring Signatures with Enhanced Anonymity
Gennaro Avitabile, Vincenzo Botta, Dario Fiore
Cryptographic protocols
Threshold ring signatures are digital signatures that allow $t$ parties to sign a message while hiding their identity in a larger set of $n$ users called ''ring''.
Recently, Aranha et al. [PKC 2022] introduced the notion of \emph{extendable} threshold ring signatures (ETRS).
ETRS allow one to update, in a non-interactive manner, a threshold ring signature on a certain message so that the updated signature has a greater threshold, and/or an augmented set of potential signers.
An...
Efficient Gaussian sampling for RLWE-based cryptography through a fast Fourier transform
Marcio Barbado Junior
Applications
Quantum computing threatens classical cryptography, leading to the search for stronger alternatives. The cryptographic approach based on lattices is considered as a viable option. Schemes with that approach use Gaussian sampling, a design which brings along two concerns: efficiency and information leakage. This work addresses those concerns in the RLWE formulation, for digital signatures. Efficiency mitigation uses the central limit theorem, and the Walsh–Hadamard transform, whereas the...
A Lattice-based Ring Signature Scheme Secure against Key Exposure
Xiaoling Yu, Yuntao Wang
Public-key cryptography
A ring signature scheme allows a group member to generate a signature on behalf of the whole group, while the verifier can not tell who computed this signature. However, most predecessors do not guarantee security from the secret key leakage of signers. In 2002, Anderson proposed the forward security mechanism to reduce the effect of such leakage. In this paper, we construct the first lattice-based ring signature scheme with forward security. Our scheme combines the binary tree and lattice...
Efficient Linkable Ring Signature from Vector Commitment inexplicably named Multratug
Anton A. Sokolov
Cryptographic protocols
In this paper we revise the idea of our previous article “Lin2-Xor Lemma: an OR-proof that leads to the membership proof and signature” and introduce another lemma, called Lin2-Choice, which is a generalization of the Lin2-Xor lemma. With the Lin2-Choice lemma we obtain a compact general-purpose trusted-setup-free log-size linkable threshold ring signature called EFLRSL. The signature size is 2log(n+1)+3l+1, where n is the ring size and l is the threshold. By extending the set membership...
BLOOM: Bimodal Lattice One-Out-of-Many Proofs and Applications
Vadim Lyubashevsky, Ngoc Khanh Nguyen
Public-key cryptography
We give a construction of an efficient one-out-of-many proof system, in which a prover shows that he knows the pre-image for one element in a set, based on the hardness of lattice problems. The construction employs the recent zero-knowledge framework of Lyubashevsky et al. (Crypto 2022) together with an improved, over prior lattice-based one-out-of-many proofs, recursive procedure, and a novel rejection sampling proof that allows to use the efficient bimodal rejection sampling throughout the...
Improving the Efficiency of Report and Trace Ring Signatures
Xavier Bultel, Ashley Fraser, Elizabeth A. Quaglia
Cryptographic protocols
Ring signatures allow signers to produce verifiable signatures and remain anonymous within a set of signers (i.e., the ring) while doing so. They are well-suited to protocols that target anonymity as a primary goal, for example, anonymous cryptocurrencies. However, standard ring signatures do not ensure that signers are held accountable if they act maliciously. Fraser and Quaglia (CANS'21) introduced a ring signature variant that they called report and trace ring signatures which balances...
Universal Ring Signatures in the Standard Model
Pedro Branco, Nico Döttling, Stella Wohnig
Cryptographic protocols
Ring signatures allow a user to sign messages on behalf of an ad hoc set of users - a ring - while hiding her identity. The original motivation for ring signatures was whistleblowing [Rivest et al. ASIACRYPT'01]: a high government employee can anonymously leak sensitive information while certifying that it comes from a reliable source, namely by signing the leak. However, essentially all known ring signature schemes require the members of the ring to publish a structured verification key...
On digital signatures based on group actions: QROM security and ring signatures
Markus Bläser, Zhili Chen, Dung Hoang Duong, Antoine Joux, Ngoc Tuong Nguyen, Thomas Plantard, Youming Qiao, Willy Susilo, Gang Tang
Public-key cryptography
Group action based cryptography was formally proposed in the seminal paper of Brassard and Yung (Crypto 1990). Based on oneway group action, there is a well-known digital signature design based on the Goldreich–Micali–Widgerson (GMW) zero-knowledge protocol for the graph isomorphism problem and the Fiat–Shamir (FS) transformation. Recently, there is a revival of activities on group action based cryptography and the GMW-FS design, as witnessed by the schemes SeaSign (Eurocrypt 2019), CSI-FiSh...
2022/1175
Last updated: 2022-09-13
A Cryptanalysis of NOVA Signature Scheme
Dongyu Wu
Attacks and cryptanalysis
NOVA signature scheme is a UOV-type signature scheme over a non-commutative coefficient ring with a novel structural map. In this article we show that a randomly generated central map for the scheme is very likely insecure and may suffer from a forgery attack in polynomial time.
TRIFORS: LINKable Trilinear Forms Ring Signature
Giuseppe D'Alconzo, Andrea Gangemi
Public-key cryptography
We present TRIFORS (TRIlinear FOrms Ring Signature), a logarithmic post-quantum (linkable) ring signature based on a novel assumption regarding the equivalence of alternating trilinear forms. The basis of this work is the construction by Beullens, Katsumata and Pintore from Asiacrypt 2020 to obtain a linkable ring signature from a cryptographic group action. The group action on trilinear forms used here is the same employed in the signature presented by Tang et al. at Eurocrypt 2022. We...
A Survey on Exotic Signatures for Post-Quantum Blockchain: Challenges & Research Directions
Maxime Buser, Rafael Dowsley, Muhammed F. Esgin, Clémentine Gritti, Shabnam Kasra Kermanshahi, Veronika Kuchta, Jason T. LeGrow, Joseph K. Liu, Raphael C.-W. Phan, Amin Sakzad, Ron Steinfeld, Jiangshan Yu
Public-key cryptography
Blockchain technology provides efficient and secure solutions to various online activities by utilizing a wide range of cryptographic tools. In this paper, we survey the existing literature on post-quantum secure digital signatures that possess exotic advanced features and which are crucial cryptographic tools used in the blockchain ecosystem for (i) account management, (ii) consensus efficiency, (iii) empowering scriptless blockchain, and (iv) privacy. The exotic signatures that we...
On the Higher bit Version of Approximate Inhomogeneous Short Integer Solution Problem
Anaëlle Le Dévéhat, Hiroki Shizuya, Shingo Hasegawa
Public-key cryptography
We explore a bitwise modification in Ajtai's one-way function. Our main contribution is to define the higher-bit approximate inhomogeneous short integer solution (ISIS) problem and prove its reduction to the ISIS problem. In this new instance, our main idea is to discard low-weighted bits to gain compactness.
As an application, we construct a bitwise version of a hash-and-sign signature in the random oracle model whose security relies on the (Ring)-LWE and (Ring)-ISIS...
Designated-Verifier Linkable Ring Signatures with unconditional anonymity
Danai Balla, Pourandokht Behrouz, Panagiotis Grontas, Aris Pagourtzis, Marianna Spyrakou, Giannis Vrettos
Public-key cryptography
We propose Designated-Verifier Linkable Ring Signatures with unconditional anonymity, a cryptographic primitive that protects the privacy of signers in two ways:
Firstly, it allows them to hide inside a ring (i.e. an anonymity set) they can create by collecting a set of public keys all of which must be used for verification.
Secondly, it allows a designated entity to simulate signatures thus making it difficult for an adversary to deduce their identity from the content of the exchanged...
Efficient Unique Ring Signatures From Lattices
Tuong Ngoc Nguyen, Anh The Ta, Huy Quoc Le, Dung Hoang Duong, Willy Susilo, Fuchun Guo, Kazuhide Fukushima, Shinsaku Kiyomoto
Cryptographic protocols
Unique ring signatures (URS) were introduced by Franklin and Zhang (FC 2012) as a unification of linkable and traceable ring signatures. In URS, each member within a ring can only produce, on behalf of the ring, at most one signature for a message. Applications of URS potentially are e-voting systems and e–token systems. In blockchain technology, URS has been implemented for mixing contracts. However, existing URS schemes are based on the Discrete Logarithm Problem, which is insecure in the...
Multimodal Private Signatures
Khoa Nguyen, Fuchun Guo, Willy Susilo, Guomin Yang
Cryptographic protocols
We introduce Multimodal Private Signature (MPS) - an anonymous signature system that offers a novel accountability feature: it allows a designated opening authority to learn some partial information $\mathsf{op}$ about the signer's identity $\mathsf{id}$, and nothing beyond. Such partial information can flexibly be defined as $\mathsf{op} = \mathsf{id}$ (as in group signatures), or as $\mathsf{op} = \mathbf{0}$ (like in ring signatures), or more generally, as $\mathsf{op} =...
MR-DSS – Smaller MinRank-based (Ring-)Signatures
Emanuele Bellini, Andre Esser, Carlo Sanna, Javier Verbel
Cryptographic protocols
In the light of NIST’s announced reopening of the call for digital signature proposals in 2023 due to lacking diversity, there is a strong need for constructions based on other established hardness assumptions. In this work we construct a new post-quantum secure digital signature scheme based on the $MinRank$ problem, a problem with a long history of applications in cryptanalysis that led to a strong belief in its hardness. Initially following a design by Courtois (Asiacrypt '01) based on...
Efficient Generic Arithmetic for KKW Practical Linear: MPC-in-the-Head NIZK on Commodity Hardware without Trusted Setup
David Heath, Vladimir Kolesnikov, Jiahui Lu
Cryptographic protocols
Katz et al., CCS 2018 (KKW) is a popular and efficient MPC-in-the-head non-interactive ZKP (NIZK) scheme, which is the technical core of the post-quantum signature scheme Picnic, currently considered for standardization by NIST. The KKW approach simultaneously is concretely efficient, even on commodity hardware, and does not rely on trusted setup. Importantly, the approach scales linearly in the circuit size with low constants with respect to proof generation time, proof verification time,...
Efficient Proofs of Knowledge for Threshold Relations
Gennaro Avitabile, Vincenzo Botta, Daniele Friolo, Ivan Visconti
Cryptographic protocols
Recently, there has been great interest towards constructing efficient zero-knowledge proofs for practical languages.
In this work, we focus on proofs for threshold relations, in which the prover is required to prove knowledge of witnesses for $k$ out of $\ell$ statements.
The main contribution of our work is an efficient and modular transformation that starting from a large class of $\Sigma$-protocols and a corresponding threshold relation $\mathcal{R}_\mathsf{k,\ell}$, provides an...
Advanced Signature Functionalities from the Code Equivalence Problem
Alessandro Barenghi, Jean-Francois Biasse, Tran Ngo, Edoardo Persichetti, Paolo Santini
Public-key cryptography
The LESS signature scheme, introduced in 2020, represented a fresh start for code-based signatures. In this paper we explore advanced functionalities for signature schemes, stemming from the work of LESS. First, we adapt a recent protocol of Beullens et al. to obtain a construction for (linkable) ring signatures. Then, we realize an identity-based signature scheme following the traditional approach by Joye and Neven. Our performance numbers confirm that signature schemes based on the code...
Squirrel: Efficient Synchronized Multi-Signatures from Lattices
Nils Fleischhacker, Mark Simkin, Zhenfei Zhang
Public-key cryptography
The focus of this work are multi-signatures schemes in the synchronized setting. A multi-signature scheme allows multiple signatures for the same message but from independent signers to be compressed into one short aggregated signature, which allows verifying all of the signatures simultaneously. In the synchronized setting, the signing algorithm takes the current time step as an additional input. It is assumed that no signer signs more than one message per time step and we aim to aggregate...
NOVA, a Noncommutative-ring Based Unbalanced Oil and Vinegar Signature Scheme with Key-randomness Alignment
Lih-Chung Wang, Po-En Tseng, Yen-Liang Kuan, Chun-Yen Chou
Public-key cryptography
In this paper, we propose a noncommutative-ring based unbalanced oil and vinegar signature scheme with key-randomness alignment: NOVA (Noncommutative Oil and Vinegar with Alignment). Instead of fields or even commutative rings, we show that noncommutative rings can be used for algebraic cryptosystems. At the same or better level of security requirement, NOVA has a much smaller public key than UOV (Unbalanced Oil and Vinegar), which makes NOVA practical in most situations. We use Magma to...
Round-Optimal Lattice-Based Threshold Signatures, Revisited
Shweta Agrawal, Damien Stehle, Anshu Yadav
Public-key cryptography
Threshold signature schemes enable distribution of the signature issuing capability to multiple users, to mitigate the threat of signing key compromise. Though a classic primitive, these signatures have witnessed a surge of interest in recent times due to relevance to modern applications like blockchains and cryptocurrencies. In this work, we study round-optimal threshold signatures in the post- quantum regime and improve the only known lattice-based construction by Boneh et al [CRYPTO’18]...
Resumable Zero-Knowledge for Circuits from Symmetric Key Primitives
Handong Zhang, Puwen Wei, Haiyang Xue, Yi Deng, Jinsong Li, Wei Wang, Guoxiao Liu
Public-key cryptography
Consider the scenario that the prover and the verifier perform the zero-knowledge (ZK) proof protocol for the same statement multiple times sequentially, where each proof is modeled as a session. We focus on the problem of how to resume a ZK proof efficiently in such scenario. We introduce a new primitive called resumable honest verifier zero-knowledge proof of knowledge (resumable HVZKPoK) and propose a general construction of the resumable HVZKPoK for circuits based on the...
Short Lattice Signature Scheme with Tighter Reduction under Ring-SIS Assumption
Kaisei Kajita, Go Ohtake, Kazuto Ogawa, Koji Nuida, Tsuyoshi Takagi
Public-key cryptography
We propose a short signature scheme under the ring-SIS assumption in the standard model.
Specifically, by revisiting an existing construction [Ducas and Micciancio, CRYPTO 2014], we demonstrate lattice-based signatures with improved reduction loss. As far as we know, there are no ways to use multiple tags in the signature simulation of security proof in the lattice tag-based signatures. We address the tag-collision possibility in the lattice setting, which improves reduction loss. Our scheme...
Designated-Verifier Linkable Ring Signatures
Pourandokht Behrouz, Panagiotis Grontas, Vangelis Konstantakatos, Aris Pagourtzis, Marianna Spyrakou
Public-key cryptography
We introduce Designated-Verifier Linkable Ring Signatures (DVLRS), a novel cryptographic primitive which combines designated-verifier and linkable ring signatures. Our goal is to guarantee signer ambiguity and provide the capability to the designated verifier to add ‘noise’ using simulated signatures that are publicly verifiable. This increases the privacy of the participants, as it does not allow an adversary to bypass the anonymity provided by ring signatures by using the
content of a...
Post-Quantum ID-based Ring Signatures from Symmetric-key Primitives
Maxime Buser, Joseph K. Liu, Ron Steinfeld, Amin Sakzad
Cryptographic protocols
Ring signatures and ID-based cryptography are considered promising in terms of application. A ring signature authenticates messages while the author of the message remains anonymous. ID-based cryptographic primitives suppress the need for certificates in public key infrastructures (PKI). In this work, we propose a generic construction for post-quantum ID-based ring signatures (IDRS) based on symmetric-key primitives from which we derive the first two constructions of IDRS. The first...
Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General
Vadim Lyubashevsky, Ngoc Khanh Nguyen, Maxime Plancon
Public-key cryptography
We present a much-improved practical protocol, based on the hardness of Module-SIS and Module-LWE problems, for proving knowledge of a short vector $s$ satisfying $As=t\bmod q$. The currently most-efficient technique for constructing such a proof works by showing that the $\ell_\infty$ norm of $s$ is small. It creates a commitment to a polynomial vector $m$ whose CRT coefficients are the coefficients of $s$ and then shows that (1) $A\cdot \mathsf{CRT}(m)=t\bmod\,q$ and (2) in the case that...
In 2022, Wang et al. proposed the multivariate signature scheme SNOVA as a UOV variant over the non-commutative ring of $\ell \times \ell $ matrices over $\mathbb{F}_q$. This scheme has small public key and signature size and is a first round candidate of NIST PQC additional digital signature project. Recently, Ikematsu and Akiyama, and Li and Ding show that the core matrices of SNOVA with $v$ vinegar-variables and $o$ oil-variables are regarded as the representation matrices of UOV with...
With the rapid advance in quantum computing, quantum security is now an indispensable property for any cryptographic system. In this paper, we study how to prove the security of a complex cryptographic system in the quantum random oracle model. We first give a variant of Zhandry's compressed quantum random oracle (${\bf CStO}$), called compressed quantum random oracle with adaptive special points ({\bf CStO}$_s$). Then, we extend the on-line extraction technique of Don et al...
The Extended Greatest Common Divisor (XGCD) computation is a critical component in various cryptographic applications and algorithms, including both pre- and post-quantum cryptosystems. In addition to computing the greatest common divisor (GCD) of two integers, the XGCD also produces Bezout coefficients $b_a$ and $b_b$ which satisfy $\mathrm{GCD}(a,b) = a\times b_a + b\times b_b$. In particular, computing the XGCD for large integers is of significant interest. Most recently, XGCD computation...
With the potential arrival of quantum computers, it is essential to build cryptosystems resistant to attackers with the computing power of a quantum computer. With Shor's algorithm, cryptosystems based on discrete logarithms and factorization become obsolete. Reason why NIST has launching two competitions in 2016 and 2023 to standardize post-quantum cryptosystems (such as KEM and signature ) based on problems supposed to resist attacks using quantum computers. EagleSign was prosed to NIT...
We construct two efficient post-quantum ring signatures with anonymity against full key exposure from isogenies, addressing limitations of existing isogeny-based ring signatures. First, we present an efficient concrete distinguisher for the SQIsign simulator when the signing key is provided using one transcript. This shows that turning SQIsign into an efficient full anonymous ring signature requires some new ideas. Second, we propose a variant of SQIsign that is resistant to the...
Dimension 4 isogenies have first been introduced in cryptography for the cryptanalysis of Supersingular Isogeny Diffie-Hellman (SIDH) and have been used constructively in several schemes, including SQIsignHD, a derivative of SQIsign isogeny based signature scheme. Unlike in dimensions 2 and 3, we can no longer rely on the Jacobian model and its derivatives to compute isogenies. In dimension 4 (and higher), we can only use theta-models. Previous works by Romain Cosset, David Lubicz and Damien...
Zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) is a kind of proof system that enables a prover to convince a verifier that an NP statement is true efficiently. In the last decade, various studies made a lot of progress in constructing more efficient and secure zk-SNARKs. Our research focuses on designated-verifier zk-SNARKs, where only the verifier knowing some secret verification state can be convinced by the proof. A natural idea of getting a designated-verifier...
Ring signatures are one of the crucial cryptographic primitives used in the design of privacy-preserving systems. Such a signature scheme allows a signer to anonymously sign a message on behalf of a spontaneously formed group. It not only ensures the authenticity of the message but also conceals the true signer within the group. An important extension of ring signatures is linkable ring signatures, which prevent a signer from signing twice without being detected (under some constraints)....
t-out-of-n threshold ring signature (TRS) is a type of anonymous signature designed for t signers to jointly sign a message while hiding their identities among n parties that include themselves. However, can TRS address those needs if one of the signers wants to revoke his signature or, additively, sign separately later? Can non-signers be revoked without compromising anonymity? Previous research has only discussed opposing situations. The present study introduces a novel property for...
A number of existing cryptosystems use the well-known linear-size LSAG signature concept, extending it in many ways. This article presents a simple logarithmic-size signature LS-LSAG which, despite a radical reduction in size, retains the basic code block of LSAG. Therefore, substituting LS-LSAG for LSAG requires minimal changes to almost any existing LSAG/CLSAG-based solution, making it logarithmic instead of linear.
Ring signatures, a cryptographic primitive introduced by Rivest, Shamir and Tauman (ASIACRYPT 2001), offer signer anonymity within dynamically formed user groups. Recent advancements have focused on lattice-based constructions to improve efficiency, particularly for large signing rings. However, current state-of-the-art solutions suffer from significant overhead, especially for smaller rings. In this work, we present a novel NTRU-based ring signature scheme, Gandalf, tailored towards...
We design and implement a novel post-quantum signature scheme based on the Legendre PRF, named Loquat. Prior to this work, efficient approaches for constructing post-quantum signatures with comparable security assumptions mainly used the MPC-in-the-head paradigm or hash trees. Our method departs from these paradigms and, notably, is SNARK-friendly, a feature not commonly found in earlier designs. Loquat requires significantly fewer computational operations for verification than other...
Ring signatures allow members of a group (called "ring") to sign a message anonymously within the group, which is chosen ad hoc at the time of signing (the members do not need to have interacted before). In this paper, we propose a physical version of ring signatures. Our signature is based on one-out-of-many signatures, a method used in many real cryptographic ring signatures. It consists of boxes containing coins locked with padlocks that can only be opened by a particular group member. To...
This work introduces DEFI - an efficient hash-and-sign digital signature scheme based on isotropic quadratic forms over a commutative ring of characteristic 0. The form is public, but the construction is a trapdoor that depends on the scheme's private key. For polynomial rings over integers and rings of integers of algebraic number fields, the cryptanalysis is reducible to solving a quadratic Diophantine equation over the ring or, equivalently, to solving a system of quadratic Diophantine...
Equivalence class signatures allow a controlled form of malleability based on equivalence classes defined over the message space. As a result, signatures can be publicly randomized and adapted to a new message representative in the same equivalence class. Notably, security requires that an adapted signature-message pair looks indistinguishable from a random signature-message pair in the space of valid signatures for the new message representative. Together with the decisional Diffie-Hellman...
We revisit the alternating-moduli paradigm for constructing symmetric-key primitives with a focus on constructing efficient protocols to evaluate them using secure multi-party computation (MPC). The alternating-moduli paradigm of Boneh, Ishai, Passelègue, Sahai, and Wu (TCC 2018) enables the construction of various symmetric-key primitives with the common characteristic that the inputs are multiplied by two linear maps over different moduli. The first contribution focuses on...
In this paper, we introduce a new framework for constructing linkable ring signatures (LRS). Our framework is based purely on signatures of knowledge (SoK) which allows one to issue signatures on behalf of any NP-statement using the corresponding witness. Our framework enjoys the following advantages: (1) the security of the resulting LRS depends only on the security of the underlying SoK; (2) the resulting LRS naturally supports online/offline signing (resp. verification), where the output...
Linkable ring signatures are an important cryptographic primitive for anonymized applications, such as e-voting, e-cash and confidential transactions. To eliminate backdoor and overhead in a trusted setup, transparent setup in the discrete logarithm or pairing settings has received considerable attention in practice. Recent advances have improved the proof sizes and verification efficiency of linkable ring signatures with a transparent setup to achieve logarithmic bounds. Omniring (CCS '19)...
We introduce a toolkit for transforming lattice-based hash-and-sign signature schemes into masking-friendly signatures secure in the t-probing model. Until now, efficiently masking lattice-based hash-and-sign schemes has been an open problem, with unsuccessful attempts such as Mitaka. A first breakthrough was made in 2023 with the NIST PQC submission Raccoon, although it was not formally proven. Our main conceptual contribution is to realize that the same principles underlying Raccoon...
We suggest the family of ciphers s^E^n, n=2,3,.... with the space of plaintexts (Z*_{2^s})^n, s >1 such that the encryption map is the composition of kind G=G_1A_1G_2A_2 where A_i are the affine transformations from AGL_n(Z_{2^s}) preserving the variety (Z*_{2^s)}^n , Eulerian endomorphism G_i , i=1,2 of K[x_1, x_2,...., x_n] moves x_i to monomial term ϻ(x_1)^{d(1)}(x_2)^{d(2)}...(x_n)^{d(n)} , ϻϵ Z*_{2^s} and act on (Z*_{2^s})^n as bijective transformations. The cipher is...
Several prior works have suggested to use non-interactive arguments of knowledge with short proofs to aggregate signatures of Falcon, which is part of the first post-quantum signatures selected for standardization by NIST. Especially LaBRADOR, based on standard structured lattice assumptions and published at CRYPTO’23, seems promising to realize this task. However, no prior work has tackled this idea in a rigorous way. In this paper, we thoroughly prove how to aggregate Falcon signatures...
The Linear Code Equivalence (LCE) Problem has received increased attention in recent years due to its applicability in constructing efficient digital signatures. Notably, the LESS signature scheme based on LCE is under consideration for the NIST post-quantum standardization process, along with the MEDS signature scheme that relies on an extension of LCE to the rank metric, namely the Matrix Code Equivalence (MCE) Problem. Building upon these developments, a family of signatures with...
Equivalence class signatures (EQS), introduced by Hanser and Slamanig (AC'14), sign vectors of elements from a bilinear group. Signatures can be ``adapted'', meaning that anyone can transform a signature on a vector to a (random) signature on any multiple of that vector. (Signatures thus authenticate equivalence classes.) A transformed signature/message pair is then indistinguishable from a random signature on a random message. EQS have been used to efficiently instantiate (delegatable)...
In response to the evolving landscape of quantum computing and the heightened vulnerabilities in classical cryptographic systems, our paper introduces a comprehensive cryptographic framework. Building upon the pioneering work of Kuang et al., we present a unification of two innovative primitives: the Quantum Permutation Pad (QPP) for symmetric key encryption and the Homomorphic Polynomial Public Key (HPPK) for Key Encapsulation Mechanism (KEM) and Digital Signatures (DS). By harnessing...
The Signal protocol and its X3DH key exchange core are regularly used by billions of people in applications like WhatsApp but are unfortunately not quantum-secure. Thus, designing an efficient and post-quantum secure X3DH alternative is paramount. Notably, X3DH supports asynchronicity, as parties can immediately derive keys after uploading them to a central server, and deniability, allowing parties to plausibly deny having completed key exchange. To satisfy these constraints, existing...
SNOVA is a variant of a UOV-type signature scheme over a noncommutative ring. In this article, we demonstrate that certain parameters provided by authors in SNOVA fail to meet the NIST security level, and the complexities are lower than those claimed by SNOVA.
SNOVA is a multivariate signature scheme submitted to the ad- ditional NIST PQC standardization project started in 2022. SNOVA is con- structed by incorporating the structure of the matrix ring over a finite field into the UOV signature scheme, and the core part of its public key is the UOV public key whose coefficients consist of matrices. As a result, SNOVA dramatically reduces the public key size compared to UOV. In this paper, we recall the construction of SNOVA, and reconsider its...
In this work, we propose two novel succinct one-out-of-many proofs from coding theory, which can be seen as extensions of the Stern's framework and Veron's framework from proving knowledge of a preimage to proving knowledge of a preimage for one element in a set, respectively. The size of each proof is short and scales better with the size of the public set than the code-based accumulator in \cite{nguyen2019new}. Based on our new constructions, we further present a logarithmic-size ring...
In today's systems, privacy is often at odds with utility: users that reveal little information about themselves get restricted functionality, and service providers mistrust them. In practice, systems tip to either full anonymity (e.g. Monero), or full utility (e.g. Bitcoin). Well-known cryptographic primitives for bridging this gap exist: anonymous credentials (AC) let users disclose a subset of their credentials' attributes, revealing to service providers "just what they need"; group...
Recently, Qiu et al. proposed a semi-quantum voting scheme based on the ring signature (International Journal of Theoretical Physics, 60: 1550–1555(2021)), in which the signer and verifier only need measure the received particles with Z-basis and perform some classical simple encryption/decryption operations on the classical message. Although their scheme is very efficient, it cannot resist against the eavesdropping attacks and forgery attack. In this paper, first, the eavesdropping attacks...
This paper conducts a comprehensive benchmarking analysis of the performance of two innovative cryptographic schemes: Homomorphic Polynomial Public Key (HPPK)-Key Encapsulation Mechanism (KEM) and Digital Signature (DS), recently proposed by Kuang et al. These schemes represent a departure from traditional cryptographic paradigms, with HPPK leveraging the security of homomorphic symmetric encryption across two hidden rings without reliance on NP-hard problems. HPPK can be viewed as a...
Let n stands for the length of digital signatures with quadratic multivariate public rule in n variables. We construct postquantum secure procedure to sign O(n^t), t ≥1 digital documents with the signature of size n in time O(n^{3+t}). It allows to sign O(n^t), t <1 in time O(n^4). The procedure is defined in terms of Algebraic Cryptography. Its security rests on the semigroup based protocol of Noncommutative Cryptography referring to complexity of the decomposition of the collision...
In the wake of recent progress on quantum computing hardware, the National Institute of Standards and Technology (NIST) is standardizing cryptographic protocols that are resistant to attacks by quantum adversaries. The primary digital signature scheme that NIST has chosen is CRYSTALS-Dilithium. The hardness of this scheme is based on the hardness of three computational problems: Module Learning with Errors (MLWE), Module Short Integer Solution (MSIS), and SelfTargetMSIS. MLWE and MSIS have...
Isogeny-based cryptography is an instance of post-quantum cryptography whose fundamental problem consists of finding an isogeny between two (isogenous) elliptic curves $E$ and $E'$. This problem is closely related to that of computing the endomorphism ring of an elliptic curve. Therefore, many isogeny-based protocols require the endomorphism ring of at least one of the curves involved to be unknown. In this paper, we explore the design of isogeny based protocols in a scenario where one...
Digital signatures is a cryptographic protocol that can provide the added assurances of identity, status, proof of origin of an electronic document, and can acknowledge informed consent by the signer. Lattice based assumptions have seen a certain rush in recent years to fulfil the desire to expand the hardness assumption beyond factoring or discrete logarithm problem on which digital signatures can rely. In this article, we cover the recent progress made in digital signatures based on...
Electronic voting has occupied a large part of the cryptographic protocols literature. The recent reality of blockchains---in particular their need for online governance mechanisms---has put new parameters and requirements to the problem. We identify the key requirements of a blockchain governance mechanism, namely correctness (including eliminative double votes), voter anonymity, and traceability, and investigate mechanisms that can achieve them with minimal interaction and under...
VOX has been submitted to the NIST Round 1 Additional Signature of the Post-Quantum Signature Competition in June 2023. VOX is a strengthened variant of UOV which uses the Quotient-Ring (QR) setting to reduce the public-key size. At the end of August 2023, Furue and Ikamatsu posted on the NIST mailing-list a post, indicating that the parameters of VOX can be attacked efficiently using the rectangular attack in the QR setting. In this note, we explain the attack in the specific case of...
In their 2022 study, Kuang et al. introduced the Multivariable Polynomial Public Key (MPPK) cryptography, a quantum-safe public key cryptosystem leveraging the mutual inversion relationship between multiplication and division. MPPK employs multiplication for key pair construction and division for decryption, generating public multivariate polynomials. Kuang and Perepechaenko expanded the cryptosystem into the Homomorphic Polynomial Public Key (HPPK), transforming product polynomials over...
Motivated by applications in anonymous reputation systems and blockchain governance, we initiate the study of predicate aggregate signatures (PAS), which is a new primitive that enables users to sign multiple messages, and these individual signatures can be aggregated by a combiner, preserving the anonymity of the signers. The resulting PAS discloses only a brief description of signers for each message and provides assurance that both the signers and their description satisfy the specified...
We present a general framework for polynomial-time lattice Gaussian sampling. It revolves around a systematic study of the discrete Gaussian measure and its samplers under extensions of lattices; we first show that given lattices $\Lambda'\subset \Lambda$ we can sample efficiently in $\Lambda$ if we know how to do so in $\Lambda'$ and the quotient $\Lambda/\Lambda'$, \emph{regardless} of the primitivity of $\Lambda'$. As a direct application, we...
Ring signature (RS) allows users to demonstrate to verifiers their membership within a specified group (ring) without disclosing their identities. Based on this, RS can be used as a privacy protection technology for users' identities in blockchain. However, there is currently a lack of RS schemes that are fully applicable to the blockchain applications: Firstly, users can only spend a UTXO once, and the current RS schemes are not yet perfect in a one-time manner. At the same time, the...
Finding isogenies between supersingular elliptic curves is a natural algorithmic problem which is known to be equivalent to computing the curves' endomorphism rings. When the isogeny is additionally required to have a specific known degree $d$, the problem appears to be somewhat different in nature, yet its hardness is also required in isogeny-based cryptography. Let $E_1,E_2$ be supersingular elliptic curves over $\mathbb{F}_{p^2}$. We present improved classical and quantum...
The Number Theoretic Transform (NTT) is a powerful mathematical tool with a wide range of applications in various fields, including signal processing, cryptography, and error correction codes. In recent years, there has been a growing interest in efficiently implementing the NTT on hardware platforms for lattice-based cryptography within the context of NIST's Post-Quantum Cryptography (PQC) competition. The implementation of NTT in cryptography stands as a pivotal advancement,...
The MPC-in-the-Head paradigm is instrumental in building zero-knowledge proof systems and post-quantum signatures using techniques from secure multi-party computation. In this work, we extend and improve the recently proposed framework of MPC-in-the-Head based on threshold secret sharing, here called Threshold Computation in the Head. We first address some limitations of this framework, namely its overhead in the communication cost, its constraint on the number of parties and its degradation...
Recently a completely new post-quantum digital signature scheme was proposed using the so called ``scrap automorphisms''. The structure is inherently multivariate, but differs significantly from most of the multivariate literature in that it relies on sparsity and rings containing zero divisors. In this article, we derive a complete and total break of Scrap, performing a key recovery in not much more time than verifying a signature. We also generalize the result, breaking unrealistic...
In this paper, we introduce a novel trapdoor generation technique for Prest's hybrid sampler over NTRU lattices. Prest's sampler is used in particular in the recently proposed Mitaka signature scheme (Eurocrypt 2022), a variant of the Falcon signature scheme, one of the candidates selected by NIST for standardization. Mitaka was introduced to address Falcon's main drawback, namely the fact that the lattice Gaussian sampler used in its signature generation is highly...
In this paper, we show that it is impossible to construct a public key encryption scheme (PKE) from a ring signature scheme in a black-box fashion in the standard model. Such an impossibility is highly non-trivial because, to the best of our knowledge, known generic constructions of ring signature scheme are based on public key cryptosystems or in the random oracle model. Technically, we introduce a new cryptographic primitive named indistinguishable multi-designated verifiers signature...
We propose a new scheme based on ephemeral elliptic curves over the ring $\mathbb{Z}/n\mathbb{Z}$ where $n=pq$ is an RSA modulus with $p=u_p^2+v_p^2$, $q=u_q^2+v_q^2$, $u_p\equiv u_q\equiv 3\pmod 4$. The new scheme is a variant of both the RSA and the KMOV cryptosystems. The scheme can be used for both signature and encryption. We study the security of the new scheme and show that is immune against factorization attacks, discrete logarithm problem attacks, sum of two squares attacks, sum of...
From the work by Laguillaumie and Vergnaud in ICICS'04, it has been widely believed that multi-designated verifier signature schemes (MDVS) can be constructed from ring signature schemes in general. However in this paper, somewhat surprisingly, we prove that it is impossible to construct an MDVS scheme from a ring signature scheme in a black-box sense (in the standard model). The impossibility stems from the difference between the definitions of unforgeability. To the best of our...
In this paper, we construct the first provably-secure isogeny-based (partially) blind signature scheme. While at a high level the scheme resembles the Schnorr blind signature, our work does not directly follow from that construction, since isogenies do not offer as rich an algebraic structure. Specifically, our protocol does not fit into the "linear identification protocol" abstraction introduced by Hauck, Kiltz, and Loss (EUROCYRPT'19), which was used to generically construct...
A linkable ring signature allows a user to sign anonymously on behalf of a group while ensuring that multiple signatures from the same user are detected. Applications such as privacy-preserving e-voting and e-cash can leverage linkable ring signatures to significantly improve privacy and anonymity guarantees. To scale to systems involving large numbers of users, short signatures with fast verification are a must. Concretely efficient ring signatures currently rely on a trusted authority...
Masking is a well-studied method for achieving provable security against side-channel attacks. In masking, each sensitive variable is split into $d$ randomized shares, and computations are performed with those shares. In addition to the computational overhead of masked arithmetic, masking also has a storage cost, increasing the requirements for working memory and secret key storage proportionally with $d$. In this work, we introduce mask compression. This conceptually simple technique is...
Lattice-based cryptographic schemes such as Crystals-Kyber and Dilithium are post-quantum algorithms selected to be standardized by NIST as they are considered to be secure against quantum computing attacks. The multiplication in polynomial rings is the most time-consuming operation in many lattice-based cryptographic schemes, which is also subject to side-channel attacks. While NTT-based polynomial multiplication is almost a norm in a wide range of implementations, a relatively new method,...
Modern security systems depend fundamentally on the ability of users to authenticate their communications to other parties in a network. Unfortunately, cryptographic authentication can substantially undermine the privacy of users. One possible solution to this problem is to use privacy-preserving cryptographic authentication. These protocols allow users to authenticate their communications without revealing their identity to the verifier. In the non-interactive setting, the most common...
We introduce a new candidate post-quantum digital signature scheme from the regular syndrome decoding (RSD) assumption, an established variant of the syndrome decoding assumption which asserts that it is hard to find $w$-regular solutions to systems of linear equations over $\mathbb{F}_2$ (a vector is regular if it is a concatenation of $w$ unit vectors). Our signature is obtained by introducing and compiling a new 5-round zero-knowledge proof system constructed using the MPC-in-the-head...
A number of supersingular isogeny based cryptographic protocols require the endomorphism ring of the initial elliptic curve to be either unknown or random in order to be secure. To instantiate these protocols, Basso et al. recently proposed a secure multiparty protocol that generates supersingular elliptic curves defined over $\mathbb{F}_{p^2}$ of unknown endomorphism ring as long as at least one party acts honestly. However, there are many protocols that specifically require curves defined...
Many to many data sharing in the group setting in a cloud environment is a challenging problem that is crucial for numerous schemes. To our best knowledge, there is no generic study to allow sharing of confidential information in many to many pattern between different groups. Thus we propose a novel data sharing scheme enabling many to many sharing of encrypted data between different groups with using cryptographic techniques such as traceable ring signatures, multiple receiver key...
In recent years, there has been much focus on developing core cryptographic primitives based on lattice assumptions, driven by the NIST cal for post-quantum key encapsulation and digital signature algorithms. However, more work must be conducted on efficient privacy-preserving protocols with post-quantum security. Electronic voting is one such privacy-preserving protocol whose adoption is increasing across the democratic world. E-voting offers both a fast and convenient alternative to...
The Linear Equivalence Problem (LEP) asks to find a linear isometry between a given pair of linear codes; in the Hamming weight this is known as a monomial map. LEP has been used in cryptography to design the family of LESS signatures, which includes also some advanced schemes, such as ring and identity-based signatures. All of these schemes are obtained applying the Fiat-Shamir transformation to a Sigma protocol, in which the prover's responses contain a description of how the monomial map...
Anonymous Credentials are an important tool to protect user's privacy for proving possession of certain credentials. Although various efficient constructions have been proposed based on pre-quantum assumptions, there have been limited accomplishments in the post-quantum and especially practical settings. This research aims to derive new methods that enhance the current state of the art. To achieve this, we make the following contributions. By distilling prior design insights, we...
Anonymous systems (e.g. anonymous cryptocurrencies and updatable anonymous credentials) often follow a construction template where an account can only perform a single anonymous action, which in turn potentially spawns new (and still single-use) accounts (e.g. UTXO with a balance to spend or session with a score to claim). Due to the anonymous nature of the action, no party can be sure which account has taken part in an action and, therefore, must maintain an ever-growing list of potentially...
Lattice gadgets and the associated algorithms are the essential building blocks of lattice-based cryptography. In the past decade, they have been applied to build versatile and powerful cryptosystems. However, the practical optimizations and designs of gadget-based schemes generally lag their theoretical constructions. For example, the gadget-based signatures have elegant design and capability of extending to more advanced primitives, but they are far less efficient than other lattice-based...
In this paper, we take inspiration from an invited talk presented at CBCrypto'23 to design identification protocols and signature schemes from group actions using the MPC-in-the-head paradigm. We prove the security of the given identification schemes and rely on the Fiat-Shamir transformation to turn them into signatures. We also establish a parallel with the technique used for the MPC-in-the-head approach and the seed tree method that has been recently used in some signature and ring...
Monero is a popular cryptocurrency with strong privacy guarantees for users’ transactions. At the heart of Monero’s privacy claims lies a complex transaction system called RingCT, which combines several building blocks such as linkable ring signatures, homomorphic commitments, and range proofs, in a unique fashion. In this work, we provide the first rigorous security analysis for RingCT (as given in Zero to Monero, v2.0.0, 2020) in its entirety. This is in contrast to prior works that only...
We present Fusion, a post-quantum one-time digital signature scheme with non-interactive aggregation with security resting on the short integer solution problem over ideal lattices. Fusion is structurally similar to CRYSTALS-Dilithium, but Fusion is based upon the aggregatable one-time lattice-based scheme by Boneh and Kim. Fusion parameters conservatively target at least $128$ bits of security against forgery, taking tightness gaps into account, and with tighter bounds than the BK scheme....
Constructing a supersingular elliptic curve whose endomorphism ring is isomorphic to a given quaternion maximal order (one direction of the Deuring correspondence) is known to be polynomial-time assuming the generalized Riemann hypothesis [KLPT14; Wes21], but notoriously daunting in practice when not working over carefully selected base fields. In this work, we speed up the computation of the Deuring correspondence in general characteristic, i.e., without assuming any special form of the...
We give a construction of a 2-round blind signature scheme based on the hardness of standard lattice problems (Ring/Module-SIS/LWE and NTRU) with a signature size of 22 KB. The protocol is round-optimal and has a transcript size that can be as small as 60 KB. This blind signature is around $4$ times shorter than the most compact lattice-based scheme based on standard assumptions of del Pino and Katsumata (Crypto 2022) and around $2$ times shorter than the scheme of Agrawal et al. (CCS 2022)...
Multi-signature is a protocol where a set of signatures jointly sign a message so that the final signature is significantly shorter than concatenating individual signatures together. Recently, it finds applications in blockchain, where several users want to jointly authorize a payment through a multi-signature. However, in this setting, there is no centralized authority and it could suffer from a rogue key attack where the attacker can generate his own keys arbitrarily. Further, to...
We introduce a new cryptographic primitive, named ring verifiable random function (ring VRF). Ring VRF combines properties of VRF and ring signatures, offering verifiable unique, pseudorandom outputs while ensuring anonymity of the output and message authentication. We design its security in the universal composability (UC) framework and construct two protocols secure in our model. We also formalize a new notion of zero-knowledge (ZK) continuations allowing for the reusability of proofs by...
Anonymous authentication primitives, e.g., group or ring signatures, allow one to realize privacy-preserving data collection applications, as they strike a balance between authenticity of data being collected and privacy of data providers. At PKC 2021, Diaz and Lehmann defined group signatures with User-Controlled Linkability (UCL) and provided an instantiation based on BBS+ signatures. In a nutshell, a signer of a UCL group signature scheme can link any of her signatures: linking evidence...
In this paper, we propose a simple noncommutative-ring based UOV signature scheme with key-randomness alignment: Simple NOVA, which can be viewed as a simplified version of NOVA[48]. We simplify the design of NOVA by skipping the perturbation trick used in NOVA, thus shortens the key generation process and accelerates the signing and verification. Together with a little modification accordingly, this alternative version of NOVA is also secure and may be more suitable for practical uses. We...
Security and privacy issues with centralized exchange services have motivated the design of atomic swap protocols for decentralized trading across currencies. These protocols follow a standard blueprint similar to the 2-phase commit in databases: (i) both users first lock their coins under a certain (cryptographic) condition and a timeout; (ii-a) the coins are swapped if the condition is fulfilled; or (ii-b) coins are released after the timeout. The quest for these protocols is to minimize...
Decentralized anonymous payment schemes may be exploited for illicit activities, such as money laundering, bribery and blackmail. To address this issue, several regulatory friendly decentralized anonymous payment schemes have been proposed. However, most of these solutions lack restrictions on the regulator’s authority, which could potentially result in power abuse and privacy breaches. In this paper, we present a decentralized anonymous payment scheme with collaborative regulation (DAPCR)....
Threshold ring signatures are digital signatures that allow $t$ parties to sign a message while hiding their identity in a larger set of $n$ users called ''ring''. Recently, Aranha et al. [PKC 2022] introduced the notion of \emph{extendable} threshold ring signatures (ETRS). ETRS allow one to update, in a non-interactive manner, a threshold ring signature on a certain message so that the updated signature has a greater threshold, and/or an augmented set of potential signers. An...
Quantum computing threatens classical cryptography, leading to the search for stronger alternatives. The cryptographic approach based on lattices is considered as a viable option. Schemes with that approach use Gaussian sampling, a design which brings along two concerns: efficiency and information leakage. This work addresses those concerns in the RLWE formulation, for digital signatures. Efficiency mitigation uses the central limit theorem, and the Walsh–Hadamard transform, whereas the...
A ring signature scheme allows a group member to generate a signature on behalf of the whole group, while the verifier can not tell who computed this signature. However, most predecessors do not guarantee security from the secret key leakage of signers. In 2002, Anderson proposed the forward security mechanism to reduce the effect of such leakage. In this paper, we construct the first lattice-based ring signature scheme with forward security. Our scheme combines the binary tree and lattice...
In this paper we revise the idea of our previous article “Lin2-Xor Lemma: an OR-proof that leads to the membership proof and signature” and introduce another lemma, called Lin2-Choice, which is a generalization of the Lin2-Xor lemma. With the Lin2-Choice lemma we obtain a compact general-purpose trusted-setup-free log-size linkable threshold ring signature called EFLRSL. The signature size is 2log(n+1)+3l+1, where n is the ring size and l is the threshold. By extending the set membership...
We give a construction of an efficient one-out-of-many proof system, in which a prover shows that he knows the pre-image for one element in a set, based on the hardness of lattice problems. The construction employs the recent zero-knowledge framework of Lyubashevsky et al. (Crypto 2022) together with an improved, over prior lattice-based one-out-of-many proofs, recursive procedure, and a novel rejection sampling proof that allows to use the efficient bimodal rejection sampling throughout the...
Ring signatures allow signers to produce verifiable signatures and remain anonymous within a set of signers (i.e., the ring) while doing so. They are well-suited to protocols that target anonymity as a primary goal, for example, anonymous cryptocurrencies. However, standard ring signatures do not ensure that signers are held accountable if they act maliciously. Fraser and Quaglia (CANS'21) introduced a ring signature variant that they called report and trace ring signatures which balances...
Ring signatures allow a user to sign messages on behalf of an ad hoc set of users - a ring - while hiding her identity. The original motivation for ring signatures was whistleblowing [Rivest et al. ASIACRYPT'01]: a high government employee can anonymously leak sensitive information while certifying that it comes from a reliable source, namely by signing the leak. However, essentially all known ring signature schemes require the members of the ring to publish a structured verification key...
Group action based cryptography was formally proposed in the seminal paper of Brassard and Yung (Crypto 1990). Based on oneway group action, there is a well-known digital signature design based on the Goldreich–Micali–Widgerson (GMW) zero-knowledge protocol for the graph isomorphism problem and the Fiat–Shamir (FS) transformation. Recently, there is a revival of activities on group action based cryptography and the GMW-FS design, as witnessed by the schemes SeaSign (Eurocrypt 2019), CSI-FiSh...
NOVA signature scheme is a UOV-type signature scheme over a non-commutative coefficient ring with a novel structural map. In this article we show that a randomly generated central map for the scheme is very likely insecure and may suffer from a forgery attack in polynomial time.
We present TRIFORS (TRIlinear FOrms Ring Signature), a logarithmic post-quantum (linkable) ring signature based on a novel assumption regarding the equivalence of alternating trilinear forms. The basis of this work is the construction by Beullens, Katsumata and Pintore from Asiacrypt 2020 to obtain a linkable ring signature from a cryptographic group action. The group action on trilinear forms used here is the same employed in the signature presented by Tang et al. at Eurocrypt 2022. We...
Blockchain technology provides efficient and secure solutions to various online activities by utilizing a wide range of cryptographic tools. In this paper, we survey the existing literature on post-quantum secure digital signatures that possess exotic advanced features and which are crucial cryptographic tools used in the blockchain ecosystem for (i) account management, (ii) consensus efficiency, (iii) empowering scriptless blockchain, and (iv) privacy. The exotic signatures that we...
We explore a bitwise modification in Ajtai's one-way function. Our main contribution is to define the higher-bit approximate inhomogeneous short integer solution (ISIS) problem and prove its reduction to the ISIS problem. In this new instance, our main idea is to discard low-weighted bits to gain compactness. As an application, we construct a bitwise version of a hash-and-sign signature in the random oracle model whose security relies on the (Ring)-LWE and (Ring)-ISIS...
We propose Designated-Verifier Linkable Ring Signatures with unconditional anonymity, a cryptographic primitive that protects the privacy of signers in two ways: Firstly, it allows them to hide inside a ring (i.e. an anonymity set) they can create by collecting a set of public keys all of which must be used for verification. Secondly, it allows a designated entity to simulate signatures thus making it difficult for an adversary to deduce their identity from the content of the exchanged...
Unique ring signatures (URS) were introduced by Franklin and Zhang (FC 2012) as a unification of linkable and traceable ring signatures. In URS, each member within a ring can only produce, on behalf of the ring, at most one signature for a message. Applications of URS potentially are e-voting systems and e–token systems. In blockchain technology, URS has been implemented for mixing contracts. However, existing URS schemes are based on the Discrete Logarithm Problem, which is insecure in the...
We introduce Multimodal Private Signature (MPS) - an anonymous signature system that offers a novel accountability feature: it allows a designated opening authority to learn some partial information $\mathsf{op}$ about the signer's identity $\mathsf{id}$, and nothing beyond. Such partial information can flexibly be defined as $\mathsf{op} = \mathsf{id}$ (as in group signatures), or as $\mathsf{op} = \mathbf{0}$ (like in ring signatures), or more generally, as $\mathsf{op} =...
In the light of NIST’s announced reopening of the call for digital signature proposals in 2023 due to lacking diversity, there is a strong need for constructions based on other established hardness assumptions. In this work we construct a new post-quantum secure digital signature scheme based on the $MinRank$ problem, a problem with a long history of applications in cryptanalysis that led to a strong belief in its hardness. Initially following a design by Courtois (Asiacrypt '01) based on...
Katz et al., CCS 2018 (KKW) is a popular and efficient MPC-in-the-head non-interactive ZKP (NIZK) scheme, which is the technical core of the post-quantum signature scheme Picnic, currently considered for standardization by NIST. The KKW approach simultaneously is concretely efficient, even on commodity hardware, and does not rely on trusted setup. Importantly, the approach scales linearly in the circuit size with low constants with respect to proof generation time, proof verification time,...
Recently, there has been great interest towards constructing efficient zero-knowledge proofs for practical languages. In this work, we focus on proofs for threshold relations, in which the prover is required to prove knowledge of witnesses for $k$ out of $\ell$ statements. The main contribution of our work is an efficient and modular transformation that starting from a large class of $\Sigma$-protocols and a corresponding threshold relation $\mathcal{R}_\mathsf{k,\ell}$, provides an...
The LESS signature scheme, introduced in 2020, represented a fresh start for code-based signatures. In this paper we explore advanced functionalities for signature schemes, stemming from the work of LESS. First, we adapt a recent protocol of Beullens et al. to obtain a construction for (linkable) ring signatures. Then, we realize an identity-based signature scheme following the traditional approach by Joye and Neven. Our performance numbers confirm that signature schemes based on the code...
The focus of this work are multi-signatures schemes in the synchronized setting. A multi-signature scheme allows multiple signatures for the same message but from independent signers to be compressed into one short aggregated signature, which allows verifying all of the signatures simultaneously. In the synchronized setting, the signing algorithm takes the current time step as an additional input. It is assumed that no signer signs more than one message per time step and we aim to aggregate...
In this paper, we propose a noncommutative-ring based unbalanced oil and vinegar signature scheme with key-randomness alignment: NOVA (Noncommutative Oil and Vinegar with Alignment). Instead of fields or even commutative rings, we show that noncommutative rings can be used for algebraic cryptosystems. At the same or better level of security requirement, NOVA has a much smaller public key than UOV (Unbalanced Oil and Vinegar), which makes NOVA practical in most situations. We use Magma to...
Threshold signature schemes enable distribution of the signature issuing capability to multiple users, to mitigate the threat of signing key compromise. Though a classic primitive, these signatures have witnessed a surge of interest in recent times due to relevance to modern applications like blockchains and cryptocurrencies. In this work, we study round-optimal threshold signatures in the post- quantum regime and improve the only known lattice-based construction by Boneh et al [CRYPTO’18]...
Consider the scenario that the prover and the verifier perform the zero-knowledge (ZK) proof protocol for the same statement multiple times sequentially, where each proof is modeled as a session. We focus on the problem of how to resume a ZK proof efficiently in such scenario. We introduce a new primitive called resumable honest verifier zero-knowledge proof of knowledge (resumable HVZKPoK) and propose a general construction of the resumable HVZKPoK for circuits based on the...
We propose a short signature scheme under the ring-SIS assumption in the standard model. Specifically, by revisiting an existing construction [Ducas and Micciancio, CRYPTO 2014], we demonstrate lattice-based signatures with improved reduction loss. As far as we know, there are no ways to use multiple tags in the signature simulation of security proof in the lattice tag-based signatures. We address the tag-collision possibility in the lattice setting, which improves reduction loss. Our scheme...
We introduce Designated-Verifier Linkable Ring Signatures (DVLRS), a novel cryptographic primitive which combines designated-verifier and linkable ring signatures. Our goal is to guarantee signer ambiguity and provide the capability to the designated verifier to add ‘noise’ using simulated signatures that are publicly verifiable. This increases the privacy of the participants, as it does not allow an adversary to bypass the anonymity provided by ring signatures by using the content of a...
Ring signatures and ID-based cryptography are considered promising in terms of application. A ring signature authenticates messages while the author of the message remains anonymous. ID-based cryptographic primitives suppress the need for certificates in public key infrastructures (PKI). In this work, we propose a generic construction for post-quantum ID-based ring signatures (IDRS) based on symmetric-key primitives from which we derive the first two constructions of IDRS. The first...
We present a much-improved practical protocol, based on the hardness of Module-SIS and Module-LWE problems, for proving knowledge of a short vector $s$ satisfying $As=t\bmod q$. The currently most-efficient technique for constructing such a proof works by showing that the $\ell_\infty$ norm of $s$ is small. It creates a commitment to a polynomial vector $m$ whose CRT coefficients are the coefficients of $s$ and then shows that (1) $A\cdot \mathsf{CRT}(m)=t\bmod\,q$ and (2) in the case that...