13 votes
Accepted

Order-Preserving Encryption (OPE) and leakage

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 ...
user avatar
  • 4,548
10 votes

Order-Preserving Encryption (OPE) and leakage

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 ...
user avatar
9 votes
Accepted

Is it secure to use order preserving encryption in practice?

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 ...
user avatar
  • 31.2k
8 votes
Accepted

What is matrix branching program?

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 ...
user avatar
  • 12.3k
6 votes

Does asymmetric order-preserving encryption exist?

No, an order preserving public key encryption scheme cannot be secure. Consider any PKE scheme for plaintext space $\mathbb{Z}_n$ for which there exists a public operation that given two ciphertexts (...
user avatar
  • 6,411
6 votes
Accepted

Applying machine learning algorithms to homomorphic encrypted data

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 ...
user avatar
  • 37.7k
5 votes

Order-Preserving Encryption (OPE) and leakage

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 ...
user avatar
  • 151
4 votes

"Practical" operations supported by functional encryption?

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 $...
user avatar
4 votes

Are large polynomials secure for order preserving "hashing"? (newbie question)

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 ...
user avatar
  • 122k
3 votes
Accepted

Understanding this notation for the probability distribution of order preserving encryption

In cryptography the notation of $x\stackrel{\\\$}{\gets}S$ (also sometimes seen as $x\gets_{\\\$}S$) means that $x$ is chosen uniformly at random from the set $S$. If an algorithm is on the right side ...
user avatar
  • 44.6k
2 votes
Accepted

How does order-preserving encryption work on string?

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 ...
user avatar
  • 198
2 votes

is OPE able to produce different cyphertext for same plaintext?

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 ...
user avatar
  • 4,548
1 vote

is OPE able to produce different cyphertext for same plaintext?

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 ...
user avatar
1 vote
Accepted

Understanding the definition of HGD

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, ...
user avatar
  • 4,548
1 vote
Accepted

Weakening of Paillier cryptosystem due to ciphertext equivalence and order in CryptDB

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 ...
user avatar
  • 12.3k
1 vote

How secure is this use of Ziv-Lempel encoding?

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 ...
user avatar
  • 636

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