Function Recovery Attacks in Gate-Hiding Garbled Circuits using SAT Solving

• URL: http://arxiv.org/abs/2601.13271v1
• Date: Mon, 19 Jan 2026 18:15:12 GMT
• Title: Function Recovery Attacks in Gate-Hiding Garbled Circuits using SAT Solving
• Authors: Chao Yin, Zunchen Huang, Chenglu Jin, Marten van Dijk, Fabio Massacci,
• Abstract summary: Semi-Private Function Evaluation enables joint computation while protecting both input data and function logic.<n>We analyze the empirical security of gate hiding under two adversarial models that capture realistic computational capabilities.<n>We present a SAT-based function-recovery attack that reconstructs hidden gate operations from a circuit's public topology.
• Score: 18.958044099636982
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Semi-Private Function Evaluation enables joint computation while protecting both input data and function logic. A practical instantiation is gate-hiding garbled circuits, which conceal gate functionalities while revealing the circuit topology. Existing security definitions intentionally exclude leakage through circuit topology, leaving the concrete impact of such leakage on function privacy insufficiently understood. We analyze the empirical security of gate hiding under two adversarial models that capture realistic computational capabilities. We present a SAT-based function-recovery attack that reconstructs hidden gate operations from a circuit's public topology. To enable recovery on larger and more complex circuits, we develop an incremental SAT-solving framework combined with a set of composable, topology-preserving simplification theorems. These techniques jointly reduce the SAT instance size and progressively constrain the search space across repeated solving iterations. We evaluate our attack on ISCAS benchmarks, representative secure computation circuits, and fault-tolerant sensor fusion circuits under a fixed 24-hour recovery budget. Compared to baseline approaches, our optimized attack achieves up to a 159-fold speedup in recovery time without increasing the number of oracle queries. Our results demonstrate that topology leakage alone can enable effective function recovery in practice.

Related papers

• Certified Circuits: Stability Guarantees for Mechanistic Circuits [80.30622018787835]
  Certified Circuits provides provable stability guarantees for circuit discovery.<n>On ImageNet and OOD datasets, certified circuits achieve up to 91% higher accuracy.
  arXiv  Detail & Related papers  (2026-02-26T13:07:31Z)
• RealSec-bench: A Benchmark for Evaluating Secure Code Generation in Real-World Repositories [58.32028251925354]
  Large Language Models (LLMs) have demonstrated remarkable capabilities in code generation, but their proficiency in producing secure code remains a critical, under-explored area.<n>We introduce RealSec-bench, a new benchmark for secure code generation meticulously constructed from real-world, high-risk Java repositories.
  arXiv  Detail & Related papers  (2026-01-30T08:29:01Z)
• Security Evaluation of Quantum Circuit Split Compilation under an Oracle-Guided Attack [12.356632680373691]
  Split compilation is one of the most studied QCO techniques, where the circuit to be compiled is split into two disjoint partitions.<n>We propose an oracle-guided security evaluation framework in which candidate connections are systematically tested against input-output observations.<n> Experimental evaluation in the RevLib benchmark suite shows that only a small number of I/O pairs are sufficient to recover the correct inter-split connections and reconstruct the entire circuits.
  arXiv  Detail & Related papers  (2025-11-06T22:06:51Z)
• Automated Design of Structured Variational Quantum Circuits with Reinforcement Learning [10.136215038345012]
  This work represents the synthesis of variational quantum circuits as a sequential decision-making problem.<n>We introduce two reinforcement learning-based methods, RLVQC Global and RLVQC Block, tailored to optimization problems.<n>Our results show that both RLVQC methods exhibit strong results with RLVQC Block consistently outperforming QAOA and generally surpassing RLVQC Global.
  arXiv  Detail & Related papers  (2025-07-21T18:40:59Z)
