🚀 go-pugleaf

In article <1992Oct28.203441.21190@ulysses.att.com>, smb@ulysses.att.com
(Steven Bellovin) writes:
| In article <1992Oct28.114927.28223@news.cs.indiana.edu>, Marc VanHeyningen
| <mvanheyn@whale.cs.indiana.edu> writes:
|> A reasonable idea, but unfortunately it is subject to the same problems
|> as a single trustee:  There is no way to "prove" that someone is using
|> an unregistered key until you get probable cause and get a court order
|> for the keys and discover that you can't decrypt the traffic.
| 
| Let's turn our attention to technical matters for a while...
| Basically, I'm not convinced you're right.  Consider, say, the Enigma
| and the Index of Coincidence.  Using the latter, it was possible to
| tell when two ciphertexts were encrypted using the same key.  Thus, one
| could supply, with protected key registration, some innocuous plaintext
| encrypted with the same key....
|
| Now -- the Index of Coincidence won't work for DES.... [reasons omitted]
| Disregarding the last point, it's an interesting question whether or not
| there's an analogous test that could be used.  Suggestions?...

Good timing!  I've been thinking about just this problem.  Abstractly, one
assumes a known encryption algorithm E, and a given ciphertext C.  The
problem is for someone who knows the key used K to prove to someone who does
not that C=E(M,K) for some message M.  More to the point, suppose we had a
pair of one-way hash functions H1 and H2.  The registry is willing to reveal
H1(K).  The sender reveals H2(M).  So now we wish to be able to prove that C
is as stated, given a known H1(K) and H2(M).

This sounds good, but it's impossible as stated, for a simple reason:  The
sender encrypts his message M with a different system (or just a different
key) producing C=E'(M',K).  Now he inverts E to find a message M' such
that C=E(M,K), then computes H2(M) and announces it.  So much for the
guarantee.

Can this be fixed?  I can think of two approaches:

	a)  Allow the examiner to ask different questions.  Suppose,
		for example, that there was a way, knowing M and K, to
		answer queries like "Tell me the distribution of the
		following set of digraphs with the first character at
		an odd position", in such a way that someone who knew
		H1(K) and H2(M) could check it.  I have no idea HOW to
		do this; it seems to be related to zero-knowledge
		proof protocols, and is perhaps possible.

	b)  Use an encryption algorithm whose range is much larger than
		its domain.  For example, suppose that E(M) was 10%
		larger than M.  If M were 640 bits long, then only
		1 in 2^64 possible M''s would actually come from some
		M, so the previous trick would be impractical.

		In the old days, cryptosystems that expanded their
		inputs were avoided, since bandwidth was expensive.
		That's really not true any more, and in fact there are
		plenty of reasons to consider such systems anyway.

							-- Jerry