Setting protocol parameters to achieve concrete security

Question

Background

One issue with modern security proofs is that they are usually asymptotic. In other words, such proofs are usually formulated as follows: For any polynomial-time adversary $\mathcal A$, we can select a large enough security parameter $n$, such that the probability that $\mathcal A$ breaks the system is a negligible function of $n$.

Unfortunately, concrete values for parameters of the protocol cannot be readily deduced from such asymptotic proofs. For instance, the size of RSA modulus for a secure signature scheme may not be obtained from an asymptotic proof of security for the given scheme.

This issue was first formalized by Bellare and Rogaway, in their famous paper "The exact security of digital signatures: How to sign with RSA and Rabin." They provided a new type of analyzing and proving the security of some scheme, which they termed exact security. Soon after, numerous papers considered this notion, and gave various results on the exact security of signature schemes.

---

Assumptions

This question considers "exact security" for identification protocols. Since we're going to give concrete parameters, we have to make some explicit assumptions:

1. The time-complexity of entities is limited to $2^{80}$ operations.
2. Entities can perform up to $2^{30}$ operations per second.
3. The best algorithm for factoring an integer is GNFS. Given this assumption, factoring a carefully chosen $1024$-bit integer requires about $2^{86}$ operations, which is infeasible according to assumption 1.
4. In the identification protocol, there is a $30$-second time-out. The adversary can take its time to perform any preprocessing, but when engaged in protocol execution, he must reply within $30$ seconds, or time-out occurs and he fails. (This is in contrast to signature schemes, where the adversary is not faced with such restriction.)
5. During the lifetime of the system, the adversary may engage in at most $10^8$ identification sessions. He is successful if he can impersonate in at least one session, and he fails otherwise. In other words, a successful adversary is one whose success probability is at least $10^{-8}$.

---

Protocol and Proof

The honest prover has the factorization of an integer $n$, and the verifier is going to verify this. Let $L = \Theta(1)$ and $m = \Theta(|n|)$.

The identification protocol is the $m$-time repetition of a $\Sigma$ protocol. The challenge of the $\Sigma$ protocol is chosen randomly from the set $\{0,\ldots,L-1\}$.

Now, we are given the following "tight" security proof (the details of how this proof is obtained is unimportant):

For any adversary $\mathcal A$ whose time-complexity is $T$, and who breaks the identification protocol with probability at least $\epsilon$, there exists another adversary $\mathcal B$, whose (expected) time-complexity is $\frac{TLm}{\epsilon} + \Theta(|n|^2)$, and can factor $n$ with probability 1.

---

Question

How can we use these assumptions and facts, to suggest concrete values for $|n|$, $L$, and $m$, such that the system is both efficient and secure? (The efficiency condition is included because the choice of extremely large parameters will obviously make the system secure.)

Answer 1

Concrete units. Nothing can be said in general until you replace $\Theta(|n|^2)$ by a concrete estimate for the actual computational costs, by filling in the constant factors with units like seconds, bits, and joules. Obviously you should be a little conservative in cost estimates, although if there are multiple different attacks with different costs—e.g., for discrete logs, NFS cost scales with size of modulus while Pollard's $\rho$ cost scales with size of group order—you should try not to be too conservative with any one of them in order to avoid unbalanced costs to defend against unreasonably pessimistic models of attacks that cause you to make foolish compromises.

Cost metric. You should take care of the actual cost model. Time is not the only cost, and many attacks are parallelizable. For example, although a sequential machine might take an expected $2^{n/2}$ operations to find a collision in an $n$-bit hash function using a gigantic table, it also costs $2^{n/2}$ space to store the table—but you can do better with with a $\rho$-type collision search in constant space, and with van Oorschot and Wiener's parallel collision search machine you can use a machine of size $2^{n/4}$ to get an answer in the time for $2^{n/4}$ sequential evaluations of the hash.

