## CryptoDB

### Huaxiong Wang

#### Publications

**Year**

**Venue**

**Title**

2022

EUROCRYPT

Field Instruction Multiple Data
📺
Abstract

Fully homomorphic encryption~(FHE) has flourished since it was first constructed by Gentry~(STOC 2009). Single instruction multiple data~(SIMD) gave rise to efficient homomorphic operations on vectors in \((\mathbb{F}_{t^d})^\ell\), for prime \(t\). RLWE instantiated with cyclotomic polynomials of the form \(X^{2^N}+1\) dominate implementations of FHE due to highly efficient fast fourier transformations. However, this choice yields very short SIMD plaintext vectors and high degree extension fields, e.g. \(\ell < 100, d > 100\) for small primes~(\(t = 3, 5, \dots\)).
In this work, we describe a method to encode more data on top of SIMD, \emph{Field Instruction Multiple Data}, applying reverse multiplication friendly embedding~(RMFE) to FHE. With RMFE, length-\(k\) \(\mathbb{F}_{t}\) vectors can be encoded into \(\mathbb{F}_{t^d}\) and multiplied once. The results have to be recoded~(decoded and then re-encoded) before further multiplications can be done. We introduce an FHE-specific technique to additionally evaluate arbitrary linear transformations on encoded vectors for free during the FHE recode operation. On top of that, we present two optimizations to unlock high degree extension fields with small \(t\) for homomorphic computation: \(r\)-fold RMFE, which allows products of up to \(2^r\) encoded vectors before recoding, and a three-stage recode process for RMFEs obtained by composing two smaller RMFEs.
Experiments were performed to evaluate the effectiveness of FIMD from various RMFEs compared to standard SIMD operations. Overall, we found that FIMD generally had \(>2\times\) better (amortized) multiplication times compared to FHE for the same amount of data, while using almost \(k/2 \times\) fewer ciphertexts required.

2022

ASIACRYPT

Improving Bounds on Elliptic Curve Hidden Number Problem for ECDH Key Exchange
📺
Abstract

Elliptic Curve Hidden Number Problem (EC-HNP) was first introduced by Boneh, Halevi and Howgrave-Graham at Asiacrypt 2001. To rigorously assess the bit security of the Diffie--Hellman key exchange with elliptic curves (ECDH), the Diffie--Hellman variant of EC-HNP, regarded as an elliptic curve analogy of the Hidden Number Problem (HNP), was presented at PKC 2017. This variant can also be used for practical cryptanalysis of ECDH key exchange in the situation of side-channel attacks.
In this paper, we revisit the Coppersmith method for solving the involved modular multivariate polynomials in the Diffie--Hellman variant of EC-HNP and demonstrate that, for any given positive integer $d$, a given sufficiently large prime $p$, and a fixed elliptic curve over the prime field $\mathbb{F}_p$, if there is an oracle that outputs about $\frac{1}{d+1}$ of the most (least) significant bits of the $x$-coordinate of the ECDH key, then one can give a heuristic algorithm to compute all the bits within polynomial time in $\log_2 p$. When $d>1$, the heuristic result $\frac{1}{d+1}$ significantly outperforms both the rigorous bound $\frac{5}{6}$ and heuristic bound $\frac{1}{2}$. Due to the heuristics involved in the Coppersmith method, we do not get the ECDH bit security on a fixed curve. However, we experimentally verify the effectiveness of the heuristics on NIST curves for small dimension lattices.

2021

PKC

Group Encryption: Full Dynamicity, Message Filtering and Code-Based Instantiation
📺
Abstract

