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.


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.


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.)

  • 2
    $\begingroup$ Cross post: crypto.stackexchange.com/q/3102/77 $\endgroup$ Jun 30 '12 at 11:52
  • 1
    $\begingroup$ Security proofs are almost always concrete reductions that allow you to translate concrete assumptions and security requirements into concrete parameters. Regarding your question, I am not sure I understand it. First, the theorem statement should have some conditions on L,m. I imagine that since this is an m-fold repetition of a Sigma protocol, the conditions are that L^m > 1/epsilon, or something similar. Once you have that it seems that since you set epsilon=10^(-8), you'll set L=2 and m accordingly. $\endgroup$
    – Boaz Barak
    Jul 8 '12 at 11:01
  • $\begingroup$ If you know L,m,epsilon and assuming the Theta(|n|^2) term is negligible, then you can just set T to be the number of operations one can do in 30 seconds, and then you want to make sure that you choose a number that can't be factored using TLm/epsilon operations. $\endgroup$
    – Boaz Barak
    Jul 8 '12 at 11:01
  • $\begingroup$ @BoazBarak: Thanks a lot for the response. Here are a few points: (1) >> "First, the theorem statement should have some conditions on L,m." In the paragraph below "Protocol and Proof," it is stated that L=Θ(1) and m=Θ(|n|). (2) I think (but I'm not sure) that your answer does not consider the pre-processing time of adversaries. (3) With L=2, and other parameters set as above, we require m=2^23; that is, about 8 million iterations! This is my main point of the question: In order for this protocol to work "securely," we have to set parameters to huge values. $\endgroup$ Jul 8 '12 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.