CryptoDB
Ron Steinfeld
Publications
Year
Venue
Title
2024
EUROCRYPT
Plover: Masking-Friendly Hash-and-Sign Lattice Signatures
Abstract
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 was an open problem unsuccessful attempts such as Mitaka. Our toolkit includes noise flooding to mitigate statistical leaks and an extended Strong Non-Interfering probing security property (SNIu) for masking gadgets to handle unshared inputs. Our main conceptual contribution lies in finding a systematic way to use noise flooding within the hash-and-sign paradigm. Our main technical contribution is to formalize, prove, instantiate and implement a hash-and-sign scheme based on these techniques.
We showcase the efficiency of our techniques in a signature scheme, Plover-RLWE, based on (hint) Ring-LWE. It is the first lattice-based masked hash-and-sign scheme with quasi-linear complexity O(d log d) in the number of shares d. Our performances are competitive with the state-of-the-art masking-friendly signature, the Fiat-Shamir scheme Raccoon.
2024
CRYPTO
Loquat: A SNARK-Friendly Post-Quantum Signature based on the Legendre PRF with Applications in Ring and Aggregate Signatures
Abstract
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 symmetric-key-based post-quantum signature schemes that support stateless signing. Our Python implementation of Loquat demonstrate a signature size of 46KB, with a signing time of 5.04 seconds and a verification time of 0.21 seconds. Instantiating the random oracle with an algebraic hash function results in the R1CS constraints for signature verification being about 148K, 7 to 175 times smaller than those required for MPC-in-the-head-based signatures and 3 to 9 times less than those for SPHINCS+ [Bernstein et al. CCS’19].
We explore two applications of Loquat. First, we incorporate it into the ID-based ring signature scheme [Buser et al. ACNS’22], achieving a significant reduction in signature size from 1.9 MB to 0.9 MB with stateless signing and practical master key generation. Our second application presents a SNARK-based aggregate signature scheme. We use the implementations of Aurora [Ben-Sasson et al. EC’19] and Fractal [Chiesa et al. EC’20] to benchmark our aggregate signature’s performance. Our findings show that aggregating 32 Loquat signatures using Aurora results in a proving time of about 7 minutes, a verification time of 66 seconds, and an aggregate signature size of 197 KB. Furthermore, by leveraging the recursive proof composition feature of Fractal, we achieve an aggregate signature with a constant size of 145 KB, illustrating Loquat’s potential for scalability in cryptographic applications.
2023
CRYPTO
Efficient Hybrid Exact/Relaxed Lattice Proofs and Applications to Rounding and VRFs
Abstract
In this work, we study hybrid exact/relaxed zero-knowledge proofs from lattices, where the proved relation is exact in one part and relaxed in the other. Such proofs arise in important real-life applications such as those requiring verifiable PRF evaluation and have so far not received significant attention as a standalone problem.
We first introduce a general framework, LANES+, for realizing such hybrid proofs efficiently by combining standard relaxed proofs of knowledge RPoK and the LANES framework (due to a series of works in Crypto'20, Asiacrypt'20, ACM CCS'20). The latter framework is a powerful lattice-based proof system that can prove exact linear and multiplicative relations. The advantage of LANES+ is its ability to realize hybrid proofs more efficiently by exploiting RPoK for the high-dimensional part of the secret witness while leaving a low-dimensional secret witness part for the exact proof that is proven at a significantly lower cost via LANES. Thanks to the flexibility of LANES+, other exact proof systems can also be supported.
We apply our LANES+ framework to construct substantially shorter proofs of rounding, which is a central tool for verifiable deterministic lattice-based cryptography. Based on our rounding proof, we then design an efficient long-term verifiable random function (VRF), named LaV. LaV leads to the shortest VRF outputs among the proposals of standard (i.e., long-term and stateless) VRFs based on quantum-safe assumptions. Of independent interest, we also present generalized results for challenge difference invertibility, a fundamental soundness security requirement for many proof systems.
2022
PKC
Efficient Verifiable Partially-Decryptable Commitments from Lattices and Applications
📺
Abstract
We introduce verifiable partially-decryptable commitments (VPDC), as a building block for constructing efficient privacy-preserving protocols supporting auditability by a trusted party. A VPDC is an extension of a commitment along with an accompanying proof, convincing a verifier that (i) the given commitment is well-formed and (ii) a certain part of the committed message can be decrypted using a (secret) trapdoor known to a trusted party.
We first formalize VPDCs and then introduce a general decryption feasibility result that overcomes the challenges in relaxed proofs arising in the lattice setting. Our general result can be applied to a wide class of Fiat-Shamir based protocols and may be of independent interest.
Next, we show how to extend the commonly used lattice-based `Hashed-Message Commitment' (HMC) scheme into a succinct and efficient VPDC. In particular, we devise a novel `gadget'-based Regev-style (partial) decryption method, compatible with efficient relaxed lattice-based zero-knowledge proofs. We prove the soundness of our VPDC in the setting of adversarial proofs, where a prover tries to create a valid VPDC output that fails in decryption.
To demonstrate the effectiveness of our results, we extend a private blockchain payment protocol, MatRiCT, by Esgin et al. (ACM CCS '19) into a formally auditable construction, which we call MatRiCT-Au, with very low communication and computation overheads over MatRiCT.
2021
PKC
On the Integer Polynomial Learning with Errors Problem
📺
Abstract
Several recent proposals of efficient public-key encryption are based on variants of the polynomial learning with errors problem (\textsf{PLWE}$^f$) in which the underlying \emph{polynomial} ring $\mZ_q[x]/f$ is replaced with the (related) modular \emph{integer} ring $\mZ_{f(q)}$; the corresponding problem is known as \emph{Integer Polynomial Learning with Errors} (\textsf{I-PLWE}$^f$). Cryptosystems based on \textsf{I-PLWE}$^f$ and its variants can
exploit optimised big-integer arithmetic to achieve good practical performance, as exhibited by the \textsf{ThreeBears} cryptosystem.
Unfortunately, the average-case hardness of \textsf{I-PLWE}$^f$
and its relation to more established lattice problems have to date remained unclear.
We describe the first polynomial-time average-case reductions for the search variant of \textsf{I-PLWE}$^f$, proving its computational equivalence with the search variant of its counterpart problem \textsf{PLWE}$^f$. Our reductions apply to a large class of defining polynomials~$f$. To obtain our results, we employ a careful adaptation of R\'{e}nyi divergence analysis techniques to bound the impact of the integer ring arithmetic carries on the error distributions.
As an application, we present a deterministic public-key cryptosystem over integer rings. Our cryptosystem, which resembles \textsf{ThreeBears}, enjoys one-way (OW-CPA) security provably based on the search variant of~\textsf{I-PLWE}$^f$.
2020
EUROCRYPT
Measure-Rewind-Measure: Tighter Quantum Random Oracle Model Proofs for One-Way to Hiding and CCA Security
📺
Abstract
We introduce a new technique called `Measure-Rewind-Measure' (MRM) to achieve tighter security proofs in the quantum random oracle model (QROM).
We first apply our MRM technique to derive a new security proof for a variant of the `double-sided' quantum One-Way to Hiding Lemma (O2H) of Bindel et al. [TCC 2019] which, for the first time, avoids the square-root advantage loss in the security proof. In particular, it bypasses a previous `impossibility result' of Jiang, Zhang and Ma [IACR eprint 2019]. We then apply our new O2H Lemma to give a new tighter security proof for the Fujisaki-Okamoto transform for constructing a strong (INDCCA) Key Encapsulation Mechanism (KEM) from a weak (INDCPA) public-key encryption scheme satisfying a mild injectivity assumption.
2020
PKC
Public-Key Puncturable Encryption: Modular and Compact Constructions
📺
Abstract
We revisit the method of designing public-key puncturable encryption schemes and present a generic conversion by leveraging the techniques of distributed key-distribution and revocable encryption. In particular, we first introduce a refined version of identity-based revocable encryption, named key-homomorphic identity-based revocable key encapsulation mechanism with extended correctness . Then, we propose a generic construction of puncturable key encapsulation mechanism from the former by merging the idea of distributed key-distribution. Compared to the state-of-the-art, our generic construction supports unbounded number of punctures and multiple tags per message, thus achieving more fine-grained revocation of decryption capability. Further, it does not rely on random oracles , not suffer from non-negligible correctness error, and results in a variety of efficient schemes with distinct features. More precisely, we obtain the first scheme with very compact ciphertexts in the standard model, and the first scheme with support for both unbounded size of tags per ciphertext and unbounded punctures as well as constant-time puncture operation. Moreover, we get a comparable scheme proven secure under the standard DBDH assumption, which enjoys both faster encryption and decryption than previous works based on the same assumption, especially when the number of tags associated with the ciphertext is large.
2020
PKC
MPSign: A Signature from Small-Secret Middle-Product Learning with Errors
📺
Abstract
We describe a digital signature scheme $$mathsf {MPSign}$$ , whose security relies on the conjectured hardness of the Polynomial Learning With Errors problem ( $$mathsf {PLWE}$$ ) for at least one defining polynomial within an exponential-size family (as a function of the security parameter). The proposed signature scheme follows the Fiat-Shamir framework and can be viewed as the Learning With Errors counterpart of the signature scheme described by Lyubashevsky at Asiacrypt 2016, whose security relies on the conjectured hardness of the Polynomial Short Integer Solution ( $$mathsf {PSIS}$$ ) problem for at least one defining polynomial within an exponential-size family. As opposed to the latter, $$mathsf {MPSign}$$ enjoys a security proof from $$mathsf {PLWE}$$ that is tight in the quantum-access random oracle model. The main ingredient is a reduction from $$mathsf {PLWE}$$ for an arbitrary defining polynomial among exponentially many, to a variant of the Middle-Product Learning with Errors problem ( $$mathsf {MPLWE}$$ ) that allows for secrets that are small compared to the working modulus. We present concrete parameters for $$mathsf {MPSign}$$ using such small secrets, and show that they lead to significant savings in signature length over Lyubashevsky’s Asiacrypt 2016 scheme (which uses larger secrets) at typical security levels. As an additional small contribution, and in contrast to $$mathsf {MPSign}$$ (or $$mathsf {MPLWE}$$ ), we present an efficient key-recovery attack against Lyubashevsky’s scheme (or the inhomogeneous $$mathsf {PSIS}$$ problem), when it is used with sufficiently small secrets, showing the necessity of a lower bound on secret size for the security of that scheme.
2019
CRYPTO
Lattice-Based Zero-Knowledge Proofs: New Techniques for Shorter and Faster Constructions and Applications
📺
Abstract
We devise new techniques for design and analysis of efficient lattice-based zero-knowledge proofs (ZKP). First, we introduce one-shot proof techniques for non-linear polynomial relations of degree $$k\ge 2$$, where the protocol achieves a negligible soundness error in a single execution, and thus performs significantly better in both computation and communication compared to prior protocols requiring multiple repetitions. Such proofs with degree $$k\ge 2$$ have been crucial ingredients for important privacy-preserving protocols in the discrete logarithm setting, such as Bulletproofs (IEEE S&P ’18) and arithmetic circuit arguments (EUROCRYPT ’16). In contrast, one-shot proofs in lattice-based cryptography have previously only been shown for the linear case ($$k=1$$) and a very specific quadratic case ($$k=2$$), which are obtained as a special case of our technique.Moreover, we introduce two speedup techniques for lattice-based ZKPs: a CRT-packing technique supporting “inter-slot” operations, and “NTT-friendly” tools that permit the use of fully-splitting rings. The former technique comes at almost no cost to the proof length, and the latter one barely increases it, which can be compensated for by tweaking the rejection sampling parameters while still having faster computation overall.To illustrate the utility of our techniques, we show how to use them to build efficient relaxed proofs for important relations, namely proof of commitment to bits, one-out-of-many proof, range proof and set membership proof. Despite their relaxed nature, we further show how our proof systems can be used as building blocks for advanced cryptographic tools such as ring signatures.Our ring signature achieves a dramatic improvement in length over all the existing proposals from lattices at the same security level. The computational evaluation also shows that our construction is highly likely to outperform all the relevant works in running times. Being efficient in both aspects, our ring signature is particularly suitable for both small-scale and large-scale applications such as cryptocurrencies and e-voting systems. No trusted setup is required for any of our proposals.
2017
CRYPTO
2015
ASIACRYPT
2012
JOFC
Graph Coloring Applied to Secure Computation in Non-Abelian Groups
Abstract
We study the natural problem of secure n-party computation (in the computationally unbounded attack model) of circuits over an arbitrary finite non-Abelian group (G,⋅), which we call G-circuits. Besides its intrinsic interest, this problem is also motivating by a completeness result of Barrington, stating that such protocols can be applied for general secure computation of arbitrary functions. For flexibility, we are interested in protocols which only require black-box access to the group G (i.e. the only computations performed by players in the protocol are a group operation, a group inverse, or sampling a uniformly random group element). Our investigations focus on the passive adversarial model, where up to t of the n participating parties are corrupted.Our results are as follows. We initiate a novel approach for the construction of black-box protocols for G-circuits based on k-of-k threshold secret-sharing schemes, which are efficiently implementable over any black-box (non-Abelian) group G. We reduce the problem of constructing such protocols to a combinatorial coloring problem in planar graphs. We then give three constructions for such colorings. Our first approach leads to a protocol with optimal resilience t<n/2, but it requires exponential communication complexity $O({\binom{2 t+1}{t}}^{2} \cdot N_{g})$ group elements and round complexity $O(\binom{2 t + 1}{t} \cdot N_{g})$, for a G-circuit of size Ng. Nonetheless, using this coloring recursively, we obtain another protocol to t-privately compute G-circuits with communication complexity $\mathcal{P}\mathit{oly}(n)\cdot N_{g}$ for any t∈O(n1−ϵ) where ϵ is any positive constant. For our third protocol, there is a probability δ (which can be made arbitrarily small) for the coloring to be flawed in term of security, in contrast to the first two techniques, where the colorings are always secure (we call this protocol probabilistic, and those earlier protocols deterministic). This third protocol achieves optimal resilience t<n/2. It has communication complexity O(n5.056(n+log δ−1)2⋅Ng) and the number of rounds is O(n2.528⋅(n+log δ−1)⋅Ng).
2004
PKC
Program Committees
- Asiacrypt 2023 (Program chair)
- Asiacrypt 2022
- Crypto 2021
- Asiacrypt 2021
- Asiacrypt 2020
- Asiacrypt 2019
- Asiacrypt 2017
- Asiacrypt 2016
- Crypto 2016
- Eurocrypt 2016
- Asiacrypt 2014
- Eurocrypt 2014
- PKC 2012
- Asiacrypt 2012
- Asiacrypt 2010
- Eurocrypt 2010
- Asiacrypt 2008
- PKC 2006
Coauthors
- Joonsang Baek (2)
- Shi Bai (3)
- Laurence Bull (1)
- Scott Contini (3)
- Dipayan Das (1)
- Yvo Desmedt (2)
- Julien Devevey (1)
- Muhammed F. Esgin (5)
- Thomas Espitau (1)
- Dawu Gu (1)
- Jian Guo (1)
- Ryo Hiromasa (1)
- Dmitry Khovratovich (1)
- Veronika Kuchta (1)
- Arjen K. Lenstra (1)
- Tancrède Lepoint (2)
- Benoît Libert (1)
- San Ling (3)
- Joseph K. Liu (3)
- Dongxi Liu (3)
- Krystian Matusiewicz (1)
- Ivica Nikolić (1)
- Guilhem Niot (1)
- Duong Hieu Phan (1)
- Josef Pieprzyk (11)
- Thomas Prest (1)
- Miruna Rosca (2)
- Adeline Roux-Langlois (3)
- Sushmita Ruj (2)
- Amin Sakzad (8)
- Przemyslaw Sokolowski (1)
- Damien Stehlé (12)
- Ron Steinfeld (32)
- Shi-Feng Sun (2)
- Xiaoming Sun (1)
- Keisuke Tanaka (1)
- Christophe Tartary (2)
- Huaxiong Wang (10)
- Keita Xagawa (1)
- Andrew Chi-Chih Yao (1)
- Xinyu Zhang (1)
- Zhenfei Zhang (1)
- Raymond K. Zhao (1)
- Yuliang Zheng (2)