Function Recovery Attacks in Gate-Hiding Garbled Circuits using SAT Solving
For designers of secure computation protocols, this work identifies circuit topology as a security-relevant leakage channel in gate-hiding garbled circuits, highlighting a previously underexplored vulnerability.
The paper presents a SAT-based attack that reconstructs hidden gate operations in gate-hiding garbled circuits from public circuit topology, demonstrating that topology leakage materially assists function recovery. The optimized attack reduces recovery time compared to a baseline and completes recovery within a 24-hour budget in some cases where the baseline fails.
Semi-Private Function Evaluation (SPFE) enables joint computation while protecting both input data and the function itself. A practical instantiation is gate-hiding garbled circuits, which conceal gate functionalities while revealing circuit topology. Existing security definitions intentionally exclude leakage through topology, leaving its concrete impact on function privacy largely unexplored. We present a SAT-based function-recovery attack that reconstructs hidden gate operations from a circuit's public topology under two attacker knowledge models. Our approach combines topology-preserving simplification theorems with a decomposition of the recovery task into smaller SAT queries, thereby reducing the candidate gate-type assignment space and improving recovery performance. We evaluate the attack on ISCAS benchmarks, representative secure computation circuits, and fault-tolerant sensor fusion circuits under a 24-hour recovery budget. Compared to a baseline attack, the optimized version substantially reduces recovery time and, in some cases, completes recovery within the evaluation budget where the baseline does not. Our results show that revealing circuit topology can materially assist recovery of hidden gate functionality, identifying topology as a security-relevant leakage channel in gate-hiding garbled circuits.