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

Chao Yin; Chenglu Jin; Fabio Massacci; Marten van Dijk; Zunchen Huang

arxiv: 2601.13271 · v4 · submitted 2026-01-19 · 💻 cs.CR · cs.LO

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

Chao Yin , Zunchen Huang , Chenglu Jin , Marten van Dijk , Fabio Massacci This is my paper

Pith reviewed 2026-05-16 13:08 UTC · model grok-4.3

classification 💻 cs.CR cs.LO

keywords garbled circuitsfunction recovery attackSAT solvingcircuit topologygate hidingsemi-private function evaluationleakage channelsecure computation

0 comments

The pith

Revealing circuit topology lets attackers recover hidden gate functions in garbled circuits via SAT solving.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that gate-hiding garbled circuits leak enough structure through their public topology for a SAT-based attack to reconstruct the concealed gate operations. It combines topology-preserving simplification rules with a decomposition of the recovery task into smaller solvable queries, shrinking the space of candidate assignments. A sympathetic reader would care because current security definitions for these circuits explicitly exclude topology from the leakage model, yet the attack shows this exclusion leaves the hidden function vulnerable on real benchmark circuits. The evaluation demonstrates that the optimized attack finishes many recoveries within a 24-hour window where a baseline approach does not.

Core claim

In gate-hiding garbled circuits the wiring diagram is public while gate functionalities stay hidden. The authors build a SAT-based recovery attack that first applies topology-preserving simplification theorems to prune impossible gate assignments and then splits the remaining problem into multiple smaller SAT instances. When run on ISCAS benchmarks, representative secure-computation circuits, and fault-tolerant sensor-fusion circuits under a 24-hour budget, the optimized attack recovers the hidden functions substantially faster than the baseline and succeeds on instances the baseline cannot finish.

What carries the argument

SAT encoding of gate-type assignments together with topology-preserving simplification theorems that reduce the search space before decomposition into smaller queries.

If this is right

Security definitions for gate-hiding garbled circuits must treat revealed topology as a leakage channel that can assist function recovery.
Function privacy weakens when the wiring diagram is public even if individual gate types remain hidden.
Recovery time drops on circuits whose structure admits effective simplification, making some practical instances newly vulnerable.
Protocols that expose topology may need additional countermeasures to restore the intended level of function hiding.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Designers of private function evaluation may need to hide or randomize topology in addition to gate types to achieve stronger privacy.
The same decomposition technique could apply to function recovery in other circuit-based privacy schemes that expose structure.
Testing the attack on larger industrial circuits would show whether the observed speedups remain practical at scale.
Combining topology leakage with timing or power side channels could further reduce the effort needed to recover functions.

Load-bearing premise

The attacker knows the complete circuit topology and the simplification theorems plus SAT encoding include every valid gate assignment without adding invalid solutions.

What would settle it

A concrete circuit whose original gate types are known in advance; after the attack runs on its public topology it must output an assignment that differs from the true gates or that fails to satisfy the circuit semantics.

Figures

Figures reproduced from arXiv: 2601.13271 by Chao Yin, Chenglu Jin, Fabio Massacci, Marten van Dijk, Zunchen Huang.

