Factoring

From Wiki

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 $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:

[edit]

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: SQRT ≡_P FACTORING

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

Use in cryptography: Rabin encryption

History:

References:

[edit]

CHARACTER^d: 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.

[edit]

MOVA^d: character problem

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

[edit]

CYCLOFACT^d: factorisation in $\mathbb{Z}[\theta]$

Definition: Let $θ$ be a $d t h$ root of unity. Let $σ$ be an element of $\mathbb{Z}[\theta]$ , 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.

[edit]

FERMAT^d: factorisation in $\mathbb{Z}[\theta]$

Definition: Let $θ$ be a $d t h$ 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: FERMAT^d ≤ CYCLOFACT^d for $d = 1,2,3,4$ , FERMAT³ ≡ Finding a square root of $- 3$ modulo $n$ , for some $n$ for which $- 3$ is a quadratic residue, FERMAT⁴ ≡ 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.

[edit]

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: 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:

[edit]

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-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:

[edit]

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 $(x i, y i)$ such that $x_i^e-y_i^e=D \pmod{n}$ , for chosen $x i$ , find a new pair $(x m, y m)$ such that $x_m^e-y_m^e=D \pmod{n}$ .

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.

[edit]

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 = g a mod n 2$ for some $a\in \{1,\ldots,ord(G)\}$ , 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.

[edit]

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 = g x mod n 2$ , $Y = g y mod n 2$ , for some $x,y \in \{1,\ldots,ord(G)\}$ , and $Z \in G$ , decide whether $Z = g x y 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.

[edit]

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 = g x mod n 2$ , $Y = g y mod n 2$ , for some $x,y \in \{1,\ldots,ord(G)\}$ , and $Z = g x y mod n$ , find $Z' = g x y 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.

[edit]

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 = p q$ 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 = g v + e r$ for some $r \in N$ . 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

[edit]

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 $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: 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

[edit]

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 $x^e \pmod{N^\ell}$ .

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.

[edit]

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

[edit]

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

[edit]

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

[edit]

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

[edit]

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 $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 $\mathbb{Z}/n\mathbb{Z}$ Equivalent to Factoring. Proceedings of Eurocrypt '96, p. 49-59.

[edit]

RFP: Root Finding Problem

Definition: Compute one (all) root(s) of a polynomial $f (x)$ over the ring $\mathbb{Z}_n$ , 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 $\mathbb{Z}_n$ . Proceedings of Eurocrypt '96, p. 60-71.

[edit]

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 $\bar{H}^b(m)$ the set $P R I M E S b - H b (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 $k f$ -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.

[edit]

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 $α = 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.

[edit]

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 $γ = c e (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 2⁶⁰. Which leads to the following conjecture: D-DRSA is intractable as soon as the exponent e is greater than 2⁶⁰, 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.

[edit]

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

[edit]

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 <_PCRC <_P FACTORING.

Use in cryptography: Paillier's cryptosystem

References:

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

[edit]

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.

[edit]

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.

[edit]

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

Retrieved from "http://www.ecrypt.eu.org/wiki/index.php/Factoring"

Factoring

From Wiki

FACTORING: integer factorisation problem

SQRT: square roots modulo a composite

CHARACTER^d: character problem

MOVA^d: character problem

CYCLOFACT^d: factorisation in $\mathbb{Z}[\theta]$

FERMAT^d: factorisation in $\mathbb{Z}[\theta]$

RSAP: RSA problem

Strong-RSAP: strong RSA problem

Difference-RSAP: Difference RSA problem

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

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

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

EPHP: Election Privacy Homomorphism problem

AERP: Approximate e-th root problem

l-HENSEL-RSAP: l-Hensel RSA

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

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

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

HRP: Higher Residuosity Problem

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

RFP: Root Finding Problem

phiA: PHI-Assumption

C-DRSA: Computational Dependent-RSA problem

D-DRSA: Decisional Dependent-RSA problem

E-DRSA: Extraction Dependent-RSA problem

DCR: Decisional Composite Residuosity problem

CRC: Composite Residuosity Class problem

DCRC: Decisional Composite Residuosity Class problem

GenBBS: generalised Blum-Blum-Shub assumption

Views

Personal tools

Navigation

Search

Toolbox

Factoring

From Wiki

FACTORING: integer factorisation problem

SQRT: square roots modulo a composite

CHARACTERd: character problem

MOVAd: character problem

CYCLOFACTd: factorisation in

FERMATd: factorisation in

RSAP: RSA problem

Strong-RSAP: strong RSA problem

Difference-RSAP: Difference RSA problem

Partial-DL-ZN2P: Partial Discrete Logarithm problem in

DDH-ZN2P: Decision Diffie-Hellman problem over

Lift-DH-ZN2P: Lift Diffie-Hellman problem over

EPHP: Election Privacy Homomorphism problem

AERP: Approximate e-th root problem

l-HENSEL-RSAP: l-Hensel RSA

DSeRP: Decisional Small e-Residues in

DS2eRP: Decisional Small 2e-Residues in

DSmallRSAKP: Decisional Reciprocal RSA-Paillier in

HRP: Higher Residuosity Problem

ECSQRT: Square roots in elliptic curve groups over

RFP: Root Finding Problem

phiA: PHI-Assumption

C-DRSA: Computational Dependent-RSA problem

D-DRSA: Decisional Dependent-RSA problem

E-DRSA: Extraction Dependent-RSA problem

DCR: Decisional Composite Residuosity problem

CRC: Composite Residuosity Class problem

DCRC: Decisional Composite Residuosity Class problem

GenBBS: generalised Blum-Blum-Shub assumption

Views

Personal tools

Navigation

Search

Toolbox

CHARACTER^d: character problem

MOVA^d: character problem

CYCLOFACT^d: factorisation in $\mathbb{Z}[\theta]$

FERMAT^d: factorisation in $\mathbb{Z}[\theta]$

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

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

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

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

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

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

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