## CryptoDB

### Ron Steinfeld

#### Publications

**Year**

**Venue**

**Title**

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).

2010

EPRINT

Faster Fully Homomorphic Encryption
Abstract

We describe two improvements to Gentry's fully homomorphic scheme
based on ideal lattices and its analysis: we provide a refined
analysis of one of the hardness assumptions (the one related to the
Sparse Subset Sum Problem) and we introduce a probabilistic decryption
algorithm that can be implemented with an algebraic circuit of low
multiplicative degree. Combined together, these improvements lead to a
faster fully homomorphic scheme, with a~$\softO(\lambda^{3})$ bit
complexity per elementary binary add/mult gate, where~$\lambda$ is the
security parameter. These improvements also apply to the fully
homomorphic schemes of Smart and Vercauteren [PKC'2010] and van Dijk
et al. [Eurocrypt'2010].

2008

EPRINT

Cryptanalysis of Short Exponent RSA with Primes Sharing Least Significant Bits
Abstract

LSBS-RSA denotes an RSA system with modulus primes, p and q, sharing a large number of least significant bits. In ISC 2007, Zhao and Qi analyzed the security of short exponent LSBS-RSA. They claimed that short exponent LSBS-RSA is much more vulnerable to the lattice attack than the standard RSA. In this paper, we point out that there exist some errors in the calculation of Zhao & Qi's attack. After re-calculating, the result shows that their attack is unable for attacking RSA with primes sharing bits. Consequently, we give a revised version to make their attack feasible. We also propose a new method to further extend the security boundary, compared with the revised version. The proposed attack also supports the result of analogue Fermat factoring on LSBS-RSA, which claims that p and q cannot share more than (n/4) least significant bits, where n is the bit-length of pq. In conclusion, it is a trade-off between the number of sharing bits and the security level in LSBS-RSA. One should be more careful when using LSBS-RSA with short exponents.

2007

EPRINT

Cryptanalysis of LASH
Abstract

We show that the LASH-$x$ hash function is vulnerable to attacks
that trade time for memory, including collision attacks as
fast as $2^{\frac{4}{11}x}$ and preimage attacks as fast as $2^{\frac47x}$.
Moreover, we describe heuristic lattice based collision attacks that
use small memory but require very long messages.
Based upon experiments, the lattice attacks are expected to find
collisions much faster than $2^{x/2}$.
All of these attacks exploit the designers' choice of an all zero IV.
We then consider whether LASH can be patched simply by changing the IV.
In this case, we show that LASH is vulnerable to a $2^{\frac78x}$
preimage attack. We also show that LASH is trivially not a PRF when any subset of input bytes is used as a secret key.
None of our attacks depend upon the particular contents of the LASH matrix -- we only assume that the distribution of elements is more or less uniform.
Additionally, we show a generalized birthday attack
on the final compression of LASH which requires
$O\left(x2^{\frac{x}{2(1+\frac{107}{105})}}\right) \approx O(x2^{x/4})$ time and memory.
Our method extends the Wagner algorithm to
truncated sums, as is done in the final transform in LASH.

2006

EPRINT

On the Provable Security of an Efficient RSA-Based Pseudorandom Generator
Abstract

Pseudorandom Generators (PRGs) based on the RSA inversion
(one-wayness) problem have been extensively studied in the
literature over the last 25 years. These generators have the
attractive feature of provable pseudorandomness security assuming
the hardness of the RSA inversion problem. However, despite
extensive study, the most efficient provably secure RSA-based
generators output asymptotically only at most $O(\log n)$ bits per
multiply modulo an RSA modulus of bitlength $n$, and hence are too
slow to be used in many practical applications.
To bring theory closer to practice, we present a simple
modification to the proof of security by Fischlin and Schnorr of
an RSA-based PRG, which shows that one can obtain an RSA-based PRG
which outputs $\Omega(n)$ bits per multiply and has provable
pseudorandomness security assuming the hardness of a well-studied
variant of the RSA inversion problem, where a constant fraction of
the plaintext bits are given. Our result gives a positive answer to an open question posed by Gennaro (J. of Cryptology, 2005) regarding finding a PRG beating the rate $O(\log n)$ bits per multiply at the cost of a reasonable assumption on RSA inversion.

2005

EPRINT

VSH, an Efficient and Provable Collision Resistant Hash Function
Abstract

We introduce VSH, {\em very smooth hash}, a new $S$-bit hash function that
is provably collision-resistant assuming the hardness of
finding nontrivial modular
square roots of very smooth numbers modulo an $S$-bit composite.
By very smooth, we mean that the smoothness bound is
some fixed polynomial function of~$S$.
We argue that finding collisions for VSH has the same asymptotic
complexity as factoring using the Number Field Sieve factoring algorithm,
i.e., subexponential in~$S$.
%We show how our asymptotic argument can be turned into a practical method to
%select parameters so that VSH meets a desired security level.
VSH is theoretically pleasing because it requires just a single
multiplication modulo the~$S$-bit composite
per $\Omega(S)$ message-bits (as opposed to $O(\log S)$
message-bits for previous provably secure hashes).
It is relatively practical.
A preliminary implementation on a 1GHz Pentium III
processor that achieves collision resistance at least equivalent
to the difficulty of factoring a 1024-bit RSA modulus, runs at 1.1
MegaByte per second, with a moderate slowdown to 0.7MB/s for
2048-bit RSA security.
VSH can be used to
build a fast, provably secure randomised trapdoor hash function,
which can be applied to speed up provably secure signature schemes (such
as Cramer-Shoup) and designated-verifier signatures.

2004

PKC

2003

EPRINT

Universal Designated-Verifier Signatures
Abstract

Motivated by privacy issues associated with dissemination of signed digital certificates, we define a new type of signature scheme called a ?Universal Designated-Verifier Signature? (UDVS). A UDVS scheme can function as a standard publicly-verifiable digital signature but has additional functionality which allows any holder of a signature (not necessarily the signer) to designate the signature to any desired designated-verifier (using the verifier?s public key). Given the designated-signature, the designated-verifier can verify that the message was signed by the signer, but is unable to convince anyone else of this fact.
We propose an efficient deterministic UDVS scheme constructed using any bilinear group-pair. Our UDVS scheme functions as a standard Boneh-Lynn-Shacham (BLS) signature when no verifier-designation is performed, and is therefore compatible with the key-generation, signing and verifying algorithms of the BLS scheme. We prove that our UDVS scheme is secure in the sense of our unforgeability and privacy notions for UDVS schemes, under the Bilinear Diffie-Hellman (BDH) assumption for the underlying group-pair, in the random-oracle model. We also demonstrate a general constructive equivalence between a class of unforgeable and unconditionally-private UDVS schemes having unique signatures (which includes the deterministic UDVS schemes) and a class of ID-Based Encryption (IBE) schemes which contains the Boneh-Franklin IBE scheme but not the Cocks IBE scheme.

2003

EPRINT

Efficient Extension of Standard Schnorr/RSA signatures into Universal Designated-Verifier Signatures
Abstract

Universal Designated-Verifier Signature (UDVS) schemes are digital signature schemes with additional
functionality which allows any holder of a signature to designate the signature to any desired
designated-verifier such that the designated-verifier can verify that the message was signed by the
signer, but is unable to convince anyone else of this fact.
Since UDVS schemes reduce to standard signatures when no verifier designation is performed, it is natural to ask
how to extend the classical Schnorr or RSA signature schemes into UDVS schemes, so that the existing key
generation and signing implementation infrastructure for these schemes can be used without modification. We show
how this can be efficiently achieved, and provide proofs of security for our schemes in the random oracle model.

2002

EPRINT

Content Extraction Signatures
Abstract

Motivated by emerging needs in online interactions, we define a
new type of digital signature called a `Content Extraction
Signature' (CES). A CES allows the owner, Bob, of a document
signed by Alice, to produce an `extracted signature' on selected
extracted portions of the original document, which can be
verified to originate from Alice by any third party Cathy, while
hiding the unextracted (removed) document portions. The new
signature therefore achieves verifiable content extraction with
minimal multi-party interaction. We specify desirable functional
and security requirements for a CES (including an efficiency
requirement: a CES should be more efficient in either computation
or communication than the simple multiple signature solution). We
propose and analyze four CES constructions which are provably
secure with respect to known cryptographic assumptions and
compare their performance characteristics.

#### Program Committees

- Asiacrypt 2020
- Asiacrypt 2019
- Asiacrypt 2017
- Asiacrypt 2016
- Crypto 2016
- Eurocrypt 2016
- Asiacrypt 2014
- Eurocrypt 2014
- PKC 2012
- Asiacrypt 2012
- Eurocrypt 2010
- Asiacrypt 2010
- Asiacrypt 2008
- PKC 2006

#### Coauthors

- Hassan Jameel Asghar (1)
- Joonsang Baek (2)
- Shi Bai (4)
- Laurence Bull (3)
- Scott Contini (5)
- Dipayan Das (1)
- Yvo Desmedt (3)
- Julien Devevey (1)
- Muhammed F. Esgin (1)
- Dawu Gu (1)
- Jian Guo (3)
- Ryo Hiromasa (1)
- Dmitry Khovratovich (2)
- Veronika Kuchta (1)
- Adeline Langlois (4)
- Arjen K. Lenstra (2)
- Tancrède Lepoint (3)
- Benoît Libert (1)
- San Ling (5)
- Joseph K. Liu (2)
- Dongxi Liu (1)
- Krystian Matusiewicz (2)
- Ivica Nikolić (2)
- Duong Hieu Phan (2)
- Josef Pieprzyk (17)
- Miruna Rosca (2)
- Adeline Roux-Langlois (1)
- Amin Sakzad (7)
- Przemyslaw Sokolowski (2)
- Damien Stehlé (16)
- Shi-Feng Sun (2)
- Xiaoming Sun (1)
- Hung-Min Sun (1)
- Keisuke Tanaka (1)
- Christophe Tartary (2)
- Huaxiong Wang (15)
- Mu-En Wu (1)
- Keita Xagawa (1)
- Andrew Chi-Chih Yao (1)
- Zhenfei Zhang (1)
- Yuliang Zheng (3)