Tag Info

Hot answers tagged

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


8

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


6

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


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

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

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

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


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


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



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