# The Gadget Decomposition in FHE

DevFeed: [The Gadget Decomposition in FHE](<https://devfeed.tech/articles/the-gadget-decomposition-in-fhe-40450.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2021/12/11/the-gadget-decomposition-in-fhe/>)

Published: 2021-12-11T13:57:25Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [FHE](<https://devfeed.tech/topics/fhe.md>), [homomorphic encryption](<https://devfeed.tech/topics/homomorphic-encryption.md>), [Cryptography](<https://devfeed.tech/topics/cryptography.md>), [Computing](<https://devfeed.tech/topics/computing.md>), [data](<https://devfeed.tech/topics/data.md>), [Code](<https://devfeed.tech/topics/code.md>), [GitHub](<https://devfeed.tech/topics/github.md>)

Tags: [bootstrapping](<https://devfeed.tech/tags/bootstrapping.md>), [core](<https://devfeed.tech/tags/core.md>), [encryption](<https://devfeed.tech/tags/encryption.md>), [fhe](<https://devfeed.tech/tags/fhe.md>), [gadget-decomposition](<https://devfeed.tech/tags/gadget-decomposition.md>), [group-theory](<https://devfeed.tech/tags/group-theory.md>), [homomorphic-encryption](<https://devfeed.tech/tags/homomorphic-encryption.md>), [learning-with-errors](<https://devfeed.tech/tags/learning-with-errors.md>), [linear-algebra](<https://devfeed.tech/tags/linear-algebra.md>), [lwe](<https://devfeed.tech/tags/lwe.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [matrix](<https://devfeed.tech/tags/matrix.md>), [number-theory](<https://devfeed.tech/tags/number-theory.md>), [operations](<https://devfeed.tech/tags/operations.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>)

## AI overview

A tutorial on gadget decomposition in fully homomorphic encryption (FHE). It explains how GSW and related schemes use random noise, how homomorphic operations increase that noise, why bootstrapping is needed, and how gadget decomposition helps limit noise growth.

## Source excerpt

Lately I've been studying Fully Homomorphic Encryption, which is the miraculous ability to perform arbitrary computations on encrypted data without learning any information about the underlying message. It's the most comprehensive private computing solution that can exist (and it does exist!). The first FHE scheme by Craig Gentry was based on ideal lattices and was considered very complex (I never took the time to learn how it worked). Some later schemes (GSW = Gentry-Sahai-Waters) are based on matrix multiplication, and are conceptually much simpler.