Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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

share|improve this question
Cross post: – M.S. Dousti Jun 30 '12 at 11:52
Shouldn't $\mathcal A$ have success probability "at least $\epsilon$" instead of "at most $\epsilon$"? – PaĆ­lo Ebermann Jul 3 '12 at 18:30
@PaĆ­loEbermann: Yes, thanks! Corrected. – M.S. Dousti Jul 4 '12 at 21:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.