Reputation
674
Next privilege 750 Rep.
See votes, expandable usercard
Badges
3 5
Newest
 Revival
Impact
~4k people reached

  • 0 posts edited
  • 0 helpful flags
  • 6 votes cast
2h
comment Signature and hash function properties
My example needed $H$ to have collisions in the first place. If $P$ is a permutation on some finite set then it is trivially collision resistant but may or may not be preimage resistant; conversely if $H$ is preimage resistant then $H'$ that throws away the first bit of its input and evaluates $H$ on the rest is obviously not collision resistant, but may still be preimage resistant. So collision and preimage resistance are incomparable in general.
7h
comment Signature and hash function properties
Imagine that $H$ is easy to invert, pick an input $s$ somewhat randomly and compute $h = H(s), s' = H^{-1}(h)$. If $s \neq s'$ then you have a collision. But $H^{-1}$ doesn't know which $s$ you picked, so if there are many preimages (which there are as soon as $H$ compresses), you have a good chance of finding a collision using a preimage oracle.
23h
awarded  Revival
1d
answered Do Gap-CDH groups exist?
1d
comment Groth-Sahai proofs and hardness assumptions
Groth-Sahai is more of a "template" that you can implement for different groups and assumptions. DLIN, SXDH and subgroup decision are three example implementations given in the original paper.
1d
comment Ephemeral key is held constant in ElGamal
If $m_1 = m_2$ then the two ciphertexts will be identical, which Eve can certainly see. Even if not, Eve can compute $m_2/m_1$ or similar combinations. It doesn't directly leak $m_1$, but if Eve ever sees $m_2$ later on then she can recover $m_1$ from the quotient.
1d
comment Hiding and Binding key in Groth-Sahai NIZK proof system
I personally find "Groth-Sahai proofs revisited" has a clearer presentation of what's going on, and it fixes a few small mistakes/typos.
1d
comment point addition in NaCl/libsodium (Curve25519)
You make a good point - perhaps I need to look for a different library. I was hoping for something to code a small ElGamal-based voting scheme based on ECC.
1d
asked point addition in NaCl/libsodium (Curve25519)
1d
comment Secure ElGamal with OAEP
@K.G. : you're right, I confused IND-CCA1 and IND-1-CCA (where you get only a single decryption query, but it may be after you've seen the challenge ciphertext).
Jul
23
awarded  Yearling
Jun
30
comment Secret key and Decryption oracle in the revised Fujisaki-Okamoto transformation
The two concepts are closely related. Consider for example Shoup and Gennaro's '98 paper with the TDH schemes. The general principle is that you take an IND-CPA scheme (ElGamal will do), add some form of PoK and then hope it's CCA. The intuition is that we make the decryption oracle useless for the adversary by making sure that the only valid ciphertexts she can construct are ones where she already knows the message - formally, the decryption oracle is based on the knowledge extractor of the PoK. Unfortunately the details are a bit more complex.
Jun
26
comment Why is the public/private key length used in libsodium so much shorter than needed for RSA
Yes. I was thinking of the original NaCl lib, which is pretty much only Curve25519.
Jun
25
answered Secret key and Decryption oracle in the revised Fujisaki-Okamoto transformation
Jun
25
answered Why is the public/private key length used in libsodium so much shorter than needed for RSA
Jun
2
comment About Primitive roots mod n in Diffie-Hellman
If p is a prime then there are no factors of p to worry about! There's something else I didn't mention above, which motivates the choice of q rather than p-1: picking a generator of prime order means that the cyclic group thus generated has no nontrivial subgroups, so you don't have to deal with the possibility of small-subgroup attacks on some schemes. Admittedly this isn't such a problem when the only other factor is 2, but it's still nicer to work in a prime order group.
Jun
1
revised About Primitive roots mod n in Diffie-Hellman
added 25 characters in body
May
29
answered How to decrypt a PGP message with only the two primes and the public exponent?
May
29
answered About Primitive roots mod n in Diffie-Hellman
May
22
comment one-way deterministic hash for low entropy input?
Here's how facebook does it : twitter.com/filosottile/status/552830697942319105 Note - they use a salt, which you really should consider as well.