Re: A question on indistinguishabilty definition


David Wagner wrote:
Sergei wrote:
I mean that if {a_1,...a_l} and {b_1,...,b_l} are sets of plaintexts,
where a_i != a_j and b_i != b_j then is it possible to have such
DETERMINISTIC encryption scheme (K,E,D) that {E_k(a_1),...,E_k(a_l)}
and {E_k(b_1),...,E_k(b_l)} are indistinguishable.

One-time-pad, obviously, fails here, but are there deteministic schemes
posessing such property?

Ah-hah! Now I get it. I somehow missed the word "deterministic",
among other things. Thanks for the restatement.

A natural kind of construction to consider would be to first encode
the plaintext using an all-or-nothing transform, then encrypt the result
using some deterministic encryption scheme. As long as the entropy of
your plaintext distribution is large enough, this might do the trick.

Have you looked at "entropic security"? See, e.g., Dodis and Smith
(ePrint 2004/219; or here: http://theory.lcs.mit.edu/~asmith/) and
Russell and Wang (ePrint 2001/028, or: http://www.engr.uconn.edu/~acr/).
I don't think it is exactly what you asked, and I don't know whether
there are any constructions of deterministic encryption schemes that
achieve "entropic security", but it seems related and maybe some of
the ideas there can be used to achieve what you want.

I'm not quite sure about entropic security since, as far as I know, it
is not equivalent to IND-security. I think Mike Amling proposed a
solution that might be an example of what I'm looking for.
But anyway, thanks a lot for the hint. I'll have a look at this.

Sergei

.