Skip to main content
23 votes
Accepted

What exactly is bootstrapping in FHE?

First off, from your question, it is not clear whether or not you understand the "circuit" part. So I'll start there. With (most) FHE schemes, you are evaluating circuits, or a bunch of gates hooked ...
mikeazo's user avatar
  • 38.7k
17 votes
Accepted

Noise in Homomorphic encryption

The noise is usually a small term added into the ciphertext while encrypting. This term may be a small integer (if the scheme is based on integers) or a small polynomial (if the scheme is based on ...
Hilder Vitor Lima Pereira's user avatar
15 votes

Chinese Remainder Theorem and RSA

What really helped me understand RSA-CRT was Section 3 of Johann Großschädl: "The Chinese Remainder Theorem and its Application in a High-Speed RSA Crypto Chip" [1]. What follows is a summary of that ...
Cédric Van Rompay's user avatar
15 votes
Accepted

Representing a function as FHE circuit

The circuit term in the evaluation of functions with FHE is a coming from Electronics. In the notion of FHE circuit, we have almost the same problem; build a circuit of a function $f$ with available ...
kelalaka's user avatar
  • 48.9k
14 votes
Accepted

What is the link, if any, between Zero Knowledge Proof (ZKP) and Homomorphic encryption?

There are many. Homomorphic encryption implies ZK proofs for NP. This is simply because homomorphic encryption implies one-way functions, which imply ZKP for NP. Homomorphic encryption allows to ...
Geoffroy Couteau's user avatar
12 votes
Accepted

How is Homomorphic Encryption secure (over integers)?

The use case for homomorphic encryption is that I encrypt my own data with my public key. I then ship this data to the cloud. The cloud can perform operations on those ciphertexts. But, since the ...
mikeazo's user avatar
  • 38.7k
12 votes
Accepted

Can Fully Homomorphic Encryption do comparisons?

This is simply not true. The above function can perfectly be homomorphically computed on FHE ciphertexts encrypting the inputs. There is no such "obvious limitation", and I wonder where your certainty ...
Geoffroy Couteau's user avatar
12 votes
Accepted

Is there a way of maintaining malleability in a homomorphic encryption system while making it infeasible to perform chosen ciphertext attacks?

I know of two lines of work on this question. It is indeed possible to allow malleability but still make some guarantees in the presence of a chosen-ciphertext attack: Manoj Prabhakaran & Mike ...
Mikero's user avatar
  • 13.5k
12 votes
Accepted

Homomorphic encryption - Why does addition not imply multiplication?

There are at least two problems; The $b$-times addition leaks the $b$. A semi-honest observer can see that you add the $a$ by $b$ times. However, in FHE, the $b$ is also encrypted with semantically ...
kelalaka's user avatar
  • 48.9k
11 votes
Accepted

Beavers Triple Vs BGW Multiplication on MPC

Yes, preprocessing Beaver triples in an offline phase leads to a faster online phase. The online phase of an AND gate requires just two openings plus local computations. But there are other ...
Mikero's user avatar
  • 13.5k
11 votes
Accepted

Somewhat Homomorphic Encryption versus Fully Homomorphic Encryption?

PHE (partially homomorphic encryption) schemes are in general more efficient than SHE and FHE, mainly because they are homomorphic w.r.t to only one type of operation: addition or multiplication. SHE ...
Dragos's user avatar
  • 656
11 votes
Accepted

Obfuscating functions that are mostly zero

I provide a summary below of what is currently known (to my knowledge) regarding obfuscation of various class of "mostly-zero" functions. From Indistinguishability Obfuscation What we can obfuscate: ...
Geoffroy Couteau's user avatar
10 votes
Accepted

Difference between somewhat homomorphic encryption and leveled homomorphic encryption?

Let $\mathcal{C}$ be the set of allowed binary circuits. Then, a $\mathcal{C}$-evaluation scheme $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Eval}, \mathsf{Dec})$ that has (i) correct decryption and (ii) ...
CAR's user avatar
  • 116
10 votes
Accepted

"Power of one" as input to functions of a cryptosystem

The notation $1^\lambda$ means a string with $\lambda$ characters all of them equal to 1. For instance, if $\lambda = 3$, then $1^\lambda$ is $111$. And yes, it typically stands to the security ...
Hilder Vitor Lima Pereira's user avatar
10 votes
Accepted

FHE: What is the difference between multiplicative depth and multiplicative level?

In Fully Homomorphic Encryption (in short FHE), we have a noise that increased with every operation, and it is almost doubled with the multiplication. When preparing the circuit $\mathcal{C}$ to $\...
kelalaka's user avatar
  • 48.9k
