18
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 together. Often, we think of circuits in terms of and/or/not gates. It turns out, however, that you can construct circuits from other types of gates. NAND by ...
17
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) as an attack, because the results remain unknown to the attacker.
For example, given two ciphertexts $c, c'$, an attacker can homomorphically compute whether ...
15
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 polynomials), etc.
How to decide if a term is small or not depends on the security and correctness properties of each system (for instance, a polynomial is ...
14
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). Furthermore, (boolean) circuits can describe any computation.
This is very nice when it comes to fully-homomorphic encryption. All we have to do is provide a way to ...
14
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. But what is it that we actually want to protect?
Let's say the message we're encrypting is AGENT DOE REPORTS 23 UNITS ON BOARD SHIP TO BASE ALPHA, DEPARTED ON ...
13
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 section.
$\newcommand{\qinv}{q_{\text{inv}}}$
Let $M$ be the message, $C$ the ciphertext, $N = PQ$ the RSA modulus, and $D$ the decryption key.
What you don't ...
13
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 FHE operations so that we can evaluate the $f$ with FHE.
Somewhat Fully Homomorphic schemes allow us to operations on ciphertexts. In the bitwise case, for ...
12
The LWE assumption
I think we should start from the LWE assumption.
Let $n$ and $q$ be integers and let $\chi$ be a distribution over $\mathbb{Z}_q$. We often take $\chi$ as a Gaussian with small variance. (We take an error $e$ from this distribution $\chi$ and assume that $|e| \ll q$.)
The LWE assumption states that any efficient adversary cannot ...
12
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 cloud does not have the private key, the cloud cannot decrypt the results of the operations.
Once the operations have been performed, the cloud sends the resulting ...
12
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 Rosulek: Reconciling Non-malleability with Homomorphic Encryption.
Dan Boneh and Gil Segev and Brent Waters: Targeted Malleability: Homomorphic Encryption for ...
12
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 secure that leaks no information. The only information available to the observer is the circuit.
In FHE, the $b$ is coming (or may come) from another result, ...
11
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 restricting to only certain depths (where the depth is calculated by looking at multiplication gates), they were able to remove the bootstrapping operation of Gentry's ...
11
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 paper A Survey of Homomorphic Encryption for Nonspecialists
Consider that the attacker has a value $c_1$ that is known by him to be a encryption of some clear text ...
11
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: all efficient functions
Which notion of security: indistinguishability obfuscation
Underlying assumptions: new, exotic, and relatively poorly understood ...
10
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 scale invariance. (Indeed, it is easy to switch between the two encodings of the plaintext, simply by multiplying the ciphertext by an appropriate scalar. See ...
10
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) correct evaluation is called a somewhat homomorphic encryption scheme (SHE).
A $\mathcal{C}$-evaluation scheme $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Eval}, \...
10
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 comes from.
Asking whether FHE is Turing complete does not really make sense: FHE is a cryptographic primitive, not a general computing device. If this is ...
10
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 compile any public-coin zero-knowledge proof into a designated-verifier non-interactive zero-knowledge proof; this was shown in the paper Non-interactive Zero-...
10
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 parameter, from which the probability of "breaking" the system is measured (as well as the resources needed to do so and also to execute the cryptosystem's ...
9
We use circuits because they are universal (any function you want to compute can be expressed as a circuit) and because they are convenient (because we know how to solve the problem of fully homomorphic encryption for circuits but not for other models). In particular, circuits are in some sense simple: all you need to do is find a way to implement an AND ...
9
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 you may ask the evaluation of the function on a single input not fixed in advance).
Indeed this is the approach to Verifiable Computation proposed in a paper ...
9
The answer is yes. Say we have an FHE scheme that supports addition and multiplication over an underlying field (so we are not limited to just 0,1). As in your question, assume we want to compute $Y=2^C$ where $C$ is encrypted and $Y$ is encrypted such that $y=D(Y)=2^m$.
We can do this using a basic square and multiply algorithm. Assume that we can do a bit ...
9
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)$ and $m_2$, you can get $E(m_1\cdot m_2)$ however. But notice that $m_2$ in this case was not encrypted. On the site you reference, $C$ is not encrypted. It ...
9
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 homomorphic encryption schemes are malleable by definition and cannot provide adaptive security against chosen ciphertext attacks (be IND-CCA2 secure).
Since ...
9
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); what they don't show is whether recoverying the plaintext requires solving a hard problem. It turns out that it isn't that difficult at all (a bit of linear ...
9
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 lattices, BGV (based on ring-LWE), and this NTRU-based approach. All three are based on hard problems that are not susceptible to Shor's algorithm.
9
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 advantages as well. Define a "linear representation" $[x]$ to be any way of representing/distributing a value $x$ among parties such that the following properties hold:
...
9
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 abilities on data, then it's easy to see how this is the case.
With normal secret-key encryption:
only the key holder(s) can create ciphertexts (write ...
9
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 can, given $E(x)$ and $E(y)$, compute $E(x + y \bmod n)$, where $n$ is a large integer; this implies that, given $E(x)$ and $k$, you can compute $E(kx \bmod n)$
...
8
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 keeping $X$ and $X^{-1}$ confidential.
Towards that goal, the paper's method is to
draw a secret key consisting of two random permutations and $2n$ non-zero ...
Only top voted, non community-wiki answers of a minimum length are eligible