# Tag Info

9

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

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

3

CryptDB implements order-preserving encryption, and its source code is publicly available. In fact, rather than building your own system that uses order-preserving encryption, you might try just using CryptDB. Alternatively, in a pinch, I suppose you could take one of the papers that describes an order-preserving encryption algorithm and implement it ...

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

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

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

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

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

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

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

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

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