International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Dongdai Lin

Publications

Year
Venue
Title
2021
CRYPTO
Differential-Linear Cryptanalysis from an Algebraic Perspective 📺
The differential-linear cryptanalysis is an important cryptanalytic tool in cryptography, and has been extensively researched since its discovery by Langford and Hellman in 1994. There are nevertheless very few methods to study the middle part where the differential and linear trail connect, besides the Differential-Linear Connectivity Table (Bar-On et al., EUROCRYPT 2019) and the experimental approach. In this paper, we study differential-linear cryptanalysis from an algebraic perspective. We first introduce a technique called Differential Algebraic Transitional Form (DATF) for differential-linear cryptanalysis, then develop a new theory of estimation of the differential-linear bias and techniques for key recovery in differential-linear cryptanalysis. The techniques are applied to the CAESAR finalist ASCON, the AES finalist SERPENT, and the eSTREAM finalist Grain v1. The bias of the differential-linear approximation is estimated for ASCON and SERPENT. The theoretical estimates of the bias are more accurate than that obtained by the DLCT, and the techniques can be applied with more rounds. Our general techniques can also be used to estimate the bias of Grain v1 in differential cryptanalysis, and have a markedly better performance than the Differential Engine tool tailor-made for the cipher. The improved key recovery attacks on round-reduced variants of these ciphers are then proposed. To the best of our knowledge, they are thus far the best known cryptanalysis of SERPENT, as well as the best differential-linear cryptanalysis of ASCON and the best initialization analysis of Grain v1. The results have been fully verified by experiments. Notably, security analysis of SERPENT is one of the most important applications of differential-linear cryptanalysis in the last two decades. The results in this paper update the differential-linear cryptanalysis of SERPENT-128 and SERPENT-256 with one more round after the work of Biham, Dunkelman and Keller in 2003.
2018
EUROCRYPT
2017
TOSC
Direct Construction of Optimal Rotational-XOR Diffusion Primitives
As a core component of SPN block cipher and hash function, diffusion layer is mainly introduced by matrices built from maximum distance separable (MDS) codes. Up to now, most MDS constructions require to perform an equivalent or even exhaustive search. In this paper, we study the cyclic structure of rotational-XOR diffusion layer, a commonly used diffusion primitive over (
2016
ASIACRYPT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
TCC
2015
ASIACRYPT
2015
ASIACRYPT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2013
FSE
2012
ASIACRYPT
2011
ASIACRYPT
2008
EPRINT
On Resettably-Sound Resttable Zero Knowledege Arguments
Yi Deng Dongdai Lin
We study the simultaneous resettability problem, namely whether resettably-sound resettable ZK arguments for non-trivial languages exist (posed by Barak et al. [BGGL FOCS'01]), in both the plain model and the bare public-key (BPK for short) model. Under general hardness assumptions, we show: 1. in the BPK model, there exist constant-round (full-fledged) resettably-sound resettable ZK arguments for NP. This resolves a main problem in this model that remained open since the Micali and Reyzin's identification of notions of soundness [MR Crypto 2001] in the BPK model. 2.in the plain model, there exist constant-round (unbounded) resettably-sound class-bounded resettable ZK (as defined by Deng and Lin in [DL Eurocrypt 2007]) arguments for NP. This improves the previous result of Deng and Lin [Eurocrypt 2007] in that the DL construction for class-bounded resettable ZK argument achieves only a weak notion of resettable-soundness. The crux of these results is a construction of constant-round instance-dependent (full-fledged) resettably-sound resettable WI argument of knowledge (IDWIAOK for short) for any NP statement of the form x_0\in L_0 or x_1\in L_1, a notion also introduced by Deng and Lin [Eurocrypt 2007], whose construction, however, obtains only weak resettable-soundness when x_0\notin L_0. Our approach to the simultaneous resettability problem in the BPK model is to make a novel use of IDWIAOK, which gives rise to an elegant structure we call \Sigma-puzzles. Given the fact that all previously known resettable ZK arguments in the BPK model can be achieved in the plain model when ignoring round complexity, we believe this approach will shed light on the simultaneous resettability problem in the plain model.
2007
EUROCRYPT
2007
EPRINT
Weakly only Unforgeable Signature and Its Application in Group Signature
Sujing Zhou Dongdai Lin
If a signature scheme is secure in the sense that no forgery on any new message (i.e., a message that has never been signed) is available for any computation restricted adversary, it is said weakly unforgeable (wUF), in contrast to strongly unforgeable (sUF) meaning no new signature on any old message (i.e., a valid signature on the message is already known) is available to such adversaries. sUF signatures are generally considered advantageous over wUF ones because of preference for high level security. But the case may be different when they are employed to construct group signatures. wUF but not sUF signatures, called WoUF signatures in this paper, are investigated in this paper. It is found that by applying a generic construction to WoUF signatures with indirectly-signability and perfectly-unlinkability (also defined in this paper), we can regenerate many efficient group signatures in literature. We also propose improvements to the group signature schemes of CL04, NSN04, KY05, in line with our generic construction.
2007
EPRINT
An Interesting Member ID-based Group Signature
Sujing Zhou Dongdai Lin
We propose an interesting efficient member ID-based group signatures, i.e., verification of output from algorithm OPEN run by the group manager does not have to refer to a registration table (acting as certification list). The proposal is free of GM-frameability, i.e., secret key of member is not escrowed to GM, which is unique among all known member ID-based group signatures as far as we know. The proposal also has two distinguished extra features, one is that the group manager does not have to maintain a registration table to obtain the real identity of the signer in contrast to other schemes, another is that it provides an alternative countermeasure against tampered registration table to applying integrity techniques to the table in case registration table is maintained.
2007
EPRINT
Unlinkable Randomizable Signature and Its Application in Group Signature
Sujing Zhou Dongdai Lin
We formalize a generic method of constructing efficient group signatures, specifically, we define new notions of unlinkable randomizable signature, indirectly signable signature and $\Sigma$-protocol friendly signature. We conclude that designing efficient secure group signatures can be boiled down to designing ordinary signatures satisfying the above three properties, which is supported by observations that almost all currently known secure efficient group signatures have alternative constructions in this line without deteriorating the efficiency.
2006
EPRINT
Resettable Zero Knowledge in the Bare Public-Key Model under Standard Assumption
Yi Deng Dongdai Lin
In this paper we resolve an open problem regarding resettable zero knowledge in the bare public-key (BPK for short) model: Does there exist constant round resettable zero knowledge argument with concurrent soundness for $\mathcal{NP}$ in BPK model without assuming \emph{sub-exponential hardness}? We give a positive answer to this question by presenting such a protocol for any language in $\mathcal{NP}$ in the bare public-key model assuming only collision-resistant hash functions against \emph{polynomial-time} adversaries.
2006
EPRINT
Shorter Verifier-Local Revocation Group Signatures From Bilinear Maps
Sujing Zhou Dongdai Lin
We propose a new computational complexity assumption from bilinear map, based on which we construct Verifier-Local Revocation group signatures with shorter lengths than previous ones.
2006
EPRINT
The Identity Escrow (Group Signature) Scheme at CT-RSA'05 Is Not Non-frameable
Sujing Zhou Dongdai Lin
Following an attack against exculpability, put forward at Asiacrypt'06, of ACJT's group signature, we further found Nguyen's identity escrow (group Signature) scheme did not satisfy non-frameabiliy either.
2006
EPRINT
A Shorter Group Signature with Verifier-Location Revocation and Backward Unlinkability
Zhou Sujing Dongdai Lin
Group signatures are generalized credential/member authentication schemes with wide applications, such as Trust Computing. Membership revocation problem is a major issue of group signatures. In some applications that group secret keys are stored in tamper resistant chips, a Verifier-Local Revocation resolution is more reasonable than other methods, such as witness based revocation. Boneh et al. formally defined such VLR group signatures and proposed a VLR resolution for a short group signature. Later Nakanishi et al. pointed out it has a disadvantage of backward linkability, and provided a VLR resolution with backward unlinkability at the cost of longer signature size and more computation. We improve Nakanishi et al.'s scheme by reducing the signature size and computations required, without compromising VLR and backward unlinkability.
2006
EPRINT
Concurrently Non-Malleable Zero Knowledge in the Authenticated Public-Key Model
We consider a type of zero-knowledge protocols that are of interest for their practical applications within networks like the Internet: efficient zero-knowledge arguments of knowledge that remain secure against concurrent man-in-the-middle attacks. As negative results in the area of concurrent non-malleable zero-knowledge imply that protocols in the standard setting (i.e., under no setup assumptions) can only be given for trivial languages, researchers have studied such protocols in models with setup assumptions, such as the common reference string (CRS) model. This model assumes that a reference string is honestly created at the beginning of all interactions and later available to all parties (an assumption that is satisfied, for instance, in the presence of a trusted party). A growing area of research in Cryptography is that of reducing the setup assumptions under which certain cryptographic protocols can be realized. In an effort to reduce the setup assumptions required for efficient zero-knowledge arguments of knowledge that remain secure against concurrent man-in-the-middle attacks, we consider a model, which we call the Authenticated Public-Key (APK) model. The APK model seems to significantly reduce the setup assumptions made by the CRS model (as no trusted party or honest execution of a centralized algorithm are required), and can be seen as a slightly stronger variation of the Bare Public-Key (BPK) model from \cite{CGGM,MR}, and a weaker variation of the registered public-key model used in \cite{BCNP}. We then define and study man-in-the-middle attacks in the APK model. Our main result is a constant-round concurrent non-malleable zero-knowledge argument of knowledge for any polynomial-time relation (associated to a language in $\mathcal{NP}$), under the (minimal) assumption of the existence of a one-way function family. We also show time-efficient instantiations of our protocol, in which the transformation from a 3-round honest-verifier zero-knowledge argument of knowledge to a 4-round concurrently non-malleable zero-knowledge argument of knowledge for the same relation incurs only $\mathcal{O}(1)$ (precisely, a {\em small} constant) additional modular exponentiations, based on known number-theoretic assumptions. Furthermore, the APK model is motivated by the consideration of some man-in-the-middle attacks in models with setup assumptions that had not been considered previously and might be of independent interest. We also note a negative result with respect to further reducing the setup assumptions of our protocol to those in the (unauthenticated) BPK model, by showing that concurrently non-malleable zero-knowledge arguments of knowledge in the BPK model are only possible for trivial languages.
2005
EPRINT
A fast parallel scalar multiplication against side-channel analysis for elliptic curve cryptosystem over prime fields
Dabi Zou Dongdai Lin
The scalar multiplication is the dominant operation in Elliptic Curve Cryptosystems (ECC). In this paper, we propose a modified width?Cw window method to compute the scalar multiplication efficiently and securely against side?Cchannel analysis, based on the side?Cchannel atomicity introduced by Benoit Chevallier?CMames. Utilizing this window method, we propose a new parallel scalar multiplication algorithm, which is secure against side?Cchannel analysis and more efficient than existing ones.
2005
EPRINT
Analyzing Unlinkability of Some Group Signatures
Zhou Sujing Dongdai Lin
Miyaji et.al proposed a fully functional(i.e., satisfying unforgeability, exculpability,anonymity, traceability, unlinkability, and revocability.) group signature over only known-order groups, that is based only on Discrete logarithm related assumptions, specifically, multiple DLP they proposed in the same paper [MU04]. In this paper, we point out their scheme and an improved scheme [ZZW05] do not have unlinkability.
2005
EPRINT
On Anonymity of Group Signatures
Zhou Sujing Dongdai Lin
A secure group signature is required to be anonymous, that is, given two group signatures generated by two different members on the same message or two group signatures generated by the same member on two different messages, they are indistinguishable except for the group manager. In this paper we prove the equivalence of a group signature's anonymity and its indistinguishability against chosen ciphertext attacks if we view a group signature as an encryption of member identity. Particularly, we prove ACJT's group signature is IND-CCA2 secure, so ACJT's scheme is anonymous in the strong sense. The result is an answer to an open question in literature.
2004
EPRINT
Security on Generalized Feistel Scheme with SP Round Function
Wu Wenling Zhang Wentao Dongdai Lin
This paper studies the security against differential/linear cryptanalysis and the pseudorandomness for a class of generalized Feistel scheme with SP round function called $GFSP$. We consider the minimum number of active s-boxes in some consecutive rounds of $GFSP$,i.e., in four, eight and sixteen consecutive rounds, which provide the upper bound of the maximum differential/linear probabilities of 16-round $GFSP$ scheme, in order to evaluate the strength against differential/linear cryptanalysis. Furthermore, We investigate the pseudorandomness of $GFSP$, point out 7-round $GFSP$ is not pseudorandom for non-adaptive adversary, by using some distinguishers, and prove that 8-round $GFSP$ is pseudorandom for any adversaries.
1988
EUROCRYPT

Program Committees

Asiacrypt 2020
PKC 2019 (Program chair)
Asiacrypt 2017
Asiacrypt 2016
Asiacrypt 2013
Asiacrypt 2012