• Rethinking Circuit Completeness in Language Models: AND, OR, and ADDER Gates [35.90665719234101]
  We introduce three types of logic gates: AND, OR, and ADDER gates, and decompose the circuit into combinations of these logical gates.<n>We propose a framework that combines noising-based and denoising-based interventions, which can be easily integrated into existing circuit discovery methods.
  arXiv  Detail & Related papers  (2025-05-15T07:35:14Z)
• Unveiling ECC Vulnerabilities: LSTM Networks for Operation Recognition in Side-Channel Attacks [6.373405051241682]
  We propose a novel approach for performing side-channel attacks on elliptic curve cryptography.<n>We adopt a long-short-term memory (LSTM) neural network to analyze a power trace and identify patterns of operation.<n>We show that current countermeasures, specifically the coordinate randomization technique, are not sufficient to protect against side channels.
  arXiv  Detail & Related papers  (2025-02-24T17:02:40Z)
• Sheaf Discovery with Joint Computation Graph Pruning and Flexible Granularity [18.71252449465396]
  We introduce DiscoGP, a framework for extracting self-contained modular units from neural language models (LMs)<n>Our framework identifies sheaves through a gradient-based pruning algorithm that operates on both of these in such a way that reduces the original LM to a sparse skeleton that preserves certain core capabilities.
  arXiv  Detail & Related papers  (2024-07-04T09:42:25Z)
• The Power of Resets in Online Reinforcement Learning [73.64852266145387]
  We explore the power of simulators through online reinforcement learning with local simulator access (or, local planning) We show that MDPs with low coverability can be learned in a sample-efficient fashion with only $Qstar$-realizability. We show that the notorious Exogenous Block MDP problem is tractable under local simulator access.
  arXiv  Detail & Related papers  (2024-04-23T18:09:53Z)
• RandOhm: Mitigating Impedance Side-channel Attacks using Randomized Circuit Configurations [6.388730198692013]
  We introduce RandOhm, which exploits a moving target defense (MTD) strategy based on the partial reconfiguration (PR) feature of mainstream FPGAs. We demonstrate that the information leakage through the PDN impedance could be significantly reduced via runtime reconfiguration of the secret-sensitive parts of the circuitry. In contrast to existing PR-based countermeasures, RandOhm deploys open-source bitstream manipulation tools to speed up the randomization and provide real-time protection.
  arXiv  Detail & Related papers  (2024-01-17T02:22:28Z)
• Adaptive Planning Search Algorithm for Analog Circuit Verification [53.97809573610992]
  We propose a machine learning (ML) approach, which uses less simulations. We show that the proposed approach is able to provide OCCs closer to the specifications for all circuits.
  arXiv  Detail & Related papers  (2023-06-23T12:57:46Z)
• Efficient Neural Network Analysis with Sum-of-Infeasibilities [64.31536828511021]
  Inspired by sum-of-infeasibilities methods in convex optimization, we propose a novel procedure for analyzing verification queries on networks with extensive branching functions. An extension to a canonical case-analysis-based complete search procedure can be achieved by replacing the convex procedure executed at each search state with DeepSoI.
  arXiv  Detail & Related papers  (2022-03-19T15:05:09Z)
• Logical blocks for fault-tolerant topological quantum computation [55.41644538483948]
  We present a framework for universal fault-tolerant logic motivated by the need for platform-independent logical gate definitions. We explore novel schemes for universal logic that improve resource overheads. Motivated by the favorable logical error rates for boundaryless computation, we introduce a novel computational scheme.
  arXiv  Detail & Related papers  (2021-12-22T19:00:03Z)
• ROME: Robustifying Memory-Efficient NAS via Topology Disentanglement and Gradient Accumulation [106.04777600352743]
  Differentiable architecture search (DARTS) is largely hindered by its substantial memory cost since the entire supernet resides in the memory. The single-path DARTS comes in, which only chooses a single-path submodel at each step. While being memory-friendly, it also comes with low computational costs. We propose a new algorithm called RObustifying Memory-Efficient NAS (ROME) to give a cure.
  arXiv  Detail & Related papers  (2020-11-23T06:34:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.