Strict Standards: Declaration of APCBagOStuff::delete() should be compatible with BagOStuff::delete($key,$time = 0) in /usr/share/mediawiki1.7/includes/BagOStuff.php on line 499
Factoring - Wiki

# Factoring

##### FACTORING: integer factorisation problem

Definition: Given a positive integer $n \in \mathbb{N}$, find its prime factorisation $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ where the pi are pairwise distinct primes and ei > 0.

Reductions: SQRTP FACTORING, RSAPP FACTORING, Strong-RSAPP FACTORING

Algorithms: The best known algorithm for FACTORING is the Number Field Sieve which has complexity LN(1 / 3,c) for some constant c.

Use in cryptography:

##### SQRT: square roots modulo a composite

Definition: Given a composite positive integer $n \in \mathbb{N}$ and a square a modulo n, find a square root of a modulo n, this is, an integer x such that $x^2 \equiv a \pmod{n}$.

Reductions: SQRTP FACTORING

Algorithms: The best known algorithm for SQRT is to actually solve the FACTORING problem.

Use in cryptography: Rabin encryption

History:

References:

##### CHARACTERd: character problem

Definition: Let n and d be positive integers. Divise an algorithm which given $x \in \mathbb{Z}_n^*$ computes χ(x) where χ is a non-trivial character of $\mathbb{Z}_n^*$ of order d.

Reductions:

Algorithms:

Use in cryptography: Undeniable Signatures

History:

Remark: This can be seen as a generalisation of the quadratic residuosity problem.

References:

• J. Monnerat, S. Vaudenay, Undeniable Signatures Based on Characters: How to Sign with One Bit, PKC 2004.

Definition: Let $n\in \mathbb{Z}$, $s\in \mathbb{Z}^+$ and χ a hard character of order d on $\mathbb{Z}_n^*$. Given s pairs i,χ(αi)), where $\alpha_i\in\mathbb{Z}_n^*$ for all $i\in [1,..,s]$ and $x\in \mathbb{Z}_n^*$, compute χ(x).

Reductions: MOVAdCHARACTERd in some cases (as the characters in each cases may be independant), MOVAdCYCLOFACTd

Algorithms:

Use in cryptography: Undeniable Signatures

History:

Remark:

References:

• J. Monnerat, S. Vaudenay, Undeniable Signatures Based on Characters: How to Sign with One Bit, PKC 2004.

##### CYCLOFACTd: factorisation in $\mathbb{Z}[\theta]$

Definition: Let θ be a dth root of unity. Let σ be an element of $\mathbb{Z}[\theta]$, find the factorisation of θ.

Reductions: CYCLOFACTdFACTORING for d = 1,2,3,4.

Algorithms:

Use in cryptography:

History:

Remark:

References:

• J. Monnerat, S. Vaudenay, Undeniable Signatures Based on Characters: How to Sign with One Bit, PKC 2004.

##### FERMATd: factorisation in $\mathbb{Z}[\theta]$

Definition: Let θ be a dth root of unity. Let $n\in \mathbb{Z}$ be such that $n=\pi\bar\pi$ for some $\pi \in \mathbb{Z}[\theta]$. Given n, find π.

Reductions: FERMATdCYCLOFACTd for d = 1,2,3,4, FERMAT3 ≡ Finding a square root of − 3 modulo n, for some n for which − 3 is a quadratic residue, FERMAT4 ≡ Finding a square root of − 1 modulo n, for some n for which − 1 is a quadratic residue.

Algorithms:

Use in cryptography:

History:

Remark:

References:

• J. Monnerat, S. Vaudenay, Undeniable Signatures Based on Characters: How to Sign with One Bit, PKC 2004.

##### RSAP: RSA problem

Definition: Given a positive integer n which is the product of at least two primes, an integer e coprime with $\varphi(n)$ and an integer c, find an integer m such that $m^e \equiv c \pmod{n}$.

Reductions: RSAPP FACTORING, Strong-RSAPP RSAP

Algorithms: The best known attack is to use the reduction to FACTORING. However, there are a number of results which either point to seperation between the RSA Problem and FACTORING, or point to their equivalence. The issue of this seperation is a topic of current research.

Use in cryptography: The RSA cryptosystem.

