改进MPCitH预处理：Mask即一切

摘要

MPC-in-the-head预处理（MPCitH-PP）范式为构建后量子数字签名（如Picnic3）提供了一种新方法。本文重新审视MPCitH-PP结构，分析其离线和在线阶段，并提出协议重构。通过识别这些阶段的冗余计算，我们将其优化为单一阶段，从而提升MPCitH-PP效率。此外，我们探索了mask的独立性，证明其可并行计算，这也优化了masked witness计算。

我们对Picnic3的优化实现显示出显著改进。在L1安全级别，最优软件实现将MPCitH-PP计算时间减少至先前实现的约30%。最优签名实现成本约为先前实现时间的78%。在L5安全级别，带并行最优的MPCitH-PP减少至先前解决方案时间的约26%，最优签名实现运行时间约为先前解决方案的53%。对于硬件实现，我们的优化将MPCitH-PP的时钟周期从r顺序轮减少到单轮并行，其中r表示LowMC算法中的轮数，硬件使用变化很小，且在AT乘积方面表现更好，尤其适用于并行计算。