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

Garbling schemes are vital primitives for privacy-preserving protocols and for secure two-party computation. This paper presents a projective garbling scheme that assigns $2^n$ values to wires in a circuit comprising XOR and unary projection gates. A generalization of FreeXOR allows the XOR of wires with $2^n$ 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 computation formulas for the S-boxes of TWINE and Midori64 in Boolean circuits. To our knowledge, our formulas give the smallest number of AND gates for the S-boxes of these two ciphers.

Note: Major revision.

Available format(s)
Cryptographic protocols
Publication info
garbled circuitsgarbling schemesubstitution-permutation cipherS-boxmulti-party computation
Contact author(s)
erik pohle @ esat kuleuven be
aysajan abidin @ esat kuleuven be
bart preneel @ esat kuleuven be
2023-06-04: last of 2 revisions
2022-09-26: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.