History:

References:

##### Strong-RSAP: strong RSA problem

Definition: Given a positive integer n which is the product of at least two primes and an integer c, find an odd integer $e \geq 3$ and an integer m such that $m^e \equiv c \pmod{n}$.

Reductions: Strong-RSAPP FACTORING, Strong-RSAPP RSAP

Algorithms: Again the best known attack is reduction to the FACTORING problem.

Use in cryptography: Cramer-Shoup signatures

History:

References:

##### Difference-RSAP: Difference RSA problem

Definition: Given a positive integer n which is the product of at least two primes, an element $D \in Z_n^*$ and m-1 pairs (xi,yi) such that $x_i^e-y_i^e=D \pmod{n}$, for chosen xi, find a new pair (xm,ym) such that $x_m^e-y_m^e=D \pmod{n}$.

Reductions: Difference-RSAPP FACTORING, Difference-RSAPP RSAP

Algorithms: Again the best known attack is reduction to the FACTORING problem.

Use in cryptography:

History:

References:

• M. Naor, On Cryptographic Assumptions and Challenges, Invited paper, Crypto 2003.

##### Partial-DL-ZN2P: Partial Discrete Logarithm problem in $\mathbb{Z}_{n^2}^*$

Definition: Given a positive integer n such that n=pq with p=2p'+1 and q=2q'+1, for prime numbers p,p',q,q', an element $g \in \mathbb{Z}_{n^2}^*$ of maximal order in $G=QR_{n^2}$ and h = gamod n2 for some $a\in \{1,\ldots,ord(G)\}$, find an integer x such that x = a(mod n).

Reductions: Partial-DL-ZN2PP FACTORING

Algorithms: The problem is not harder than the FACTORING problem.

Use in cryptography: Homomorphic public key encryption, public key encryption with double trapdoor decryption mechanism

History:

References:

• P. Paillier, Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, Eurocrypt 1999.
• E. Bresson, D. Catalano, D. Pointcheval, A Simple Public Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications, Asiacrypt 2003.

##### DDH-ZN2P: Decision Diffie-Hellman problem over $\mathbb{Z}_{n^2}^*$

Definition: Given a positive integer n such that n=pq with p=2p'+1 and q=2q'+1, for prime numbers p,p',q,q', an element $g \in \mathbb{Z}_{n^2}^*$ of maximal order in $G=QR_{n^2}$, elements X = gxmod n2, Y = gymod n2, for some $x,y \in \{1,\ldots,ord(G)\}$, and $Z \in G$, decide whether Z = gxymod n2.

Reductions: DDH-ZN2PP FACTORING

Algorithms: The problem is not harder than the FACTORING problem.

Use in cryptography: Public key encryption with double trapdoor decryption mechanism

History:

References:

• E. Bresson, D. Catalano, D. Pointcheval, A Simple Public Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications, Asiacrypt 2003.

##### Lift-DH-ZN2P: Lift Diffie-Hellman problem over $\mathbb{Z}_{n^2}^*$

Definition: Given a positive integer n such that n=pq with p=2p'+1 and q=2q'+1, for prime numbers p,p',q,q', an element $g \in \mathbb{Z}_{n^2}^*$ of maximal order in $G=QR_{n^2}$, elements X = gxmod n2, Y = gymod n2, for some $x,y \in \{1,\ldots,ord(G)\}$, and Z = gxymod n, find Z' = gxymod n2.

Reductions: Partial-DL-ZN2PP Lift-DH-ZN2P

Algorithms:

Use in cryptography: Public key encryption with double trapdoor decryption mechanism

History:

References:

• E. Bresson, D. Catalano, D. Pointcheval, A Simple Public Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications, Asiacrypt 2003.

##### EPHP: Election Privacy Homomorphism problem

Definition: Given a fixed small prime e, a prime p such that e | (p − 1), and a prime q such that $e\not|(q-1)$ let n = pq and let $g\in \mathbb{Z}_n$ such that e divides the order of g. We refer to the group generated by g as G.

The EPHP problem is to decide for $w \in G$ and $v \in [0,e]$ whether w = gv + er for some $r \in N$. This should be done with a probability significantly greater than (e − 1) / e.

