Computational hardness assumption

{{short description|Hypothesis in computational complexity theory}} In computational complexity theory, a '''computational hardness assumption''' is the hypothesis that a particular problem cannot be solved efficiently (where ''efficiently'' typically means "in polynomial time"). It is not known how to prove (unconditional) hardness for essentially any useful problem. Instead, computer scientists rely on reductions to formally relate the hardness of a new or complicated problem to a computational hardness assumption about a problem that is better-understood.

Computational hardness assumptions are of particular importance in cryptography. A major goal in cryptography is to create cryptographic primitives with provable security. In some cases, cryptographic protocols are found to have information theoretic security; the one-time pad is a common example. However, information theoretic security cannot always be achieved; in such cases, cryptographers fall back to computational security. Roughly speaking, this means that these systems are secure ''assuming that any adversaries are computationally limited'', as all adversaries are in practice.

Computational hardness assumptions are also useful for guiding algorithm designers: a simple algorithm is unlikely to refute a well-studied computational hardness assumption such as P ≠ NP.

==Comparing hardness assumptions== Computer scientists have different ways of assessing which hardness assumptions are more reliable.

===Strength of hardness assumptions=== We say that assumption <math>A</math> is ''stronger'' than assumption <math>B</math> when <math>A</math> implies <math>B</math> (and the converse is false or not known). In other words, even if assumption <math>A</math> were false, assumption <math>B</math> may still be true, and cryptographic protocols based on assumption <math>B</math> may still be safe to use. Thus when devising cryptographic protocols, one hopes to be able to prove security using the ''weakest'' possible assumptions.

