Geometry-Based Garbled Circuits Relying Solely on One Evaluation Algorithm Under Standard Assumption

Garbled circuits are the leading cryptographic techniques for constant-round secure two-party computation (S2PC). Classical constructions of Garbled circuits (GC) utilize 4 ciphertexts per gate which have attracted great attention for optimizing the performance of communication. Under standard assumption, the best existing optimizations on GC have reduced the number of ciphertexts per gate to 2, while other more efficient optimizations rely on the very strict non-standard assumption. However, these optimizations are based on the different evaluation algorithms of different garbled gates, leading to the switching requirement of the evaluator between different types of binary gates. In this paper, we focus on the optimization under standard assumption, and propose a garbling method with two ciphertexts per gate. Our scheme requires only 1 evaluation algorithm to evaluate all the binary gates, inspired by the geometric theorems of “the distance from any point on the circle to the center of the circle is equal” and “the distance from any point on the perpendicular bisector of the line segment to the two ends of the line segment is equal”. We transfer the four possible input options of each garbled gate into four binary coordinates in a two-dimensional surface, and construct garbled AND gates and garbled XOR gates with detailed garbling functions according to related geometric theorems. Finally, we proposed the geometry-based garbling scheme which could garble any circuits with AND gates, XOR gates and NOT gates by the proposed garbling algorithm, and the evaluation of all binary gates is to calculate the square of the distance between specific two-dimensional points, such that the number of evaluation algorithm is 1 during the whole garbling process. The security proof demonstrates that the proposed geometry-based garbling scheme satisfies the security requirements of privacy, obliviousness and authenticity. Related demo codes for our proposed Geometry-based GC is publicly available on Github: https://github.com/TAN-OpenLab/Geom-GC .