Reputation
2,082
Top tag
Next privilege 3,500 Rep.
Protect questions
Badges
1 14
Newest
 Custodian
Impact
~41k people reached

  • 0 posts edited
  • 0 helpful flags
  • 59 votes cast
13h
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.
20h
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?
Aug
30
comment Proof for composed signatures
Recall that a scheme is $\epsilon$-secure if any adversary has advantage at most $\epsilon$. For any $\epsilon_3$-forger (adversary with advantage $\epsilon_3$) against the composed system, we get an $\epsilon_3$-forger against any of the three systems. Now we apply the definition of secure.
Jul
31
comment Rainbow table for DES with all-zero plaintext?
No, $L$ chains of length $k$; checking if we are in a chain requires computing $k$ sequences of average length $k/2$.