33
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 ...
12
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 ...
12
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 ...
9
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 *...
8
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 columns
...
8
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$ ...
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 ...
7
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 ...
5
If you want to know more about leakage in Order Preserving Encryption (OPE) and Order Revealing Encryption (ORE) Scheme, you can find some interesting findings in two papers:
What Else is Revealed by Order-Revealing Encryption?, 2016 ACM SIGSAC.
Leakage-Abuse Attacks against Order-Revealing Encryption, 2017 IEEE S&P
In the first paper they explain how ...
4
The basic method is easily cracked: it is well known how to find a polynomial of degree at most $k$ from $k+1$ (input, output) pairs; that's the polynomial interpolation problem. There are numerous ways to efficiently carry it for high degree and large integers (one such method is to carry it modulo some medium primes, and use the Chinese Remainder Theorem ...
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
4
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 ...
4
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 ...
3
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 ...
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 ...
2
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 ...
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 ...
2
Boldyreva et al.'s scheme is not randomized. However, there is a folklore way to "randomize" it by choosing randomly from the range gap in the last recursive step of the algorithm. It's not clear what security improvement this buys you, though, since it only really randomizes the last few bits of the ciphertext.
There are schemes meeting a randomized ...
1
The definition of OPE used in Boldyreva's work (section 3.1) is basically
$$\forall m_0, m_1 \in \mathcal{M}, m_0 > m_1 \Leftrightarrow E(m_0) > E(m_1) $$
and any scheme satisfying this definition is deterministic.
To understand it, consider that $m_0$ and $m_1$ are equal messages. Then, $E(m_0) \not > E(m_1)$, otherwise we would have $m_0 > ...
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
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
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
