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) ...
- 5,609
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 ...
- 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). ...
- 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. ...
- 44.4k
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 ...
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 ...
- 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 ...
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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
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 ...
- 16.7k
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 ...
- 16.7k
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: ...
- 16.7k
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)...
- 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 ...
- 5,609
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) ...
- 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 ...
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 ...
- 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 ...
- 91
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)...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 26.9k
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 ...
- 2,237
Only top scored, non community-wiki answers of a minimum length are eligible