18 votes
Accepted

breaking fully homomorphic encryption schemes

Even though all the operations you described can be performed homomorphically, the result remains encrypted, i.e., the attacker cannot "see" it. So homomorphic computation is not useful (on its own) ...
user avatar
18 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 ...
user avatar
  • 37.7k
16 votes
Accepted

What does "circuits" mean in Cryptography?

Circuits can be expressed using very simple operations. For example, a boolean circuit consists of only two types of gates, addition and multiplication (where the input values are each 1 bit). ...
user avatar
  • 37.7k
16 votes

Why is "semantically secure" important for cryptosystems?

Let me try to answer your second question, and hopefully shed some light on the first one in doing so. When we encrypt a message, it's because we want to keep something about that message secret. ...
user avatar
16 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 ...
user avatar
14 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 ...
user avatar
  • 43.4k
13 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 ...
user avatar
12 votes

difference between leveled FHE and normal FHE scheme

FHE should be able to evaluate any circuit. Leveled FHE can evaluate circuits which have a bounded depth. BGV was, I believe, the first to offer leveled FHE. The gain was in performance. By ...
user avatar
  • 37.7k
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 ...
user avatar
  • 37.7k
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 ...
user avatar
  • 10.6k
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 ...
user avatar
  • 43.4k
11 votes
Accepted

Cipher text only attacks on deterministic fully homomorphic encryption schemes

Yes, your understanding is correct. It is well-known that homomorphic encryption schemes are vulnerable to cipher text attacks if they are deterministic. See, for example, the section 2.4 of the ...
user avatar
11 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 ...
user avatar
11 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 ...
user avatar
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: ...
user avatar
10 votes

Paillier can add and multiply, why is it only partially homomorphic?

It can not do multiplication in the plaintext domain using two ciphertexts. In other words, given $E(m_1)$ and $E(m_2)$, you can not get $E(m_1\cdot m_2)$. You can only get $E(m_1+m_2)$. Given $E(m_1)...
user avatar
  • 37.7k
10 votes
Accepted

What is scale-invariance notion of a fully homomorphic encryption scheme?

While @j.p. is correct that the scale-invariant scheme encodes the plaintext a bit differently than in other FHE schemes, this is mostly just a syntactic point that doesn't really get to the heart of ...
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) ...
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 ...
user avatar
9 votes
Accepted

Can a homomorphic encryption scheme be made CCA2 Secure?

The best you can get for homomorphic encryption schemes is non-adaptive chosen ciphertext security (IND-CCA1 security), see e.g. here for a quite up to date characterization. As you rightly observe ...
user avatar
  • 12.1k
9 votes

garbled circuit vs fully homomorphic encryption

Yes, standard GC are not re-usable, thus by means of GC you may outsource the computation of a single function on a single input (i.e. you delegate a function described by a Boolean circuit and later ...
user avatar
9 votes

Fast attack on approximate GCD problem?

This doesn't address your question; however the algorithm in the paper is broken. The paper does show that recovering the key requires you to solve the approximate GCD problem (which may be difficult)...
user avatar
  • 132k
9 votes
Accepted

Is full Homomorphic encryption quantum resistant?

Actually, most of the primitives that are currently believed to be secure FHE methods would appear to be quantum resistant; a partial list would include Craig Gentry's original scheme based on ideal ...
user avatar
  • 132k
9 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 ...
user avatar
  • 10.6k
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 ...
user avatar
  • 19.2k
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 ...
user avatar
  • 132k
8 votes
Accepted

What is this cryptosystem called?

Review of the paper The paper's goal is to offload to a server the computation of the inverse of a (non-singular) $n\times n$ matrix $X$ of (the floating-point approximation of) real numbers, while ...
user avatar
  • 124k
8 votes

Key Size for Symmetric Homomorphic Encryption Over the Integers

The paper says that the parameters are $r ≈ 2^{\sqrt \eta}$ and $q ≈ 2^{\eta^3}$. Note that these values are expressed as functions of $\eta$, not $N$. With regard to the parameters, it is common ...
user avatar
  • 4,832
8 votes
Accepted

Homomorphic Encryption vs. Garbled circuits

There has been work on using garbled circuits while also hiding the function. This can be done via implementing a universal circuit inside the garbled circuit. However, the standard garbled circuit ...
user avatar
8 votes
Accepted

Homomorphic OR operations

For any $x,y$ represented by $\{0, 1\}$, $x \lor y = 1 - (1-x)(1-y)$. It follows, any one-multiplication homomorphic scheme would do. It also follows, just additively homomorphic scheme would be not ...
user avatar

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