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
- On the implementation of cryptosystems based on real quadratic number fields (extended abstract)
- Two Generic Constructions of Probabilistic Cryptosystems and Their Applications
- New designing of cryptosystems based on quadratic fields
- A p + 1 Method of Factoring
- A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms
- Elliptic curve Paillier schemes
- Finding a small root of a univariate modular equation
- Lucas Pseudoprimes
- New public-key schemes based on elliptic curves over the ring \(\mathbb Z_ n\)
- On the security of the Lucas function
- Public-key cryptosystems based on composite degree residuosity classes
- Some remarks on Lucas-based cryptosystems
- The hardness of Hensel lifting: the case of RSA and discrete logarithm
- The XTR public key system
- 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
- Design and analysis of fast provably secure public-key cryptosystems based on a modular squaring
- 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)