Tag Info

45

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

20

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

18

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

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

15

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

10

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

9

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

8

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

7

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 ... 7 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 ... 6 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 ... 6 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 ... 5 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 ... 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 ... 4 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 ... 4 It depends on how strict you are. In the traditional cloud computing sense, where one party "sends their data to the cloud" for all the computations to be performed, no. There aren't any other methods other than homomorphic encryption. The most common techniques for computation on encrypted data besides homomorphic encryption are garbled circuits and secret ... 4 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$... 4 It depends on what you mean by "32-bit integer". If you want to add integers which will never exceed the range -231..231-1 (i.e. integers which fit in 32 bits), then Paillier cryptosystem will be fine. It uses mathematics which can be viewed as "slightly complex" so you could also rely on a simpler ElGamal encryption. With ElGamal, you do not add; you ... 3 While I haven't read the paper, I believe I can answer these questions: I'm not sure if the implied modulus of each operation is$q$, as I added myself to the above formulas. Could someone please clarify this? The paper omits it... No, the arithmetic is done modulo$p$. Remember, you're working in a subgroup of size$q$of$\mathbb{Z}^*_{p}$; ... 3 As far as I can tell from your description, the modulus is p. To multiply two group elements, you compute x*y (mod p); because the generator g you choose has period q it'll all work out fine. No, p, q, and g can (and must) all be public. This is ElGamal, not RSA we're talking about - the security comes from the (presumed) hardness of taking discrete ... 3 If you are not limited to HMAC, blind signatures would meet your requirements. In RSA, you can do blind signatures as follows: Let$M$be the message to be signed (probably the hash of a message) and let$e,N$be A's public key,$d$is A's private key. B computes$M' = M\cdot r^e \bmod{N}$and sends$M'$to A. A computes$S' = ...

3

You definitely cannot get semantic security defined by Goldwasser and Micali; however, you can get some weaker form of security notion. Boldyreva et al. has motivated more on this in their first paper on Order Preserving Encyption. They have a follow up paper with more security analysis and an alternative scheme. I guess both of them solves the issue that ...

3

To answer your second question, Paillier and other CPA-secure homomorphic encryption schemes cannot provide order-preserving encryption. The security of these schemes rely on using a random factor during encryption to ensure their ciphertexts are distributed randomly in the ciphertext space. OPE must use a weaker notion of security than CPA. In terms of ...

3

There are roughly two common techniques for multi-party computation, garbled circuits and secret sharing. Either may work for your situation, so I've detailed some info and recommendations about each below. Garbled Circuits GC is most often applied to the 2 party case. It can be made to be secure against malicious adversaries and can be fairly efficient (a ...

3

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

3

Yao's garbled circuit is simple to understand. First of all, note that if we can securely compute $\mathsf{NAND/NOR}$ of two input bit, we can perform any boolean operation. Yao's garbled circuit tries to achieve the same. Lets look at scrambled $\mathsf{OR}$ gate. Alice creates a set of four keys, $K_{x=0},K_{x=1},K_{y=0},K_{y=1}$ She then creates 4 ...

3

What I'll describe works with any homomorphic scheme, whether multiplicative (Elgamal) or additive (Paillier; maybe exponential Elgamal or BGN depending), but I'll describe it with multiplicative. I assume what you mean is something like this: you have, say, five people. They all generate a random value $r_i$, and post the encryption of it: ...

3

In general, it seems that right now, searching on encrypted data is still quite limited. Besides CryptDB, SADS is another that I have seen. Without knowing more about your security requirements, however, it will be hard to say exactly (e.g., is the regex kept private or is only the data that it is being matched against kept private? Is there a trusted third ...

3

Theoretically, with fully-homomorphic encryption (like with Gentry's scheme), you could make a circuit (with memory) which computes over encrypted data and outputs encrypted results. The circuit could be a general-purpose CPU, and the encrypted data the code which is to be executed (reading this again, I think this is what @ByteCoin suggests). Since this ...

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