3 ms·

The article leaves me hanging. Long introduction, describes IO and EO, and when it's time to talk about their uses, it just handwaves "lots of exciting stuff co

by cuu508 13y ago

The article leaves me hanging. Long introduction, describes IO and EO, and when it's time to talk about their uses, it just handwaves "lots of exciting stuff coming in future!" > obfuscating 'symmetric' primitives like pseudorandom functions So how would be obfuscated and indistinguishable RNGs be useful, if they generate the same numbers? I'm sure there is something there, but the article doesn't tell :-/

pbsd 13y ago
Obfuscating a PRF turns a symmetric primitive into an asymmetric one. You can think of a PRF as a keyed hash. Now, you can turn this into an encryption scheme by running it in counter mode: keystream = PRF(K, 0) || PRF(K, 1) || ... ciphertext = plaintext XOR keystream Now suppose we can obfuscate this PRF with a specific key (i.e. Obf(PRF(K, _))), in a way that makes it impossible to find out what K is. Then you can distribute the encrypted program as a public key, and the private key would simply be K. That's the gist of it.
- AnthonyMouse 13y ago
  I don't think you can do it with a stream cipher like that. Rule 1 for a stream cipher is that you never encrypt multiple messages with the same keystream. 'ciphertext = plaintext XOR keystream' means 'keystream = ciphertext XOR plaintext' and the attacker could just encrypt some arbitrary plaintext with the publicly available code and XOR the plaintext back out to obtain the keystream, even if the code itself is a black box. You could probably manage to do it with a block cipher though.
  - pbsd 13y ago
    Yes, you're right, perhaps I oversimplified too much. That is the main hurdle Waters and Sahai have overcome. They do this by not using a counter, but randomly-selected nonces that feed a keyless stream generator (like AES-CTR with a fixed known key), and use a mechanism (puncturing) to 'blacklist' previously-used nonces so that they reveal nothing about previous keystreams used. Without being able to ask for encryptions of arbitrary messages using a previous nonce, the attacker has little options. Granted, this is annoying because you have to 'recompile' the obfuscated encryptor for each new nonce, but that is of no concern in the model being used.

by cuu508 13y ago

pbsd 13y ago

Obfuscating a PRF turns a symmetric primitive into an asymmetric one. You can think of a PRF as a keyed hash. Now, you can turn this into an encryption scheme by running it in counter mode: keystream = PRF(K, 0) || PRF(K, 1) || ... ciphertext = plaintext XOR keystream Now suppose we can obfuscate this PRF with a specific key (i.e. Obf(PRF(K, _))), in a way that makes it impossible to find out what K is. Then you can distribute the encrypted program as a public key, and the private key would simply be K. That's the gist of it.

AnthonyMouse 13y ago
I don't think you can do it with a stream cipher like that. Rule 1 for a stream cipher is that you never encrypt multiple messages with the same keystream. 'ciphertext = plaintext XOR keystream' means 'keystream = ciphertext XOR plaintext' and the attacker could just encrypt some arbitrary plaintext with the publicly available code and XOR the plaintext back out to obtain the keystream, even if the code itself is a black box. You could probably manage to do it with a block cipher though.
- pbsd 13y ago
  Yes, you're right, perhaps I oversimplified too much. That is the main hurdle Waters and Sahai have overcome. They do this by not using a counter, but randomly-selected nonces that feed a keyless stream generator (like AES-CTR with a fixed known key), and use a mechanism (puncturing) to 'blacklist' previously-used nonces so that they reveal nothing about previous keystreams used. Without being able to ask for encryptions of arbitrary messages using a previous nonce, the attacker has little options. Granted, this is annoying because you have to 'recompile' the obfuscated encryptor for each new nonce, but that is of no concern in the model being used.