Suppose I have the following encryption scheme: for a message $m\in\mathbb{F}_p^*$, I generate the ciphertext = $(g^r,f^mh^r)$ where $g$ is the generator of a cyclic group $G$ of unknown order $n$ and $F$ is a cyclic subgroup of $G$ of order $p$ and $h=g^x$ where $x$ is the secret key.

Since $G$'s order is unknown we randomly generate $x$ from a sufficiently large set of numbers $\{0, \cdots, B\}$ where $B$ is an upper bound on $n$ that can be calculated for a $b$ bit security level and $B$ is chosen in way such that $g^x$ is indistinguishable from the uniform distribution in $G$ i.e. to ensure $g^x$ is a random element from $G$.

Now suppose we want to protect this scheme against generic discrete log attacks for 80 bits of security and in this case our $\log_2B\gg 160$. Also, for 80 bits security, our secret key $x$ has to be at least 160 bits as our generic discrete log attacks have a $\sqrt n$ complexity.

Question -- Because I only need $x$ to be of 160 bits, can I explicitly choose a random $x$ of 160 bits and disregard my theoretical bound $B$ which is huge in size. My reasoning is yes because I want to prevent an attack at 80 bit security level, all I need is $x$ to be 160 bits and I can ignore $B$. Is my reasoning valid? Also, some explanation would be great if I am wrong.


Your Answer

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

Browse other questions tagged or ask your own question.