[91028] in Cypherpunks
Re: Hospitality for the Home and Office Invaders
daemon@ATHENA.MIT.EDU (Ryan Lackey)
Thu Nov 27 14:43:48 1997
To: cypherpunks@sirius.infonex.com
Date: Thu, 27 Nov 1997 14:12:29 EST
From: Ryan Lackey <rdl@mit.edu>
Reply-To: Ryan Lackey <rdl@mit.edu>
X-Yow: NOW, I'm taking the NEXT FLIGHT to ACAPULCO so I can write POEMS about
BROKEN GUITAR STRINGS and sensuous PRE-TEENS!!
X-spook: Qaddafi Treasury colonel NSA South Africa White Water
In-Reply-To: Lucky Green's message of Thu, 27 Nov 1997 08:29:00 +0100 (CET)
Message-ID: <tw7afeq44ea.fsf@tana.mit.edu>
Lines: 71
X-Mailer: Gnus v5.4.52/XEmacs 20.2
<shamrock@cypherpunks.to> (Lucky Green) writes:
> On 27 Nov 1997, Ryan Lackey wrote:
> >
> > ObCrypto: if I decide to use Goldwasser-Micali Probabilistic Encryption
> > (provable security for individual bits, etc. etc.), have I done anything
> > totally wrong? For TX of week-long session keys, as an alternative to
> > OTP.
>
> Is that the IBM scheme? If so, you have no guarantee to be able to recover
> the plaintext.
>
> -- Lucky Green <shamrock@cypherpunks.to> PGP v5 encrypted email preferred.
> "Tonga? Where the hell is Tonga? They have Cypherpunks there?"
No, it's the scheme that uses Quadratic Residuosity of bits to
probabilistically encode them. Prof. Micali's class (which I'm taking
this term), which used to be Prof. Goldwasser's class, uses it a lot --
they came up with it about 10 years ago. Way too much of my life this
fall has been spent proving silly things about the system.
rdl brazenly steals from the RSA crypto FAQ:
> Question 36. What is Probabilistic Encryption?
> Probabilistic encryption, discovered by Goldwasser and Micali
> [GM84], is a design approach for encryption where a message
> is encrypted into one of many possible ciphertexts (not just a
> single ciphertext as in deterministic encryption), in such a way
> that it is provably as hard to obtain partial information about the
> message from the ciphertext, as it is to solve some hard
> problem. In previous approaches to encryption, even though it
> was not always known whether one could obtain such partial
> information, neither was it proved that one could not do so.
> A particular example of probabilistic encryption given by
> Goldwasser and Micali operates on "bits" rather than "blocks"
> and is based on the quadratic residuosity problem.
> The problem is to find whether an integer x is a square modulo a
> composite integer n. (This is easy if the factors of n are known,
> but presumably hard if they are not.) In their example, a "0" bit
> is encrypted as a random square, and a "1" bit as a non-square;
> thus it is as hard to decrypt as it is to solve the quadratic
> residuosity problem. The scheme has substantial message expansion
> due to the bit-by-bit encryption of the message. Blum and Goldwasser
> later proposed an efficient probabilistic encryption scheme with
> minimal message expansion [BG85].
[GM84] S. Goldwasser and S. Micali. Probabilistic encryption.
Journal of Computer and System Sciences, 28: 270-299, 1984.
[BG85] M. Blum and S. Goldwasser. An efficient probabilistic public-key
encryption scheme which hides all partial information.
In Advances in Cryptology - Crypto '84, pages 289-299,
Springer-Verlag, 1985.
The BG system falls to chosen ciphertext. GM has a factor of n (size of
key, security parameter, etc.) data expansion...each bit is encrypted
separately. You still need to hash and sign to verify message integrity.
However, it is the only PK system I've found which is provably secure
against certain kinds of attacks.
ObIrrelevantViolence: it's fun taking over the kitchen to make carnivore
dishes, to the dismay of my veggie housemates.
--
Ryan Lackey
rdl@mit.edu
http://mit.edu/rdl/
