The Effect Of The Difference Enumeration Attack On LowMC Instances

The LowMC is an algorithm with low multiplicative complexity proposed at Eurocrypt 2015.It consists of partial nonlinear layers and randomly linear layers,and can be used to obtain a variety of application instances by changing the block size,key size,number of S-boxcs per round and allowed data complexity.After many modifications,there are three versions of LowMCv1,LowMCv2,and LowMCv3.LowMC that the key size is n bits is denoted as LowMC-n.There are classical versions such as LowMC-80 and LowMC-128.At present,many attacks have achieved great results against LowMC.At ASI-ACRYPT 2015,Dinur et al.proposed an optimized interpolation attack against the first version of LowMC(LowMCv1).Under a weak key,the full LowMCv1-80 that the parameters are set to 80-bit key size,256-bit block size,49 S-boxes per round,264 data complexity and 11 rounds was broken with the time complexity of 257.In addition,the full LowMCv1-128 that the parameters are set to 128-bit key size,56-bit block size,63 S boxes per round,2128 data and 12 rounds was broken with the time complexity of 2118.Then,Dobraunig et al.proposed a high-order algebraic attack in ICIS 2015 which improve the above two attacks.The time complexity of LowMCv1-80 and LowMCv1-128 is reduced to 233 and 265,respectively.To ensure that the LowMC is resistant to above attacks,the designers of LowMC give a new formula for calculating the number of rounds,and the updated LowMC algorithm is called LowMCv2.Then,LowMCv2 with low S-box and low data was adopted as the encryption algorithm by newly proposed publickey signature schemes based on non-interactive zero-knowledge proofs.In FSE 2018,Rechberger et al.evaluated the security of LowMC instances with low data and low S-boxes with the help of difference enumeration attack and achieved the break of full LowMC.In addition,the time complexity is set to be close to the complexity of exhaustive search and the maximum number of rounds under differential enumeration attack is obtained.In order to resist the differential enumeration attack,LowMC version 3(LowMCv3)modified the round setting again.Although the attack of Rechbergerd et al.achieved the theoretical breaking of the full LowMC,we noticed that its attack is based on the ideal linear layer assumption and the actual effect of differential enumeration attack on the LowMCv2 instances is still unknown.Based on this observation,the actual rounds of differential enumeration attack is analyzed.As above,the linear layer is completely random in difference enumeration attack,which dose not match with the application situation.In order to comprehend the security of LowMC synthetically,we studied the strength of LowMC against difference enumeration attack under the specific linear layer.Firstly,by studying the key initial round,it is found that the differential enumeration attack cannot always reach the theoretical attack rounds.For some instances of LowMC that actual key initial rounds is smaller than the theoretical,differential enumeration attack even fails.Because the round setting of LowMC is based on existing attacks,this analysis may has important practical implications for the design of the new versions of LowMC in round setting.Furthermore,the effect of the Hamming weight of the linear layer matrix on the attack is also studied.We find that as long as the positions of 0 and 1 in the matrix are randomly distributed,the total amount of hamming has almost no effect on the differential enumeration attack.That is to say,we can reduce the hamming weight of the matrix of the lincar layer of LowMC without changing the security of LowMC,thus providing greater freedom for the selection of the linear layer.