20,510 reputation
32573
bio website
location
age
visits member for 3 years, 2 months
seen 2 days ago

Mar
14
comment Traitor-tracing PRF
@RickyDemer, I realized there is a big hole in my reasoning. The argument only shows that if the PRF can be evaluated in NC1, then it's implausible that something like I described can be used for traitor tracing (since we have good reason to believe that indistinguishability obfuscation of NC1 functions is possible). However, if the PRF lives in a higher complexity class, then I think that kind of reasoning goes away, since if I understand correctly, we only know plausible constructions for obfuscation of NC1. Is that right?
Mar
14
comment Traitor-tracing PRF
Thank you! The first paragraph doesn't rule out all constructions, right, since we don't know whether indistinguishability obfuscation is possible beyond NC1? Are there any guesses/conventional wisdom about whether indistinguishability obfuscation is likely to be feasible for higher complexity classes? Your construction from a puncturable PRF is elegant... but alas, I was hoping for something efficient in practice, and with known constructions for indistinguishability obfuscation, I'm afraid this will be highly inefficient.
Mar
13
comment Traitor-tracing PRF
2. Do any other alternative approaches occur to you, for dealing with this problem? Namely, the problem that one of the participants might have their server hacked and their key stolen, and if that happens, it'd be nice if there was some way to track down which participant was responsible (which participant didn't secure their server well enough). Any creative ideas?
Mar
11
comment Private set intersection, using a semi-trusted server
@DrLecter, yup! Isn't that exactly the scheme I described in the body of the question? Or am I misunderstanding something? Thank you for all your help thinking through this!
Mar
11
comment Private set intersection, using a semi-trusted server
@DrLecter, if it would help for Alice and Bob to have a shared secret, feel free to assume they have one. That's not unreasonable.
Mar
11
comment Private set intersection, using a semi-trusted server
@DrLecter, yes, the elements have relatively low entropy (say, 10-40 bits). Therefore, applying a deterministic unkeyed one-way hash function would be highly insecure, because it's so easy to brute-force them, as you say. The use of a (keyed) PRF helps with this particular problem -- but maybe there is an even better or more secure solution?
Feb
28
comment ElGamal signature without calculating the inverse
Nice scheme! For the curious: You are right, it is not secure. Let $(\gamma,\delta)$ be a valid signature on the message $x$. Then $(\gamma^2,\gamma \delta)$ will be a valid signature on the message $\gamma x/2$. (This works as long as either $\gamma$ or $x$ is even.) Therefore, the scheme is not secure against existential forgery. Your answer still seems like a good response to the textbook question, though.
Feb
27
comment Would this simple encrypted chat program be feasible using One Time Pads?
@zuallauz, it doesn't matter if your algorithm is secure in theory against computationally unbounded adversaries if the implementation has a buffer overflow vulnerability that lets anyone penetrate it. That's why I say that in practice this is an information security problem, not just a crypto-mathematics problem.
Feb
24
comment PRP, PRF and modular arithmetic
Please edit your question to give a precise definition of what you mean by an "arithmetic function". Is AES an "arithmetic function"? How about cubing modulo a RSA modulus? Also, please elaborate on what you mean by "simulate". Finally, I suggest you add some context and motivation: why are you asking? what is the real goal? what research have you done to try to solve this on your own?
Feb
24
comment PRP, PRF and modular arithmetic
I've upvoted it because I think it is correct and points the original poster to the key technical term, from which they can find more. You can look up what $k$-wise independent hash functions are pretty easily; I expect they're probably in Wikipedia and in good textbooks on derandomization/randomized algorithms.
Feb
24
comment $f : \mathbb{Z}_n \rightarrow \mathbb{Z}^\times_n$?
Please clarify your question. As it stands, your parenthesis does not correspond to any notion of inversion that I am familiar with. Also please define your notation, e.g., the $\mathbb{Z}_n^\times$ notation. And why is this a cryptography question? Please add some context or motivation, and tell us what you've tried to do on your understand to figure out the answer for yourself. Have you reviewed standard material on modular arithmetic?
Feb
24
comment Seed / reseed DRBG too often?
rzetterberg, for most applications (if you can reseed), the advice in your library documentation is undoubtedly good advice. But for many DRBG's, that advice is probably more cautious than is really necessary. Therefore, if there's some reason why you can't re-seed, don't take that advice as gospel: do a risk analysis to see if it's really necessary.
Feb
21
comment Homomorphic crypto allowing anonymous yes/no votes?
Are you aware that there is tons of work on secure voting schemes? Probably hundreds of papers. Have you done a search on this site and a literature search in the literature? Are you familiar with E2E (end-to-end) cryptographic voting systems? For instance, Helios and VoteBox? That would be a good starting point for you.
Feb
21
comment Compared to GCM or XTS modes, how secure is H xor R1, E (R2, R1, Message) for confidentiality and integrity?
@poncho, I took a second look, and you are right. I updated my message accordingly. The bottom line is still the same, though: I can't see any reason to use this scheme.
Feb
21
comment Practical usage of S/KEY
You know that S/KEY and OTP have serious problems if they are used on their own (e.g., over an insecure channel, or if the user does not carefully check who they are authenticating to every time), right? That might be why you haven't heard of much deployed use of it.
Feb
21
comment Seed / reseed DRBG too often?
Actually, the premise that you need to reseed periodically ain't necessarily so. Some documents might suggest that reseeding is mandatory, but if you choose a good DBRG, it's not strictly necessary. The decision of whether to reseed should be based upon a thoughtful risk analysis, not just a blind rule-based "the standard says I have to reseed so I guess I have to".
Feb
21
comment Is there a “brainwallet” for GPG keys?
@RobKohr, you might personally think that password quality not a problem.... but in practice, it is a problem. A 5-word passphrase might have entropy as low as 50 bits or lower. That's not enough to resist off-line attack and would have security problems if you faced a serious motivated adversary.
Feb
18
comment Proving that a function is not a OWF (One-way-function)
@Pinocchio, yes, for a random $x$. Yes, my answer does not depend upon how $f$ is constructed; it applies regardless.
Feb
18
comment Proof of work for standard computers
Two candidates come to mind. (1) Find an input to scrypt that makes the first 20 bits of its output all zeros. Verification is now pretty cheap. (2) Use timelock puzzles. They admit a very large ratio between the time to solve the puzzle vs the time to construct the puzzle (or to verify the solution).
Feb
16
comment Known vulnerabilities in (EC-)KCDSA
jimmy, Have you done a literature search? That's the obvious first step.