# Tag Info

16

In the last couple weeks I've become pretty well-acquainted with the recent work in this area. I also built a prototype order-preserving encryption scheme following the algorithms presented in 'Order-preserving Symmetric Encryption' by Boldyreva et al. I'll take a stab at explaining the method I just implemented, which requires some understanding of discrete ...

10

The problem with a hash function like you ask for is that, if you hash an $n$-bit string and give the hash to someone else, they can recover the string using $n$ hash calculations with a binary search. For a simple example, let's say the $n=8$, your string is $01011001$ in binary, and its hash is $Y = H(01011001)$. To recover the string from the hash, I ...

7

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

6

If you know the order of the plaintext just possessing the correspondent ciphertext, then you can perform sorting, interval querying, and all the sort of algorithms based on neighborhoods on the ciphertext domain. This is why those schemes are used in practice. To see another example of the use of OPE, take a look at the cryptoDB: Queries of type "SELECT *...

5

I do work in this area. OPE and ORE are important primarily because of their tremendous utility in building systems which can perform some computation on encrypted data. Contrary to general-purpose solutions like fully-homomorphic encryption, OPE and ORE can be used to provide drop-in (with no code change) security in applications like databases. They can do ...

5

Timely question, since attacks on the order preserving encryption in CryptDB were recently in the news. Quoting the research paper (pdf), there are two attacks they use on OPE: sorting attack: is an attack that decrypts OPE-encrypted columns. This folklore attack is very simple but, as we show, very powerful in practice. It is applicable to ...

4

cryptdb has these implementations inside it . But their licensing is not Open sources as in GPL etc . They say its available for research purposes ! I have implemented Symmetric Searchable Encryption in Java, its LGPL

3

Homomorphic Encryption on Reals In theory, homomorphic encryption can be done on real numbers. This answer describes two options you have when dealing with real numbers or operations that will result in real numbers. Kristin Lauter is doing some of the cutting edge research in this area. In a recent paper, CryptoNets: Applying Neural Networks to Encrypted ...

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

How to know how much space to reserve? There are two ways: Take an implementation of the scheme, encrypt a 32-bit plaintext, and see how long the resulting ciphertext is. This is the simplest approach. Understand the scheme at a conceptual level, and then use your understanding of the algorithm to predict how long the ciphertext will be. Since it sounds ...

3

Yes, in fact there is an alternative to CryptDB. After our libraries pass muster with crypto consultants, my company will be open-sourcing our crypto. We implement Boldyreva's OPE scheme, SSE and a few kinds of format-preserving encryption. We're also looking at expanding our stable of cryptographic algorithms, so in the near future we might implement other ...

3

For an easy to grasp explanation, you can have a look at the talk Obfuscation I at the Cryptography Bootcamp by Amit Sahai. Here's a link to youtube. In this context he also explains matrix branching programs, which are also used in the construction of indistuingishability obfuscation. He starts explaining them at the minute 40. In short: You're given $2k$ ...

2

I think you are confusing functional encryption and homomorphic encryption. In a functional encryption scheme, using a secret key for some function $f$ on a ciphertext $c$ which is an encryption of $m$ allows you to get $f(m)$ in clear. In an homomorphic encryption scheme, you can run some operation on ciphertexts, and get an encryption of the result, for ...

2

The question as currently stated is true if we assume the equation takes place in $\mathbb{Z}$, since all the values are small integers. Proof: If $x<x'$, then $x^3<(x')^3$ and $ax<ax'$, so $$E(x)= x^3 +ax+b < (x')^3 +ax'+b = E(x')$$ The problem with trying to answer the more general issue you appear to be considering is working out what it ...

2

Paillier cryptosystem has the property that the product of 2 ciphertexts decrypt to the sum of the plaintexts. Strings are integers. Only that they are usually large. So this algorithm is also available for strings. This algorithm doesn't allow you to find encrypted string in a ciphertext. If you want an encryption scheme in which you can do any operation ...

1

In cryptography it is common to reason about the probability of an event in the probability space of all the random choices made (i.e. the random bits generated) during an algorithm's execution. So, in this description, "over the random coins of HGD" means the probability is computed over the probability space defined by the random bits used during HGD ...

1

Your hunch is wrong because of the definition of CPA security: Assume that some knowing some kind of relation between two plaintexts would give the attacker an advantage. Now think of the INC-CPA game: Nothing stops the attacker from choosing exactly this kind of relationship. And if the scheme is IND-CPA secure, knowledge of such a relation does not break ...

1

As mentioned above this is not possible in a direct way. However there exists a Zero Knowledge Proof that may do the job. It proofs that a message encrypts one out of a publicly known number of plain text messages. If these known messages only contain values greater or equal 0 this may be what you are looking for but unfortunately message and computation ...

1

In Paillier, the size of ciphertext is about the double of the plaintext. (Might be interesting for you to read: http://courses.engr.illinois.edu/cs598man/fa2011/slides/ac-f11-lect15.pdf‎) For Order-Preserving symmetric Encryption (OPE), check http://www.cc.gatech.edu/~aboldyre/papers/operev.pdf which describes "Choosing the Ciphertext Space Size" on page 9. ...

1

Ziv-Lempel is a data compression algorithm, so in general it doesn't protect your data. As for your question: More generally, how difficult is it for an adversary to distinguish two strings which have been Ziv-Lempel encoded but not encrypted? An adversary just can decode two strings and compare them. Due to the fact that Ziv-Lempel is an encoding ...

1

There are a number of ways to do this. The simplest way is to simply add a number to it. Given a key of X, it would show: A>B A+X>B+X Of course, this isn't a very complex method by any means, but more complex formula could be used to give the same result. Generally speaking, they simply need to preserve the sign, which there are a multitude of ...

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