Reputation
2,092
Top tag
Next privilege 3,500 Rep.
Protect questions
Badges
2 15
Newest
 Caucus
Impact
~44k people reached

  • 0 posts edited
  • 0 helpful flags
  • 59 votes cast
Jul
25
comment Secure ElGamal with OAEP
I've briefly considered the hashed ElGamal case, and I can't immediately see a security proof. For certain groups, there are CCA2 attacks, but for other groups, I can't find good attacks.
Jul
25
comment Secure ElGamal with OAEP
Your argument is fine, but only for CCA2 security. (For CCA1, you don't have a decryption oracle after you get the challenge ciphertext.) Also, there are no good CCA1 attacks against ElGamal on its own, and the padding doesn't change that.
May
21
comment Given $g^a, g^b, g^c, g^{1/b}$, is it hard to distinguish $e(g, g)^{abc}$ from a random value?
That seems like it might work, cygnusv. You need to verify that, given the distribution of the input tuple, the distribution of the tuple you produce is the same as the solver expects. When T is random, your Q should be random. When T is real, so should Q be.
May
21
comment Given $g^a, g^b, g^c, g^{1/b}$, is it hard to distinguish $e(g, g)^{abc}$ from a random value?
This answer is incorrect. To see why, consider a solver that simply computes the requisite d.logs. and then trivially decides the correct answer. Now modify the solver so that if its third and fourth inputs are identical, it instead flips a coin to determine its answer. Since they are almost never identical, this is still a good solver. Apply your reduction to this modified solver. This results in an algorithm that flips a coin, which is not a good solver for 2-wBDHI. Ergo, your reduction does not work. Perhaps it can be fixed.
Apr
22
comment Verification of Pinocchio (verifiable computation)
You should probably add a link to the paper and make it easier for readers to find this $y$ and the verification procedure in the paper.
Mar
18
comment Concatenation of two strong hashes may have striking weakness
If $H_0$ and $H_1$ are independent hashes, the intuitive result holds in ROM, I guess.
Mar
18
comment Concatenation of two strong hashes may have striking weakness
Preimage resistance is indeed much more difficult to define than most basic texts pretend. Many natural definitions are defective in that obviously insecure constructions are secure according to the definition (e.g. choose an element at random from the co-domain: the preimage-finder must find a preimage of that element). I think a plausible definition is: the adversary chooses a suitable plaintext distribution, you sample from the distribution and compute the hash value, finally the adversary recovers any preimage. Under this definition, concatenation is not preimage-resistance-preserving.
Jan
13
comment Key derivation of public key without knowledge of private key
Yep. ten letters
Jan
12
comment Key derivation of public key without knowledge of private key
The Elgamal signature scheme is quite different from the Elgamal encryption scheme. This idea won't work for Elgamal signatures, indeed, it can't work for any signature scheme.
Jan
12
comment Key derivation of public key without knowledge of private key
Any encryption of $1$ can be used as a public key. The extra per-key information is not needed, as the same decryption key can be used for all the public keys made in this way.
Jan
11
comment How much (home PC) CPU time is required to generate a prime number of a given size?
Would you do AKS for every candidate? Why not eliminate candidates with simpler tests first, then do AKS (or ECPP) once you know you have a prime?
Jan
11
comment Strength of RSA with OAEP
You could also mention that RSA-KEM is often a better alternative than RSA-OAEP (simpler, better security guarantee).
Jan
8
comment Variant of the Decisional Bilinear Diffie Hellman problem
I've looked at it for a few minutes, and I wouldn't expect them to be equivalent. The information about $y$ in your problem lies only in the field. To get a DBDH relation related to $y$ seems to require some kind of pairing inversion, which is very hard to do.
Dec
29
comment Formal proof of theorem concerning the Random Oracle Model
It's obvious. Recall that choosing a random function is equivalent to choosing the function values independently, one at a time.
Dec
23
comment Which multiplicatively homomorphic encryption scheme supports encryption of 0?
If you can live with $\{0,1\}$ as the message space, use any additively homomorphic scheme with a large message space and interpret encryptions of zero as $1$, and encryptions of anything else as $0$. Note that if you combine a ciphertext with itself a random number of times, this does not change the interpreted value of the ciphertext. To "multiply" two ciphertexts, randomize them (as above) and combine them.
Dec
22
comment Protecting a short password
Clarify your question, then add a n choose k. By the way, if you replace bytes in the Base64 expansion, you should use 6 above, not 8.
Dec
21
comment Can a cryptosystem be unconditional secure if the same key $k \in \mathcal K$ is used for more than one encryption?
This isn't actually unconditionally secure unless you have state. Without a state, you may end up reusing key material.
Oct
20
comment Security proof of FO(Fujisaki-Okamoto) hybrid encryption
ECIES. RSA-KEM.
Sep
11
comment Proof for composed signatures
If $\epsilon_3$ is smaller than all three of $\epsilon$, $\epsilon'$ and $\epsilon''$, it will be smaller than the minimum, not the maximum...
Sep
4
comment Proof for composed signatures
You have $\epsilon_3 \leq \epsilon$, $\epsilon_3 \leq \epsilon'$ and $\epsilon_3 \leq \epsilon''$. Can you find a smaller bound?