International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Xiangxue Li

Publications

Year
Venue
Title
2019
ASIACRYPT
Collision Resistant Hashing from Sub-exponential Learning Parity with Noise
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
EPRINT
2015
EPRINT
2015
TCC
2015
CRYPTO
2014
EPRINT
2014
EPRINT
2013
ASIACRYPT
2008
EPRINT
Democratic Group Signatures with Threshold Traceability
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.