International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Efficient Private Circuits with Precomputation

Authors:
Weijia Wang , School of Cyber Science and Technology, Shandong University, Qingdao, China; Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Qingdao, China; Quan Cheng Shandong Laboratory, Jinan, China
Fanjie Ji , School of Cyber Science and Technology, Shandong University, Qingdao, China
Juelin Zhang , School of Cyber Science and Technology, Shandong University, Qingdao, China
Yu Yu , Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai, China; Shanghai Qi Zhi Institute, Shanghai, China; Shanghai Key Laboratory of Privacy-Preserving Computation, Shanghai, China
Download:
DOI: 10.46586/tches.v2023.i2.286-309
URL: https://tches.iacr.org/index.php/TCHES/article/view/10285
Search ePrint
Search Google
Abstract: At CHES 2022, Wang et al. described a new paradigm for masked implementations using private circuits, where most intermediates can be precomputed before the input shares are accessed, significantly accelerating the online execution of masked functions. However, the masking scheme they proposed mainly featured (and was designed for) the cost amortization, leaving its (limited) suitability in the above precomputation-based paradigm just as a bonus. This paper aims to provide an efficient, reliable, easy-to-use, and precomputation-compatible masking scheme. We propose a new masked multiplication over the finite field Fq suitable for the precomputation, and prove its security in the composable notion called Probing-Isolating Non-Inference (PINI). Particularly, the operations (e.g., AND and XOR) in the binary field can be achieved by assigning q = 2, allowing the bitsliced implementation that has been shown to be quite efficient for the software implementations. The new masking scheme is applied to leverage the masking of AES and SKINNY block ciphers on ARM Cortex M architecture. The performance results show that the new scheme contributes to a significant speed-up compared with the state-of-the-art implementations. For SKINNY with block size 64, the speed and RAM requirement can be significantly improved (saving around 45% cycles in the online-computation and 60% RAM space for precomputed values) from AES-128, thanks to its smaller number of AND gates. Besides the security proof by hand, we provide formal verifications for the multiplication and T-test evaluations for the masked implementations of AES and SKINNY. Because of the structure of the new masked multiplication, our formal verification can be performed for security orders up to 16.
BibTeX
@article{tches-2023-33039,
  title={Efficient Private Circuits with Precomputation},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2023, Issue 2},
  pages={286-309},
  url={https://tches.iacr.org/index.php/TCHES/article/view/10285},
  doi={10.46586/tches.v2023.i2.286-309},
  author={Weijia Wang and Fanjie Ji and Juelin Zhang and Yu Yu},
  year=2023
}