19,761 reputation
32271
bio website
location
age
visits member for 2 years, 11 months
seen 12 hours ago

Mar
16
comment How can I create an RSA modulus for which no one knows the factors?
Yes, but the algorithms are not practical for reasonable-sized RSA modulus. I'm pretty sure this has been asked before on this site but I can't seem to find where...
Mar
14
comment How to best mix two arbitrary/random n-bit words?
@Mok-KongShen, it would have been better if you had listed those requirements in the question. This is related to why poncho told you your question was too broad/ill-defined. Generally speaking, we tend not to like chameleon questions where someone asks a broad question without listing the requirements, then when they get an answer that answers the question-as-stated, they respond by saying "oh, that wasn't really what I was looking for, I actually had this extra requirement/goal/criterion I didn't tell you about". You can avoid that by asking narrower questions that include all the criteria.
Mar
14
comment Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
@Seth, thank you! I have fixed the error you pointed out. (I had miscounted the number of queries made by my distinguishing algorithm. I've revised my answer; should be fixed now.)
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.