Fast Evaluation of S-boxes with Garbled Circuits

Erik Pohle; Aysajan Abidin; Bart Preneel

Paper 2022/1278

Fast Evaluation of S-boxes with Garbled Circuits

Erik Pohle

, imec-COSIC, KU Leuven

Aysajan Abidin

, imec-COSIC, KU Leuven

Bart Preneel

, imec-COSIC, KU Leuven

Abstract

Garbling schemes are vital primitives for privacy-preserving protocols and secure two-party computation. In projective garbling schemes, $n$ values are assigned to each wire in the circuit. Current state-of-the-art schemes project two values. This paper presents a projective garbling scheme that assigns values to wires in a circuit comprising XOR and unary projection gates. A generalization of FreeXOR allows the XOR of wires with values to be very efficient. We then analyze the performance of our scheme by evaluating substitution-permutation ciphers. Using our proposal, we measure high-speed evaluation of the ciphers with a moderately increased cost in garbling and bandwidth. Theoretical analysis suggests that for evaluating the nine examined ciphers, one can expect a 4- to 70-fold improvement in evaluation performance with, at most, a 4-fold increase in garbling cost and, at most, an 8-fold increase in communication cost compared to state-of-the-art garbling schemes. In an offline/online setting, such as secure function evaluation as a service, the circuit garbling and communication to the evaluator can proceed before the input phase. Thus, our scheme offers a fast online phase. Furthermore, we present efficient Boolean circuits for the S-boxes of TWINE and Midori64 ciphers. To our knowledge, our formulas give the smallest number of AND gates for the S-boxes of these two ciphers.

Note: This is the submitted version. For copyright reasons, the published version can be found in IEEE Transactions on Information Forensics and Security, vol. 19, pp. 5530-5544, 2024 or on https://arxiv.org/abs/2405.20713

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Major revision. IEEE Transactions on Information Forensics and Security
DOI: 10.1109/TIFS.2024.3402145
Keywords: garbled circuits garbling scheme substitution-permutation cipher S-box multi-party computation
Contact author(s): erik pohle @ esat kuleuven be
aysajan abidin @ esat kuleuven be
bart preneel @ esat kuleuven be
History: 2024-06-05: last of 3 revisions; 2022-09-26: received; See all versions
Short URL: https://ia.cr/2022/1278
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1278,
      author = {Erik Pohle and Aysajan Abidin and Bart Preneel},
      title = {Fast Evaluation of S-boxes with Garbled Circuits},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1278},
      year = {2022},
      doi = {10.1109/TIFS.2024.3402145},
      url = {https://eprint.iacr.org/2022/1278}
}