Reductions: EPHPP Partial-DL-ZN2PP FACTORING

Algorithms:

Use in cryptography: Homomorphic public key encryption and electronic voting protocols

References:

• Kenneth R. Iversen: A Cryptographic Scheme for Computerized Elections. CRYPTO 1991: 405-419

##### AERP: Approximate e-th root problem

Definition: Given a positive integer n which is of the form p2q, with p, q prime and | n | = 3k, an integer $e\geq 4$ and a $y\in Z_n$, find an integer x such that $(x^e \;\mathit{ mod } \;n) \in I_k(y)$, where $I_k(y)=\{u | y\leq u < y+2^{2k-1}\}$.

Reductions: AERPP FACTORING

Algorithms: The best known attack is to use the reduction to FACTORING.

Use in cryptography: The ESIGN signature scheme.

History:

References:

• Jacques Stern: Why Provable Security Matters? EUROCRYPT 2003: 449-461

##### l-HENSEL-RSAP: l-Hensel RSA

Definition: Given N = pq, e coprime with φ(N), and xe(mod N) for a random integer 1 < x < N, compute $x^e \pmod{N^\ell}$.

Reductions: 2-HENSEL-RSAPP RSAP for a public exponent e coprime with N.

3-HENSEL-RSAPP CLASS for the public exponent e = N.

Algorithms:

Use in cryptography: Public-key encryption

References:

• Dario Catalano, Phong Q. Nguyen, and Jacques Stern, The Hardness of Hensel Lifting: The Case of RSA and Discrete Logarithm, ASIACRYPT 2002, LNCS 2501, pp. 299–310.

##### DSeRP: Decisional Small e-Residues in $\mathbb{Z}_{n^2}^*$

Definition: Given a positive integer n such that n=pq for prime numbers p,q and an integer e>2 such that gcd(e,n(p − 1)(q − 1)) = 1, distinguish the distributions $D_0=\{c=r^{e} \bmod n^2 | r \in_R \mathbb{Z}_n \}$ and $D_1=\{ c \in_R \mathbb{Z}_{n^2} \}$.

Reductions: DSeRPP RSAPP FACTORING

Algorithms:

Use in cryptography: Semantically secure public key encryption from Paillier-related assumptions

History:

References:

• D. Catalano, R. Gennaro, N. Howgrave-Graham, P. Nguyen, Paillier's Cryptosystem Revisited, ACM-CCS 2001.

##### DS2eRP: Decisional Small 2e-Residues in $\mathbb{Z}_{n^2}^*$

Definition: Given a positive integer n such that n=pq for prime numbers p,q such that p = q = 3mod 4 and an integer e such that gcd(e,n(p − 1)(q − 1)) = 1 and | n | / 2 < e < | n | , distinguish the distributions $D_0=\{c=r^{2e} \bmod n^2 | r \in_R QR_n \}$ and $D_1=\{ c \in_R QR_{n^2} \}$.

Reductions: DS2eRPP FACTORING

Algorithms:

Use in cryptography: Semantically secure public key encryption mixing Paillier and Rabin functions

History:

References:

• D. Galindo, S. Martin, P. Morillo, J. L. Villar, A Practical Public Key Cryptosystem from Paillier and Rabin Schemes, Public Key Cryptography 2003.
• K. Kurosawa, T. Takagi, Some RSA-Based Encryption Schemes with Tight Security Reduction, Asiacrypt 2003.

##### DSmallRSAKP: Decisional Reciprocal RSA-Paillier in $\mathbb{Z}_{n^2}^*$

Definition: Given a positive integer n such that n=pq for prime numbers p,q, an element α such that (α / p) = (α / q) = − 1, an integer e such that | n | / 2 < e < | n | , distinguish the distributions $D_0=\{ (n,e,\alpha,c) | c=\big(r + \frac{\alpha}{r} \big)^e \bmod n^2,~r\in_R \mathbb{Z}_n~s.t.~(r/n)=1,~(\alpha/r ~\bmod n)>r \}$ and $D_1=\{ (n,e,\alpha,c) | c=\big(r + \frac{\alpha}{r} \big)^e \bmod n^2,~r \in_R \mathbb{Z}_{n^2} \}$.

