## CryptoDB

### Huaxiong Wang

#### Affiliation: Nanyang Technological University, SG

#### Publications

**Year**

**Venue**

**Title**

2019

PKC

Zero-Knowledge Elementary Databases with More Expressive Queries
Abstract

Zero-knowledge elementary databases (ZK-EDBs) are cryptographic schemes that allow a prover to commit to a set $$\mathsf {D}$$ of key-value pairs so as to be able to prove statements such as “x belongs to the support of $$\mathsf {D}$$ and $$\mathsf {D}(x)=y$$” or “x is not in the support of $$\mathsf {D}$$”. Importantly, proofs should leak no information beyond the proven statement and even the size of $$\mathsf {D}$$ should remain private. Chase et al. (Eurocrypt’05) showed that ZK-EDBs are implied by a special flavor of non-interactive commitment, called mercurial commitment, which enables efficient instantiations based on standard number theoretic assumptions. On the other hand, the resulting ZK-EDBs are only known to support proofs for simple statements like (non-)membership and value assignments. In this paper, we show that mercurial commitments actually enable significantly richer queries. We show that, modulo an additional security property met by all known efficient constructions, they actually enable range queries over keys and values – even for ranges of super-polynomial size – as well as membership/non-membership queries over the space of values. Beyond that, we exploit the range queries to realize richer queries such as $$k$$-nearest neighbors and revealing the $$k$$ smallest or largest records within a given range. In addition, we provide a new realization of trapdoor mercurial commitment from standard lattice assumptions, thus obtaining the most expressive quantum-safe ZK-EDB construction so far.

2019

CRYPTO

New Results on Modular Inversion Hidden Number Problem and Inversive Congruential Generator
Abstract

The Modular Inversion Hidden Number Problem (MIHNP), introduced by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001, is briefly described as follows: Let $${\mathrm {MSB}}_{\delta }(z)$$ refer to the $$\delta $$ most significant bits of z. Given many samples $$\left( t_{i}, {\mathrm {MSB}}_{\delta }((\alpha + t_{i})^{-1} \bmod {p})\right) $$ for random $$t_i \in \mathbb {Z}_p$$, the goal is to recover the hidden number $$\alpha \in \mathbb {Z}_p$$. MIHNP is an important class of Hidden Number Problem.In this paper, we revisit the Coppersmith technique for solving a class of modular polynomial equations, which is respectively derived from the recovering problem of the hidden number $$\alpha $$ in MIHNP. For any positive integer constant d, let integer $$n=d^{3+o(1)}$$. Given a sufficiently large modulus p, $$n+1$$ samples of MIHNP, we present a heuristic algorithm to recover the hidden number $$\alpha $$ with a probability close to 1 when $$\delta /\log _2 p>\frac{1}{d\,+\,1}+o(\frac{1}{d})$$. The overall time complexity of attack is polynomial in $$\log _2 p$$, where the complexity of the LLL algorithm grows as $$d^{\mathcal {O}(d)}$$ and the complexity of the Gröbner basis computation grows as $$(2d)^{\mathcal {O}(n^2)}$$. When $$d> 2$$, this asymptotic bound outperforms $$\delta /\log _2 p>\frac{1}{3}$$ which is the asymptotic bound proposed by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001. It is the first time that a better bound for solving MIHNP is given, which implies that the conjecture that MIHNP is hard whenever $$\delta /\log _2 p<\frac{1}{3}$$ is broken. Moreover, we also get the best result for attacking the Inversive Congruential Generator (ICG) up to now.

2018

CRYPTO

Lattice-Based Zero-Knowledge Arguments for Integer Relations
📺
Abstract

We provide lattice-based protocols allowing to prove relations among committed integers. While the most general zero-knowledge proof techniques can handle arithmetic circuits in the lattice setting, adapting them to prove statements over the integers is non-trivial, at least if we want to handle exponentially large integers while working with a polynomial-size modulus q. For a polynomial L, we provide zero-knowledge arguments allowing a prover to convince a verifier that committed L-bit bitstrings x, y and z are the binary representations of integers X, Y and Z satisfying $$Z=X+Y$$ over $$\mathbb {Z}$$. The complexity of our arguments is only linear in L. Using them, we construct arguments allowing to prove inequalities $$X<Z$$ among committed integers, as well as arguments showing that a committed X belongs to a public interval $$[\alpha ,\beta ]$$, where $$\alpha $$ and $$\beta $$ can be arbitrarily large. Our range arguments have logarithmic cost (i.e., linear in L) in the maximal range magnitude. Using these tools, we obtain zero-knowledge arguments showing that a committed element X does not belong to a public set S using $$\widetilde{\mathcal {O}}(n \cdot \log |S|)$$ bits of communication, where n is the security parameter. We finally give a protocol allowing to argue that committed L-bit integers X, Y and Z satisfy multiplicative relations $$Z=XY$$ over the integers, with communication cost subquadratic in L. To this end, we use our protocol for integer addition to prove the correct recursive execution of Karatsuba’s multiplication algorithm. The security of our protocols relies on standard lattice assumptions with polynomial modulus and polynomial approximation factor.