===Average-case vs. worst-case assumptions=== {{See also|Best, worst and average case}} An average-case assumption says that a specific problem is hard on most instances from some explicit distribution, whereas a worst-case assumption only says that the problem is hard on ''some'' instances. For a given problem, average-case hardness implies worst-case hardness, so an average-case hardness assumption is stronger than a worst-case hardness assumption for the same problem. Furthermore, even for incomparable problems, an assumption like the exponential time hypothesis is often considered preferable to an average-case assumption like the planted clique conjecture.<ref name=BKW15>{{Cite conference |doi=10.1137/1.9781611973730.66 |isbn=978-1-61197-374-7 |contribution=Approximating the best Nash Equilibrium in <math>n^{o(\log(n))}</math>-time breaks the Exponential Time Hypothesis |title=Symposium on Discrete Algorithms (SODA) |pages=970–982 |year=2015 |author1-link=Mark Braverman (mathematician) |first1=Mark |last1=Braverman |first2=Young Kun |last2=Ko |first3=Omri |last3=Weinstein |publisher=Society for Industrial and Applied Mathematics}}</ref> However, for cryptographic applications, knowing that a problem has some hard instance (the problem is hard in the worst-case) is useless because it does not provide us with a way of generating hard instances.<ref name="katz07">J. Katz and Y. Lindell, Introduction to Modern Cryptography (Chapman and Hall/CRC Cryptography and Network Security Series), Chapman and Hall/CRC, 2007.</ref> Fortunately, many average-case assumptions used in cryptography (including RSA, discrete log, and some lattice problems) can be based on worst-case assumptions via worst-case-to-average-case reductions.<ref name=GK16>{{Cite conference |doi=10.1007/978-3-662-49096-9_21 |contribution=Cryptographic Assumptions: A Position Paper |title=Theory of Cryptography Conference (TCC) 2016 |pages=505–522 |year=2016 |author1-link=Shafi Goldwasser |first1=Shafi |last1=Goldwasser |author2-link=Yael Tauman Kalai |first2=Yael Tauman |last2=Kalai |publisher=Springer |title-link=International Association for Cryptologic Research#Theory of Cryptography |series=Lecture Notes in Computer Science |volume=9562 |doi-access=free|isbn=978-3-662-49095-2 }}</ref>

===Falsifiability=== A desired characteristic of a computational hardness assumption is falsifiability, i.e. that if the assumption were false, then it would be possible to prove it. In particular, {{harvtxt|Naor|2003}} introduced a formal notion of cryptographic falsifiability.<ref>{{cite conference | last = Naor | first = Moni | editor-last = Boneh | editor-first = Dan | contribution = On cryptographic assumptions and challenges | doi = 10.1007/978-3-540-45146-4_6 | location = Berlin | mr = 2093188 | pages = 96–109 | publisher = Springer | series = Lecture Notes in Computer Science | title = Advances in Cryptology – CRYPTO 2003: 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings | volume = 2729 | year = 2003| doi-access = free | isbn = 978-3-540-40674-7 }}</ref> Roughly, a computational hardness assumption is said to be falsifiable if it can be formulated in terms of a challenge: an interactive protocol between an adversary and an efficient verifier, where an efficient adversary can convince the verifier to accept if and only if the assumption is false.

==Common cryptographic hardness assumptions==

There are many cryptographic hardness assumptions in use. This is a list of some of the most common ones, and some cryptographic protocols that use them.

===Integer factorization=== {{Main|Integer factorization}} Given a composite integer <math>n</math>, and in particular one which is the product of two large primes <math>n = p\cdot q</math>, the integer factorization problem is to find <math>p</math> and <math>q</math> (more generally, find primes <math>p_1,\dots,p_k</math> such that <math>n = \prod_i p_i</math>). It is a major open problem to find an algorithm for integer factorization that runs in time polynomial in the size of representation (<math>\log n</math>). The security of many cryptographic protocols rely on the assumption that integer factorization is hard (i.e. cannot be solved in polynomial time). Cryptosystems whose security is equivalent to this assumption include Rabin signature and the Okamoto–Uchiyama cryptosystem. Many more cryptosystems rely on stronger assumptions such as RSA, residuosity problems, and phi-hiding.

====RSA problem==== {{Main|RSA problem}} Given a composite number <math>n</math>, exponent <math>e</math> and number <math>c := m^e (\mathrm{mod}\; n)</math>, the RSA problem is to find <math>m</math>. The problem is conjectured to be hard, but becomes easy given the factorization of <math>n</math>. In the RSA cryptosystem, <math>(n,e)</math> is the public key, <math>c</math> is the encryption of message <math>m</math>, and the factorization of <math>n</math> is the secret key used for decryption.

====Residuosity problems==== {{Main|Higher residuosity problem}} Given a composite number <math>n</math> and integers <math>y,d</math>, the residuosity problem is to determine whether there exists (alternatively, find an) <math>x</math> such that :<math> x^d \equiv y \pmod{n}.</math> Important special cases include the quadratic residuosity problem and the decisional composite residuosity problem. As in the case of RSA, this problem (and its special cases) are conjectured to be hard, but become easy given the factorization of <math>n</math>. Some cryptosystems that rely on the hardness of residuousity problems include: *Goldwasser–Micali cryptosystem (quadratic residuosity problem) *Blum Blum Shub generator (quadratic residuosity problem) *Paillier cryptosystem (decisional composite residuosity problem) *Benaloh cryptosystem (higher residuosity problem) *Naccache–Stern cryptosystem (higher residuosity problem)

====Phi-hiding assumption==== {{Main|Phi-hiding assumption}} For a composite number <math>m</math>, it is not known how to efficiently compute its Euler's totient function <math>\phi(m)</math>. The phi-hiding assumption postulates that it is hard to compute <math>\phi(m)</math>, and furthermore even computing any prime factors of <math>\phi(m)</math> is hard. This assumption is used in the Cachin–Micali–Stadler PIR protocol.<ref>{{cite book |last1=Cachin |first1=Christian |last2=Micali |first2=Silvio|last3=Stadler|first3=Markus |title=Advances in Cryptology — EUROCRYPT '99 |chapter=Computationally Private Information Retrieval with Polylogarithmic Communication |series=Lecture Notes in Computer Science |year=1999|publisher=Springer|volume= 1592|pages=402–414|doi=10.1007/3-540-48910-X_28 |editor1-last=Stern |editor1-first=Jacques|isbn=978-3-540-65889-4 |s2cid=29690672 }}</ref>

===Discrete log problem (DLP)=== {{Main|Discrete logarithm}} Given elements <math>a</math> and <math>b</math> from a group <math>G</math>, the discrete log problem asks for an integer <math>k</math> such that <math>a = b^k</math>. The discrete log problem is not known to be comparable to integer factorization, but their computational complexities are closely related.

