What are standard cryptographic assumptions?

Question

I am struggling to understand what is meant by "standard cryptographic assumption".

The Wikipedia artice on the Goldwasser–Micali system (GM) reads "GM has the distinction of being the first probabilistic public-key encryption scheme which is provably secure under standard cryptographic assumptions."

But what are standard cryptographic assumptions? I suppose that

• FACTORING: Given a positive integer $n$, find its prime factorisation.
• Quadratic Residuosity Problem (QRP): Given an odd composite integer $n$ and $a$ with Jacobi Symbol $(a|n) = +1$ decide whether $a$ is a quadratic residue or a pseudosquare modulo $n$.

are commonly assumed to be difficult and thus "standard cryptographic assumptions". Is why GM is provably secure? But what about the RSA Problem (RSAP)?

Given are a positive integer $n$ that is a product of two distinct odd primes $p$ and $q$, a positive integer $e$ with $\gcd(e, (p-1)(q-1)) = 1$ and an integer $c$. Find an integer $m$ such that $m^e \equiv c \pmod n$.

Is RSAP also commonly supposed to be hard? Is thus RSA provably secure?

Answer 1

I am struggling to understand what is meant by "standard cryptographic assumption".

‘Standard assumption’ broadly means an assumption that has withstood the scrutiny of many smart cryptanalysts for a long time. Examples:

• We think that, for uniform random 1024-bit primes $p$ and $q$, solving $y = x^3 \bmod pq$ for uniform random $x$ is hard given $pq$ and $y$.

  Why? The best way anyone has been able to figure out how to do it is by factoring $n$ to recover $p$ and $q$, and the best known methods—ECM and NFS—cost more than anyone has the budget for.

• We think that solving $y = \operatorname{AES}_k(x)$ for uniform random $k$ is hard given $x$ and $y$.

  Why? The best way anyone has been able to figure out how to do it is essentially by a generic search, and the best known methods—parallel rainbow tables, parallel distinguished points—cost more than anyone has the budget for.

Half-examples:

• Pairing-based cryptography. Pairings are highly popular in academic cryptography at conferences but see very little use in the real world, outside exotic cryptocurrency applications. The security story for pairing-friendly elliptic curves is nowhere near as stable as the security story for elliptic curves for more traditional DLOG applications like Diffie–Hellman key agreement and Schnorr signatures.
• SVP, LWE, and other lattice problems. Lattices are a promising area for post-quantum cryptography, but there is a large design space with a complicated security story that has not stabilized yet—no matter how many completely incomprehensible arguments Chris Peikert and Dan Bernstein have about average-case/worst-case reductions on Twitter.

Non-examples:

• Conjugacy search in a braid group. Braid cryptography is not widely studied by cryptographers and most existing proposals turn out to be broken.
• SIMON and SPECK. These block ciphers are popular among spooks trying to muscle their way into international standardization, but it turns out standards bodies are no longer happy to accept the word of spooks without technical justification these days, and also block sizes smaller than 128 bits are foolish.

The Wikipedia artice on the Goldwasser–Micali system (GM) reads "GM has the distinction of being the first probabilistic public-key encryption scheme which is provably secure under standard cryptographic assumptions."

This is an example of academic obfuscation, and evidence that Wikipedia is a terrible resource for learning about cryptography. What it means is:

• We proved a theorem,¹ and the theorem involves pretty number theory² and asymptotic growth curves!³

  _{¹ This is what provable security means. It does not mean that the theorem has any real-world consequences whatsoever.
  ² This is what ‘standard assumptions’ means here: ugly problems like inverting DES are not allowed, but pretty problems like factoring a product of uniform random primes are allowed.
  ³ Not formally stated: We are only interested in asymptotic growth curves of attack costs for families of problems, so DES is doubly disqualified both because it's ugly and because there's only one DES, whereas you can consider the problem of factoring as a function of the size of the factors. (‘Provable security’ treatment with concrete parameter choices, sometimes called ‘exact security’, didn't come until a decade later with the help of Bellare and Rogaway.)}

To be fair, the GM paper was helpful for setting down some formalizations like semantic security for public-key encryption, which is essentially equivalent to the modern standard of ciphertext indistinguishability which we use today. But the GM encryption scheme? Completely useless, even if there is a theorem.

This kind of obfuscation—and fetishization of number-theoretic prettiness—leads people down regrettable paths like adopting Dual_EC_DRBG, which admits proofs of ‘number-theoretic-based security’, as major national cryptography standards simply by virtue of being number-theoretic, propelled by prestidigitators like Dan Brown whose principal area of expertise is obfuscating gaping back doors among reams of analytic prose that nobody can get through.

Is RSAP also commonly supposed to be hard? Is thus RSA provably secure?

The RSA problem—computing $e^{\mathit{th}}$ roots modulo a product of large secret primes—is commonly supposed to be hard. There are public-key encryption schemes and public-key signature schemes built out of RSA that have theorems—e.g., RSAES-OAEP, RSA-KEM, RSASSA-PSS, RSA-FDH—which are even somewhat useful in relating the difficulty of breaking the security of the cryptosystem (distinguishing ciphertexts, forging signatures) to the difficulty of computing $e^{\mathit{th}}$ roots modulo a product of large secret primes.

But I recommend that you stay away from the dishonest term of art ‘provable security’ because it obfuscates what you're actually saying—especially in the form ‘X is provably secure’.

Whether a scheme has ‘provable security’ or not is irrelevant to users or engineers making decisions about building systems—the conclusions of cryptanalysts about what cryptography will withstand attack are what's relevant to them. ‘Provable security’ is really about guiding cryptanalysts to focus their effort. There's no point in analyzing AES-CTR separately from AES, because any way to break AES-CTR either (a) depends on on misuse of CTR, (b) is based on AES's nature as a permutation rather than arbitrary function, or (c) implies an attack on AES. That's because there is a useful theorem relating any attack on AES-CTR to an attack on AES itself.

Similarly, there's not much point trying to forge RSA-FDH signatures without trying to compute $e^{\mathit{th}}$ roots, because—thanks to a useful theorem—we know that any work done on one problem translates immediately to the other, as long as the hash function doesn't interact in any interesting way with RSA (which would be quite astonishing). So cryptanalysts can ignore the details of RSA-FDH and focus on computing $e^{\mathit{th}}$ roots to give us confidence in the security of RSA-FDH.

Answer 2

There is no formal definition of standard assumption, but we usually say that an assumption is standard if it has already been used in several cryptographic schemes and if it is well-accepted in the crypto community.

It usually also implies that several researchers tried to solve the problem and were not able to find efficient ways of doing so, therefore, if we set the parameters correctly, there is no known fast way of solving the problem.

For instance, assuming that the RSA problem is hard is a standard assumption.

But GM is provably secure because it has a proof of security, not because the problem it is based on is a standard problem. Being provably secure (in this case) just means that assuming that the underlying problem is hard to solve, one can prove that the scheme satisfies some security notion (e.g., CPA security). But if the underlying problem is not standard, the scheme is still provably secure.