While reading some text on cryptography, I found that algorithm $A$, that the adversary (called Eve by convention) runs to break the cipher message, needs two parameters, candidate message ($y$) and length of message ($k$).

Now, this $k$ is being supplied in unary.

The reasons for that are being put forth in one text like this:

Technically, we will have to explicitly supply $k$ as part of the input. However, instead of giving them $k$ in binary, which is only log $k$ bits long, we will give $k$ in unary, which is indeed $k$ bits long. This is done to ensure that all our algorithms — which are polynomial in their input length — are allowed to run in time polynomial in the security parameter $k$. Thus, providing $k$ in unary is a convenient way to ensure that polynomial in $k$ time is allowed.

Introduction to Cryptography, Lecture 1, Yevgeniy Dodis (PDF)

I understand above text, more or less. We need to ensure that all the inputs are $k$ length. So, the algorithm will run in polynomial time $k$. But my point is, why would the adversary bother? Is it not more convenient for Eve, if the input is shorter? (Sorry, if I misunderstood this.)

Another text mentions the same reasons as:

The main reason for this convention is to rule out the possibility that a function will be considered one-way merely because it drastically shrinks its input, and so the inverting algorithm just does not have enough time to print the desired output (i.e., the corresponding pre-image). (There some more text on log of input length.)

Foundations of Cryptography, Oded Goldreich, Cambridge University Press

In addition to the previous queries, I fail to understand the point of `printing'.

Please explain the point, why input $k$ needs to be in unary?

  • $\begingroup$ Incidentally, this would probably fit better on cstheory. $\:$ $\endgroup$
    – user991
    May 18 '13 at 19:12

I explained this at Why does key generation take an input $1^k$, and how do I represent it in practice?. Take a look at that one. Basically, it's an artificial little detail that's only there to keep the theoretical details squared away. You can safely ignore it on first reading.

In concrete security, this $1^k$ is no longer needed; it only shows up in asymptotic complexity theory. Concrete security is more relevant in practice anyway.

In asymptotic crypto-theory, we allow the adversary to run in time polynomial in the length of the input. The longer the input, the longer the adversary is allowed to take. Thus, it's not more convenient for the adversary if the input is shorter. Notice that this is a purely artificial element of asymptotic theory, where "efficient" is defined as "runs in asymptotically polynomial time in the length of the input" -- that definition is artificial and doesn't really correspond to reality (but it's sometimes convenient for theoretical analysis).


The adversary would bother to be 'allowed' more time.
It is not more convenient for Eve if the input is shorter becase, [for all functions $\hspace{.02 in}f : \{0,1,2,3,...\} \to \{0,1,2,3,...\} \:$ and $\: g : \{0,1,2,3,...\} \to \{0,1,2,3,...\} \:$,
if [$\hspace{.005 in}$for all non-negative integers $n$, $\: f(n) \leq g(n) \:$], then
"polynomial in $\hspace{.01 in}f(n)$" is no less restrictive than "polynomial in $g(n)$"].

The point of 'printing' is that the machine needs to have the
(candidate) preimage on the relevant tape in order to output it.


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