Most cryptographic protocols related to the discrete log problem actually rely on the stronger Diffie–Hellman assumption: given group elements <math>g, g^a, g^b</math>, where <math>g</math> is a generator and <math>a,b</math> are random integers, it is hard to find <math>g^{a\cdot b}</math>. Examples of protocols that use this assumption include the original Diffie–Hellman key exchange, as well as the ElGamal encryption (which relies on the yet stronger Decisional Diffie–Hellman (DDH) variant).

====Multilinear maps==== A multilinear map is a function <math>e: G_1 ,\dots,G_n \rightarrow G_T</math> (where <math>G_1 ,\dots,G_n,G_T</math> are groups) such that for any <math>g_1, \dots, g_n \in G_1, \dots G_n</math> and <math>a_1, \dots, a_n</math>, :<math>e(g_1^{a_1},\dots,g_n^{a_n}) = e(g_1,\dots,g_n)^{a_1\cdots a_n}</math>.

For cryptographic applications, one would like to construct groups <math>G_1,\dots,G_n,G_T</math> and a map <math>e</math> such that the map and the group operations on <math>G_1,\dots,G_n,G_T</math> can be computed efficiently, but the discrete log problem on <math>G_1,\dots,G_n</math> is still hard.<ref name = BS02> {{cite journal |author1-link= Dan Boneh|first1=Dan|last1=Boneh|author2-link=Alice Silverberg|first2=Alice|last2=Silverberg|year= 2002|title= Applications of Multilinear Forms to Cryptography|url= https://eprint.iacr.org/2002/080|journal= Cryptology ePrint Archive}}</ref> Some applications require stronger assumptions, e.g. multilinear analogs of Diffie-Hellman assumptions.

For the special case of <math>n=2</math>, bilinear maps with believable security have been constructed using Weil pairing and Tate pairing.<ref name = DBS04> {{cite journal |first1= Ratna|last1=Dutta|first2= Rana|last2=Barua|first3 = Palash|last3=Sarkar|year= 2004|title= Pairing-Based Cryptographic Protocols : A Survey|url= https://eprint.iacr.org/2004/064|journal= Cryptology ePrint Archive}}</ref> For <math>n>2</math> many constructions have been proposed in recent years, but many of them have also been broken, and currently there is no consensus about a safe candidate.<ref> {{cite web |url= http://malb.io/are-graded-encoding-schemes-broken-yet.html|title= Are Graded Encoding Scheme broken yet?|first= Martin R.|last=Albrecht|access-date= 22 March 2018}}</ref>

Some cryptosystems that rely on multilinear hardness assumptions include: * Boneh-Franklin scheme (bilinear Diffie-Hellman) * Boneh–Lynn–Shacham (bilinear Diffie-Hellman) * Garg-Gentry-Halevi-Raykova-Sahai-Waters candidate for indistinguishability obfuscation and functional encryption (multilinear jigsaw puzzles)<ref> {{cite journal |first1 = Sanjam|last1=Garg| first2 = Craig|last2=Gentry| first3 = Shai|last3=Halevi| first4 = Mariana |last4=Raykova| first5 = Amit|last5=Sahai|first6 = Brent |last6=Waters|year=2016|title=Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits|publisher=SIAM|volume= 45|number=3|pages=882–929|url=https://eprint.iacr.org/2013/451.pdf|journal=SIAM Journal on Computing|doi=10.1137/14095772X}}</ref>

===Lattice problems=== {{Main|Lattice problem}} The most fundamental computational problem on lattices is the shortest vector problem (SVP): given a lattice <math>L</math>, find the shortest non-zero vector <math>v \in L</math>. Most cryptosystems require stronger assumptions on variants of SVP, such as shortest independent vectors problem (SIVP), GapSVP,<ref name = peikert09>{{cite conference | first = Chris |last=Peikert | contribution = Public-key cryptosystems from the worst-case shortest vector problem: extended abstract | doi = 10.1145/1536414.1536461 | pages = 333–342 | title = Proceedings on 41st Annual ACM Symposium on Theory of Computing (STOC) | year = 2009}}</ref> or Unique-SVP.<ref name = ad97>{{cite conference | author1-link = Miklós Ajtai | first1=Miklós|last1= Ajtai | author2-link = Cynthia Dwork|first2=Cynthia|last2=Dwork | contribution = A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence | doi = 10.1145/258533.258604 | pages = 284–293 | title = Proceedings on 29th Annual ACM Symposium on Theory of Computing (STOC) | year = 1997| isbn=0-89791-888-6}} </ref>

The most useful lattice hardness assumption in cryptography is for the learning with errors (LWE) problem: Given samples to <math>(x,y)</math>, where <math>y = f(x)</math> for some linear function <math>f(\cdot)</math>, it is easy to learn <math>f(\cdot)</math> using linear algebra. In the LWE problem, the input to the algorithm has errors, i.e. for each pair <math>y\neq f(x)</math> with some small probability. The errors are believed to make the problem intractable (for appropriate parameters); in particular, there are known worst-case to average-case reductions from variants of SVP.<ref name = regev10>{{cite conference | first = Oded |last=Regev | contribution = The Learning with Errors Problem (Invited Survey) | doi = 10.1109/CCC.2010.26 | pages = 191–204 | title = Conference on Computational Complexity (CCC) 2010 | year = 2010|title-link=Computational Complexity Conference |isbn=978-1-4244-7214-7 }}</ref>

For quantum computers, factoring and discrete log problems are easy, but lattice problems are conjectured to be hard.<ref name = peikert16>{{cite journal |first = Chris|last= Peikert|year= 2016|title= A Decade of Lattice Cryptography|url= https://eprint.iacr.org/2015/939|journal= Foundations and Trends in Theoretical Computer Science|volume= 10|number = 4|pages = 283–424|doi= 10.1561/0400000074}}</ref> This makes some lattice-based cryptosystems candidates for post-quantum cryptography.

Some cryptosystems that rely on hardness of lattice problems include: *NTRU (both NTRUEncrypt and NTRUSign) * Most candidates for fully homomorphic encryption

==Non-cryptographic hardness assumptions== As well as their cryptographic applications, hardness assumptions are used in computational complexity theory to provide evidence for mathematical statements that are difficult to prove unconditionally. In these applications, one proves that the hardness assumption implies some desired complexity-theoretic statement, instead of proving that the statement is itself true. The best-known assumption of this type is the assumption that P ≠ NP,<ref>{{cite journal|first=Lance|last=Fortnow|author-link=Lance Fortnow|url=http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf|archive-url=https://wayback.archive-it.org/all/20110224135332/http://www.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf|url-status=dead|archive-date=2011-02-24|title=The status of the P versus NP problem|journal=Communications of the ACM|volume=52|year=2009|issue=9|pages=78–86|doi=10.1145/1562164.1562186|s2cid=5969255}}.</ref> but others include the exponential time hypothesis,<ref>{{cite book | last = Woeginger | first = Gerhard | author-link = Gerhard J. Woeginger | doi = 10.1007/3-540-36478-1_17 | title = Combinatorial Optimization — Eureka, You Shrink! | series = Lecture Notes in Computer Science | pages = 185–207 | publisher = Springer-Verlag | contribution = Exact algorithms for NP-hard problems: A survey | year = 2003 | volume = 2570| isbn = 978-3-540-00580-3 | s2cid = 289357 }}.</ref> the planted clique conjecture, and the unique games conjecture.<ref name = khot10>{{cite conference | author-link = Subhash Khot | last = Khot | first = Subhash | contribution = On the Unique Games Conjecture | title = Proc. 25th IEEE Conference on Computational Complexity | url = http://cs.nyu.edu/~khot/papers/UGCSurvey.pdf | year = 2010 | pages = 99–121 | doi = 10.1109/CCC.2010.19 }}.</ref>

===''C''-hard problems=== Many worst-case computational problems are known to be hard or even complete for some complexity class <math>C</math>, in particular NP-hard (but often also PSPACE-hard, PPAD-hard, etc.). This means that they are at least as hard as any problem in the class <math>C</math>. If a problem is <math>C</math>-hard (with respect to polynomial time reductions), then it cannot be solved by a polynomial-time algorithm unless the computational hardness assumption <math>P \neq C</math> is false.

===Exponential time hypothesis (ETH) and variants=== {{Main|Exponential time hypothesis}} The exponential time hypothesis (ETH) is a strengthening of <math>P \neq NP</math> hardness assumption, which conjectures that not only does the Boolean satisfiability problem (SAT) not have a polynomial time algorithm, it furthermore requires exponential time (<math>2^{\Omega(n)}</math>).<ref>{{cite conference | last1 = Impagliazzo | first1 = Russell | author1-link = Russell Impagliazzo | last2 = Paturi | first2 = Ramamohan | contribution = The Complexity of k-SAT | doi = 10.1109/CCC.1999.766282 | pages = 237–240 | title = Proc. 14th IEEE Conf. on Computational Complexity | year = 1999| isbn = 0-7695-0075-7 }}</ref> An even stronger assumption, known as the strong exponential time hypothesis (SETH) conjectures that <math>k</math>-SAT requires <math>2^{(1-\varepsilon_k)n}</math> time, where <math>\lim_{k \rightarrow \infty} \varepsilon_k = 0</math>. ETH, SETH, and related computational hardness assumptions allow for deducing fine-grained complexity results, e.g. results that distinguish polynomial time and quasi-polynomial time,<ref name=BKW15 /> or even <math>n^{1.99}</math> versus <math>n^2</math>.<ref>{{cite conference | last1 = Abboud | first1 = Amir | last2 = Vassilevska-Williams | first2 = Virginia |author2-link = Virginia Vassilevska Williams | last3 = Weimann | first3 = Oren | contribution = Consequences of Faster Alignment of Sequences | doi = 10.1007/978-3-662-43948-7_4 | pages = 39–51 | title = Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014 | series = Lecture Notes in Computer Science | year = 2014| volume = 8572 | isbn = 978-3-662-43947-0 }}</ref> Such assumptions are also useful in parametrized complexity.<ref name = LMS11> {{cite journal | last1 = Lokshtanov | first1 = Daniel | last2 = Marx | first2 = Daniel | last3 = Saurabh | first3 = Saket | title = Lower bounds based on the Exponential Time Hypothesis | journal = Bulletin of the EATCS | volume = 105 | pages = 41–72 | year = 2011 | url = http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/96 }}</ref>

===Average-case hardness assumptions=== {{Main|Average-case complexity}} Some computational problems are assumed to be hard on average over a particular distribution of instances. For example, in the planted clique problem, the input is a random graph sampled, by sampling an Erdős–Rényi random graph and then "planting" a random <math>k</math>-clique, i.e. connecting <math>k</math> uniformly random nodes (where <math>2\log_2 n \ll k \ll \sqrt n</math>), and the goal is to find the planted <math>k</math>-clique (which is unique w.h.p.).<ref name="ab">{{cite book|title=Computational Complexity: A Modern Approach|first1=Sanjeev|last1=Arora|author1-link=Sanjeev Arora (computer scientist)|first2=Boaz|last2=Barak|publisher=Cambridge University Press|year=2009|isbn=9780521424264|pages=362–363|url=https://books.google.com/books?id=8Wjqvsoo48MC&pg=PA362}}.</ref> Another important example is Feige's Hypothesis, which is a computational hardness assumption about random instances of 3-SAT (sampled to maintain a specific ratio of clauses to variables).<ref name = Feige02> {{cite conference | last1 = Feige | first1 = Uriel |author1-link = Uriel Feige | contribution = Relations between average case complexity and approximation complexity | doi = 10.1145/509907.509985 | pages = 534–543 | title = Proceedings on 34th Annual ACM Symposium on Theory of Computing (STOC) | year = 2002 | isbn = 1-58113-495-9 }}</ref> Average-case computational hardness assumptions are useful for proving average-case hardness in applications like statistics, where there is a natural distribution over inputs.<ref name = BR13> {{cite conference | last1 = Berthet | first1 = Quentin | last2 = Rigollet | first2 = Philippe | contribution = Complexity Theoretic Lower Bounds for Sparse Principal Component Detection | pages = 1046–1066 | title = COLT 2013 | url = http://jmlr.org/proceedings/papers/v30/Berthet13.html | year = 2013 }}</ref> Additionally, the planted clique hardness assumption has also been used to distinguish between polynomial and quasi-polynomial worst-case time complexity of other problems,<ref name = HK11>{{cite journal | last1 = Hazan | first1 = Elad | last2 = Krauthgamer | first2 = Robert | title = How Hard Is It to Approximate the Best Nash Equilibrium? | doi = 10.1137/090766991 | pages = 79–91 | journal = SIAM Journal on Computing | volume = 40 | number = 1 | year = 2011| citeseerx = 10.1.1.139.7326 }}</ref> similarly to the exponential time hypothesis.

===Unique games=== {{Main|Unique games conjecture}} The unique label cover problem is a constraint satisfaction problem, where each constraint <math>C</math> involves two variables <math>x,y</math>, and for each value of <math>x</math> there is a ''unique'' value of <math>y</math> that satisfies <math>C</math>. Determining whether all the constraints can be satisfied is easy, but the '''unique game conjecture''' (UGC) postulates that determining whether almost all the constraints (<math>(1-\varepsilon)</math>-fraction, for any constant <math>\varepsilon>0</math>) can be satisfied or almost none of them (<math>\varepsilon</math>-fraction) can be satisfied is NP-hard.<ref name=khot10 /> Approximation problems are often known to be NP-hard assuming UGC; such problems are referred to as UG-hard. In particular, assuming UGC there is a semidefinite programming algorithm that achieves optimal approximation guarantees for many important problems.<ref name = rag08> {{cite conference | first = Prasad |last=Raghavendra | contribution = Optimal algorithms and inapproximability results for every CSP? | doi = 10.1145/1374376.1374414 | pages = 245–254 | title = 40th Annual ACM Symposium on theory of Computing (STOC) 2008 | year = 2008|isbn=978-1-60558-047-0 }}</ref>

====Small set expansion==== {{main|Small set expansion hypothesis}} Closely related to the unique label cover problem is the '''small set expansion (SSE)''' problem: Given a graph <math>G = (V,E)</math>, find a small set of vertices (of size <math>n/\log(n)</math>) whose edge expansion is minimal. It is known that if SSE is hard to approximate, then so is unique label cover. Hence, the ''small set expansion hypothesis'', which postulates that SSE is hard to approximate, is a stronger (but closely related) assumption than the unique game conjecture.<ref name = rs10> {{cite conference | first1 = Prasad |last1=Raghavendra | first2 = David |last2=Steurer | contribution = Graph Expansion and the Unique Games Conjecture | doi = 10.1145/1806689.1806792 | pages = 755–764 | title = 42nd Annual ACM Symposium on theory of Computing (STOC) 2010 | year = 2010|isbn=978-1-4503-0050-6 }}</ref> Some approximation problems are known to be SSE-hard<ref>{{cite journal | first1 = Yu |last1=Wu | first2 = Per |last2=Austrin | first3 = Toniann |last3=Pitassi | first4 = David|last4= Liu | title = Inapproximability of Treewidth and Related Problems | doi = 10.1613/jair.4030 | pages = 569–600 | journal = Journal of Artificial Intelligence Research | volume = 49 | year = 2014| doi-access = free }}</ref> (i.e. at least as hard as approximating SSE).

===The 3SUM conjecture=== {{Main|3SUM}} Given a set of <math>n</math> numbers, the 3SUM problem asks whether there is a triplet of numbers whose sum is zero. There is a quadratic-time algorithm for 3SUM, and it has been conjectured that no algorithm can solve 3SUM in "truly sub-quadratic time": the '''3SUM conjecture''' is the computational hardness assumption that there are no <math>O(n^{2-\varepsilon})</math>-time algorithms for 3SUM (for any constant <math>\varepsilon > 0</math>). This conjecture is useful for proving near-quadratic lower bounds for several problems, mostly from computational geometry.<ref> {{cite conference | last1 = Vassilevska Williams | first1 = Virginia | author1-link = Virginia Vassilevska Williams | contribution = On some fine-grained questions in algorithms and complexity | title = ICM 2018 | url = http://people.csail.mit.edu/virgi/eccentri.pdf | year = 2018 }}</ref>

== See also == * Security level

==References== {{reflist}}

{{Computational hardness assumptions}}

Category:Theory of cryptography Category:Computational number theory Category:Computational hardness assumptions