**Figure 2.** Figure 2: Circuit Complexity of the Evaluated Benchmarks. [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Figure 3: Log-scale recovery runtime on representative MPC functions. Each subplot reports the recovery time as a function of [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

**Figure 4.** Figure 4: Overall Impact of Simplifications 1 1 1 1 $!" " 1 1 1 1 " " %& # && # ' &&" ##!& # ' [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗

**Figure 5.** Figure 5: Impact of Baseline vs Optimized Algorithm [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗

**Figure 6.** Figure 6: Scaling of discriminating inputs and solver time with circuit complexity for Models A and B. Each panel shows data [PITH_FULL_IMAGE:figures/full_fig_p011_6.png] view at source ↗

**Figure 7.** Figure 7: Comparing 8-bits Point Functions with Circuits [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper shows topology leakage in gate-hiding garbled circuits can be turned into a practical SAT-based gate recovery attack, with simplifications and decomposition that beat a baseline on benchmarks.

read the letter

The core result is that public circuit topology gives an attacker enough structure to recover hidden gate types via SAT solving, and the authors' optimizations make this feasible on real circuits where a direct attack times out. They combine topology-preserving simplification theorems with a decomposition of the global assignment problem into smaller independent SAT queries. This is the new piece relative to earlier garbled-circuit attacks in the literature they cite, and the benchmark numbers on ISCAS circuits plus sensor-fusion examples show clear runtime gains and more completed recoveries inside the 24-hour budget. That empirical side is the paper's strongest contribution: it turns an intentional omission in existing security definitions into a measurable privacy leak. The evaluation uses standard benchmarks and reports concrete improvements, which is the kind of evidence that matters for this subfield. The main soft spot is exactly the one the stress-test flags. The attack's validity rests on the simplification theorems preserving every valid gate assignment without introducing spurious ones, and on the decomposition not dropping constraints that span subcircuits. The abstract describes the method but does not include the theorem proofs or an explicit check that the decomposed queries remain complete. If the full paper supplies those details and verifies them on the evaluated circuits, the results stand; otherwise the reported recoveries could include false solutions or miss some. The SAT encoding itself looks standard, so the risk is contained rather than fatal, but it still needs referee scrutiny. This work is aimed at people who design or analyze secure computation primitives, especially those tightening definitions around function privacy. A reader who cares about concrete attacks on garbled-circuit constructions will find the benchmarks and the attack technique useful. It is worth sending to peer review because it supplies a new attack vector with supporting data, even though the formal claims around the simplifications will probably need tightening or extra verification in revision.

Referee Report

3 major / 2 minor

Summary. The manuscript presents a SAT-based function recovery attack against gate-hiding garbled circuits that exploits public circuit topology. It introduces topology-preserving simplification theorems to prune the gate-type assignment space and decomposes the global SAT problem into smaller independent queries. The attack is evaluated on ISCAS benchmarks, secure-computation circuits, and fault-tolerant sensor-fusion circuits under a 24-hour recovery budget, where the optimized version recovers hidden gate functions faster than a baseline and succeeds on instances where the baseline times out.

Significance. If the simplification theorems and decomposition are sound, the work supplies concrete evidence that topology leakage can materially aid recovery of hidden gate functionality. This identifies topology as a security-relevant leakage channel in gate-hiding garbled circuits and supplies an empirical basis for re-examining security definitions of semi-private function evaluation that currently exclude topology from the leakage model.

major comments (3)

[Simplification theorems (abstract and § on attack construction)] The topology-preserving simplification theorems are load-bearing for the claim that recovered assignments are valid. The manuscript states that the theorems reduce the candidate space while preserving all valid gate-type assignments, yet provides neither a formal proof nor an exhaustive argument that no false solutions are introduced and no valid assignments are eliminated. Without this, the reported recoveries on the benchmark circuits cannot be guaranteed to be correct.
[SAT decomposition (abstract and experimental setup)] The decomposition of the recovery task into independent smaller SAT queries is presented as preserving completeness. It is unclear whether cross-subcircuit constraints are fully retained; if any global constraint is lost, the attack could miss valid assignments or report spurious ones. A concrete completeness argument or verification procedure for the decomposition is required.
[Evaluation section and tables] The experimental results compare recovery times against a baseline but omit error bars, number of independent runs, or statistical tests. This weakens the claim that the optimized attack 'substantially reduces recovery time' and 'completes recovery within the evaluation budget where the baseline does not.'

minor comments (2)

[Abstract] The abstract refers to 'two attacker knowledge models' without defining them; these should be stated explicitly in the introduction.
[Evaluation tables] Tables reporting recovery results should include success rate (fraction of gates recovered) in addition to wall-clock time to allow readers to assess partial versus complete recoveries.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough review and constructive comments. We address each major comment below and have made revisions to strengthen the manuscript accordingly.

read point-by-point responses

Referee: [Simplification theorems (abstract and § on attack construction)] The topology-preserving simplification theorems are load-bearing for the claim that recovered assignments are valid. The manuscript states that the theorems reduce the candidate space while preserving all valid gate-type assignments, yet provides neither a formal proof nor an exhaustive argument that no false solutions are introduced and no valid assignments are eliminated. Without this, the reported recoveries on the benchmark circuits cannot be guaranteed to be correct.

Authors: We agree that a formal proof is necessary to rigorously establish the soundness of the simplification theorems. In the revised manuscript, we will include a detailed formal proof demonstrating that the theorems preserve all valid gate-type assignments and do not introduce any invalid ones. The proof proceeds by induction on the circuit structure, showing that each simplification rule maintains equivalence with respect to the possible gate functionalities consistent with the topology. revision: yes
Referee: [SAT decomposition (abstract and experimental setup)] The decomposition of the recovery task into independent smaller SAT queries is presented as preserving completeness. It is unclear whether cross-subcircuit constraints are fully retained; if any global constraint is lost, the attack could miss valid assignments or report spurious ones. A concrete completeness argument or verification procedure for the decomposition is required.

Authors: We appreciate this observation. The decomposition is designed such that subcircuits are chosen to be independent with respect to gate-type constraints, with all inter-subcircuit dependencies explicitly encoded as additional clauses in the SAT instances. In the revision, we will add a formal completeness argument explaining how the global constraints are preserved through the choice of decomposition points and the inclusion of boundary constraints. Additionally, we will describe a verification procedure that checks the consistency of solutions across subproblems. revision: yes
Referee: [Evaluation section and tables] The experimental results compare recovery times against a baseline but omit error bars, number of independent runs, or statistical tests. This weakens the claim that the optimized attack 'substantially reduces recovery time' and 'completes recovery within the evaluation budget where the baseline does not.'

Authors: We acknowledge that the current presentation lacks statistical rigor. The experiments were conducted as single runs due to the computational intensity and the 24-hour time budget per instance. However, for the revised version, we will perform multiple independent runs on the smaller benchmark circuits where feasible, include error bars to show variability, and apply appropriate statistical tests to support the claims of performance improvement. For the larger instances, we will note the deterministic aspects of the SAT solver configuration used. revision: partial

Circularity Check

0 steps flagged

No circularity in derivation chain

full rationale

The paper describes an empirical SAT-based recovery attack that applies topology-preserving simplification theorems and decomposes the problem into smaller queries. No quoted step reduces a claimed prediction or result to a fitted parameter, self-definition, or self-citation chain by construction; the theorems and decomposition are presented as independent techniques whose soundness is assumed rather than derived from the attack outputs themselves. Evaluation on external ISCAS and other benchmarks supplies falsifiable evidence outside any internal fit, keeping the central claim self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard cryptographic assumptions about garbled circuits and the correctness of off-the-shelf SAT solvers; no new free parameters, axioms beyond domain standards, or invented entities are introduced.

axioms (1)

domain assumption Existing security definitions for SPFE intentionally exclude topology leakage
Invoked in the abstract to motivate the attack.

pith-pipeline@v0.9.0 · 5495 in / 1030 out tokens · 48511 ms · 2026-05-16T13:08:53.651190+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

[1]

Mohamed El Massad, Siddharth Garg, and Mahesh V Tripunitara. 2015. Inte- grated circuit (IC) decamouflaging: Reverse engineering camouflaged ICs within minutes.. InNDSS. 1–14

work page 2015
[2]

Daniel Günther, Ágnes Kiss, Lukas Scheidel, and Thomas Schneider. 2019. Poster: Framework for semi-private function evaluation with application to se- cure insurance rate calculation. InProceedings of the 2019 ACM SIGSAC Confer- ence on Computer and Communications Security . 2541–2543

work page 2019
[3]

Daniel Günther, Joachim Schmidt, Thomas Schneider, and Hossein Yalame. 2024. FLUENT: A Tool for Efficient Mixed-Protocol Semi-Private Function Evaluation. Cryptology ePrint Archive (2024)

work page 2024
[4]

Chenglu Jin, Chao Yin, Marten van Dijk, Sisi Duan, Fabio Massacci, Michael K Reiter, and Haibin Zhang. 2024. PG: Byzantine Fault-Tolerant and Privacy- Preserving Sensor Fusion With Guaranteed Output Delivery. InProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security . 3272–3286

work page 2024
[5]

Jonathan Katz and Lior Malka. 2011. Constant-round private function evaluation with linear complexity. InInternational Conference on the Theory and Application of Cryptology and Information Security . Springer, 556–571

work page 2011
[6]

Carmen Kempka, Ryo Kikuchi, and Koutarou Suzuki. 2016. How to circum- vent the two-ciphertext lower bound for linear garbling schemes. InAdvances in Cryptology–ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part II 22 . Springer, 967–997

work page 2016
[7]

Vladimir Kolesnikov. 2018. Free IF: How to omit inactive branches and imple- ment S-universal garbled circuit (almost) for free. InInternational Conference on the Theory and Application of Cryptology and Information Security . Springer, 34–58

work page 2018
[8]

Vladimir Kolesnikov and Thomas Schneider. 2008. A practical universal circuit construction and secure evaluation of private functions. InFinancial Cryptogra- phy and Data Security: 12th International Conference, FC 2008, Cozumel, Mexico, January 28-31, 2008. Revised Selected Papers 12 . Springer, 83–97

work page 2008
[9]

Ruixiao Li and Hayato Yamana. 2024. Non-interactive Private Multivariate Func- tion Evaluation using Homomorphic Table Lookup.IACR Communications in Cryptology 1, 3 (2024)

work page 2024
[10]

Ruixiao Li and Hayato Yamana. 2024. Privacy Preserving Function Evaluation Using Lookup Tables with Word-Wise FHE.IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 107, 8 (2024), 1163–1177

work page 2024
[11]

Ke Lin. 2023. Skipping Scheme for Gate-hiding Garbled Circuits.arXiv preprint arXiv:2312.02514 (2023)

work page arXiv 2023
[12]

Fabio Massacci and Laura Marraro. 2000. Logical cryptanalysis as a SAT problem. Journal of Automated Reasoning 24 (2000), 165–203

work page 2000
[13]

Payman Mohassel and Saeed Sadeghian. 2013. How to hide circuits in MPC an efficient framework for private function evaluation. InAnnual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 557–574

work page 2013
[14]

Annika Paus, Ahmad-Reza Sadeghi, and Thomas Schneider. 2009. Practical se- cure evaluation of semi-private functions. InApplied Cryptography and Network Security: 7th International Conference, ACNS 2009, Paris-Rocquencourt, France, June 2-5, 2009. Proceedings 7 . Springer, 89–106

work page 2009
[15]

Jeyavijayan Rajendran, Michael Sam, Ozgur Sinanoglu, and Ramesh Karri. 2013. Security analysis of integrated circuit camouflaging. InProceedings of the 2013 ACM SIGSAC conference on Computer & communications security . 709–720

work page 2013
[16]

Mike Rosulek. 2017. Improvements for gate-hiding garbled circuits. InProgress in Cryptology–INDOCRYPT 2017: 18th International Conference on Cryptology in India, Chennai, India, December 10-13, 2017, Proceedings 18 . Springer, 325–345

work page 2017
[17]

Mike Rosulek and Lawrence Roy. 2021. Three halves make a whole? Beating the half-gates lower bound for garbled circuits. InAnnual International Cryptology Conference. Springer, 94–124

work page 2021
[18]

Hao Shen et al. 2025. Bootstrapping in approximate fully homomorphic encryp- tion: a research survey.Cybersecurity (2025). doi:10.1186/s42400-025-00384-3

work page doi:10.1186/s42400-025-00384-3 2025
[19]

Yuanqi Shen, Amin Rezaei, and Hai Zhou. 2018. SAT-based bit-flipping attack on logic encryptions. In2018 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 629–632

work page 2018
[20]

Pramod Subramanyan, Sayak Ray, and Sharad Malik. 2015. Evaluating the se- curity of logic encryption algorithms. In2015 IEEE International Symposium on Hardware Oriented Security and Trust (HOST) . IEEE, 137–143

work page 2015
[21]

Yongge Wang and Qutaibah M Malluhi. 2024. Reducing garbled circuit size while preserving circuit gate privacy. InInternational Conference on Cryptology in Africa. Springer, 149–173

work page 2024
[22]

Yang Xie and Ankur Srivastava. 2016. Mitigating SAT attack on logic locking. In Cryptographic Hardware and Embedded Systems–CHES 2016: 18th International Conference, Santa Barbara, CA, USA, August 17-19, 2016, Proceedings 18. Springer, 127–146

work page 2016
[23]

Xiaolin Xu, Bicky Shakya, Mark M Tehranipoor, and Domenic Forte. 2017. Novel bypass attack and BDD-based tradeoff analysis against all known logic locking attacks. InCryptographic Hardware and Embedded Systems–CHES 2017: 19th International Conference, Taipei, Taiwan, September 25-28, 2017, Proceedings . Springer, 189–210

work page 2017
[24]

Muhammad Yasin, Bodhisatwa Mazumdar, Jeyavijayan JV Rajendran, and Ozgur Sinanoglu. 2016. SARLock: SAT attack resistant logic locking. In2016 IEEE In- ternational Symposium on Hardware Oriented Security and Trust (HOST) . IEEE, 236–241

work page 2016
[25]

Cunxi Yu, Xiangyu Zhang, Duo Liu, Maciej Ciesielski, and Daniel Holcomb. 2017. Incremental SAT-based reverse engineering of camouflaged logic circuits.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 36, 10 (2017), 1647–1659

work page 2017
[26]

Mingfei Yu and Giovanni De Micheli. 2026. Faster Homomorphic Operations and Beyond: Expediting Homomorphic Computation via Boolean Circuit Opti- mization: M. Yu, G. De Micheli.Journal of Cryptology 39, 1 (2026), 6

work page 2026
[27]

Shuoyao Zhao, Yu Yu, Hanlin Liu, Jiang Zhang, Wenling Liu, and Zhenkai Hu

work page
[28]

IEEE Transactions on Dependable and Secure Computing (2024)

Improving the Efficiency of Private Function Evaluation Via Optimized Universal Circuits. IEEE Transactions on Dependable and Secure Computing (2024)

work page 2024
[29]

Hai Zhou, Ruifeng Jiang, and Shuyu Kong. 2017. CycSAT: SAT-based at- tack on cyclic logic encryptions. In2017 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). IEEE, 49–56

work page 2017
[30]

Haoyun Zhu, Takuya Suzuki, and Hayato Yamana. 2025. Private Function Evalu- ation using CKKS-based Homomorphic Encrypted LookUp Tables. In2025 22nd Annual International Conference on Privacy, Security, and Trust (PST). IEEE, 1–10. A Proofs We first define a set of special type set operators which will facili- tate the following proofs of Theorem4.1 and4.5...

work page 2025

[1] [1]

Mohamed El Massad, Siddharth Garg, and Mahesh V Tripunitara. 2015. Inte- grated circuit (IC) decamouflaging: Reverse engineering camouflaged ICs within minutes.. InNDSS. 1–14

work page 2015

[2] [2]

Daniel Günther, Ágnes Kiss, Lukas Scheidel, and Thomas Schneider. 2019. Poster: Framework for semi-private function evaluation with application to se- cure insurance rate calculation. InProceedings of the 2019 ACM SIGSAC Confer- ence on Computer and Communications Security . 2541–2543

work page 2019

[3] [3]

Daniel Günther, Joachim Schmidt, Thomas Schneider, and Hossein Yalame. 2024. FLUENT: A Tool for Efficient Mixed-Protocol Semi-Private Function Evaluation. Cryptology ePrint Archive (2024)

work page 2024

[4] [4]

Chenglu Jin, Chao Yin, Marten van Dijk, Sisi Duan, Fabio Massacci, Michael K Reiter, and Haibin Zhang. 2024. PG: Byzantine Fault-Tolerant and Privacy- Preserving Sensor Fusion With Guaranteed Output Delivery. InProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security . 3272–3286

work page 2024

[5] [5]

Jonathan Katz and Lior Malka. 2011. Constant-round private function evaluation with linear complexity. InInternational Conference on the Theory and Application of Cryptology and Information Security . Springer, 556–571

work page 2011

[6] [6]

Carmen Kempka, Ryo Kikuchi, and Koutarou Suzuki. 2016. How to circum- vent the two-ciphertext lower bound for linear garbling schemes. InAdvances in Cryptology–ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part II 22 . Springer, 967–997

work page 2016

[7] [7]

Vladimir Kolesnikov. 2018. Free IF: How to omit inactive branches and imple- ment S-universal garbled circuit (almost) for free. InInternational Conference on the Theory and Application of Cryptology and Information Security . Springer, 34–58

work page 2018

[8] [8]

Vladimir Kolesnikov and Thomas Schneider. 2008. A practical universal circuit construction and secure evaluation of private functions. InFinancial Cryptogra- phy and Data Security: 12th International Conference, FC 2008, Cozumel, Mexico, January 28-31, 2008. Revised Selected Papers 12 . Springer, 83–97

work page 2008

[9] [9]

Ruixiao Li and Hayato Yamana. 2024. Non-interactive Private Multivariate Func- tion Evaluation using Homomorphic Table Lookup.IACR Communications in Cryptology 1, 3 (2024)

work page 2024

[10] [10]

Ruixiao Li and Hayato Yamana. 2024. Privacy Preserving Function Evaluation Using Lookup Tables with Word-Wise FHE.IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 107, 8 (2024), 1163–1177

work page 2024

[11] [11]

Ke Lin. 2023. Skipping Scheme for Gate-hiding Garbled Circuits.arXiv preprint arXiv:2312.02514 (2023)

work page arXiv 2023

[12] [12]

Fabio Massacci and Laura Marraro. 2000. Logical cryptanalysis as a SAT problem. Journal of Automated Reasoning 24 (2000), 165–203

work page 2000

[13] [13]

Payman Mohassel and Saeed Sadeghian. 2013. How to hide circuits in MPC an efficient framework for private function evaluation. InAnnual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 557–574

work page 2013

[14] [14]

Annika Paus, Ahmad-Reza Sadeghi, and Thomas Schneider. 2009. Practical se- cure evaluation of semi-private functions. InApplied Cryptography and Network Security: 7th International Conference, ACNS 2009, Paris-Rocquencourt, France, June 2-5, 2009. Proceedings 7 . Springer, 89–106

work page 2009

[15] [15]

Jeyavijayan Rajendran, Michael Sam, Ozgur Sinanoglu, and Ramesh Karri. 2013. Security analysis of integrated circuit camouflaging. InProceedings of the 2013 ACM SIGSAC conference on Computer & communications security . 709–720

work page 2013

[16] [16]

Mike Rosulek. 2017. Improvements for gate-hiding garbled circuits. InProgress in Cryptology–INDOCRYPT 2017: 18th International Conference on Cryptology in India, Chennai, India, December 10-13, 2017, Proceedings 18 . Springer, 325–345

work page 2017

[17] [17]

Mike Rosulek and Lawrence Roy. 2021. Three halves make a whole? Beating the half-gates lower bound for garbled circuits. InAnnual International Cryptology Conference. Springer, 94–124

work page 2021

[18] [18]

Hao Shen et al. 2025. Bootstrapping in approximate fully homomorphic encryp- tion: a research survey.Cybersecurity (2025). doi:10.1186/s42400-025-00384-3

work page doi:10.1186/s42400-025-00384-3 2025

[19] [19]

Yuanqi Shen, Amin Rezaei, and Hai Zhou. 2018. SAT-based bit-flipping attack on logic encryptions. In2018 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 629–632

work page 2018

[20] [20]

Pramod Subramanyan, Sayak Ray, and Sharad Malik. 2015. Evaluating the se- curity of logic encryption algorithms. In2015 IEEE International Symposium on Hardware Oriented Security and Trust (HOST) . IEEE, 137–143

work page 2015

[21] [21]

Yongge Wang and Qutaibah M Malluhi. 2024. Reducing garbled circuit size while preserving circuit gate privacy. InInternational Conference on Cryptology in Africa. Springer, 149–173

work page 2024

[22] [22]

Yang Xie and Ankur Srivastava. 2016. Mitigating SAT attack on logic locking. In Cryptographic Hardware and Embedded Systems–CHES 2016: 18th International Conference, Santa Barbara, CA, USA, August 17-19, 2016, Proceedings 18. Springer, 127–146

work page 2016

[23] [23]

Xiaolin Xu, Bicky Shakya, Mark M Tehranipoor, and Domenic Forte. 2017. Novel bypass attack and BDD-based tradeoff analysis against all known logic locking attacks. InCryptographic Hardware and Embedded Systems–CHES 2017: 19th International Conference, Taipei, Taiwan, September 25-28, 2017, Proceedings . Springer, 189–210

work page 2017

[24] [24]

Muhammad Yasin, Bodhisatwa Mazumdar, Jeyavijayan JV Rajendran, and Ozgur Sinanoglu. 2016. SARLock: SAT attack resistant logic locking. In2016 IEEE In- ternational Symposium on Hardware Oriented Security and Trust (HOST) . IEEE, 236–241

work page 2016

[25] [25]

Cunxi Yu, Xiangyu Zhang, Duo Liu, Maciej Ciesielski, and Daniel Holcomb. 2017. Incremental SAT-based reverse engineering of camouflaged logic circuits.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 36, 10 (2017), 1647–1659

work page 2017

[26] [26]

Mingfei Yu and Giovanni De Micheli. 2026. Faster Homomorphic Operations and Beyond: Expediting Homomorphic Computation via Boolean Circuit Opti- mization: M. Yu, G. De Micheli.Journal of Cryptology 39, 1 (2026), 6

work page 2026

[27] [27]

Shuoyao Zhao, Yu Yu, Hanlin Liu, Jiang Zhang, Wenling Liu, and Zhenkai Hu

work page

[28] [28]

IEEE Transactions on Dependable and Secure Computing (2024)

Improving the Efficiency of Private Function Evaluation Via Optimized Universal Circuits. IEEE Transactions on Dependable and Secure Computing (2024)

work page 2024

[29] [29]

Hai Zhou, Ruifeng Jiang, and Shuyu Kong. 2017. CycSAT: SAT-based at- tack on cyclic logic encryptions. In2017 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). IEEE, 49–56

work page 2017

[30] [30]

Haoyun Zhu, Takuya Suzuki, and Hayato Yamana. 2025. Private Function Evalu- ation using CKKS-based Homomorphic Encrypted LookUp Tables. In2025 22nd Annual International Conference on Privacy, Security, and Trust (PST). IEEE, 1–10. A Proofs We first define a set of special type set operators which will facili- tate the following proofs of Theorem4.1 and4.5...

work page 2025