Reductions: DSmallRSAKPP FACTORING

Algorithms:

Use in cryptography: Semantically secure public key encryption from Paillier-related assumptions

History:

References:

• K. Kurosawa, T. Takagi, Some RSA-Based Encryption Schemes with Tight Security Reduction, Asiacrypt 2003.

##### HRP: Higher Residuosity Problem

Definition: Let n and a be positive integers such that $a \mid \phi(n)$. Given $x \in Z_n^*$, decide whether there exists y such that ya = x.

Reductions: HRPP FACTORING

Algorithms: The best known <= algorithm is to factor n first. There are algorithms solving this problem efficiently when the factorization of n is known.

Use in cryptography: Convertible Group Signatures, Public Key Encryption.

History:

Remark: The special case a = 2 corresponds to the quadratic residuosity problem.

References:

• S.J. Kim, S.J. Park, D.H. Won, Convertible Group Signatures, Proceedings of Asiacrypt '96, p.311-321.
• D. Naccache and J. Stern, A New Public Key Cryptosystem Based on Higher Residues, ACM Conference on Computer and Communications Security, 1998, p. 59-66.
• B. Pfitzmann, M. Schunter, Asymmetric Fingerprinting, Proceedings of Eurocrypt '96, p. 84-95.

##### ECSQRT: Square roots in elliptic curve groups over $\mathbb{Z}/n\mathbb{Z}$

Definition: Let $E(\mathbb{Z}/n\mathbb{Z})$ be the elliptic curve group over $\mathbb{Z}/n\mathbb{Z}$. Given a point $Q \in E(\mathbb{Z}/n\mathbb{Z})$. Compute all points $P \in E(\mathbb{Z}/n\mathbb{Z})$ such that 2P = Q.

Reductions: ECSQRTP FACTORING

Algorithms: The best algorithm for ECSQRT is to solve the FACTORING problem.

Use in cryptography: Public Key Encryption

History:

References:

• B. Meyer, V. Müller, A Public-Key Cryptosystem Based on Elliptic Curves over $\mathbb{Z}/n\mathbb{Z}$ Equivalent to Factoring. Proceedings of Eurocrypt '96, p. 49-59.

##### RFP: Root Finding Problem

Definition: Compute one (all) root(s) of a polynomial f(x) over the ring $\mathbb{Z}_n$, where n = pq is the product of two large primes..

Reductions: RFPP FACTORING whenever f(x) has at least two different roots.

Algorithms: The best algorithm for RFP is to solve the FACTORING problem.

Use in cryptography: Public key encryption and signature schemes

History:

References:

• J. Schwenk and J. Eisfeld, Public Key Encryption and Signature schemes based on Polynomials over $\mathbb{Z}_n$. Proceedings of Eurocrypt '96, p. 60-71.

##### phiA: PHI-Assumption

Preliminaries and notation: Let PRIMESa be the set of all primes of length a and Ha be the set of the composite integers that are product of two primes of length a. We say that a composite integer m φ-hides a prime p if p | φ(m). Denote by Hb(m) the set of b-bit primes p that are φ-hidden by m, and denote by $\bar{H}^b(m)$ the set PRIMESbHb(m).

Definition: φ-Hiding Assumption: $\exist e,f,g,h > 0$ such that: $\forall k > h and \forall 2^{ek}$-gate circuits C, $Pr[m \leftarrow H^k; p_0 \leftarrow H^k(m); p_1 \leftarrow \bar{H}^k(m); b \leftarrow {0,1}: C(m,p_b)=b ] > 1/2 + 2^{-gk}$.

φ-Sampling Assumption: $\exist e,f,g,h > 0$ such that: $\forall k > h$ there exists a sampling algorithm S() such that for all k-bit primes p, S(p) outputs a random kf-bit number $m \in H^k_{k^f}$ that φ-hides p together with m's integer factorization.

Reductions:

Algorithms:

References:

• C. Cachin, S. Micali and M. Stadler, Computationally Private Information Retrival with Polylogarithmic Communication, EUROCRYPT 1999, LNCS 1592, pp. 402-414.

##### C-DRSA: Computational Dependent-RSA problem