9 votes
Accepted

What is the purpose of Homomorphic encryption?

In addition to the other answers: A secure secret-key homomorphic encryption scheme can be used to create a public-key encryption scheme. If we consider encryption to be control of read and write ...
Ella Rose's user avatar
  • 19.7k
9 votes
Accepted

What is modulo switching, in a nutshell?

The basic idea: In homomorphic encryption schemes, the ciphertexts are noisy and we want to refrain the noise from growing too fast as we operate homomorphically. So the idea here is to multiply a ...
Hilder Vitor Lima Pereira's user avatar
9 votes
Accepted

Advantages of Paillier vs Goldwasser-Micali

They're both additively homomorphic, but over different groups. With Goldwasser-Micali, you can, given $E(x)$ and $E(y)$, compute $E(x \oplus y)$ (where $\oplus$ is exclusive or) With Pallier, you ...
poncho's user avatar
  • 148k
8 votes

Practical multivariate quadratic FHE – how does it compare to other FHEs?

I've spoken to the CEO a couple times. They've contracted some prominent French cryptographers to vet their cryptosystem, but no security analysis or whitepaper has been released. Their KFHE scheme ...
pg1989's user avatar
  • 4,646
8 votes
Accepted

Difference between a circuit and a normal function

A circuit is a representation of a (computable) function. There are many other ways to represent a function (mathematical notation, Turing machines, pseudo-code, etc.), but for some purposes it ...
fkraiem's user avatar
  • 8,152
8 votes
Accepted

Paillier encryption: Many private keys for a public key

No, that doesn't work. If one party chooses primes $p,q$ and sets $n = pq$, then other parties would also have to know $p$ and $q$, because it is the only way to get the same $n$. But you just left ...
tylo's user avatar
  • 12.7k
8 votes
Accepted

How can fully homomorphic encryption ever be secure?

Interpreting the question Firstly, I should state that I interpreted "Since this is a FHE scheme that allows arbitrary computation, the cloud service builds a full-text search function on the ...
Ella Rose's user avatar
  • 19.7k
8 votes

Isn't fully homomorphic encryption trivial with a complex enough decryption function?

No, this is not considered homomorphic encryption. This is excluded by requiring that the ciphertext size and running time of the decryption operation be bounded by the security parameter, ...
Squeamish Ossifrage's user avatar
8 votes
Accepted

Why is Approximate GCD a hard problem?

TL;DR The AGCD problem does require asymptotic exponential time to be solved. In general, LLL cannot solve the AGCD problem The parameters $(\gamma, \eta, \rho) = (\lambda^5, \lambda^2, \lambda)$ ...
Hilder Vitor Lima Pereira's user avatar
8 votes
Accepted

Why is the Domingo-Ferrer cryptosystem not used in practice?

TLDR: The scheme is symmetric only, its "provable security" argument is flawed, and it is practically insecure when even a modest amount of plaintext is available to attackers. I'm commenting on the ...
fgrieu's user avatar
  • 142k
7 votes
Accepted

Equality checking using additive homomorphic encryption

I'm not sure if I understand what you are asking, so I'll clarify what I am about to answer. We are given two ciphertexts and we want to know if they encrypt the same plaintext or if they encrypt ...
Yehuda Lindell's user avatar
7 votes

Are Paillier and El Gamal encryption schemes secure against quantum attacks?

Sure there's a difference between Paillier and ElGamal as opposed to lattice-based cryptography regarding quantum attackers. Paillier's security is broken as soon as you can efficiently factor large ...
SEJPM's user avatar
  • 46.1k
7 votes
Accepted

SEAL Homomorphic multiplication

In this answer, I am reducing using that centered representation of $\mathbb{Z}_q$ and $\mathbb{Z}_w$. Also, I am writing $\ell$ instead of $l_{w,q}$ to simplify the notation. Concrete examples: $...
Hilder Vitor Lima Pereira's user avatar
7 votes
Accepted

SPDZ for the 2-party case

Your understanding is correct. The SPDZ protocol can be used for any number of two or more parties. In fact, this is one of the strengths of the SPDZ protocol. Namely, many recent secure computation ...
Guut Boy's user avatar
  • 2,877
7 votes

FHE Bootstrapping vs. Relinearization

Bootstrapping is the procedure that refreshs a ciphertext by running the decryption function homomorphically. By refresh you should think in something like decrypting and encrypting again, so the ...
Hilder Vitor Lima Pereira's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible