Assumption - Zoo

I know that this list is far from being complete. This site is heavily under construction and i will complete the enumeration from time to time. See also the document from ECrypt, which is a very comprehensive list of assumption.

I will add from time to time a small example for each assumption, with a bitsize such that the toy instance should be solveable for (mostly) everybody with a little coding skills.

1. Integer Factoring

Integer Factoring Assumption Description: Given an $k$-bit integer $N$, then the task to find $N$'s prime factorization $N = p_1^{e_1}...p_m^{e_m}$ is assumed to be hard. E.g. used in: Dennis Hofheinz, Eike Kiltz, Victor Shoup: Practical Chosen Ciphertext Secure Encryption from Factoring. J. Cryptology 26(1): 102-118 (2013)

Factor the balanced RSA-Modulus:
N = 85386100664860528053641167981538321005181798385749705139376237339340778739897 (256-bit)

RSA Assumption  Description: Given a RSA public key $(e,N)$ as well as a ciphertext $c \equiv m^e \pmod{N}$, for some secret message $m$. Then the task to compute $m$ given only $(e,N)$ and $c$ is assumed to be hard. E.g. used in: Rivest, R.; A. Shamir; L. Adleman (1978). "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems". Communications of the ACM 21 (2): 120–126.

RSA Instance (plaintext is ASCII):
N = 58904824382002760628373360619171746276508356388689857825374232574996100508073 (256-bit)
e = 3
c = 57503508358159947345082062226328132978094847736943208483653218522110040303126

Strong RSA Assumption  Description:  Given a RSA public key $(e,N)$ as well as a ciphertext $c \equiv m^e \pmod{N}$, for some secret message $m$. Then the task to compute any integer $M$, such that $c \equiv M^{E}\pmod{N}$ for an odd integer $E$ given only $(e,N)$ and $c$ is assumed to be hard. (The RSA Assumption is to force $E = e$). E.g. used in: Ronald Cramer and Victor Shoup. Signature schemes based on the strong RSA assumption. ACM Transactions on Information and System Security, 3(3):161–185, 2000.

Difference RSA Assumption  Description:  Given a RSA public key $(e,N)$ and $D \in \mathbb{Z}^*_N$ as well as $m-1$ pairs $(x_i,y_i)$ such that $x_i^e - y_i^e \equiv D\pmod{N}$, then the task to find a new pair $(x_m,y_m)$ such that $y_m^e - x_m^e \equiv D\pmod{N}$ is assumed to be hard. E.g. used in: M. Naor, On Cryptographic Assumptions and Challenges, Invited paper, Crypto 2003.

Quadratic Residuosity Assumption Description:  Let $N=pq$ with two odd secret primes $p$ and $q$ and let $\mathbb{QR} = \{a \in \mathbb{Z}^*_N | \binom{a}{p} = \binom{a}{q} = 1\}$ as well as $\mathbb{QNR} = \{a \in \mathbb{Z}^*_N | \binom{a}{p} = \binom{a}{q} = -1\}$, then the task to decide better than random guessing, given only $N$ and $a$, if $a \in \mathbb{QR}$ or $a \in \mathbb{QNR}$ is assumed to be hard. E.g. used in: S. Goldwasser, S. Micali (1982). "Probabilistic encryption and how to play mental poker keeping secret all partial information". Proc. 14th Symposium on Theory of Computing: 365–377.

Higher Residuosity Assumption Description:  Let $N=pq$ with two odd secret primes $p$ and $q$ and let $d > 1$ be an odd integer such that $d|(p-1)$, then given only $N,d$ and an integer $a < N$, the the task to decide better than random guessing if $a$ is a $d$-th residue (i.e. $\exists b < N$ such that $b^d \equiv a\pmod{N}$) is assumed to be hard. (Setting $d = 2$ and picking $a$ only from the subset of integers $< N$ with positive Jacoby symbol is equal to the Quadratic Residuosity Assumption). E.g. used in: Benaloh, J. ,Dense Probabilistic Encryption, Proceedings of the Workshop on Selected Areas of Cryptography. Kingston, ON. May 1994. pp. 120--128.

Decisional Composite Residuosity Assumption Description:  Let $N=pq$ with two odd secret primes $p$ and $q$. Then given only an integer $z < N^2$ and $N$ itself, the the task to decide better than random guessing if $z$ is a $N$-th residue modulo $N^2$ (i.e. $\exists b < N^2$ such that $b^N \equiv z\pmod{N^2}$) is assumed to be hard. E.g. used in: P. Paillier, Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, Eurocrypt 1999.

Phi-hiding Assumption Description:  Let $N$ be an integer with unknown factorization. Let $\rho_1$ and $\rho_2$ be two primes in the interval $N^{1/4} > \rho_1, \rho_2 > 3$. The setup is chosen that way, that exactly one of these two primes $\rho_1$ and $\rho_2$ divides $\varphi(N)$. Then the task to decide better than random guessing, given only the triple $N,\rho_1,\rho_2$, which of them divides $\varphi(N)$ is assumed to be hard. E.g. used in: Cachin, Christian; Micali, Silvio; Stadler, Markus (1999). Computationally Private Information Retrieval with Polylogarithmic Communication. In Stern, Jacques. Lecture Notes in Computer Science (Springer) 1592: 402–414.

 

2. Discrete Logarithm

The Discrete Logarithm Assumption Description:  Let $g$ be a generator of prime order that generates the group $\mathbb{G}$. Then given $g,\mathbb{G}$ and an group element $r$, the task to compute the integer $x$ such that $g^x = r$ is assumed to be hard. E.g. used in: Schnorr (1989). "Efficient Identification and Signatures for Smart Cards". Proceedings of CRYPTO '89.

The Computational Diffie-Hellman Assumption Description:  Let $g$ be a generator of prime order that generates the group $\mathbb{G}$. Then given the group elements $g^x,g^y$ for random integers $x,y$, the task to compute the integer $g^{xy}$ is assumed to be hard. A triple $(g^x,g^y,g^{xy})$ is called a Diffie-Hellman triple. E.g. used in: Diffie, W. and Hellman, M. E.: New Directions in Cryptography. In: IEEE Transactions on Information Theory. 22, Nr. 6, 1976, S. 644–654.

The Static Diffie-Hellman Assumption Description:  Let $g$ be a generator of prime order that generates the group $\mathbb{G}$. Then given the group elements $g,g^x$ for a random integer $x$ as well as an $h \in \mathbb{G}$, the task to compute the integer $h^{x}$ is assumed to be hard. E.g. used in: Daniel R. L. Brown, Robert P. Gallant: The Static Diffie-Hellman Problem. IACR Cryptology ePrint Archive 2004: 306 (2004).

The Decisional Diffie-Hellman Assumption Description:  Let $g$ be a generator of prime order that generates the group $\mathbb{G}$. Then given the two triples of group elements $T_1 = (g^x,g^y,g^{xy})$ and $T_2 = (g^x,g^y,g^{z})$ for random integers $x,y,z$, the task to decide better than random guessing if $T_1$ or $T_2$ is a Diffie-Hellman triple is assumed to be hard. E.g. used in: Boneh, Dan (1998). "The Decision Diffie–Hellman Problem". Proceedings of the Third Algorithmic Number Theory Symposium. Lecture Notes in Computer Science 1423

The Strong Decisional Diffie-Hellman Assumption Description:  Let $g$ be a generator of prime order that generates the group $\mathbb{G}$. Then given $g,\mathbb{G}$ and the two quadruple of group elements $T_1 = (g^x,g^y,g^{xy})$ and $T_2 = (g^x,g^y,g^{z})$ for random integers $x,y,z$ as well as the element $g^{y^{-1}}$, the task to decide better than random guessing if $T_1$ or $T_2$ is a Diffie-Hellman triple is assumed to be hard. E.g. used in: B. Pfitzmann and A. Sadeghi, Anonymous Fingerprinting with Direct Non-repudiation, Advances in Cryptology - AsiaCrypt 2000.

The Square Diffie-Hellman Assumption Description:  Let $g$ be a generator of prime order that generates the group $\mathbb{G}$. Then given the element $g^{x}$, then the task to compute $g^{x^2}$ is assumed to be hard. E.g. used in: Dongyoung Roh,Sang Geun Hahn, The square root Diffie–Hellman problem, Designs, Codes and Cryptography, February 2012, Volume 62, Issue 2, pp 179-187.

The Gap Diffie-Hellman Assumption Description:  Let $g$ be a generator of prime order that generates the group $\mathbb{G}$. Then given the element $g^{x},g^{y}$, then the task to compute $g^{xy}$ is assumed to be hard, even if one has access to an oracle that solves the Decisional Diffie-Hellman Assumption. E.g. used in: T. Okamoto and D. Pointcheval, “The gap-problem: a new class of problems for the security of cryptographic schemes”, PKC 2001 , LNCS 1992, Springer-Verlag, pp. 104–118, 2001.

The Linear Assumption Description:  Let $g$ be a generator of prime order that generates the group $\mathbb{G}$. Then given the element $g^{a},g^{b},g^{ac},g^{bd}$, then the task to compute $g^{c+d}$ is assumed to be hard. E.g. used in: [TBA].

The $l$-Hensel Discrete Logarithm Assumption Description:  Let $g$ be a generator of prime order $r$ that generates the group $\mathbb{G}$ in $\mathbb{Z}^*_p$ for a prime number $p$. Let further $g^r \equiv 1\pmod{p^{l-1}}$ but $g^r \not \equiv 1\pmod{p^l} $. Then given an element $g^x \pmod{p^{l-1}}$ for some random and secret $x < r-1$, computing $g^x\pmod{g^l}$ is assumed to be hard. E.g. used in: Dario Catalano, Phong Q. Nguyen, Jacques Stern: The Hardness of Hensel Lifting: The Case of RSA and Discrete Logarithm. ASIACRYPT 2002: 299-310.

The Discrete Logarithm Assumption with Auxiliary Input Description:  Let $g$ be a generator of prime order that generates the group $\mathbb{G}$. Then given $g,g^x,g^{x^2},...,g^{x^d}$ and $\mathbb{G}$ with $g^x = r$, the task to compute the integer $x$ is assumed to be hard. E.g. used in: Jung Hee Cheon, Discrete Logarithm Problems with Auxiliary Inputs, Journal of Cryptology, July 2010, Volume 23, Issue 3, pp 457-476