International Association
for Cryptologic Research

The MPC-in-the-head with preprocessing (MPCitH-PP) paradigm presents a novel approach for constructing post-quantum digital signatures like Picnic3. This paper revisits the MPCitH-PP construction, analyzing both its offline and online phases and proposing a reformulation of the protocol. By identifying redundant computations in these phases, we optimize them into a single phase, thereby enhancing the efficiency of MPCitH-PP. Furthermore, we explore the independence of the mask, demonstrating that it can be calculated in parallel, which also enables the optimization of the masked witness calculation.Our optimized implementation of Picnic3 shows significant improvements. At the L1 security level, the optimal software implementation reduces MPCitH-PP calculation time to about 30% of the previous implementation. The optimal signature implementation costs about 78% of the previous implementation time. At the L5 security level, MPCitH-PP with parallelism optimal is reduced to about 26% of the previous solution’s time, and the optimal signature implementation runs at about 53% of the previous solution’s time. For the hardware implementation, our optimizations reduce the clock cycles of MPCitH-PP from r sequential rounds to a single parallel round, where r denotes the number of rounds in the LowMC algorithm, with little change in hardware usage, and perform better in AT product, especially for parallel computing.

With the dramatic increase of easily accessible IoT devices, there is a growing demand to protect these cryptographic hardware implementations against Side-Channel Analysis (SCA) attacks. Among various proposed countermeasures against SCA, masking is a widely adopted countermeasure. Constructing a correct and secure masking hardware scheme is a challenging task, even for experienced engineers. Composable gadgets have recently been proposed to facilitate the process of masking large circuits by using the free composition property. For the composable gadget design, besides composability, minimizing hardware overhead in the overall composable masking scheme is also an important factor. To reduce the area overhead, we propose first- and second-order composable gadgets based on a ring circuit design, named OBS. The design of the ring circuit reduces the number of registers and sources of randomness, thereby reducing the area of the gadgets. From the perspective of composing large masked circuits, we propose several optimization methods based on the characteristics of ring circuits, such as register optimization, frozen technique and bubble strategy. These optimization methods can further optimize the overall area of the masked circuit. Furthermore, we also provide the proof of the first- and second-order security of the OBS gadgets under the glitch- and transition-extended probe model. To show the area advantage of the OBS schemes, we give the are comparison results with other schemes at the gadget level and masked circuit level. The best optimization rate compared to the state-of-the-art can reach 40% for the AES S-box. The comparison results of different implementations show that our scheme outperforms various other composable masking schemes in terms of area overhead. We also use the formal verification tool SILVER and practical FPGA-based experiments to confirm the claimed first- and second-order security.