Covert Computation
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.
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.
