From: jpp@jpplap.markv.com (Jay Prime Positive)
Date: Fri, 27 May 94 19:55:22 PDT
To: cypherpunks@toad.com
Subject: Re: (fwd) Re: NSA Helped Yeltsin Foil 1991 Coup
In-Reply-To: <9405272141.AA23574@toad.com>
Message-ID: <m0q7Dbb-0003paC@jpplap>
MIME-Version: 1.0
Content-Type: text/plain


  The problem with forming product cyphers is the birthday paradox.
The problem with threshold cyphers is bandwidth.

  Concider for example e1( e2( e3( x ))), and the permutations it
generates.  Let E1 represent the number of permutations generated by
e1 under all the different keys, and similarly E2 and E3 the number
generated by e2 and e3 respectively.  E1, E2, and E3 are all nearly
the same as the number of keys for the respective cryptosystems.  But
there is no garantee that the number of permutation that the
composition of e1, e2, adn e3 is equal to the product of the number of
keys (E1*E2*E3).  Infact, the birthday paradox just about garantees
that the number is less than E1*E2*E3.  So some of the additional
keybits are lost.

  On the other hand, the number of permutations that the system Eli
and I describe *is* garanteed to increase with the addition of
cyphers.  Concider the same three encryption functions as in the
previous case.  If the number of permutations generated by e1, e2, and
e3 is E1, E2, and E3 respectively, then the number of permutations in
ej{e1,e2,e3}(xi) == <e1(xi xor ri), e2(ri)> and ri is a cryptographic
random number generated by e3, is exactly E1 * E2 * E3.  The problem
with thresholding is the linear increase in cyphertext with linear
increase in number of keybits.

  So if you are a bit too paranoid to rely on a single non DOD/NSA
cypher, but not willing to use a one time pad, then concider
thresholding.  If you don't have the communication bandwidth to
support it, then certainly fall back to the simpler scheme Perry
describes.

  (Note that Eli and My scheme is only slightly slower to compute than
Perry's.  It requires computing one extra xor per block.  Also note
that the actual increase in bandwidth for a three cypher system
threshold in a practical encryption package like PGP would not be 2 to
1 since it likely compresses before encryption.)

j'