In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
, 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
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adv ...
. A major goal in cryptography is to create
cryptographic primitive
Cryptographic primitives are well-established, low-level cryptographic algorithms that are frequently used to build cryptographic protocols for computer security systems. These routines include, but are not limited to, one-way hash functions and ...
s with
provable security. In some cases, cryptographic protocols are found to have
information theoretic security; the
one-time pad
In cryptography, the one-time pad (OTP) is an encryption technique that cannot be cracked, but requires the use of a single-use pre-shared key that is not smaller than the message being sent. In this technique, a plaintext is paired with a ra ...
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
is ''stronger'' than assumption
when
implies
(and the converse is false or not known).
In other words, even if assumption
were false, assumption
may still be true, and cryptographic protocols based on assumption
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
An
average-case
In computer science, best, worst, and average cases of a given algorithm express what the resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running time, i.e. time complexity, ...
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.
Note, however, that in most cryptographic applications, knowing that a problem has some hard instance (i.e. a problem is hard on the worst-case) is useless because it does not provide us with a way of generating hard instances.
[J. Katz and Y. Lindell, Introduction to Modern Cryptography (Chapman and Hall/Crc Cryptography and Network Security Series), Chapman and Hall/CRC, 2007.] Fortunately, many average-case assumptions used in cryptography (including
RSA,
discrete log
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log' ...
, and some
lattice problems In computer science, lattice problems are a class of optimization problems related to mathematical objects called lattices. The conjectured intractability of such problems is central to the construction of secure lattice-based cryptosystems: La ...
) can be based on worst-case assumptions via worst-case-to-average-case reductions.
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, introduced a formal notion of cryptographic falsifiability.
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
Given a
composite number
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor
In mathematics, a divisor of an integer n, also called a factor ...
, and in particular one which is the product of two large primes
, the integer factorization problem is to find
and
(more generally, find primes
such that
).
It is a major open problem to find an algorithm for integer factorization that runs in time polynomial in the size of representation (
).
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 the
Rabin cryptosystem
The Rabin cryptosystem is a family of public-key encryption schemes
based on a trapdoor function whose security, like that of RSA, is related to the difficulty of integer factorization.
The Rabin trapdoor function has the advantage that invert ...
and the
Okamoto–Uchiyama cryptosystem.
Many more cryptosystems rely on stronger assumptions such as
RSA,
Residuosity problems, and
Phi-hiding.
RSA problem
Given a composite number
, exponent
and number
, the RSA problem is to find
.
The problem is conjectured to be hard, but becomes easy given the factorization of
.
In the
RSA cryptosystem,
is the
public key,
is the encryption of message
, and the factorization of
is the secret key used for decryption.
Residuosity problems
Given a composite number
and integers
, the residuosity problem is to determine whether there exists (alternatively, find an)
such that
:
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
.
Some cryptosystems that rely on the hardness of residuousity problems include:
*
Goldwasser–Micali cryptosystem (quadratic redisduosity problem)
*
Blum Blum Shub generator (quadratic redisduosity problem)
*
Paillier cryptosystem (decisional composite residuosity problem)
*
Benaloh cryptosystem The Benaloh Cryptosystem is an extension of the Goldwasser-Micali cryptosystem (GM) created in 1985 by Josh (Cohen) Benaloh. The main improvement of the Benaloh Cryptosystem over GM is that longer blocks of data can be encrypted at once, whereas i ...
(higher residuosity problem)
*
Naccache–Stern cryptosystem (higher residuosity problem)
Phi-hiding assumption
For a composite number
, it is not known how to efficiently compute its
Euler's totient function . The Phi-hiding assumption postulates that it is hard to compute
, and furthermore even computing any prime factors of
is hard. This assumption is used in the Cachin–Micali–Stadler
PIR protocol.
Discrete log problem (DLP)
Given elements
and
from a
group , the discrete log problem asks for an integer
such that
.
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
, where
is a generator and
are random integers, it is hard to find
. 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
(where
are
groups
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
) such that for any
and
,
:
.
For cryptographic applications, one would like to construct groups
and a map
such that the map and the group operations on
can be computed efficiently, but the discrete log problem on
is still hard.
[
]
Some applications require stronger assumptions, e.g. multilinear analogs of Diffie-Hellman assumptions.
For the special case of
,
bilinear maps with believable security have been constructed using
Weil pairing and
Tate pairing
In mathematics, Tate pairing is any of several closely related bilinear pairings involving elliptic curves or abelian varieties, usually over local or finite fields, based on the Tate duality pairings introduced by and extended by . applied ...
.
[
]
For
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.
Some cryptosystems that rely on multilinear hardness assumptions include:
*
Boneh-Franklin scheme (blinear Diffie-Hellman)
*
Boneh–Lynn–Shacham (blinear Diffie-Hellman)
* Garg-Gentry-Halevi-Raykova-Sahai-Waters candidate for
indistinguishability obfuscation
In cryptography, indistinguishability obfuscation (abbreviated IO or iO) is a type of software obfuscation with the defining property that obfuscating any two programs that compute the same mathematical function results in programs that cannot be ...
and
functional encryption (multilinear jigsaw puzzles)
Lattice problems
The most fundamental computational problem on lattices is the
Shortest vector problem (SVP): given a lattice
, find the shortest non-zero vector
.
Most cryptosystems require stronger assumptions on variants of SVP, such as
Shortest independent vectors problem (SIVP),
GapSVP,
or Unique-SVP.
[
]
The most useful lattice hardness assumption in cryptography is for the
Learning with errors (LWE) problem: Given samples to
, where
for some linear function
, it is easy to learn
using linear algebra. In the LWE problem, the input to the algorithm has errors, i.e. for each pair
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.
For quantum computers, Factoring and Discrete Log problems are easy, but lattice problems are conjectured to be hard.
This makes some
lattice-based cryptosystems candidates for
post-quantum cryptography.
Some cryptosystems that rely on hardness of lattice problems include:
*
NTRU (both
NTRUEncrypt
The NTRUEncrypt public key cryptosystem, also known as the NTRU encryption algorithm, is an NTRU lattice-based alternative to RSA and elliptic curve cryptography (ECC) and is based on the shortest vector problem in a lattice (which is not known ...
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
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
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, but others include the
exponential time hypothesis, the
planted clique conjecture, and the
unique games conjecture.
[.]
''C''-hard problems
Many
worst-case computational problems are known to be hard or even
complete
Complete may refer to:
Logic
* Completeness (logic)
* Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable
Mathematics
* The completeness of the real numbers, which implies t ...
for some
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms o ...
, 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
.
If a problem is
-hard (with respect to polynomial time reductions), then it cannot be solved by a polynomial-time algorithm unless the computational hardness assumption
is false.
Exponential Time Hypothesis (ETH) and variants
The Exponential Time Hypothesis (ETH) is a
strengthening
Chinese food therapy (, also called nutrition therapy and dietary therapy) is a mode of dieting rooted in Chinese beliefs concerning the effects of food on the human organism, and centered on concepts such as eating in moderation. Its basic pr ...
of
hardness assumption, which conjectures that not only does the
Boolean satisfiability problem
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisf ...
not have a polynomial time algorithm, it furthermore requires exponential time (
).
An even stronger assumption, known as the
Strong Exponential Time Hypothesis
In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . It states that satisfiability of 3-CNF Boolean formulas cannot be solved more quickly than exponential t ...
(SETH) conjectures that
-SAT requires
time, where
.
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
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
,
or even
versus
.
Such assumptions are also useful in
parametrized complexity.
[
]
Average-case hardness assumptions
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
-clique, i.e. connecting
uniformly random nodes (where
), and the goal is to find the planted
-clique (which is unique w.h.p.).
[.]
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).
[
]
Average-case computational hardness assumptions are useful for proving average-case hardness in applications like statistics, where there is a natural distribution over inputs.
[
]
Additionally, the planted clique hardness assumption has also been used to distinguish between polynomial and quasi-polynomial worst-case time complexity of other problems,
similarly to the
Exponential Time Hypothesis.
Unique Games
The
Unique Label Cover problem is a constraint satisfaction problem, where each constraint
involves two variables
, and for each value of
there is a ''unique'' value of
that satisfies
.
Determining whether all the constraints can be satisfied is easy, but the Unique Game Conjecture (UGC) postulates that determining whether almost all the constraints (
-fraction, for any constant
) can be satisfied or almost none of them (
-fraction) can be satisfied is NP-hard.
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.
[
]
Small Set Expansion
Closely related to the Unique Label Cover problem is the Small Set Expansion (SSE) problem: Given a graph
, find a small set of vertices (of size
) 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.
[
]
Some approximation problems are known to be SSE-hard (i.e. at least as hard as approximating SSE).
The 3SUM Conjecture
Given a set of
numbers, the 3SUM problem asks whether there is a triplet of numbers whose sum is zero.
There is an 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
-time algorithms for 3SUM (for any constant
).
This conjecture is useful for proving near-quadratic lower bounds for several problems, mostly from
computational geometry.
[
]
See also
*
Security level
In cryptography, security level is a measure of the strength that a cryptographic primitive — such as a cipher or hash function — achieves. Security level is usually expressed as a number of " bits of security" (also security stren ...
References
{{Computational hardness assumptions
Theory of cryptography
Computational number theory
Computational hardness assumptions