Difference between revisions of "Covert Computation"
(Created page with "Category:Self-assembly ==Overview== Typically, algorithmic self-assembly leaves behind a permanent record of every step of the computation in the form of a final assembly....") |
|||
| Line 4: | Line 4: | ||
==Covert Circuits== | ==Covert Circuits== | ||
| − | In order to conceal computational steps, the authors design logic gates in the aTAM that, after propagating their output signal, "backfill"<ref name=cantu2019covert/>. 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 <i>true</i> input, it will output <i>false</i> to the next logical component. When the NOT gate backfills, the unused <i>true</i> output will begin to fill in all the way through to the <i>false</i> input. Below is their construction of the NOT gate and its two potential assembly paths. | + | In order to conceal computational steps, the authors design logic gates in the aTAM that, after propagating their output signal, "backfill"<ref name=cantu2019covert/>. 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 <i>true</i> input, it will output <i>false</i> to the next logical component. When the NOT gate backfills, the unused <i>true</i> output will begin to fill in all the way through to the <i>false</i> 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. |
[[File:Simple-NOT-Gate.png|250px|thumb|center|A simple covert NOT gate; Figure 5a from <ref name=cantu2019covert/>]] | [[File:Simple-NOT-Gate.png|250px|thumb|center|A simple covert NOT gate; Figure 5a 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/>]] | [[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. | ||
==Results== | ==Results== | ||
Revision as of 12:41, 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.
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.
