5
$\begingroup$

In many cryptographic games, the adversary doesn't seem to be parameterized by the security parameter.‡ Are such games equivalent to variants in which the adversary is parameterized by the security parameter?‡‡

‡ E.g., Bellare et al.'s IND-CPA (Crypto'98) defines: $(pk,sk) \leftarrow K(1^k)$; $(x_0,x_1,s) \leftarrow A_1(pk); ...$, i.e., $A_1$ isn't taking $1^k$.

‡‡ E.g., is the game above equivalent to: $(pk,sk) \leftarrow K(1^k)$; $(x_0,x_1,s) \leftarrow A_1(pk,1^k); ...$.

$\endgroup$
  • $\begingroup$ If you mean "making the adversary depend on the seu-curity parameter", you may want to look into the notion of non-uniformity. $\endgroup$ – fkraiem Jun 22 '16 at 16:10
  • $\begingroup$ I meant is A(k) more powerful than A(), where k is a security parameter and A is the adversary. I suspect they are not, but I don't understand why. Perhaps A() can find k by brute force, thus k isn't needed. Or ... $\endgroup$ – user2768 Jun 22 '16 at 16:59
  • $\begingroup$ What do you mean by "more powerful"? $\endgroup$ – fkraiem Jun 22 '16 at 17:13
  • $\begingroup$ @user2768 Can you give an example of a scheme in which A() is not taking the security parameter as an input? $\endgroup$ – curious Jun 22 '16 at 20:31
  • $\begingroup$ @fkraiem, "more powerful" as in can A() simulate A(k)'s challenger. $\endgroup$ – user2768 Jun 23 '16 at 7:36
3
$\begingroup$

The adversary should definitely always be "allowed to know" the security parameter. In other words, a security definition should allow the adversary's behavior to depend on the security parameter. This can be accomplished either by quantifying the adversary after the security parameter is chosen, or by letting the security parameter be an explicit input to the adversary.

The alternative would fly in the face of Kerckhoff's principle -- since the adversary is not allowed to "know" the security parameter, it would mean that the scheme is (apparently) deriving some important property from the secrecy of the security parameter.

Nonetheless, here are some valid reasons why this dependence on security parameter might be omitted in the notation:

  • Authors are lazy, the extra parameter to the adversary is cumbersome to write, and the intended audience probably knows the standard conventions about security parameters.

  • In an earlier section, authors have said "all algorithms are assumed to take a global security parameter as common input" or something along those lines.

  • The adversary already gets to see certain things from which it could infer the security parameter anyway. So it is redundant to give the security parameter explicitly. For example, the adversary sees a public key in some security game, and the length of the public key is the security parameter. Especially in things like public-key crypto, it is without loss of generality that you include the security parameter in the public key.

$\endgroup$

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.