Bristol
Reputation
674
Next privilege 750 Rep.
 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). Jul23 awarded Yearling Jun30 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. Jun26 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. Jun25 answered Secret key and Decryption oracle in the revised Fujisaki-Okamoto transformation Jun25 answered Why is the public/private key length used in libsodium so much shorter than needed for RSA Jun2 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. Jun1 revised About Primitive roots mod n in Diffie-Hellman added 25 characters in body May29 answered How to decrypt a PGP message with only the two primes and the public exponent? May29 answered About Primitive roots mod n in Diffie-Hellman May22 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.