Reputation
21,551
Next tag badge:
97/100 score
23/20 answers
Badges
4 29 79
Impact
~445k people reached

Dec
11
answered Block Cipher Mode Amicable to Fast Key Change/Rotation Like XOR?
Dec
11
revised RC2, RC4, RC5 key length
added 278 characters in body
Dec
11
answered Can one use a Cryptographic Accumulator to efficiently store Lamport public keys without the need of a Merkle Tree?
Dec
10
comment Slow one-way pseudo-random permutation?
@K.G., cool! Would you care to add that as a separate answer, so we can upvote it? Also, do you know anything about the security of the discrete log on such curves? Is it also the case that the best currently-known algorithm is a square-root algorithm (i.e., we don't know how to do better than the generic algorithms for square roots in a black-box group)?
Dec
9
revised How hard is to invert the function that computes the middle-bits of (x^2)?
Improve based upon poncho's suggestion.
Dec
9
comment Slow one-way pseudo-random permutation?
Why do you need to store the permutation as $2^m$ words of $m$ bits, rather than just using any short-block cipher on $m$-bit blocks? Also: what's the security gap you expect from this? (i.e., the ratio in workfactor to break vs the workfactor for the legitimate parties to compute this function.) My rough back-of-the-envelope estimate suggests you should expect a very small security gap. If we precompute the discrete log of all primes up to $2^{21}$ (about $2^{17}$) of them, the time to compute a single discrete log is about 200 smoothness tests (sieving + ECM on a $\le 84$-bit number).
Dec
9
answered What is “serial concatenation”?
Dec
8
comment Slow one-way pseudo-random permutation?
Right. This answer doesn't work. If the matrix is non-invertible, then this won't be a permutation. The original question asks for a one-way permutation. (If it didn't need to be a permutation, this question would be easy to solve: you could just use SHA256 truncated appropriately.)
Dec
7
revised PRP representation size
added 126 characters in body
Dec
7
comment PRP representation size
@Bush, your question still has the same problems. Have you tried answering the questions in the last paragraph of my question? They are intended to get you thinking along lines that enable you to clear up your confusion on your own.
Dec
7
answered PRP representation size
Dec
7
comment Slow one-way pseudo-random permutation?
@fgrieu, excellent point. OK, I guess I don't know how to make this slow after all (unless each person will only use the key once -- but that's probably a relatively rare situation). Thank you for catching that.
Dec
7
revised Slow one-way pseudo-random permutation?
added 15 characters in body
Dec
7
comment Slow one-way pseudo-random permutation?
@RickyDemer, yup, either do that (i.e., iterate: a standard way to make something slow), or make the key expansion of $k \mapsto (k_0,k_1)$ slow (if each person will only use the key $k$ once -- which might not apply here, but I mention it just for completeness).
Dec
6
revised Keyed digest function with odds of collision below the birthday bound?
Improve the construction a little bit, per the comment from fgrieu.
Dec
6
comment Keyed digest function with odds of collision below the birthday bound?
Is there any reason to think that the polynomial given here is hard to invert? It looks to me like that paper shows that these polynomials are easy to invert. In particular, it looks like the proofs of Propositions 1 and 2 give an explicit algorithm to find $x$ such that $p(x)=d$ (where $p$ is one of these permutation polynomials). For instance, equation (9) shows how to solve $(x^{2^k}+x+a)^{-l}+x=d$ for $x$, and the displayed equation at the end of Proposition 2 shows how to solve $(x^{2^k}+x+a)^s+x=d$ for $x$. (Cc:ing @fgrieu)
Dec
6
revised Slow one-way pseudo-random permutation?
added 52 characters in body
Dec
6
answered Slow one-way pseudo-random permutation?
Dec
6
comment Slow one-way pseudo-random permutation?
I still don't think I understand the requirements, but I suspect if you took a step back and allowed yourself to admit other solutions you could find better, simpler solutions. For instance, something using a trusted server or HSM. P.S. I think there's a solution to the mobile app issue you mentioned. Suppose there's a 256-bit SHA256 hash. You can ask the user to enter in the first 64 bits of the hash, then look it up in the database of items and see if that's to uniquely identify the item; if it isn't, have them enter in the rest. It will be extremely rare that a user needs to enter more.
Dec
6
comment Can insecure algorithms be combined to form a secure algorithm?
Also, they are hoping it will be safe, but there is no proof that this is safe.