# Factoring

### From Wiki

##### FACTORING: integer factorisation problem

Definition: Given a positive integer , find its prime factorisation
where the *p*_{i} are pairwise distinct primes and *e*_{i} > 0.

Reductions: SQRT ≡_{P} FACTORING, RSAP ≤_{P} FACTORING,
Strong-RSAP ≤_{P} FACTORING

Algorithms: The best known algorithm for FACTORING is the Number Field Sieve which has
complexity *L*_{N}(1 / 3,*c*) for some constant *c*.

Use in cryptography:

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

Definition: Given a composite positive integer and a square *a* modulo *n*, find a square root
of *a* modulo *n*, this is, an integer *x* such that .

Reductions: SQRT ≡_{P} FACTORING

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

Use in cryptography: Rabin encryption

History:

References:

##### CHARACTER^{d}: character problem

Definition: Let *n* and *d* be positive integers. Divise
an algorithm which given computes
χ(*x*) where χ is a non-trivial character of
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.

##### MOVA^{d}: character problem

Definition: Let , and χ a hard character of order *d* on . Given *s* pairs (α_{i},χ(α_{i})), where for all and , compute χ(*x*).

Reductions: MOVA^{d} ≤ CHARACTER^{d} in some cases (as the characters in each cases may be independant),
MOVA^{d} ≤ CYCLOFACT^{d}

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.

##### CYCLOFACT^{d}: factorisation in

Definition: Let θ be a *d*^{th} root of unity. Let σ be an element of , find the factorisation of θ.

Reductions: CYCLOFACT^{d} ≡ FACTORING 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.

##### FERMAT^{d}: factorisation in

Definition: Let θ be a *d*^{th} root of unity. Let be such that for some . Given *n*, find π.

Reductions: FERMAT^{d} ≤ CYCLOFACT^{d} for *d* = 1,2,3,4,
FERMAT^{3} ≡ Finding a square root of − 3 modulo *n*, for some *n* for which − 3 is a quadratic residue,
FERMAT^{4} ≡ 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:

##### RSAP: RSA problem

Definition: Given a positive integer *n* which is the product of at least two primes, an integer
*e* coprime with and an integer *c*, find an integer *m* such that
.

Reductions: RSAP ≤_{P} FACTORING, Strong-RSAP ≤_{P} 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 and an integer *m* such that .

Reductions: Strong-RSAP ≤_{P} FACTORING, Strong-RSAP ≤_{P} 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 and m-1 pairs (*x*_{i},*y*_{i}) such that , for chosen *x*_{i},
find a new pair (*x*_{m},*y*_{m}) such that .

Reductions: Difference-RSAP ≤_{P} FACTORING, Difference-RSAP ≤_{P} 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

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 of maximal order in and *h* = *g*^{a}mod *n*^{2} for some , find an integer *x* such that *x* = *a*(mod *n*).

Reductions: Partial-DL-ZN2P ≤_{P} 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

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 of maximal order in , elements *X* = *g*^{x}mod *n*^{2}, *Y* = *g*^{y}mod *n*^{2}, for some , and , decide whether *Z* = *g*^{xy}mod *n*^{2}.

Reductions: DDH-ZN2P ≤_{P} 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

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 of maximal order in , elements *X* = *g*^{x}mod *n*^{2}, *Y* = *g*^{y}mod *n*^{2}, for some , and *Z* = *g*^{xy}mod *n*, find *Z*' = *g*^{xy}mod *n*^{2}.

Reductions: Partial-DL-ZN2P ≤_{P} 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 let *n* = *p**q* and let 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 and whether *w* = *g*^{v + er} for some . This should be done with a probability significantly greater than (*e* − 1) / *e*.

Reductions: EPHP ≤_{P} Partial-DL-ZN2P ≤_{P} 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 *p*^{2}*q*, with p, q prime and | *n* | = 3*k*, an integer
and a , find an integer *x* such that
, where .

Reductions: AERP ≤_{P} 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* = *p**q*, *e* coprime with φ(*N*), and *x*^{e}(mod *N*) for a random integer 1 < *x* < *N*, compute .

Reductions:
2-HENSEL-RSAP ≡_{P} RSAP for a public exponent *e* coprime with *N*.

3-HENSEL-RSAP ≡_{P} 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

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 and .

Reductions: DSeRP ≤_{P} RSAP ≤_{P} 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

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 and .

Reductions: DS2eRP ≤_{P} 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

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 and .

Reductions: DSmallRSAKP ≤_{P} 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 . Given , decide whether there exists *y* such that *y*^{a} = *x*.

Reductions: HRP ≤_{P} 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

Definition: Let be the elliptic curve group over . Given a point . Compute all points such that 2*P* = *Q*.

Reductions: ECSQRT ≡_{P} 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 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 , where *n* = *p**q* is the product of two large primes..

Reductions: RFP ≡_{P} 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 . Proceedings of Eurocrypt '96, p. 60-71.

##### phiA: PHI-Assumption

Preliminaries and notation: Let *P**R**I**M**E**S*_{a} be the set of all primes of length *a* and *H*_{a} 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 *H*^{b}(*m*) the set of b-bit primes *p* that are φ-hidden by *m*, and denote by the set *P**R**I**M**E**S*_{b} − *H*^{b}(*m*).

Definition: φ-Hiding Assumption: such that: -gate circuits C, .

φ-Sampling Assumption: such that: there exists a sampling algorithm *S*() such that for all k-bit primes p, *S*(*p*) outputs a random *k*^{f}-bit number 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 find (*a* + 1)^{e}(mod *n*) where α = *a*^{e}(mod *n*).

Reductions: C-DRSA <_{P} RSA. It also holds: RSA ≡_{P} 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, distinguish if γ = (*a* + 1)^{e}(mod *n*) or γ = *c*^{e}(mod *n*) where *a*,*c* are taken at random in .

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 2^{60}. Which leads to the following conjecture:
D-DRSA is intractable as soon as the exponent e is greater than 2^{60}, 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 and , find *a*(mod *n*).

Reductions: E-DRSA <_{P} RSA. It also holds: RSA ≡_{P} 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 *n*^{2} or not, namely if there exists *y* such that *z* = *y*^{n}(mod *n*^{2}).

Reductions: DCR ≡_{P} DCRC <_{P}CRC <_{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 the set of elements of order *n*α and by *B* their disjoint union for where λ = λ(*n*) is the Carmichael's function taken on *n*.
Given a composite *n* and , 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 the set of elements of order *n*α and by *B* their disjoint union for where λ = λ(*n*) is the Carmichael's function taken on *n*.
Given a composite *n*, , decide wether *x* = [*w*]_{g} or not.

Reductions: DCRC <_{P}CRC <_{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 and a sequence to distinguish from a random *r*^{2}(mod *n*).

Reductions: GenBBS ≤_{P} 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.