LUC is a public-key cryptosystem [SS95] developed by a group of researchers in Australia and New Zealand. The cipher implements the analogs of ElGamal (see Question 29), Diffie-Hellman (see Question 24), and RSA (see Question 8) over Lucas sequences. LUCELG is the Lucas sequence analog of ElGamal, while LUCDIF and LUCRSA are the Diffie-Hellman and RSA analogs. Lucas sequences used in the cryptosystem are the general second-order linear recurrence relation defined by

*T _{n} = PT_{n}*-1 -

where* P* and *Q* are relatively prime integers. The encryption
of the message is computed by iterating the recurrence, instead of by exponentiation
as in RSA and Diffie-Hellman.

A recent paper by Bleichenbacher *et al.*
[BBL95] shows that many
of the supposed security advantages of LUC over cryptosystems based on
modular exponentiation are either not present, or not as substantial as
claimed.