NERDS - A Public-Key Encryption Scheme
With the advent of PDAs and other constrained computing environments come new security requirements that are not compliant with RSA and other typically trusted encryption schemes. To help meet this need, the CoreLabs team has developed The Non-Euclidean Ring Data Scrambler, NERDS, public-key encryption scheme. NERDS performs efficiently on a vast array of computer systems and works with minimal system requirements.
NERDS is based on certain number-theoretic problems on non-Euclidean rings (e.g., inverse norm). NERDS profits from the efficiency of polynomial multiplication and gets its security from the inverse norm problem for non-Euclidean rings. Roughly speaking, let Z[X] denote the ring of univariate polynomials with integer coefficients. On setup the user will select a non-euclidean ring A = Z[X]/p(X), and choose a private key n in A. The public key is given by a pair N,b in A where b is an invertible element of A/nA (actually it's class in A/nA), and
N is a multiple of n chosen such that the class of b is not invertible in A/NA. Encryption is simply defined by the homothety m → bm of A/NA, and decryption is defined by the map
c → b-¹c of A/nA (here b-¹ denotes a representative in A of the inverse of b in A/nA). Every element is represented by a polynomial of degree deg(p)-1, and efficiency follows from the efficiency of the polynomial ring Z[X].
NERDS was originally presented at a rump session at the Crypto 2001 conference in Santa Barbara, California (USA). Subsequently, the scheme has been publicly scrutinized and an effective attack was discovered. Research for a fix is ongoing.
- Kargieman, Emiliano | Pacetti, Ariel | Waissbein, Ariel; "A Non-Euclidean Ring Data Scrambler (NERDS) - a public-key cryptosystem", (CoreLabs Technical Report), 2000.