## CryptoDB

### Jian Weng

#### Affiliation: Jinan University

#### 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

2013

ASIACRYPT

2010

EPRINT

CCA-Secure Unidirectional Proxy Re-Encryption in the Adaptive Corruption Model without Random Oracles
Abstract

Proxy re-encryption (PRE), introduced by Blaze, Bleumer and Strauss in Eurocrypt'98, allows a semi-trusted proxy to convert a ciphertext originally intended for Alice into an encryption of the same message intended for Bob. PRE has recently drawn great interest, and many interesting PRE schemes have been proposed. However, up to now, it is still an important question to come up with a chosen-ciphertext secure unidirectional PRE in the adaptive corruption model. To address this problem, we propose a new unidirectional PRE scheme, and prove its chosen-ciphertext security in the adaptive corruption model without random oracles. Compared with the best known unidirectional PRE scheme proposed by Libert and Vergnaud in PKC'08, our schemes enjoys the advantages of both higher efficiency and stronger security.

2010

EPRINT

On the Security of a Bidirectional Proxy Re-Encryption Scheme from PKC 2010
Abstract

In PKC 2010, Matsuda, Nishimaki and Tanaka proposed a bidirectional proxy re-encryption (PRE) scheme without bilinear maps, and claimed that their scheme is chosen-ciphertext secure in the standard model. However, by giving a concrete attack, in this paper we indicate that their PRE scheme fails to achieve the chosen-ciphertext security. The purpose of this paper is to clarify the fact that, it is still an open problem to come up with a chosen-ciphertext secure PRE scheme without bilinear maps in the standard model.

2010

EPRINT

CCA-Secure PRE Scheme without Public Verifiability
Abstract

In a proxy re-encryption (PRE) scheme, a semi-trusted proxy can
transform a ciphertext under Alice's public key into another
ciphertext that Bob can decrypt. However, the proxy cannot access
the plaintext. Due to its transformation property, PRE can be used
in many applications, such as encrypted email forwarding. All
the existing CCA-secure PRE schemes have a crucial property: the
public verifiability of the original ciphertext, i.e., everyone can
check the validity of the original ciphertext. In this paper, we
propose a novel CCA-secure PRE scheme without public
verifiability. This proposal is proven-secure based on the DDH
assumption in the standard model. To the best of our knowledge, our
proposal is the first CCA-secure unidirectional PRE scheme
without pairings in the standard model, which answers an open
problem in the PRE field.

2007

EPRINT

Fast Digital Signature Schemes as Secure as Diffie-Hellman Assumptions
Abstract

This paper presents two fast digital signature schemes based on Diffie-Hellman assumptions. In the random oracle model, the first scheme S1 has a tight security reduction to the computational Diffie-Hellman (CDH) problem; and the second scheme S2 has a tight security reduction to the decisional Diffie-Hellman (DDH) problem.
Comparing with existing signature schemes (whose security is tightly related to CDH problem) like EDL signature schemes, the signature generation of S1 is about 27% faster, and the verification is about 35% faster, if without considering the hash function evaluations. Comparing with existing signature schemes (whose security is tightly related to DDH problem) like KW-DDH signature scheme, the signing of S2 is about 40% faster and the verification is about 35% faster.
The high efficiency of the proposed schemes is attributed to a new
protocol EDL_mwz which implements the proof of equality of discrete logarithm. The EDL_mwz protocol outperforms its counterpart, the Chaum and Pedersen protocol, as its computation is about 38% faster and its bandwidth is |G| bits shorter. This new protocol may be of independent interests.

#### Coauthors

- Feng Bao (1)
- Jie Chen (1)
- Minrong Chen (1)
- Kefei Chen (1)
- Robert H. Deng (4)
- Junqing Gong (1)
- Dawu Gu (3)
- Chun Guo (1)
- Goichiro Hanaoka (1)
- Junzuo Lai (3)
- Xiangxue Li (5)
- Peng Liu (1)
- Shengli Liu (2)
- Changshe Ma (2)
- Kouichi Sakurai (1)
- Jun Shao (1)
- Yanjiang Yang (1)
- Yu Yu (5)
- Jiang Zhang (1)
- Yunlei Zhao (4)
- Dong Zheng (1)