# Tag Info

59

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 ...

23

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 ...

21

My recommendation: No, you should not trust CipherCloud. Justification: Yes, there has been analysis of the CipherCloud system -- some of it right here on the Cryptography StackExchange. That analysis found what appear to be severe vulnerabilities in the CipherCloud system. Unfortunately, CipherCloud has apparently sent StackExchange a DMCA takedown ...

20

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 ...

17

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 ...

11

Bottom line. The short answer is that none of them are practical ... yet. But there is a lot of active research, and if we're lucky, maybe that will lead to enough improvements that it might become practical. We'll see. More information. You can find some useful information at the following questions: What Partial Homomorphic Encryption implementations ...

11

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 ...

11

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 ...

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 ...

9

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 ... 9 Roadblocks Some further research answers one of my questions. In "Fully Homomorphic Encryption over the Integers with Shorter Public Keys", the authors state: We obtain similar performances as the Gentry-Halevi implementation of Gentry's scheme 7. More precisely we use four security levels inspired by the levels from 7 (though they may not be directly ... 9 You are asking the wrong question. You shouldn't do it the way you described (by multiplying or adding random numbers submitted by the participants). This problem has been well-studied, and there are solutions to it. Your question assumes a particular approach to the problem, but that approach turns out to be flawed. Your approach is vulnerable to ... 8 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 ... 8 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 ... 7 Using exponential Elgamal as the encryption function, Define the list of candidates: e.g., Alice, Bob, Carol Voters submit an encryption of their vote: e.g., to voter for Alice:$v=\langle\mathsf{Enc}(1),\mathsf{Enc}(0),\mathsf{Enc}(0)\rangle$Use an OR-proof (Fig 2) to show each ciphertext encrypts a 0 or a 1: e.g.,$\langle \pi_1, \pi_2, \pi_3 \rangle$... 7 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 ... 7 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 ... 7 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 ... 6 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 ... 6 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. ... 6 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 ... 6 This concept is called targeted malleability: http://crypto.stanford.edu/~dabo/pubs/abstracts/reshom.html The abstract and introduction of that paper give a good overview of the ideas. In brief, the goal is to ensure that a homomorphic evaluator can only produce a ciphertext by evaluating a function from an "approved" class of functions. It is trivial to ... 6 So is it possible for homomorphic encryption to actually filter and return a small encrypted subset of a larger encrypted database based on a query? Sure it is. Say we have a database with (encrypted) test scores and student id and want to query the DB for the student with the highest score. Using FHE we can do comparison that for our purposes assume ... 6 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 ... 5 None. When enciphering any small set of values (including a fair coin flip, a byte, even a small password..), unpadded RSA (or RSA with any padding that does not include randomness) is a terminally weak encryption method: the adversary can enumerate the possible plaintext values, encrypt them using the public key, and check against the ciphertext to ... 5 In Paillier, if it were possible to determine whether an encrypted number is less than 0 (that is, is equivalent modulo N to a value$x$where$N/2 < x < N$), then it would be possible to decrypt arbitrary encrypted values with only the public key. That is, if someone found such a method, they will have broken Paillier as a public key system. The ... 5 Have you read Wikipedia: homomorphic encryption and Bruce Schneier: Homomorphic Encryption Breakthrough? In summary: Is it possible to subtract numbers using homomorphic encryption? Is it possible to multiply numbers using homomorphic encryption? Yes, there are many known partially homomorphic cryptosystems, each one can either multiply or add ... 5 To answer your question: no this is not homomorphic encryption because one of the plaintexts is used unencrypted. There may be times when it is a useful property, but the only uses I know of it are to demonstrate the malleability of xor ciphers. To be a homomorphic encryption function, it should be possible to calculate the encryption of some function of ... 5 Well, the problem is with logical OR and subtraction (which Pallier can also do), you've got FHE; that is, you can compute any combinatorial function of encrypted (binary) inputs. Here's how it works, you can construct the NAND function:$NAND(x, y) = (Enc(1) - x)\ OR\ (Enc(1) - y)$If we limit$x$and$y\$ to being either encrypted 0, or encrypted 1, ...

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