## CryptoDB

### Xuejia Lai

#### Publications

**Year**

**Venue**

**Title**

2010

EPRINT

Distinguishing Properties of Higher Order Derivatives of Boolean Functions
Abstract

Higher order differential cryptanalysis is based on the property of higher order derivatives of Boolean functions that the degree of a Boolean function can be reduced by at least 1 by taking a derivative on the function at any point. We define \emph{fast point} as the point at which the degree can be reduced by at least 2. In this paper, we show that the fast points of a $n$-variable Boolean function form a linear subspace and its dimension plus the algebraic degree of the function is at most $n$. We also show that non-trivial fast point exists in every $n$-variable Boolean function of degree $n-1$, every symmetric Boolean function of degree $d$ where $n \not\equiv d \pmod{2}$ and every quadratic Boolean function of odd number variables. Moreover we show the property of fast points for $n$-variable Boolean functions of degree $n-2$.

2008

EPRINT

Improved efficiency of Kiltz07-KEM
Abstract

Kiltz proposed a practical key encapsulation mechanism(Kiltz07-KEM) which is secure
against adaptive chosen ciphertext attacks(IND-CCA2) under the gap hashed
Diffie-Hellman(GHDH) assumption\cite{Kiltz2007}. We show a variant of Kiltz07-KEM which
is more efficient than Kiltz07-KEM in encryption. The new scheme can be proved to be
IND-CCA2 secure under the same assumption, GHDH.

2008

EPRINT

Higher Order Differential Cryptanalysis of Multivariate Hash Functions
Abstract

In this paper we propose an attack against multivariate hash
functions, which is based on higher order differential
cryptanalysis. As a result, this attack can be successful in finding
the preimage of the compression function better than brute force and
it is easy to make selective forgeries when a MAC is constructed by
multivariate polynomials. It gives evidence that families of
multivariate hash functions are neither pseudo-random nor
unpredictable and one can distinguish a function from random
functions, regardless of the finite field and the degree of the
polynomials.

2008

EPRINT

On the Design of Secure Double Block Length Hash Functions with Rate 1
Abstract

This paper reconsiders the security of the rate-1 double block
length hash functions, which based on a block cipher with a block
length of $n$-bit and a key length of $2n$-bit. Counter-examples and
new attacks are presented on this general class of double block
length hash functions with rate 1, which disclose there exist
uncovered flaws in the former analysis given by Satoh \textit{et
al.} and Hirose. Preimage and second preimage attacks are designed
to break Hirose's two examples which were left as an open problem.
Some refined conditions are proposed for ensuring this general class
of the rate-1 hash functions to be optimally secure against the
collision attack. In particular, two typical examples, which
designed under the proposed conditions, are proven to be
indifferentiable from the random oracle in the ideal cipher model.
The security results are extended to a new class of double block
length hash functions with rate 1, where one block cipher used in
the compression function has the key length is equal to the block
length, while the other is doubled.

2008

EPRINT

Chosen ciphertext secure public key encryption under DDH assumption with short ciphertext
Abstract

An efficient variant of the ElGamal public key encryption scheme is proposed which is
provably secure against adaptive chosen ciphertext attacks(IND-CCA2) under the decisional
Diffie-Hellman(DDH) assumption. Compared to the previously most efficient scheme under
DDH assumption by Kurosawa and Desmedt [Crypto 2004] it has one group element shorter
ciphertexts, 50\% shorter secret keys, 25\% shorter public keys and it is 28.6\% more
efficient in terms of encryption speed, 33.3\% more efficient in terms of decryption
speed. A new security proof logic is used, which shows directly that the decryption
oracle will not help the adversary in the IND-CCA2 game. Compared to the previous
security proof, the decryption simulation is not needed in the new logic. This makes the
security proof simple and easy to understand.

2008

EPRINT

On the Design of Secure and Fast Double Block Length Hash Functions
Abstract

This paper reconsiders the security of the rate-1 double block
length hash functions, which based on a block cipher with a block
length of $n$-bit and a key length of $2n$-bit. Counter-examples and
new attacks are presented on this general class of double block
length hash functions with rate 1, which disclose there exist
uncovered flaws in the former analysis given by Satoh \textit{et
al.} and Hirose. Preimage and second preimage attacks are designed
to break Hirose's two examples which were left as an open problem.
Some refined conditions are proposed for ensuring this general class
of the rate-1 hash functions to be optimally secure against the
collision attack. In particular, two typical examples, which
designed under the proposed conditions, are proven to be
indifferentiable from the random oracle in the ideal cipher model.
The security results are extended to a new class of double block
length hash functions with rate 1, where one block cipher used in
the compression function has the key length is equal to the block
length, while the other is doubled.

