Tag Info

New answers tagged complexity

2

Well, ECC takes about $2^{n/2}$ time to break because there are smarter ways to attack it than literally trying each possible key separately. With AES, the best known-attack is to try a key, and see if it works. If it doesn't, all you've learned is that that specific key wasn't it, only $2^{n}-1$ more to go... However, with ECC, there are other methods. ...

1

Bitcoin's proof-of-work problem is solved in constant time, since there is no asymptotics. Complexity classes are irrelevant here.

4

On the first question The public key of DGHV's SHE scheme consists of $\tau+1$ $\gamma$-bit numbers, that is, $pk = (x_0,\dots,x_\tau)$, where $x_i$ is chosen from the distribution $\mathcal{D}_{\gamma,\rho}(p)$ over $[0,2^{\gamma})$. Therefore, the length of $pk$ is $O(\tau \gamma)$, which is $\tilde{O}(\lambda^{10})$ if we adopt the parameters \$\gamma = ...

Top 50 recent answers are included