7
$\begingroup$

A deterministic encryption scheme is a cryptosystem which always produces the same ciphertext for a given plaintext and key, even over separate executions of the encryption algorithm.

Although we cannot achieve semantic security or indistinguishability for deterministic encryption due to lack of randomness in cipher text, there is an analysis of maximum possible security for deterministic encryption.

I could not understand much from these papers though. Can somebody say what that means in simple terms? How can we achieve it, if we want to implement it? I suppose I need deterministic encryption because I want to be able to search on the ciphertext.

The papers I tried to understand:

Improve this question
$\endgroup$
4
  • $\begingroup$ See en.wikipedia.org/wiki/Probabilistic_encryption $\endgroup$
    – Mok-Kong Shen
    Mar 20, 2013 at 11:08
  • $\begingroup$ no i cannot go for probabilistic encryption, my application needs to be able to perform search over cipher text $\endgroup$
    – sashank
    Mar 20, 2013 at 14:32
  • 2
    $\begingroup$ Pretty much the only inherent issue with deterministic encryption is that it leaks if two inputs are identical. So if you apply it to individual words, security will suck. If you apply it to complete and complex files, you'll probably be OK. $\endgroup$
    – CodesInChaos
    Mar 20, 2013 at 18:43
  • $\begingroup$ @sashank: The link I cited was intended for you to get some useful informations via comparing deterministic with probabilistic (non-deterministic) encryptions. You may also look at Wikipedia's article on deterministic encryption. $\endgroup$
    – Mok-Kong Shen
    Mar 20, 2013 at 19:07

2 Answers 2

Reset to default
6
$\begingroup$

You might be limiting yourself at the wrong aspect there.

Your goal is the ability to search on ciphertext; and you just look at deterministic encryption in your set of tools.

In order to use DE securely, the messagespace HAS TO contain enough entropy in order to protect from brute-force search. The only way to solve this is adding entropy at random either in the encryption process and/or the message (e.g. extend message by a couple of random bits at the start).

But what you actually want is "Searchable Encryption", google scholar will help you out. For example Abdalla et al. published "Searchable Encryption Revisited: Consistency Properties, Relation to Anonymous IBE, and Extensions" and Boneh et al. published "Public Key Encryption with Keyword Search". However, I don't know if there are any implementations of these schemes, and probably they are quite huge: PEKS based on IBE, which is based on pairings in elliptic curves.

Improve this answer
$\endgroup$
3
  • $\begingroup$ thanks would check out those papers, in an imaginary application if the client searches for all the possible words the server has, do you think searchable encryption would have advantage over Deterministic encryption ? $\endgroup$
    – sashank
    Mar 23, 2013 at 12:25
  • $\begingroup$ Ehm, I am not sure where you're going with this, and maybe you should specify which information should be retrievable by whom, and who has the private key(s). $\endgroup$
    – tylo
    Mar 25, 2013 at 15:02
  • $\begingroup$ The kind of searchable encryption described in these papers is wildly impractical for real-world use. Read Bellare's paper on deterministic encryption from CRYPTO 2007, it describes a new security notion for deterministic encryption and presents a couple schemes that meet it. $\endgroup$
    – pg1989
    Aug 8, 2013 at 23:34
0
$\begingroup$

Since determnistic encryption can not achieve semantic security with indistinguishability in mind the theory says that we assume the underlying plaintext to have enough high-min entropy such that they are not easily gueassable

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes the message structure should ensure the uniqueness , but what if we don't have much choice there ? what is the best possible thing that can be done if we cannot avoid DE or high entropy ? $\endgroup$
    – sashank
    Mar 21, 2013 at 3:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.