## CryptoDB

### Xiangxue Li

#### Publications

**Year**

**Venue**

**Title**

2019

ASIACRYPT

Collision Resistant Hashing from Sub-exponential Learning Parity with Noise
Abstract

The Learning Parity with Noise (LPN) problem has recently found many cryptographic applications such as authentication protocols, pseudorandom generators/functions and even asymmetric tasks including public-key encryption (PKE) schemes and oblivious transfer (OT) protocols. It however remains a long-standing open problem whether LPN implies collision resistant hash (CRH) functions. Inspired by the recent work of Applebaum et al. (ITCS 2017), we introduce a general construction of CRH from LPN for various parameter choices. We show that, just to mention a few notable ones, under any of the following hardness assumptions (for the two most common variants of LPN) 1.constant-noise LPN is $$2^{n^{0.5+\varepsilon }}$$-hard for any constant $$\varepsilon >0$$;2.constant-noise LPN is $$2^{\varOmega (n/\log n)}$$-hard given $$q=\mathsf {poly}(n)$$ samples;3.low-noise LPN (of noise rate $$1/\sqrt{n}$$) is $$2^{\varOmega (\sqrt{n}/\log n)}$$-hard given $$q=\mathsf {poly}(n)$$ samples. there exists CRH functions with constant (or even poly-logarithmic) shrinkage, which can be implemented using polynomial-size depth-3 circuits with NOT, (unbounded fan-in) AND and XOR gates. Our technical route LPN $$\rightarrow $$ bSVP $$\rightarrow $$ CRH is reminiscent of the known reductions for the large-modulus analogue, i.e., LWE $$\rightarrow $$ SIS $$\rightarrow $$ CRH, where the binary Shortest Vector Problem (bSVP) was recently introduced by Applebaum et al. (ITCS 2017) that enables CRH in a similar manner to Ajtai’s CRH functions based on the Short Integer Solution (SIS) problem.Furthermore, under additional (arguably minimal) idealized assumptions such as small-domain random functions or random permutations (that trivially imply collision resistance), we still salvage a simple and elegant collision-resistance-preserving domain extender combining the best of the two worlds, namely, maximized (depth one) parallelizability and polynomial shrinkage. In particular, assume $$2^{n^{0.5+\varepsilon }}$$-hard constant-noise LPN or $$2^{n^{0.25+\varepsilon }}$$-hard low-noise LPN, we obtain a collision resistant hash function that evaluates in parallel only a single layer of small-domain random functions (or random permutations) and shrinks polynomially.

2015

CRYPTO

2014

EPRINT

2014

EPRINT

2013

ASIACRYPT

2008

EPRINT

Democratic Group Signatures with Threshold Traceability
Abstract

Recently, democratic group signatures(DGSs) particularly catch our
attention
due to their great flexibilities, \emph{i.e}., \emph{no
group manager}, \emph{anonymity}, and \emph{individual
traceability}. In existing DGS schemes, individual traceability says
that any member in the group can reveal the actual signer's
identity from a given signature. In this paper, we formally describe
the definition of DGS, revisit its security notions by strengthening
the requirement for the property of traceability, and present a
concrete DGS construction with $(t, n)$-\emph{threshold
traceability} which combines the concepts of group signatures and of
threshold cryptography. The idea behind the $(t, n)$-threshold
traceability is to distribute between $n$ group members the
capability of tracing the actual signer such that any subset of not
less than $t$ members can jointly reconstruct a secret and reveal
the identity of the signer while preserving security even in the
presence of an active adversary which can corrupt up to $t-1$ group
members.

#### Coauthors

- Aytac Azgin (1)
- Kefei Chen (1)
- Xiaoli Dong (1)
- Dawu Gu (4)
- Chun Guo (1)
- Jianhua Li (1)
- Changshe Ma (1)
- Jian Weng (5)
- Yu Yu (6)
- Jiang Zhang (1)
- Qinglan Zhao (1)
- Qingji Zheng (1)
- Dong Zheng (2)