2018

PKC

Constant-Size Group Signatures from Lattices
Abstract

Lattice-based group signature is an active research topic in recent years. Since the pioneering work by Gordon, Katz and Vaikuntanathan (Asiacrypt 2010), ten other schemes have been proposed, providing various improvements in terms of security, efficiency and functionality. However, in all known constructions, one has to fix the number N of group users in the setup stage, and as a consequence, the signature sizes are dependent on N.In this work, we introduce the first constant-size group signature from lattices, which means that the size of signatures produced by the scheme is independent of N and only depends on the security parameter $$\lambda $$λ. More precisely, in our scheme, the sizes of signatures, public key and users’ secret keys are all of order $$\widetilde{\mathcal {O}}(\lambda )$$O~(λ). The scheme supports dynamic enrollment of users and is proven secure in the random oracle model under the Ring Short Integer Solution (RSIS) and Ring Learning With Errors (RLWE) assumptions. At the heart of our design is a zero-knowledge argument of knowledge of a valid message-signature pair for the Ducas-Micciancio signature scheme (Crypto 2014), that may be of independent interest.

2016

EUROCRYPT

2016

ASIACRYPT

2016

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

A New Human Identification Protocol and Coppersmith's Baby-Step Giant-Step Algorithm
Abstract

We propose a new protocol providing cryptographically secure authentication to unaided humans against passive adversaries. We also propose a new generic passive attack on human identification protocols. The attack is an application of Coppersmith's baby-step giant-step algorithm on human identification protcols. Under this attack, the achievable security of some of the best candidates for human identification protocols in the literature is further reduced. We show that our protocol preserves similar usability while achieves better security than these protocols. A comprehensive security analysis is provided which suggests parameters guaranteeing desired levels of security.

2010

EPRINT

Advanced Meet-in-the-Middle Preimage Attacks: First Results on Full Tiger, and Improved Results on MD4 and SHA-2
Abstract

We revisit narrow-pipe designs that are in practical use, and their security against preimage attacks.
Our results are the best known preimage attacks on Tiger, MD4, and reduced SHA-2, with the result on Tiger
being the first cryptanalytic shortcut attack on the full hash function. Our attacks runs in time $2^{188.8}$ for finding preimages, and $2^{188.2}$ for second-preimages. Both have memory requirement of order $2^{8}$, which is much less than in any other recent preimage attacks on reduced Tiger.
Using pre-computation techniques, the time complexity for finding a new preimage or second-preimage for MD4 can now be as low as $2^{78.4}$ and $2^{69.4}$ MD4 computations, respectively. The second-preimage attack works for all messages longer than 2 blocks.
To obtain these results, we extend the meet-in-the-middle framework recently developed by Aoki and Sasaki in a series of papers. In addition to various algorithm-specific techniques, we use a number of conceptually new ideas that are applicable to a larger class of constructions. Among them are (1) incorporating multi-target scenarios into the MITM framework, leading to faster preimages from pseudo-preimages, (2) a simple precomputation technique that allows for finding new preimages at the cost of a single pseudo-preimage, and (3) probabilistic initial structures, compared with deterministic ones, to enable more neutral words, and hence to reduce the attack time complexity. All the techniques developed await application to other hash functions. To illustrate this, we give as another example improved preimage attacks on SHA-2 members.

2010

ASIACRYPT

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

Privacy-Preserving Distributed Set Intersection
Abstract

With the growing demand of databases outsourcing and its security concerns, we investigate privacy-preserving set intersection in a distributed scenario. We propose a one-round protocol for privacy-preserving set intersection based on a combination of secret sharing scheme and homomorphic encryption. We then show that, with an extra permutation performed by each of contacted servers, the cardinality of set intersection can be computed efficiently. All protocols constructed in this paper are provably secure against a semi-honest adversary under the Decisional Diffie-Hellman assumption.

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

The Bilinear Pairing-based Accumulator Proposed at CT-RSA'05 is not Collision Resistant
Abstract

