86
I could not find any evidence pointing towards homomorphic encryption. What I could find were different combinations of deterministic and format-preserving encryption. There is probably also a variant that preserves order, but I couldn't find any material depicting it.
This post is based on material published on the CipherCloud website at CipherCloud Cloud ...
33
I don't think they have implemented homomorphic encryption at all. They have just implemented regular AES encryption (they have a FIPS 197 certificate for their AES), but in what appears to be a very insecure way. Why would they choose to do that? Because they had no choice. Here's what I mean:
The challenge for cloud encryption providers like CipherCloud ...
27
I haven't posted in a while, so long in fact that the email tied to my Stack Exchange account is no more, I forgot my StackEx password, and I had to create a new account. (I'll leave it to the reader to decide if this is the real me.)
But I did want to just to follow up here, because there were some unanswered questions from my last post and the follow-up ...
23
Well, the idea behind the CRT optimization is that if we know the factorization of the modulus $N$ (which we may if we have the private key), then we can split up the message $M$ into two halves (one modulo $p$, and one modulo $q$), compute each modulo separately, and then recombine them. That is, we compute:
$m_1 = (M^d \bmod N) \bmod p = ((M \bmod p)^{d \...
20
They are not using any exotic encryption. In fact, based on data, it appears it's just 1:1 mapping (tokenization) after lowering the case on plain text data. I don't know about others but to me this pattern just stood out when I had a look at the demo video. To see it yourself, check their publicly visible demo video. Hit HD, go full screen to 2:19. You will ...
17
Elgamal can be made additive by encrypting $g^m$ instead of $m$ with traditional Elgamal for some generator $g$ (usually the same one used to generate the public key). This variant is sometimes called exponential Elgamal. The difficulty is decryption: running the standard decryption gives you $g^m$ and recovering $m$ requires you to solve the discrete log. ...
15
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 ...
14
Well, since I'm one of the authors on the paper, let me try to answer your question.
First I should explain that the paper you link to is not the original paper proposing that approach, but rather the first implementation of it (in this case using quantum optics). The original paper which introduced the Universal Blind Quantum Computing (UBQC) protocol ...
13
Yes (and always).
Given $\mathsf{Enc}(a)$ and $b$, you can compute $\mathsf{Enc}(a \cdot b^{-1} \bmod{n})$ by simply computing $\hat{b}=b^{-1} \bmod{n}$ and $Enc(a)^\hat{b} \bmod{n^2}$.
Paillier encryption is built on the bijeective mapping from $(x,y)\in \mathbb{Z}_n \times \mathbb{Z}_n^*$ to:
$E_{g,n}(x,y)=g^x y^n \bmod{n^2}$.
Generator $g$ is chosen ...
13
I also watched the video (thanks Sid, for the link) and after looking at it, it reveals some of the other methods that Ciphercloud appears to be using to preserve search. Nothing appears to be an implementation of any sort of homomorphic encryption.
I snapped a copy of one screen after the response from John is entered and encrypted, and have attached an ...
13
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 ...
13
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
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 ...
12
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 ...
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 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 ...
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
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 ...
10
Here's a paper showing how to realize the BGN cryptosystem with a prime order group. You could implement the cryptosystem with PBC or one of the other paring libs.
"Converting Pairing-Based Cryptosystems from Composite-Order Groups to Prime-Order Groups"
David Mandell Freeman
Eurocrypt 2010
http://theory.stanford.edu/~dfreeman/papers/subgroups.pdf
http://...
10
I don't know how CipherCloud works. However, a related question is: How could you encrypt data in a database, in a way that allows you to achieve these goals? What are the best cryptographic techniques currently known, for that goal?
As it happens, that question has a good answer. Take a look at CryptDB, a system built by MIT researchers to encrypt all ...
10
As you probably know $f(\lambda)=O(\lambda^4)$ means that $|f|$ asymptotically upper bounded by some constant times $\lambda^4$. The notation $f(\lambda)=\Omega(\lambda^4)$ corresponds to an asymptotic lower-bound.
Now, the $\tilde O$ and $\tilde \Omega$ are closely related notations, where we not only ignore constants but also values which are polynomial ...
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
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 ...
10
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 ...
9
CipherCloud's website now clearly states, here, that CipherCloud DOES NOT use homomorphic encryption.
This also states that CipherCloud DOES NOT implement 1:1 mapping or ECB mode in any customer deployment. Other statements are next to acknowledging that CipherCloud's early demos did that, citing the will to illustrate the functionality, features that where ...
9
The multiplicatively homomorphic variant of RSA is not semantically secure. This is a major disadvantage. ElGamal is a semantically secure, multiplicativey homomorphic cipher. Paillier is a semantically secure, additively homomorphic cipher.
As described by tylo, all homomorphic ciphers are malleable by definition. Chances are, however, if you are ...
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
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 ...
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
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
