2,852 reputation
1022
bio website
location
age
visits member for 3 years, 3 months
seen yesterday

Nov
19
comment Do data-dependent rotations have any advantage over fixed rotations?
Probably. Analysis is still more difficult on data-dependent rotations, and so it may be wise to assume the attacker can force them to have no difference. This is especially the case in hash functions, where the attacker controls almost everything; here's an example. When assuming no differences in the rotations, fixed rotations start to seem like the better choice.
Oct
30
comment What are these twist attacks with cost $2^{58.4}$ on NIST P-224 curve, and when do they apply?
Nevermind, I was assuming you had direct access to the points on the twist. Here you cannot use plain rho.
Oct
30
comment What are these twist attacks with cost $2^{58.4}$ on NIST P-224 curve, and when do they apply?
The complexity for kangaroo is slighly different when taking the negation map into account. You can use rho in this situation, though, like you would in Pohlig-Hellman.
Oct
30
comment What are these twist attacks with cost $2^{58.4}$ on NIST P-224 curve, and when do they apply?
$\log(\pi/4 l)/\log(4) = \log(\sqrt{\pi/4 l})/\log(2) = \log(\sqrt{\pi l / 2} / \sqrt{2})/\log(2)$. It's the usual Pollard rho complexity with the negation map taken into account.
Aug
15
comment Subverting the key generation step in RSA public key cryptography
This method subverts the RSA public key in several ways, one of which is by embedding part of the secret prime in the modulus itself. The rest can be recovered in polynomial time.
Jun
19
comment Parallelized Pollard's Rho algorithm for ECDLP + Jacobian coordinates
That should work (modulo a few unlikely corner cases). But keep in mind that will still be slower than affine with batch inversions; for a large enough batch, an inversion costs 3 multiplications, and affine coordinates look much better performance-wise than Jacobian, even assuming the DP check is free.
Jan
13
comment Is there a feasible method by which NIST ECC curves over prime fields could be intentionally rigged?
The only thing that comes close to what you are asking is Edlyn Teske's isogeny trick, mentioned in the other question. Apart from that, there is only speculation about unknown weaknesses.
Jan
13
comment Time complexity to solve Discrete log problem
You're right, of course. Given it's little-oh, that factor can actually be any function, as long as it becomes insignificant at infinity input sizes.
Dec
6
comment Why are these techniques not feasible to crack RSA?
It seems I misunderstood what you said earlier. You're correct.
Dec
6
comment Why are these techniques not feasible to crack RSA?
It's actually equivalent to factoring: you can compute $\phi(n)$ quickly from the factors, and you can find the factors quickly from $phi(n)$. No, $d = 1/e \bmod \phi(n)$. This does not result in a fraction, because we are working in modular arithmetic. There are efficient algorithms to do this.
Dec
6
comment Why are these techniques not feasible to crack RSA?
Like factoring, it becomes much harder as $n$ grows. If you try to do it for a $2048$-bit $n$, it will not be so easy.
Dec
6
comment Why are these techniques not feasible to crack RSA?
To solve for $d$, you must find out $\phi(n)$, since $d = e^{-1} \bmod \phi(n)$. That is the hard part.
Dec
4
comment Keyed digest function with odds of collision below the birthday bound?
Are you aware of any attempt to invert such permutations faster than brute-force? First step would probably be to distinguish the polynomial system from random.
Nov
21
comment When using Curve25519, why does the private key always have a fixed bit at 2^254?
It is true that the reference code protects against this by starting with $(P, \infty)$; however, every textbook displays the version I described, so there's a good chance that an independent implementer could make that mistake. Setting that bit to 1 is a preventive measure that costs almost nothing.
Nov
8
comment What is so special about elliptic curves?
A sphere ($x^2 + y^2 + z^2 = 1$) would still not be secure; however, if you intersect two quadric surfaces (i.e. surfaces defined by quadratic polynomials) you actually can get a secure curve, which --- guess what --- is actually an elliptic curve! The Jacobi intersection curves are an example of this.
Sep
19
comment Is the inverse of a secure PRP, also a secure PRP?
The stronger concept of sPRP (e.g., 4-round Feistel with PRF) implies that the inverse is secure as well --- an sPRP allows the attacker to query both the permutation and its inverse.
Sep
15
comment What stops the Multiply-With-Carry Random Number Generator from being a Cryptographically Secure Pseudo-Random Number Generator?
This article may be helpful: eprint.iacr.org/2011/007 The short story is that given MWC output, it's fairly easy to recover internal state and do all kinds of bad things from there.
Aug
1
comment What exactly is the base for the KECCAK (SHA3) claim that a security strength of 256 bits is “post-quantum sufficient”?
It is also worth noting that both the Grover and Brassard-Hoyer-Tapp algorithms for quantum search and collision finding are essentially optimal, i.e., they match the asymptotic known lower-bounds.
Jul
31
comment Practical consequences of using functional encryption for software obfuscation
There's nothing practical about that paper. Notice the use of multilinear maps and fully homomorphic encryption. I suspect this will only be practical when FHE is also practical.
Jul
6
comment Snowden Challenge II: Can we solve Snowden challenge quantumly?
The classical attack on the original 1978 parameters of McEliece is hardly evidence of weakness of the scheme. In comparison, RSA key size was originally proposed to be 200 digits (665 bits), and estimated to take billions of years to factor.