An efficient probabilistic public-key cryptosystem over quadratic fields quotients
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.
- A new public-key cryptosystem over a quadratic order with quadratic decryption time.
- A public-key cryptosystem based on Lucas sequences
- scientific article; zbMATH DE number 1689013
- Two Generic Constructions of Probabilistic Cryptosystems and Their Applications
- New designing of cryptosystems based on quadratic fields
- A p + 1 Method of Factoring
- Elliptic curve Paillier schemes
- Finding a small root of a univariate modular equation
- scientific article; zbMATH DE number 176555 (Why is no real title available?)
- scientific article; zbMATH DE number 1024494 (Why is no real title available?)
- scientific article; zbMATH DE number 1030971 (Why is no real title available?)
- scientific article; zbMATH DE number 1759768 (Why is no real title available?)
- Lucas Pseudoprimes
- On the security of the Lucas function
- Public-Key Cryptosystems Based on Composite Degree Residuosity Classes
- The Hardness of Hensel Lifting: The Case of RSA and Discrete Logarithm
- A key-exchange system based on imaginary quadratic fields
- A generalized attack on RSA type cryptosystems
- A generalized attack on some variants of the RSA cryptosystem
- A public-key cryptosystem utilizing cyclotomic fields
- A new public-key cryptosystem over a quadratic order with quadratic decryption time.
- A Wiener-type attack on an RSA-like cryptosystem constructed from cubic Pell equations
- Cryptanalysis of RSA variants with primes sharing most significant bits
- A new cryptosystem using generalized Mersenne primes
- A new attack on three variants of the RSA cryptosystem
- An improved analysis on three variants of the RSA cryptosystem
- scientific article; zbMATH DE number 5308303 (Why is no real title available?)
- Two Generic Constructions of Probabilistic Cryptosystems and Their Applications
- Parallel computation for LUC cryptosystems on distributed memory multiprocessor machine
- scientific article; zbMATH DE number 1759646 (Why is no real title available?)
- Efficient probabilistic public-key cryptosystem based on the diffie-hellman problem
- A new attack on some RSA variants
- Further cryptanalysis of a type of RSA variants
- Partial prime factor exposure attacks on some RSA variants
- RSA quantum cryptanalysis: a thorough exploration of n-bit attacks and emerging factoring techniques
- A novel cryptanalytic attack on a family of RSA-like cryptosystems
- Further cryptanalysis of some variants of the RSA cryptosystem
- On integer sequences in cryptography
- SoK: a generalized attack on RSA and its variants
- Secure public-key encryption scheme without random oracles
This page was built for publication: An efficient probabilistic public-key cryptosystem over quadratic fields quotients
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2370640)
