In this paper: Sequential Aggregate Signatures with Short Public Keys: Design, Analysis and Implementation Studies the authors sell the paper as the first who propose Aggregate signatures without interactive assumptions as LRSW but with static ones. What renders an assumption interactive? The fact that is not a standard: DDH, CDH, DL, QR, RSA ,etc well known assumption?


You can define most hardness assumptions in terms of a game played with an adversary. See Shoup & Bellare-Rogaway for details.

Example: You can define DDH assumption in terms of the following game:

  • Challenger picks a random bit $\beta$; and random $a,b,c \gets \mathbb{Z}_p$. He computes $A = g^a; B=b^b$ and $C = \begin{cases}g^{ab} & \mbox{if }\beta =0 \\ g^c& \mbox{if } \beta=1\end{cases}$ and sends $A,B,C$ to the adversary.

  • Adversary tries to guess $\beta$.

Example: You can define CPA-secure (public-key) encryption in terms of the following game:

  • Challenger generates keypair $(sk,pk)$ and gives $pk$ to the adversary.

  • Adversary chooses two plaintexts $m_0, m_1$.

  • Challenger chooses random bit $\beta$ and gives $\textsf{Enc}(pk,m_\beta)$ to the adversary.

  • Adversary tries to guess $\beta$.

The first game is non-interactive, with the adversary simply receiving values (the final guess of the adversary is not really counted). So DDH is a non-interactive assumption.

The second game is interactive since the adversary is allowed to choose his plaintexts after seeing the public key. So CPA security is an interactive assumption.

Now suppose you're trying to prove that some interactive system of yours is secure. You can always just take "my system is secure" as an assumption, but you haven't actually done anything in this case. On the other hand, if you base the security of your interactive system on a non-interactive assumption, then you must have actually done something non-trivial. In general, we want to base security on the simplest possible assumptions, and interaction is a natural way to measure the "simplicity" of an assumption.

Victor Shoup. Sequences of games: a tool for taming complexity in security proofs. Cryptology ePrint Archive, Report 2004/332, 2004.

Mihir Bellare and Phillip Rogaway. The security of triple encryption and a framework for code-based game-playing proofs. In EUROCRYPT 2006, LNCS vol 4004, p409-426.

| improve this answer | |
  • $\begingroup$ If at some point of your protocol there is an instance of exactly equivalent well known assumption (e.g: DDH), then during the proof the argumentation is "this is an instance of a well-known assumption" and the proof is over? Or you have to instantiate an attacker who is given an instance to the well known problem and he will use attacker A of the scheme to solve his problem? But this is difficult when we are talking about the same assumptions, because the instance of problem B is given should much with that of A. $\endgroup$ – curious Feb 9 '16 at 17:07
  • $\begingroup$ Also comparing CPA with DDH is like comparing apples and oranges...Isn't it? CPA maybe secure because internally the attacker cannot solve ddh for instance. So we can't really compare them i think $\endgroup$ – curious Feb 9 '16 at 17:09

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.