bitlength of $a,(3)a_i$ is the $i-$th bit of $a,(4)a_{[i,j]}$ is a substring $a_i|dots|a_j$ of $a($if $1ij|a|),$

$(5)$ if $|a|=n$ for some even $n$ then $a_L$ and $a_R$ stand for respectively $a_{[1,\frac{n}{2}]}$ and $a_{[\frac{n}{2}+1,n]}.$

$1$ How safe are negligible attacks if attack resources grow?

Adversarial advantage in breaking some cryptographic scheme is a function of the security

parameter $$ used to instantiate the scheme $($ is typically the length of the key$)$ and of the

adversary's computational resources. Assume that the adversarial advantage grows linearly

with adversary's resources, i$.$e$.$ if adversary's computing power grows by a factor of $$ then his

chance of breaking a cryptosystem will grow by the same factor of $.$ Assume that if you fix

adversary's computing power then his adversarial advantage against a given cryptographic

scheme is a decreasing function $lon()$ of the security parameter $.$ Assume that advantage

$lo{n}_1=2^{-20}$ is considered safe in the context of some application. Whatever function $lon()$ is$,$

this maps to some threshold value ${}_1$ which is the smallest value s$.$t$.lon({}_1)lo{n}_1,$ but since we

can assume that $lon$ is strictly decreasing, you can just define ${}_1$ as the value s$.$t$.lon({}_1)=lo{n}_1.$

Consider the possibility that adversary's resources grow by a factor of $,$ e$.$g$.$ because

of continuing decrease in computational costs. To achieve the same security bound of $2^{-20}$

against such stronger attacks we need to increase the security parameter to a new threshold

value ${}_2$ s$.$t$.lon({}_2)=lo{n}_2$ where $lo{n}_2=(\frac{1}{})**lo{n}_1.$ To see why, note that if the adversary has $lon$

advantage using $x$ computation, then if he can perform $**x$ computation instead, then

one thing he can do is to repeat the $x-$computation attack $$ times, which will bump up his

probability of attack to $1-(1-lon{)}^{},$ which for small $lon$ comes very close to $**lon.$ This is why

if adversary's resources grow by a factor of $$ and we need to maintain the $2^{-20}$ security

bound then we need to set $$ s$.$t$.lon()$ satisfies $**lon()2^{-20}.$

Consider the following functions $lon(),$ and in each case do the following: $($a$)$ compute

${}_1$ s$.$t$.lon({}_1)=lo{n}_1=2^{-20},($b$)$ express ${}_2$ as a function of $($note that ${}_2$ should satisfy

$\{$:$lon({}_2)=lo{n}_2=(\frac{1}{})**lo{n}_1=(\frac{1}{})**2^{-20}),($c$)$ compute ${}_2$ for $=2^{30}.$

$lon()=2^{-}$

$lon()=2^{-\sqrt[\phantom{2}]{}}$

$lon()=\frac{1}{{}^4}$

Assume that the computational cost of the cryptographic scheme used in this application

is $T()={}^2.($The cost of an efficient scheme must be at most some polynomial in $.)$ For

each of the above three cases of function $lon,$ do the following: $($a$)$ compute $T_1=T({}_1),($b$)$

state what $T_2=T({}_2)$ is as