On Tue, 9 May 2000, Brian Hurt wrote:
> I don't remember it in AC. But I'm wondering- if this definition is the
> case, couldn't you then build a non-deterministic crypto system using
> standard deterministic crypto building blocks? Like thus:
AC is not a bible!
To achieve even elementary security properties (like semantic security,
not to talk about cryptosystems secure against chosen ciphertext attacks),
a cryptosystem has to be probabilistic. PRobably the best known prob. CS
is ElGamal, where a message m is encrypted to (mh^r,g^r), where g is a
group element, h=g^x for some g, x is secret key, h is public key, and r
is a newly generated random element. ElGamal can be applied over arbitrary
group G; it can proven that ElGamal is semantically secure in so called
generic model (where G is an ideal group). Practical instantiation where G
is an elliptic curve group is usually called ECC.
Another examples are RSA+OAEP, Cramer-Shoup, ...
Helger
>
> Assume the deterministic crypto system encrypts blocks of n bits of plain
> text to n bits of cipher text. On encryption, the system seperates the
> input into blocks of size n-k bits. Each block has appended to it (or
> interspersed with it in a known fasion) k bits of random data, and
> encrypted with the deterministic crypto system. On decryption, after
> decrypting the cipher block, the k bits of random data are discarded, and
> the n-k bits of plain text are added to the output. Each n-k bits of
> input can encrypt to one of 2**k encryptions.
>
> The advantage of doing this is that it makes choosen or even known
> plaintext attacks more difficult, as you also have to take into account
> the random additions (you'd want to make the random additions
> cryptographically secure). The disadvantage of this is that it increases
> the cipher text size by a factor of n/(n-k). But I don't see how you can
> get around that last requirement- if you have 2**n distinct inputs, you
> need 2**n distinct outputs. If every input has c potiential inputs, you
> need c * 2**n distinct outputs.
>
> Sorry if I'm trodding well worn ground here.
>
> Brian
>
>
>