2007

EPRINT

Efficient chosen ciphertext secure PKE scheme with short ciphertext
Abstract

Kurosawa and Matsuo\cite{Kurosawa20042} showed that MAC can be removed from DHIES while
the underlying symmetric-key encryption(SKE) scheme is secure against adaptive chosen
ciphertext attacks(IND-CCA). We construct a variant of DHIES which eliminate the MAC
while the SKE scheme is secure against passive attacks(IND-PA). Since IND-PA is the basic
requirement of SKE schemes, the new scheme is more flexible than \cite{Kurosawa20042}.
Our new scheme can be seen as a combination of a tag-KEM \cite{Abe2005} and a DEM. Our
construction offers the first tag-KEM with single element. When the hash function $H$ in
the ODH assumption is a non-malleable hash function we can prove that the new scheme is
IND-CCA secure under the ODH assumption.

2007

EPRINT

A new paradigm of chosen ciphertext secure public key encryption scheme
Abstract

For all current adaptive chosen ciphertext(CCA) secure public key encryption
schemes in standard model there are two operations in the decryption algorithm,
``validity check" and decryption. The decryption algorithm returns the
corresponding plaintext if the ciphertext is valid otherwise it returns a
rejection symbol $\perp$. We call this paradigm ``invalid ciphertext
rejection". However the ``validity check" is not necessary for an encryption
scheme. Also in this case the adversary will get the information that the
ciphertext is "invalid" which he may not know before the decryption query. We
propose a new paradigm for constructing CCA secure public key encryption
schemes which combines ``validity check" and decryption together. The
decryption algorithm will execute the same operation regardless of the
ciphertext's validity. We call this new paradigm ``uniform decryption".
Compared with the "invalid ciphertext rejection" paradigm, the decryption
oracle of schemes in the new paradigm will reveal less information. The
attacker even can not get whether the queried ciphertext is ``valid" or not.
Moreover the combination of ``validity check" and the decryption will yield
more efficient schemes.
Using the new paradigm we construct an efficient public key encryption scheme.
Our scheme is more efficient than CS98 in both computation and bandwidth.
Compered with KD04 and HK07 the new scheme is more efficient in bandwidth and
the same efficient in computation. The new scheme is as efficient as Kiltz07
both in computation and bandwidth. However the new scheme is CCA secure based
on DDH assumption which is more flexible than GHDH assumption that Kiltz07
based on.
Kurosawa and Desmedt proposed an efficient hybrid scheme named as
KD04\cite{Kurosawa2004}. Although the key encapsulation part of KD04(KD04-KEM)
is not CCA secure \cite{Hofheinz2006}, the whole scheme can be proved to be CCA
secure. We show that if the key derivation function(KDF) of KD04-KEM is a
non-malleable hash function it will be a CCA secure KEM in the new paradigm.

2007

EPRINT

On the hash function of ODH
Abstract

M. Abdalla, M. Bellare and P. Rogaway proposed a variation of Diffie-Hellman assumption
named as oracle Diffie-Hellman(ODH) assumption. They recommend to use a one-way
cryptographic hash function for the ODH assumption. We notice that if the hash function
is just one-way then there will be an attack. We show that if the the hash function is
non-malleable then the computational version of ODH assumption can be reduced to the
computational Diffie-Hellman(CDH) assumption. But we can not reduce the ODH assumption to
the decisional Diffie-Hellman(DDH) even if the hash function is non-malleable. It seems
that we need a random oracle hash function to reduce the ODH assumption to the DDH
assumption.

2007

EPRINT

Weak adaptive chosen ciphertext secure hybrid encryption scheme
Abstract

We propose a security notion named as weak adaptive chosen ciphertext security(IND-WCCA)
for hybrid encryption schemes. Although it is weaker than adaptive chosen ciphertext
security(IND-CCA), a IND-WCCA secure hybrid encryption scheme can be used in any
situations that a IND-CCA secure hybrid encryption scheme used in. We show that IND-WCCA
secure hybrid encryption scheme can be constructed from IND-CCA secure KEM and IND-PA
secure DEM. Since IND-PA is the basic requirement of symmetric key encryption schemes,
IND-WCCA hybrid encryption scheme is very flexible and can use most of the stream ciphers
and block ciphers as the DEM part of the scheme. Use the new secure notion we can refine
current IND-CCA secure hybrid encryption schemes and get more efficient IND-WCCA secure
hybrid encryption schemes.

