An efficient probabilistic public-key cryptosystem over quadratic fields quotients (Q2370640)

Quotients of quadratic fields feature in important primality tests and factoring. The LUC cryptosystem which was described by Smith, Lennon and Skinner in terms of Lucas sequences can be recast in this setting making its similarity to the RSA scheme clear. To this end, let \(d\) be an integer which is not a square, \(\mathcal O\) the ring of integers of \({\mathbb Q}(\sqrt d)\), \(n\) an integer prime to \(d\), \(N\) the norm on \({\mathbb Q}(\sqrt d)\) defined by \(N(x+y\sqrt d)=x^2-dy^2\) and Tr the trace defined by \(\text{Tr}(x+y\sqrt d)=2x\). Work in the multiplicative group \({(\mathcal O}/n{\mathcal O})^\times\) which is also the set of finite points on the conic \(X^2-dY^2=1\). Let \(d=P^2-4Q\) and define the Lucas sequences: \[ \begin{align*}{U_{k+1}(P,Q)&=PU_k(P,Q)-QU_{k-1}(P,Q), U_1(P,Q)=1, U_0(P,Q)=0\cr V_{k+1}(P,Q)&=PV_k(P,Q)-QV_{k-1}(P,Q), V_1(P,Q)=P, V_0(P,Q)=2\cr}\end{align*} \] Lucas sequences enable efficient exponentiation in \({\mathcal O}\). Let \(\alpha\equiv x+y\sqrt d\bmod n\). Then \[ \alpha^r\equiv {V_r(2x,N\alpha)\over 2}+yU_r(2x,N\alpha)\sqrt d, \quad \text{Tr}(\alpha^r)\equiv V_r(2x, N\alpha)\bmod n. \] Let \(n=pq\) where \(p,q\) are distinct odd primes and let \(e\) be an integer prime to \((p^2-1)(q^2-1)\). The \(\text{LUC}_e\) function is defined by \(x\rightarrow V_e(x)\). It is a permutation on the integers \(x\) with \(0<x<n\) and \(\text{gcd}(x^2-4,n)=1\) and the connection to exponentiation \(\alpha\rightarrow\alpha^e\) via the above congruence shows the analogy with the RSA function \(x\rightarrow x^e\) defined on the integers modulo \(n\). The properties of LUC can be derived from the relationship to exponentiation \(\alpha\rightarrow\alpha^e\) on \({\mathcal O}\bmod n\). For example, the inverse of \(\text{LUC}_e\) is \(\text{LUC}_d\) where \(de\equiv 1\bmod \phi_d(n)\) and \(\phi_d(n)=(p-({d\over p}))(q-({d\over q}))\) is the order of \({\mathcal O}\bmod n\). The author uses LUC to define a new probabilistic cryptosystem in the same way that Catalano, Gennaro, Howgrave-Graham and Nguyen used RSA. The encryption function is \[ {\mathcal E}_e: (m,r)\rightarrow (1+n)^mV_e(r)\bmod n^2 \] where \(m\) is in \({\mathbb Z}/n{\mathbb Z}\) and \(x\) is an integer with \(0<x<n, \text{ gcd}(x^2-4,n)=1, \text{ gcd}(x,n)=1\). To encrypt \(m\) take \(r\) randomly from \(\{1,2,\ldots,n-1\}\) and calculate \(c=(1+n)^mV_e(r)\bmod n^2\). The scheme appears to be at least as secure as RSA and the author shows that it is computationally competitive with other probabilistic schemes such as El Gamal's method based on RSA and elliptic curves.