Reducing Randomness Complexity of Mask Refreshing Algorithm

摘要

Among the existing countermeasures against side-channel analysis, masking is the most widely deployed one. In order to mask large functions (e.g. S-boxes), each basic operation of the function should be replaced with the d-th order secure operation. In this process, the multiplication with dependent inputs always exists, which may lead to security bias. In order to preserve the security of the dependent-input multiplication, a refreshing algorithm should be utilized to eliminate the dependence. Among the existing refreshing algorithms, only one proposal satisfying d-Strong Non-Interferent (d-SNI) can effectively solve the dependent-input issue. However, it suffers a low efficiency with a high randomness complexity. In this paper, we claim that the d-SNI refreshing algorithm is overqualified and a weaker refreshing algorithm can also ensure the security of the dependent-input multiplication. According to the property of the ISW multiplication, we prove that a refreshing algorithm satisfying a "conditional d-SNI" (weaker than d-SNI) can solve the dependent-input issue. In this way, we relax the security requirement of the refreshing algorithm. Based on this new security requirement, we propose a new refreshing algorithm satisfying conditional d-SNI. The randomness complexity of the new proposal is much lower than that of the original refreshing algorithm. As a validation, we implement the two refreshing algorithms on the 32-bit ARM core, and compare their random generations, clock cycles, and ROM consumptions. The comparison results indicate that our proposal outperforms the d-SNI refreshing algorithm in terms of both the randomness complexity and the arithmetic complexity, as significantly less random generations (33%-70% reduction), less clock cycles, and less ROM consumptions are involved in our proposal than in the d-SNI refreshing.