2007

EPRINT

A Synthetic Indifferentiability Analysis of Block Cipher based Hash Functions
Abstract

Nowadays, investigating what construction is better to be a
cryptographic hash function is red hot. In TCC'04, Maurer
et al. first introduced the notion of indifferentiability as a
generalization of the concept of the indistinguishability of two
cryptosystems. In AsiaCrypt
06, Chang et al. analyzed the indifferentiability security of some
popular block-cipher-based hash functions, such as PGV
constructions and MDC-2. In this paper, we investigate Chang et
al.'s analysis of PGV constructions and the PBGV double block
length constructions. In particular, we point out a more precise
adversarial advantage of indifferentiability, by considering the
two situations that whether the hash function is either keyed or
not. Furthermore, Chang et al. designed attacks on 4
PGV hash functions and PBGV hash function to prove they are
differentiable from random oracle with prefix-free padding. We
find a limitation in their differentiable attacks and construct
our simulations to obtain the controversy results that those
schemes are indifferentiable from random oracle with prefix-free
padding and some other popular constructions.

2006

EPRINT

Revisit of KD04
Abstract

KD04 proposed by K. Kurosawa and Y. Desmedt is the most efficient public key
encryption scheme provably secure against adaptive chosen ciphertext attack in
standard model based on decision diffie-hellman problem. We proposed a simplify
version of KD04 which is more efficient than KD04 while still can be proved to
be secure against adaptive chosen ciphertext attack in standard model based on
decision diffie-hellman problem.

2006

EPRINT

Revisit of CS98
Abstract

Cramer and Shoup proposed the first provably secure practical public-key
encryption scheme in the standard model (CS98). We find new way to construct
the secure reduction in which the decryption oracle is not needed yet. Thus we
get a simplified version of CS98 which is more efficient than the original
scheme, and also provably secure against chosen ciphertext attack in standard
model.

2005

EPRINT

Improved Collision Attack on Hash Function MD5
Abstract

In this paper, we present a fast attack algorithm to find two-block collision of hash function MD5. The algorithm is based on the two-block collision differential path of MD5 that was presented by Wang et al. in EUROCRYPT 2005[6]. We found that the derived conditions for the desired differential path in [6] were not sufficient to guarantee the differential path to hold and that some conditions could be relaxed to enlarge the collision set. By using technique of small range searching and omitting the computing steps to check the characteristics in algorithm, we can speed up the attack of MD5 efficiently. Compared with the Advanced Message Modification technique [5,6], the small range searching technique can correct 4 more conditions for the first iteration differential and 3 more conditions for the second iteration differential, thus improving the probability and the complexity to find collisions. The whole attack on the MD5 can be accomplished within 5 hours using a PC with Pen-tium4 1.70GHZ CPU.

1994

EUROCRYPT

#### Program Committees

- Crypto 2018
- Asiacrypt 2016
- Asiacrypt 2015
- Asiacrypt 2014
- Eurocrypt 2013
- Asiacrypt 2010
- Asiacrypt 2009
- Asiacrypt 2007
- FSE 2006
- Asiacrypt 2006 (Program chair)
- Asiacrypt 2005
- FSE 2005
- Crypto 1999
- Asiacrypt 1998
- Eurocrypt 1998

#### Coauthors

- Hui Chen (1)
- Kefei Chen (4)
- Ming Duan (1)
- Dengguo Feng (2)
- Zheng Gong (3)
- Dake He (8)
- Walter Hohl (1)
- Jialin Huang (1)
- Lars R. Knudsen (3)
- Guomin Li (5)
- Jie Liang (1)
- Xianhui Lu (8)
- Yiyuan Luo (1)
- James L. Massey (3)
- Thomas Meier (1)
- Kaisa Nyberg (1)
- Bart Preneel (1)
- Rainer A. Rueppel (2)
- Xiaorui Sun (2)
- Serge Vaudenay (1)
- Christian Waldvogel (1)
- Xiaoyun Wang (2)
- Jack Woollven (1)
- Mohan Yang (1)
- Xiuyuan Yu (1)
- Hongbo Yu (1)
- Bo Zhu (1)