First-Order and Composable Masking with Only 1-Bit of Reusable Fresh Randomness

Masking is actively studied as a promising countermeasure against side-channel attacks (SCAs) with provable security. Consumption of many random bits is a major overhead in masking, and researchers approached the problem by reusing randomness across multiple gadgets thereby making randomness consumption independent of circuit size. Faust et al. proposed a first-order masking with only two random bits, but their method lacked composability. Then, C O M A R proposed by Knichel and Moradi achieved first-order and composable gadgets, but the required randomness increased to six bits. Consequently, further reduction of reusable randomness in composable masking has been an open research problem. This paper approaches the problem by introducing new properties, Security under Input-Dependent Non-Interference and Output-Independence, wherein the two properties combined imply randomness reusability. We propose a generic gadget converter CoC that converts any gadget into the one satisfying the above two properties. We also propose optimized AND and XOR gadgets C O 2 with randomness reusability, which achieve first-order protection using only one fresh random bit per cycle. In our performance evaluation, the AES-128, Skinny64-64, CRAFT, LED-64, Midori-64, and PRESENT implementations protected with C O 2 have smaller circuit area compared to those based on the state-of-the-art masking schemes, namely H P C 2 , G H P C , G H P C L L , and C O M A R . The security of implementations protected with C O 2 is further verified with the formal verification tool SILVER and a physical experiment on an FPGA.