# Question on gadgets sampling **URL:** \ **Category:** FHE Questions\ **Created:** [July 30, 2024, 2:09pm UTC](https://openfhe.discourse.group/t/question-on-gadgets-sampling/1464 "2024-07-30T14:09:54Z")\ **Posts on this page:** 5\ **Page:** 1
**Author:** ![narger](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/narger/32/420_2.png) [@narger](https://openfhe.discourse.group/u/narger)\ **Post date:** [July 30, 2024, 2:09pm UTC](https://openfhe.discourse.group/t/question-on-gadgets-sampling/1464/1 "2024-07-30T14:09:54Z")
Hello everyone, 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]](https://eprint.iacr.org/2018/946), 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}… Thank you in advance for the time!! 🙂 ---
**Author:** ![ypolyakov](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/ypolyakov/32/47_2.png) [@ypolyakov](https://openfhe.discourse.group/u/ypolyakov)\ **Post date:** [August 1, 2024, 3:47am UTC](https://openfhe.discourse.group/t/question-on-gadgets-sampling/1464/2 "2024-08-01T03:47:35Z")
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](https://eprint.iacr.org/2018/946) 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. The cited paper focuses on the first two uses of the gadget. Discrete Gaussian sampling for trapdoor sampling (what your question at the end is about) is described in a different paper: [Faster Gaussian Sampling for Trapdoor Lattices with Arbitrary Modulus](https://eprint.iacr.org/2017/308) A simpler (implementation-focused) explanation is provided in [Implementation and Evaluation of Improved Gaussian Sampling for Lattice Trapdoors](https://eprint.iacr.org/2017/285) and [Implementing Conjunction Obfuscation under Entropic Ring LWE](https://eprint.iacr.org/2017/844) (Section 4). I suggest reading the cited material. It should clarify your confusion. ---
**Author:** ![narger](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/narger/32/420_2.png) [@narger](https://openfhe.discourse.group/u/narger)\ **Post date:** [August 1, 2024, 2:50pm UTC](https://openfhe.discourse.group/t/question-on-gadgets-sampling/1464/3 "2024-08-01T14:50:33Z")
Thank you very much for the references 🙂 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). Thank you for your time 🙂 ---
**Author:** ![ypolyakov](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/ypolyakov/32/47_2.png) [@ypolyakov](https://openfhe.discourse.group/u/ypolyakov)\ **Post date:** [August 1, 2024, 10:32pm UTC](https://openfhe.discourse.group/t/question-on-gadgets-sampling/1464/4 "2024-08-01T22:32:25Z")
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. ---
**Author:** ![narger](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/narger/32/420_2.png) [@narger](https://openfhe.discourse.group/u/narger)\ **Post date:** [August 2, 2024, 12:31pm UTC](https://openfhe.discourse.group/t/question-on-gadgets-sampling/1464/5 "2024-08-02T12:31:11Z")
Got it, thank you very much!!!