Difference between revisions of "Covert Computation"
| Line 9: | Line 9: | ||
[[File:Covert-NOT-Assembly-Examples.png|800px|thumb|center|Example true and false inputs followed by their respective backfilled assembly; Figure 6 from <ref name=cantu2019covert/>]] | [[File:Covert-NOT-Assembly-Examples.png|800px|thumb|center|Example true and false inputs followed by their respective backfilled assembly; Figure 6 from <ref name=cantu2019covert/>]] | ||
| − | Using these covert NOT gates, it is possible to construct covert NAND gates. | + | |
| + | Using these covert NOT gates, it is possible to construct covert NAND gates as shown below. | ||
| + | [[File:Covert-NAND-Block-Diagram.png|650px|thumb|center|High level construction of a covert NAND gate using the previous NOT gate construction; Figure 7a from <ref name=cantu2019covert/>]] | ||
| + | [[File:Covert-NAND.png|650px|thumb|center|Full-detail construction of the covert NAND gate; Figure 7b from <ref name=cantu2019covert/>\]] | ||
| + | |||
==Results== | ==Results== | ||
Revision as of 13:05, 14 June 2022
Contents
Overview
Typically, algorithmic self-assembly leaves behind a permanent record of every step of the computation in the form of a final assembly. Analysis of this mass of tiles allows one to see every operation performed on the input as well as the input itself. In the modern world, sensitive data is rarely handled in this fashion since it would leave information vulnerable to theft by potential attackers. Covert computation in self-assembly should produce the correct output for a given computation while making it impossible to see the path the assembling process took to get there. The authors construct logic gates that satisfy these requirements in the growth-only (tiles are permanent once they attach) negative-glue aTAM[1].
Covert Circuits
In order to conceal computational steps, the authors design logic gates in the aTAM that, after propagating their output signal, "backfill"[1]. Backfilling is the process of using tiles to fill in the unused input/output of the gate. For example, consider the NOT gate. If it receives a true input, it will output false to the next logical component. When the NOT gate backfills, the unused true output will begin to fill in all the way through to the false input. Below is their construction of the NOT gate and its two potential assembly paths. The true signal is generally the upper signal, while the false signal is lower. Solid lines denote strength 2 glues, and their arrows denote the direction of assembly. Blue glues are strength 1, and red glues are of strength -1, meaning they are repulsive.
Using these covert NOT gates, it is possible to construct covert NAND gates as shown below.
Results
The authors prove that their covert constructions can indeed compute any function computable by Boolean circuits by directly simulating Boolean circuits with their covert components [1]. They go on to prove that unique assembly verification in the growth-only negative-glue aTAM is coNP-complete by using their construction and a reduction from Planar Circuit SAT.