In this paper, we demonstrate that the construction proposed by Lan Nguyen at CT-RSA'05 does lead to a cryptographic accumulator which is not collision resistant.

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.

2006

EPRINT

Formal Analysis and Systematic Construction of Two-factor Authentication Scheme
Abstract

One of the most commonly used two-factor authentication mechanisms is
based on smart card and user's password. Throughout the years, there
have been many schemes proposed, but most of them have already been
found flawed due to the lack of formal security analysis. On the
cryptanalysis of this type of schemes, in this paper, we further
review two recently proposed schemes and show that their security
claims are invalid. To address the current issue, we propose a new
and simplified property set and a formal adversarial model for
analyzing the security of this type of schemes. We believe that the
property set and the adversarial model themselves are of independent
interest.
We then propose a new scheme and a generic construction framework. In
particular, we show that a secure password based key exchange
protocol can be transformed efficiently to a smartcard and password
based two-factor authentication scheme provided that there exist
pseudorandom functions and collision-resistant hash functions.

2005

EPRINT

Anonymous Signature Schemes
Abstract

Digital signature is one of the most important primitives in public key cryptography. It provides authenticity, integrity and non-repudiation to many kinds of applications. On signer privacy however, it is generally unclear or suspicious of whether a signature scheme itself can guarantee the anonymity of the signer. In this paper, we give some affirmative answers to it. We formally define the signer anonymity for digital signature and propose some schemes of this type. We show that a signer anonymous signature scheme can be very useful by proposing a new anonymous key exchange protocol which allows a client Alice to establish a session key with a server Bob securely while keeping her identity secret from eavesdroppers. In the protocol, the anonymity of Alice is already maintained when Alice sends her signature to Bob in clear, and no additional encapsulation or mechanism is needed for the signature. We also propose a method of using anonymous signature to solve the collusion problem between organizers and reviewers of an anonymous paper review system.

2004

PKC

2003

EPRINT

Distributing the Encryption and Decryption of a Block Cipher
Abstract

In threshold cryptography the goal is to distribute the computation of
basic cryptographic primitives across a number of nodes in order to relax trust assumptions on individual nodes, as well as to introduce a level of fault-tolerance against node compromise. Most threshold cryptography has previously looked at the distribution of public key primitives, particularly threshold signatures and threshold decryption mechanisms. In this paper we look at the application of threshold cryptography to symmetric primitives, and in particular the encryption or decryption of a symmetric key block cipher. We comment on some previous work in this area and then propose a model for shared encryption / decryption of a block cipher. We will present several approaches to enable such systems and will compare them.

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.

#### Program Committees

- PKC 2019
- Asiacrypt 2016
- Asiacrypt 2015
- Asiacrypt 2014
- Asiacrypt 2008

#### Coauthors

- Hassan Jameel Asghar (1)
- Alex Biryukov (1)
- Laurence Bull (2)
- Yeow Meng Chee (1)
- Scott Contini (3)
- Xiaotie Deng (3)
- Yvo Desmedt (2)
- Sareh Emami (2)
- Martianus Frederic Ezerman (2)
- Praveen Gauravaram (1)
- Jian Guo (6)
- Lei Hu (1)
- Tao Huang (1)
- Khoongming Khoo (1)
- Dmitry Khovratovich (1)
- Adeline Langlois (2)
- Hyung Tae Lee (2)
- Benoît Libert (7)
- Chu-Wee Lim (1)
- San Ling (28)
- Mulan Liu (1)
- Keith M. Martin (1)
- Krystian Matusiewicz (3)
- Amir Moradi (2)
- Fabrice Mouhartem (3)
- Phuong Ha Nguyen (1)
- Khoa Nguyen (15)
- Ivica Nikolić (3)
- Christof Paar (1)
- Yanbin Pan (1)
- Thomas Peyrin (1)
- Josef Pieprzyk (20)
- Axel Poschmann (3)
- Christian Rechberger (2)
- Reihaneh Safavi-Naini (4)
- Santanu Sarkar (1)
- Przemyslaw Sokolowski (1)
- Damien Stehlé (1)
- Ron Steinfeld (15)
- Xiaoming Sun (1)
- Hung-Min Sun (1)
- Benjamin Hong Meng Tan (1)
- Christophe Tartary (4)
- Lei Wei (1)
- Peter R. Wild (1)
- Duncan S. Wong (3)
- Mu-En Wu (1)
- Hongjun Wu (1)
- Jun Xu (1)
- Yanhong Xu (1)
- Guomin Yang (3)
- Andrew Chi-Chih Yao (1)
- Qingsong Ye (1)
- Zhifang Zhang (1)