What is LUC?

LUC is a public-key cryptosystem 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 - QT_n-2

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.