I am studying the implementation of FHEW-style cryptosystems (BinFHE), and I have a question about gadgets. I know that they are matrices that define very simple lattices in which discrete (sub)gaussian sampling is done quickly without computing GSOs. To the best of my knowledge, they are injected as trapdoors in public keys (as shown in [MP12]).
Nevertheless, I am missing a key point. For example, in [GMP19], the algorithm for subgaussian digit decomposition (when q = 2^k) samples subgaussian points in the lattice generated by the gadget matrix. Nevertheless, the public key contains the gadget lattice, but it is not the gadget lattice!
So, I guess, that the sampled point should be transformed after the sampling?
In other words, we know how to efficiently sample from {\bf G}, but the public key is (something like) [{\bf A} | {\bf G} - {\bf RA}] (kind of, I suppose?), so it is not {\bf G}…
There are different kinds of using the gadget \mathbf{G}: digit decomposition, subgaussian sampling, discrete Gaussian sampling (for trapdoor sampling). These are all different capabilities, each serving its own purpose. A good high-level introduction to them is given in the Introduction of Building an Efficient Lattice Gadget Toolkit: Subgaussian Sampling and More The question seems to refer to all three of them at the same time: digit decomposition in first paragraph, subgaussian sampling in the second paragraph, and discrete gaussian sampling for trapdoor sampling at the end.
Just one little more question: in order to have a secure reduction in {\sf LWE} we set m=n\log_2(q).
Does it mean that Gadgets different from the bit decomposition, that decompose w.r.t., for example, base 4, would not be secure? In this case we would have m = n \log_4(q), which is smaller than n\log_2(q).
No ,the base does not directly affect the security. It only affects the noise growth during digit decomposition, and, hence, larger parameters may be needed for the same functionality (this may indirectly affect the security because the increased \log q may require increasing the ring/lattice dimension n). These tradeoffs are discussed in the implementation papers I cited, e.g., see the conjunction obfuscation paper.
