Reputation
24,766
Next tag badge:
106/100 score
19/20 answers
Badges
2 32 103
Impact
~360k people reached

Apr
26
revised Non adjacent form of an integer is unique
add link
Apr
26
comment Why does applying 56-bit DES twice only give 57 bits of security?
@CodesInChaos: As is, this attack is not really much work only on an hypothetical computer with at least $2^{59}$ bytes of memory (like 500 times the total RAM on the 80,000 CPUs in the current top supercomputer of the TOP500). Otherwise said, as is, it is purely theoretical. $\;$ That why I'd like to understand what you have in mind.
Apr
26
revised How does ROTL work?
Left to right diffusion is no sped up by rotation; it is created.
Apr
26
revised Non adjacent form of an integer is unique
Put simplified proof of uniqueness first. Streamline existence argument. Explicit formula for length of NAF. Cleanup.
Apr
26
revised Non adjacent form of an integer is unique
Add bibliography
Apr
25
revised How does ROTL work?
Give example uses including those given as tag in the question
Apr
25
revised How does ROTL work?
Notable CPUs that use the ROTL mnemonic. Explain how that's done from C.
Apr
25
answered How does ROTL work?
Apr
25
revised Non adjacent form of an integer is unique
add missing tilde
Apr
25
comment How to securely map an element from an smaller domain to the other element in a large domain
The previous comment makes a convincing argument that if $e$ can be guessed, and $Enc_{pk}(r \cdot e)$ known, and $Enc_{pk}$ is homomorphic, and $e^{-1}$ in the sense of the homomorphism can be computed from $e$, then $Enc_{pk}(r)$ can be successfully guessed. While this is far from the question as written (which does not mention anything like homomorphic, or multiplication by $r$, or that this is random), my conclusion is that what's asked in question and comments can't be achieved.
Apr
25
comment How to securely map an element from an smaller domain to the other element in a large domain
I have trouble relating the above comment to the question. $\;$ In particular, is the " small sized domain " of the question that of $r$, $e$, or $v$ in the comment? Is the " public encoding " of the question the " Paillier encryption " of the comment? Also, what is meant by " eliminate $e$ " in that comment? I suggest reformulation the question, incorporating the comment in a unified framework.
Apr
25
revised Non adjacent form of an integer is unique
Bounds of the number of digits in the NAF; polish
Apr
25
comment Non adjacent form of an integer is unique
@Vi Jay: Yes, your summary is correct. The answer now gives more details on the general method, called infinite descent , a special form of proof by contradiction. $\;$ Also I revised the proof. Formerly I used $b=(a−1)/4$ in the second case of the second proof, in order to match the first proof, but that left a gap because I assumed without proof that small $a$ had a single NAF. Now I'm first proving that $0$ has a single NAF, and in the second case of the second proof use $b=a−1$, which is simplest. $b=(a−1)/2$ also works.
Apr
25
revised Non adjacent form of an integer is unique
Explain relevance of NAF to crypto
Apr
25
revised Non adjacent form of an integer is unique
Spacing
Apr
25
revised Non adjacent form of an integer is unique
Simpler definition of NAF as a tuple. Make the proofs more detailed and rigorous. In particular, get rid of the "Clearly, a>3" which was clear as mud in the second proof, and required extensive rework.
Apr
25
answered Non adjacent form of an integer is unique
Apr
24
comment Which one these alternatives using authentication and encryption will solve this multiple-user database problem?
@Ricky Demer: We also need that " different users " bit.
Apr
24
comment How to securely map an element from an smaller domain to the other element in a large domain
With the requirements as I understand them, and the addition that the encoding/mapping is a deterministic function (in addition to public), there is no solution, for precisely the reason given in mikeazo's comment.
Apr
24
comment How to securely map an element from an smaller domain to the other element in a large domain
Anything wrong with simply: each user $j$ secretly chooses a 256-bit random secret key $K_j$, then computes the 256-bit $\operatorname{HMAC-SHA-256}(K_j,x)$ where $x$ is a $s$-bit element of the small domain? $\;$ Perhaps that does not match the "public encoding" requirement, even though the method is public?