David Molnar Wrote:
> Anyway, recipient-hiding is most obviously useful when public bulletin
> boards are involved. I'm not so sure it's useful between remailers, since
> the underlying transport protocol will tend to reveal the ID of the next
> hop anyway...but it strikes me as something to have as a hedge against
> future clever attacks I can't think of.
Missed most of this thread (victim of nym-revelation attack, luckily
being anyminous it won't apply...).
There seem to be three points:
A. How to achieve recipient hiding encryption
B. When and whether it is useful to use recipient hiding
C. How to efficiently tell whether a message is for use if recipient
hiding is in use.
(A) is easy, but it sounds like it has already been discussed. El Gamal
with a common p&g does it automatically. RSA can do it easily, just pad
the ciphertext with a random multiple of the modulus to bring it up to
some standard size.
(B) can probably be justified (the nym server idea may not apply, as
the public key of the nym is public knowledge).
(C) is the interesting part, but although there are several partial
solutions there doesn't seem to be a perfect one. This has been discussed
many times in years past.
If two parties are communicating many messages, each message can contain
(in the encrypted payload) a random nonce which will appear in the clear
as the header of the next message. This provides very fast screening.
Variations on this idea seem to be the most effective approach.
For other messages, it may be safe to put a few bits of the public key
into the clear - maybe 4-5 bits or so. If there are many people using the
channel then this will not reveal much information about the recipient.
Each additional bit reduces the chaff by a factor of 2.
Beyond this, you'd like some kind of PK system where you can send a
very small message, just a few bits, with extremely cheap decryption.
There don't seem to be any which satisfy this.
Shamir pointed out that RSA decryption can be sped up if you know the
plaintext is less than one of the primes. You do the decryption mod p
and not mod q, and skip the CRT. It's a factor of 2 faster but this is
only a modest gain. (A few more primes could be used to make the RSA
modulus for slightly more improvement.)
You can also design fast-decryption RSA exponents, at some theoretical
risk of increasing vulnerability. Pick a "d" which has a fast addition
chain, but still has appropriate entropy (100-150 bits for a 1024 bit
key). This will speed things up a factor of 5 or so for a 1024 bit key.
Using short exponents is already common in DL systems of course. Combining
this idea with the previous paragraph gives you perhaps a factor of 10
speedup, and combining with the key-leakage idea gives you another factor
of about 20, for a total factor of about 200.
To go beyond this, you can use a batch decryption system. See "Batch
RSA" by Fiat in Crypto 89, or "Batch Diffie-Hellman..." by Beller &
Yacobi in Eurocrypt 92.
Fiat's system allows you to do a bunch of RSA decryptions in the cost
asymptotically of about one large exponentiation. The catch is that each
decryption must use a different public exponent. So for this to work,
the public key would include the modulus plus several public exponents,
say 16 of them. To encrypt, one exponent is chosen at random and the
RSA encryption is performed. The cyphertext could be appended with four
bits which show which exponent was used. Since these are random it does
not leak any information about which key it is for.
The decryption batching must then collect 16 messages, all with a
different four-bit field telling which exponent is used. It then uses
Fiat's algorithm and efficiently calculates all 16 decryptions. These
can then be inspected to see which produced well formed messages; those
are the ones which are actually directed towards this key.
Fiat's system is a bit complicated but he shows the basic idea with
a simple example. Suppose you have two messages, M1 and M2. M1 is
encrypted with the exponent 3, and M2 with the exponent 5. You want to
compute M1^(1/3) and M2^(1/5).
Compute M = M1^5 * M2^3. Then do one full-sized exponentiation and
compute I = M^(1/15). This means that I is the product M1^(1/3) *
M2^(1/5) of the two values that we want.
To get M2^(1/5), compute I^6 / (M1^2 * M2). Once you have that you
can get M1^(1/3) just by dividing it into I: I / M2^(1/5).
So we had to do several short exponentiations and one long one to get
the two results. With Fiat's more general technique you construct a
binary tree and essentially apply the same idea recursively.
Unfortunately Fiat's batches become inefficient beyond about 16. So
this is just another constant-factor speedup.
For earlier versions of the concepts in this message see:
http://cypherpunks.venona.com/date/1998/01/msg00203.html and
http://jya.com/RSA-stego.htm