Definition: Given (N,e) as above and $\alpha \in \mathbb{Z}_n^*$ find (a + 1)e(mod n) where α = ae(mod n).

Reductions: C-DRSA <P RSA. It also holds: RSAP C-DRSA + E-DRSA

Use in cryptography: DRSA-2 encryption scheme by Pointcheval (see the reference below)

References:

• D. Pointcheval, New Public Key Cryptosystems Based on the Dependent-RSA Problems, EUROCRYPT 1999, LNCS 1592, pp. 239-254.

##### D-DRSA: Decisional Dependent-RSA problem

Definition: Given (N,e) as above, $\alpha=a^e \pmod{n}, \gamma \in \mathbb{Z}_n^*$ distinguish if γ = (a + 1)e(mod n) or γ = ce(mod n) where a,c are taken at random in $\mathbb{Z}_n^*$.

Reductions: D-DRSA <P C-DRSA, D-DRSA <P E-DRSA.

Algorithms: The gcd technique seems to be the best known attack against the D-DRSA problem and is impractical as soon as the exponent e is greater than 260. Which leads to the following conjecture: D-DRSA is intractable as soon as the exponent e is greater than 260, for large enough RSA moduli.

Use in cryptography: DRSA encryption scheme by Pointcheval.

References:

• D. Pointcheval, New Public Key Cryptosystems Based on the Dependent-RSA Problems, EUROCRYPT 1999, LNCS 1592, pp. 239-254.

##### E-DRSA: Extraction Dependent-RSA problem

Definition: Given (N,e) as above and $\alpha = a^e \in \mathbb{Z}_n^*$ and $\gamma=(a+1)^e \in \mathbb{Z}_n^*$, find a(mod n).

Reductions: E-DRSA <P RSA. It also holds: RSAP C-DRSA + E-DRSA

Use in cryptography:

References:

• D. Pointcheval, New Public Key Cryptosystems Based on the Dependent-RSA Problems, EUROCRYPT 1999, LNCS 1592, pp. 239-254.

##### DCR: Decisional Composite Residuosity problem

Definition: Given a composite n and an integer z, decide if z is a n-residue modulo n2 or not, namely if there exists y such that z = yn(mod n2).

Reductions: DCRP DCRC <PCRC <P FACTORING.

Use in cryptography: Paillier's cryptosystem

References:

• P. Paillier, Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, Eurocrypt 1999.

##### CRC: Composite Residuosity Class problem

Definition: Denote by $B_{\alpha} \subset \mathbb{Z}_{n^2}^*$ the set of elements of order nα and by B their disjoint union for $\alpha=1, \cdots, \lambda$ where λ = λ(n) is the Carmichael's function taken on n. Given a composite n and $w \in \mathbb{Z}_{n^2}^*, g \in B$, compute the n-residuosity class of w with respect to g: [w]g.

Reductions: CRC <P FACTORING.

Use in cryptography:

References:

• P. Paillier, Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, Eurocrypt 1999.

##### DCRC: Decisional Composite Residuosity Class problem

Definition: Denote by $B_{\alpha} \subset \mathbb{Z}_{n^2}^*$ the set of elements of order nα and by B their disjoint union for $\alpha=1, \cdots, \lambda$ where λ = λ(n) is the Carmichael's function taken on n. Given a composite n, $w \in \mathbb{Z}_{n^2}^*, g \in B, x \in \mathbb{Z}_n$, decide wether x = [w]g or not.

Reductions: DCRC <PCRC <P FACTORING.

Use in cryptography:

References:

• P. Paillier, Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, Eurocrypt 1999.

##### GenBBS: generalised Blum-Blum-Shub assumption

Definition: Given a composite positive integer $n \in \mathbb{N}$ and a sequence $g, g^2 \pmod{n}, g^4 \pmod{n}, g^8 \pmod{n}, \dots, g^{2^{2^k}} \pmod{n}$ to distinguish $g^{2^{2^{k+1}}} \pmod{n}$ from a random r2(mod n).

Reductions: GenBBSP FACTORING

Algorithms: The best known algorithm for GenBBS is to actually solve the FACTORING problem.

Use in cryptography: Timed commitments.

History:

References: D. Boneh and M. Naor, `Timed commitments', CRYPTO 2000.