FHE Basic

Homomorphic encryption (HE) is a method of encryption that allows computations to be carried out on encrypted data, generating an encrypted result which, when decrypted, matches the outcome of computations performed on the plaintext. This property enables sophisticated computations on encrypted data while maintaining data security. HE schemes are a type of encryption method that can protect data privacy because they allow computations to be performed directly on the encrypted data. For example, an HE scheme might allow a user to perform operations like addition and multiplication on encrypted numbers, and these operations would have the same result as if they were performed on the original, unencrypted numbers. This technology is seen as a key component for secure cloud computing since it allows complex data manipulations to be carried out on completely secure encrypted data.

Fully Homomorphic Encryption (FHE) is a more advanced form of Homomorphic Encryption. FHE allows arbitrary computations to be carried out on encrypted data, which is not the case with normal HE that might be limited in the types of computation it supports. FHE computations generate a result that, when decrypted, corresponds to the result of the same computations performed on the plaintext. This makes FHE extremely useful for cases where sensitive data must be processed or analyzed, but security and privacy considerations prevent the data from being decrypted. With FHE, you can perform unlimited calculations on this encrypted data just like you would on unencrypted data. For instance, in the field of cloud computing, FHE allows users to operate computations on encrypted data stored in the cloud, preserving data confidentiality and privacy.

We present here a few popular FHE schemes.

BGV (Brakerski-Gentry-Vaikuntanathan):

The BGV scheme is a Fully Homomorphic Encryption (FHE) method, proposed by Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. It offers a choice of FHE schemes based on the learning with error (LWE) or ring-LWE problems that have substantial security against known attacks. BGV allows the encryption of a single bit at a time and the efficiency of the encryption is largely considered in cloud storage models.

BFV (Brakerski/Fan-Vercauteren):

BFV is another homomorphic encryption scheme that is often considered for its practical performance alongside the BGV scheme. BFV supports a set of mathematical operations such as addition and multiplication to be performed directly on the encrypted data. It has been implemented efficiently and there have also been several optimizations proposed to enhance its performance in different applications.

The Brakerski-Gentry-Vaikuntanathan (BGV) and Brakerski/Fan-Vercauteren (BFV) schemes differ mainly in how they encode information. BGV encodes messages in the least significant digit (LSD) of the integer, while BFV encodes messages in the most significant digit (MSD) of the integer. This difference can affect how the encrypted data is handled and manipulated during computations.

Verisense utilizes the BFV scheme for its FHE functionalities.

CKKS (Cheon-Kim-Kim-Song):

The CKKS scheme is known for being a Leveled Homomorphic Encryption method that supports approximate arithmetic operations over encrypted data. The CKKS scheme is especially suitable for computations involving real or complex numbers. Its ability to perform operations on encrypted data without the necessity for decryption makes it highly useful for maintaining data security during computations.

The Cheon-Kim-Kim-Song (CKKS) scheme is particularly useful in the field of Artificial Intelligence (AI), largely due to its ability to handle computations with real or complex numbers - including floating-point numbers. In many AI applications, computations involve floating-point numbers. Especially in machine learning and deep learning scenarios, data is represented as floating-point numbers, and neural networks operate over these numbers. The CKKS scheme allows these computations to be carried out on encrypted data, thus providing a privacy-preserving solution for AI applications. Its capabilities make it a significant tool for implementing machine learning algorithms that can operate directly on encrypted data, which is critical for situations where the privacy of the data is paramount.

