I was reading this paper https://eprint.iacr.org/2014/816.pdf "Bootstratpping in less than one second" but I didn't understand it throughly. What's the point to build a cheap NAND gate ? Maybe to build cheaper AND and OR gates based on this NAND gate and then follow the approach of Regev's type cryptosystems? Or maybe to use the technique from this paper and build your own cheap AND and OR gates ?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ The main point of the paper is to show that bootstrapping per se doesn't require the high latency (at least few minutes for a packed ciphertext) seen in all implementations before, therefore giving hope that other systems might become more practical, too. By the way, Gentry-Halevi ([17] in the paper you linked) still needed 1/2 hour for bootstrapping a single bit in 2011. $\endgroup$– j.p.Oct 29, 2015 at 11:18
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
What's the point to build a cheap NAND gate ?
Because it's a complete operation; you can build any circuit with a sufficiently large pile of them.
Maybe to build cheaper AND and OR gates based on this NAND gate and then follow the approach of Regev's type cryptosystems?
You could build AND and OR gates with them (and INVERT; AND and OR by themselves are not complete); however you'd probably be better off designing the larger circuits directly with the NAND gates.
