3 ms·
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 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 agoI 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 agoYes, 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.