Fast Evaluation of S-boxes with Garbled Circuits
<|reference_start|>Fast Evaluation of S-boxes with Garbled Circuits: Garbling schemes are vital primitives for privacy-preserving protocols and 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 the Half-Gates (Zahur, Rosulek and Evans; Eurocrypt'15) and ThreeHalves (Rosulek and Roy; Crypto'21) 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 in the offline 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.<|reference_end|>
@article{pohle2024fast,
    title={Fast Evaluation of S-boxes with Garbled Circuits},
    author={Erik Pohle, Aysajan Abidin, Bart Preneel},
    journal={IEEE Transactions on Information Forensics and Security, vol. 19,
  pp. 5530-5544, 2024.},
    year={2024},
    doi={10.1109/TIFS.2024.3402145},
    archivePrefix={arXiv},
    eprint={2405.20713},
    primaryClass={cs.CR}
}