On Mon, 8 May 2000, John Kelsey wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
>
> At 01:25 PM 5/7/00 -0400, dmolnar wrote:
>
> ...
> >An "indeterministic cryptosystem" is defined there as one in which
> >"equal plaintext blocks are encrypted to different ciphertext
> >blocks."
> ...
> > 1) is the term "indeterministic cryptosystem" formally
> > defined anywhere?
>
> I've seen the term ``nondeterministic cryptosystem'' or ``randomized
> cryptosystem,'' which I've understood to mean cryptosystems which can
> map one plaintext into some huge number of ciphertexts, all of which
> may be decrypted back to the original plaintext. There may be some
> nuances of definition I'm missing. Have you looked in the _Handbook
> of Applied Cryptography_ or in _Applied Cryptography_? If you look
> under the above two terms, I think you may find a formal definition.
> (_HAC_ is more likely to have a formal definition, I think.)
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:
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