The encryption process of BFV can be described as \[ \mathbf{a}\cdot \mathbf{s} +\Delta m +\mathbf{e} \] where \(\mathbf{a}\) is a uniformly random polynomial ring element: \(\mathbf{a}\in R_Q\), \( R_Q=(\mathbb{Z}/Q\mathbb{Z})[X]/(X^N+1)\). Similarly, \(\mathbf{s}\) is secret key and \(\mathbf{e}\) is a Gaussian distributed noise: \(\mathbf{s}\in R,\mathbf{e}\in R\). \(\mathbf{m}\) is the message \(\mathbf{m}\in R_t\), \(\Delta\) is the scaling factor \(\Delta = \lfloor Q/t\rfloor\). The choice of \( t \) is often a balancing act between these two constraints. On one hand, we want \(t\) to be large enough so that the encrypted data remains secure (that is, the noise isn't so small that it makes the encryption scheme vulnerable), but on the other hand, we want \( t \) to be small enough so that the noise after homomorphic computations( especially for homomorphic multiplication) does not lead to inaccuracies in the decrypted results. Thus, the selection of \( t \) often depends on the specific application, the security requirements, and the nature of the computations to be performed.

When homomorphic computations (especially multiplications) are performed on the encrypted data (ciphertext), it leads to an increase in the "noise" present in the ciphertext. This increase in the noise can interfere with the decryption process, leading to an inaccurate output. This is where the bootstrapping technique comes into play in Fully Homomorphic Encryption (FHE) systems. Bootstrapping is a unique process designed to "refresh" the ciphertext by reducing this increased noise while still preserving the computed result in an encrypted form. It essentially involves applying the FHE decryption circuit homomorphically to the "noisy" ciphertext to yield a "cleaner" version of it - one that embodies the same output but with significantly reduced noise. In this way, bootstrapping ensures that the resulting ciphertext can be decrypted correctly and accurately, despite the many computations that it underwent. Some Fully Homomorphic Encryption (FHE) schemes, such as FHEW and TFHE - which is used by Zama, don't easily support CRT packing schemes, making it challenging to perform parallel homomorphic computations efficiently. On the brighter side, TFHE offers swift bootstrapping, which aids in managing noise effectively and enhances overall computational efficiency.

Homomorphic operations, such as multiplication, tend to create ciphertexts that are no longer associated with the original linear secret key but some higher-degree variant of the key (for instance, a degree-2 key or squared key after a multiplication operation). This higher degree key form can disrupt further computations and complicate the decryption process. This is where key switching steps in. Key switching is a technique that allows the transformation of the ciphertext from being associated with a higher-degree key back to a simpler form associated with the linear key. This technique ensures that the ciphertext can be either decrypted correctly with the simple secret key or subjected to further homomorphic operations.

Differences between FHE and ZKPs and integration solutions

1. FHE allows arbitrary computations on encrypted data without needing to decrypt it. The results, once decrypted, are the same as if they were performed on the original plaintext data. This makes FHE highly valuable for preserving confidentiality in situations where sensitive data must be analyzed or manipulated. ZKPs, on the other hand, allow one party to prove to another that they know a value or a secret, without conveying any information apart from the truth of the claim. This makes ZKPs essential in contexts where you need to confirm information without revealing it, thereby maintaining privacy.
2. The security of most FHE schemes, including the popular ones like BGV, BFV, and CKKS, is based on the hardness of lattice problems. Lattice-based cryptography is believed to be resistant to attacks from quantum computers, which makes FHE schemes potentially useful for post-quantum cryptography. Their resilience to quantum attacks is due to the fact that no efficient quantum algorithm is known for solving the hard lattice problems that underpin these cryptographic systems. Many ZKPs, including some of the most efficient ones like zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge), rely on the hardness of problems in pairing-based elliptic curve cryptography. These approaches offer powerful privacy-preserving properties and have been used in various cryptographic system constructions. However, it should be noted that these schemes are not necessarily resistant to quantum computing attacks. The security of the elliptic curve depends on the difficulty of the elliptic curve discrete logarithm problem, which can be solved using Shor's algorithm on a sufficiently powerful quantum computer.
3. In many practical scenarios, Fully Homomorphic Encryption (FHE) is used in combination with Zero-Knowledge Proofs (ZKPs) to achieve secure data processing and validation. The reason behind this is that while FHE allows computations on encrypted data without revealing the original data, it does not provide a means of independently verifying the correctness of these computations without access to the secret key. This is where ZKPs come into play. By using ZKPs along with FHE, a system can offer proofs that computations were performed correctly without revealing any sensitive data, including the secret key. This is highly valuable in blockchain or distributed ledger technologies where trustless validation is necessary. For example, when an entity performs computations on encrypted data using their private key, they can generate a ZKP to attest that the computation was performed correctly according to the rules of the specific protocol, without revealing any information about the private key or the original data. When this ZKP is submitted to the network (or 'chain'), other participants can verify the computation's correctness without accessing the encrypted data or the private key. Therefore, the combination of FHE and ZKPs can create a powerful cryptographic toolset capable of both preserving data privacy and ensuring computational integrity, particularly in decentralized environments where trustless verification is required.