Group encryption (\textsf{GE}), introduced by Kiayias, Tsiounis and Yung (Asiacrypt'07), is the encryption analogue of group signatures. It allows to send verifiably encrypted messages satisfying certain requirements to certified members of a group, while keeping the anonymity of the receivers. Similar to the tracing mechanism in group signatures, the receiver of any ciphertext can be identified by an opening authority - should the needs arise. The primitive of \textsf{GE} is motivated by a number of interesting privacy-preserving applications, including the filtering of encrypted emails sent to certified members of an organization.
This paper aims to improve the state-of-affairs of \textsf{GE} systems. Our first contribution is the formalization of fully dynamic group encryption (\textsf{FDGE}) - a \textsf{GE} system simultaneously supporting dynamic user enrolments and user revocations. The latter functionality for \textsf{GE} has not been considered so far. As a second contribution, we realize the message filtering feature for \textsf{GE} based on a list of $t$-bit keywords and $2$ commonly used policies: ``permissive'' - accept the message if it contains at least one of the keywords as a substring; ``prohibitive'' - accept the message if all of its $t$-bit substrings are at Hamming distance at least $d$ from all keywords, for $d \geq 1$. This feature so far has not been substantially addressed in existing instantiations of \textsf{GE} based on DCR, DDH, pairing-based and lattice-based assumptions. Our third contribution is the first instantiation of GE under code-based assumptions. The scheme is more efficient than the lattice-based construction of Libert et al. (Asiacrypt'16) - which, prior to our work, is the only known instantiation of \textsf{GE} under post-quantum assumptions. Our scheme supports the $2$ suggested policies for message filtering, and in the random oracle model, it satisfies the stringent security notions for \textsf{FDGE} that we put forward.

2020

PKC

PAKEs: New Framework, New Techniques and More Efficient Lattice-Based Constructions in the Standard Model
📺
Abstract

Password-based authenticated key exchange (PAKE) allows two parties with a shared password to agree on a session key. In the last decade, the design of PAKE protocols from lattice assumptions has attracted lots of attention. However, existing solutions in the standard model do not have appealing efficiency. In this work, we first introduce a new PAKE framework. We then provide two realizations in the standard model, under the Learning With Errors (LWE) and Ring-LWE assumptions, respectively. Our protocols are much more efficient than previous proposals, thanks to three novel technical ingredients that may be of independent interests. The first ingredient consists of two approximate smooth projective hash (ASPH) functions from LWE, as well as two ASPHs from Ring-LWE. The latter are the first ring-based constructions in the literature, one of which only has a quasi-linear runtime while its function value contains $$varTheta (n)$$ field elements (where n is the degree of the polynomial defining the ring). The second ingredient is a new key conciliation scheme that is approximately rate-optimal and that leads to a very efficient key derivation for PAKE protocols. The third one is a new authentication code that allows to verify a MAC with a noisy key.

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.

2019

ASIACRYPT

New Code-Based Privacy-Preserving Cryptographic Constructions
Abstract

Code-based cryptography has a long history but did suffer from periods of slow development. The field has recently attracted a lot of attention as one of the major branches of post-quantum cryptography. However, its subfield of privacy-preserving cryptographic constructions is still rather underdeveloped, e.g., important building blocks such as zero-knowledge range proofs and set membership proofs, and even proofs of knowledge of a hash preimage, have not been known under code-based assumptions. Moreover, almost no substantial technical development has been introduced in the last several years.This work introduces several new code-based privacy-preserving cryptographic constructions that considerably advance the state-of-the-art in code-based cryptography. Specifically, we present 3 major contributions, each of which potentially yields various other applications. Our first contribution is a code-based statistically hiding and computationally binding commitment scheme with companion zero-knowledge (ZK) argument of knowledge of a valid opening that can be easily extended to prove that the committed bits satisfy other relations. Our second contribution is the first code-based zero-knowledge range argument for committed values, with communication cost logarithmic in the size of the range. A special feature of our range argument is that, while previous works on range proofs/arguments (in all branches of cryptography) only address ranges of non-negative integers, our protocol can handle signed fractional numbers, and hence, can potentially find a larger scope of applications. Our third contribution is the first code-based Merkle-tree accumulator supported by ZK argument of membership, which has been known to enable various interesting applications. In particular, it allows us to obtain the first code-based ring signatures and group signatures with logarithmic signature sizes.

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

ASIACRYPT

2004

PKC

#### Program Committees

- Asiacrypt 2021 (Program chair)
- Asiacrypt 2020 (Program chair)
- PKC 2019
- Asiacrypt 2016
- Asiacrypt 2015
- Asiacrypt 2014
- Asiacrypt 2008

#### Coauthors

- Khin Mi Mi Aung (1)
- Alex Biryukov (1)
- Laurence Bull (1)
- Yeow Meng Chee (1)
- Scott Contini (2)
- Xiaotie Deng (1)
- Yvo Desmedt (2)
- Sareh Emami (1)
- Martianus Frederic Ezerman (1)
- Praveen Gauravaram (1)
- Guang Gong (1)
- Jian Guo (3)
- Jingnan He (1)
- Lei Hu (2)
- Tao Huang (1)
- Shaoquan Jiang (1)
- Khoongming Khoo (1)
- Dmitry Khovratovich (1)
- Hyung Tae Lee (1)
- Benoît Libert (7)
- Enhui Lim (1)
- Chu-Wee Lim (1)
- San Ling (22)
- Mulan Liu (1)
- Krystian Matusiewicz (2)
- Amir Moradi (2)
- Fabrice Mouhartem (3)
- Phuong Ha Nguyen (1)
- Khoa Nguyen (15)
- Ivica Nikolić (2)
- Christof Paar (1)
- Yanbin Pan (1)
- Thomas Peyrin (1)
- Josef Pieprzyk (14)
- Axel Poschmann (3)
- Christian Rechberger (1)
- Adeline Roux-Langlois (1)
- Reihaneh Safavi-Naini (4)
- Santanu Sarkar (2)
- Jun Jie Sim (1)
- Przemyslaw Sokolowski (1)
- Damien Stehlé (1)
- Ron Steinfeld (10)
- Xiaoming Sun (1)
- Willy Susilo (1)
- Benjamin Hong Meng Tan (2)
- Hanh Tang (1)
- Christophe Tartary (2)
- Lei Wei (1)
- Duncan S. Wong (1)
- Hongjun Wu (1)
- Jun Xu (2)
- Yanhong Xu (2)
- Guomin Yang (1)
- Andrew Chi-Chih Yao (1)
- Sze Ling Yeo (1)
- Neng Zeng (2)
- Zhifang Zhang (1)