Largely the best metric seems to be the area*time cost: the two-dimensional size of the machine multiplied by the amount of time you have to run it, which is usually a good proxy for the cost in rials or joules. In this metric, the van Oorschot–Wiener collision search still costs $2^{n/2}$. Other metrics include RAM metric and NAND metric. One often-ignored part of the cost is communication between large memories and the parallel computational machines.

Precomputation? There is a foundational issue about quantifying human ignorance in the concrete, nonuniform setting.

• We don't know messages $m \ne m'$ such that $\operatorname{SHA256}(m) = \operatorname{SHA256}(m')$, but we know such a message pair exists. So there obviously exists a random algorithm $A()$ that finds SHA-256 collisions very efficiently—specifically, the trivial algorithm that returns $(m, m')$. We just haven't found that algorithm yet.

• Similarly, there almost certainly exists a string $s$ such that the first bit of $\operatorname{MD5}(s \mathbin\| F(0))$ is zero significantly more often when $F = \operatorname{AES}_k$ for a uniform random key $k$ than when $F$ is a uniform random function, which means there exists a high-advantage, low-cost distinguisher for AES—we just don't know what $s$ is, nor do we have any idea how to find it at reasonable cost.

These foundational issues are discussed by Bernstein and Lange in their nonuniform cracks in the concrete paper, which is worth reading if you're interested in the theory—there are more issues, and potential remedies, and compounded issues introduced by the remedies, than I can hope to address in a single crypto.se answer.

So, how do you decide what parameters to use? It's easy as 1-2-3!

1. Solve a gigantic open problem in the foundations of cryptology of quantifying human ignorance and precomputation in the concrete nonuniform setting and rewrite the entire literature to address your solution.

2. Write down a concrete formula giving a cost estimate for the best attack on the system, based on attack costs on primitives and derived attack costs of reductions.

3. Choose the parameters optimizing your concrete costs, subject to a lower bound on the budget needed to break the parameters above what you assume the adversary has.

That is to say, find the best parameters for your budget that are beyond the reach of your adversary given an assumption about their budget.

Let's ignore space costs and communication costs and constant factors for the moment, and pretend the precomputation issue didn't exist. If the adversary can break your protocol in time $T = 30\,\text{sec}$ with probability $\epsilon$, then they can factor $n$ in expected time $\frac{T L m}{\epsilon} + \tau |n|^2$, where $\tau$ is the constant to make the units work out. What choices of $|n|$ (and $|p|$ and $|q|$) and $L$ optimize your costs, subject to the constraint that $|n|$ be out of reach for the NFS (or ECM, or Pollard's $\rho$, or whatever gives the best concrete factoring costs for $|n|$) to factor with a budget of $\frac{T L m}{\epsilon} + \tau |n|^2$?

For this to work, you need to be armed with:

• an estimate of your costs, e.g. from https://bench.cr.yp.to or from your own measurements or from your own analysis
• an estimate of NFS and ECM costs per key, which can be complicated

Of course, if you're not generating a fresh $n$ in each instance of the protocol, you also need to constrain the optimization so that $|n|$ is out of reach of the NFS/ECM with a budget of $2^{80}$ operations offline as you posited.

I'd give a concrete example but I'm too dizzy from reading about NFS costs and I need to sit still for a while.

Some caveats to beware of:

• One type of attack cost is number of queries to an oracle. This represents your application's maximum bandwidth; you might hazard a guess about limits on bandwidth of normal usage, but an adversary will saturate all remaining possible bandwidth to maximize the efficacy of an attack.
• While you often care about the latency of a single operation, the adversary often cares instead about the bandwidth of many simultaneous attacks.
• There are often batch advantages to attacks and opportunities for parallelism; brute force does not just mean trying every key sequentially.
• Reduction theorems sometimes give wildly unreasonable bounds. If there's a concrete attack actually attaining the bound, then this should worry you; if not, you are stuck in a limbo of wondering whether you really need a 100000-bit RSA modulus or you just didn't work hard enough to prove a better bound.