20,677 reputation
32574
bio website
location
age
visits member for 3 years, 3 months
seen Nov 10 at 4:37

Mar
14
revised Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
Address bug from @Seth.
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
13
asked Traitor-tracing PRF
Mar
13
accepted Private set intersection, using a semi-trusted server
Mar
13
answered How to best mix two arbitrary/random n-bit words?
Mar
13
answered Do any one-key-of-many cryptographic schemes exist?
Mar
13
answered Linear Cryptanalysis - possible without plaintext?
Mar
13
answered Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
Mar
13
revised Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)
Clean up the question. Improve the latex. Eliminate unnecessary parenthesis, avoid gratuitous \big's. Generalize and focus the question slightly.
Mar
13
answered Are there use cases where a signature itself needs to be signed?
Mar
13
awarded  Popular Question
Mar
12
awarded  rsa
Mar
12
awarded  Enlightened
Mar
11
awarded  Nice Answer
Mar
11
revised Private set intersection, using a semi-trusted server
Clarify that S* is computed locally.
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?