International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Mingsheng Wang

Publications

Year
Venue
Title
2020
ASIACRYPT
Mind the Propagation of States New Automatic Search Tool for Impossible Differentials and Impossible Polytopic Transitions 📺
Impossible differentials cryptanalysis and impossible polytopic cryptanalysis are the most effective approaches to estimate the security of block ciphers. However, the previous automatic search methods of their distinguishers, impossible differentials and impossible polytopic transitions, neither consider the impact of key schedule in the single-key setting and the differential property of large S-boxes, nor apply to the block ciphers with variable rotations. Thus, unlike previous methods which focus on the propagation of the difference or s-difference, we redefine the impossible differentials and impossible (s + 1)-polytopic transitions according to the propagation of state, which allow us to break through those limitations of the previous methods. Theoretically, we prove that traditional impossible differentials and impossible (s+1)-polytopic transitions are equivalent to part of our redefinitions, which have advantages from broader view. Technically, we renew the automatic search model and design an SAT-based tool to evaluate our redefined impossible differentials and impossible (s + 1)-polytopic transitions efficiently. As a result, for GIFT64, we get the 6-round impossible differentials which cannot be detected by all previous tools. For PRINTcipher, we propose the first modeling method for the key-dependent permutation and key-dependent S-box. For MISTY1, we derive 902 4-round impossible differentials by exploiting the differential property of S-boxes. For RC5, we present the first modeling method for the variable rotation and get 2.5-round impossible differentials for each version of it. More remarkable, our tool can be used to evaluate the security of given cipher against the impossible differentials, and we prove that there exists no 5-round 1 input active word and 1 output active word impossible differentials for AES-128 even consider the relations of 3-round keys. Besides, we also get the impossible (s + 1)-polytopic transitions for PRINTcipher, GIFT64, PRESENT, and RC5, all of which can cover more rounds than their corresponding impossible differentials as far as we know.
2018
TOSC
On the Generalization of Butterfly Structure
Butterfly structure was proposed in CRYPTO 2016 [PUB16], and it can generate permutations over
2017
TOSC
Optimal Differential Trails in SIMON-like Ciphers
Zhengbin Liu Yongqiang Li Mingsheng Wang
In the present paper, we propose an automatic search algorithm for optimal differential trails in SIMON-like ciphers. First, we give a more accurate upper bound on the differential probability of SIMON-like round function. It is shown that when the Hamming weight of the input difference α , which is denoted by wt(α), is less than one half of the input size, the corresponding maximum differential probability of SIMON-like round function is less than or equal to 2−wt(α)−1. Based on this, we adapt Matsui’s algorithm and propose an efficient algorithm for searching for optimal differential trails. With the proposed algorithm, we find the provably optimal differential trails for 12, 16, 19, 28 and 37 rounds of SIMON32/48/64/96/128. To the best of our knowledge, it is the first time that the provably optimal differential trails for SIMON64, SIMON96 and SIMON128 are reported. The provably optimal differential trails for 13, 19 and 25 rounds of SIMECK32/48/64 are also found respectively, which confirm the results given by Kölbl et al. [KR15]. Besides the optimal differential trails, we also find the 14, 17, 23, 31 and 41-round differentials for SIMON32/48/64/96/128, and 14, 21 and 27-round differentials for SIMECK32/48/64, respectively. As far as we know, these are the best differential distinguishers for SIMON and SIMECK so far. Compared with the approach based on SAT/SMT solvers used by K¨olbl et al., our algorithm is more efficient and more practical to evaluate the security against differential cryptanalysis in the design of SIMON-like ciphers.
2016
EUROCRYPT
2016
FSE
2015
EPRINT
2014
CHES
2013
ASIACRYPT
2010
EPRINT
A Flaw in The Internal State Recovery Attack on ALPHA-MAC
Shengbao Wu Mingsheng Wang Zheng Yuan
An distinguisher was constructed by utilizing a 2-round collision differential path of ALPHA-MAC, with about $2^{65.5}$ chosen messages and $2^{65.5}$ queries. Then, this distinguisher was used to recover the internal state(\cite{Yuan1},\cite{Yuan2}). However, a flaw is found in the internal state recovery attack. The complexity of recovering the internal state is up to $2^{81}$ exhaustive search. And the complexity of the whole attack will be up to $2^{67}$ chosen messages and $2^{81}$ exhaustive search. To repair the flaw, a modified 2-round differential path of ALPHA-MAC is present and a new distinguisher based on this path is proposed. Finally, an attack with about $2^{65.5}$ chosen messages and $2^{65.5}$ queries is obtained under the new distinguisher.
2008
EPRINT
Perfectly Hiding Commitment Scheme with Two-Round from Any One-Way Permutation
Commitment schemes are arguably among the most important and useful primitives in cryptography. According to the computational power of receivers, commitments can be classified into three possible types: {\it computational hiding commitments, statistically hiding commitments} and {\it perfect computational commitments}. The fist commitment with constant rounds had been constructed from any one-way functions in last centuries, and the second with non-constant rounds were constructed from any one-way functions in FOCS2006, STOC2006 and STOC2007 respectively, furthermore, the lower bound of round complexity of statistically hiding commitments has been proven to be $\frac{n}{logn}$ rounds under the existence of one-way function. Perfectly hiding commitments implies statistically hiding, hence, it is also infeasible to construct a practically perfectly hiding commitments with constant rounds under the existence of one-way function. In order to construct a perfectly hiding commitments with constant rounds, we have to relax the assumption that one-way functions exist. In this paper, we will construct a practically perfectly hiding commitment with two-round from any one-way permutation. To the best of our knowledge, these are the best results so far.
2003
EPRINT
A Verifiable Secret Sharing Scheme with Statistical zero-knowledge
Chunming Tang Zhuojun Liu Mingsheng Wang
In this paper, we first propose a protocol in which the prover can show that a=b holds for two committed integers a and b; also, we present a protocol in which the prover can prove that a\neq 0 holds for committed integer a; then, we construct a protocol to prove that the degree of a polynomial f(x) equals to t-1 exactly, which has been as an open problem(see[21]); finally, we provide a protocol in which the prover proves that a pair (x,y) is generated by a polynomial f(x), i.e., y=f(x)(mod m), where m is a prime. Based on above four protocols, we put forward a verifiable (t,n)-secret sharing scheme, which can avoid all known the dealer's cheats. In particular, all above protocols are statistical zero-knowledge.