- #1
mXSCNT
- 315
- 1
I got to thinking about code obfuscation. Current code obfuscators use ad hoc techniques like symbol renaming. But is it possible to have a cryptographically secure code obfuscator that outputs programs that work the same way as the originals, but provably no one can understand?
So here's the key idea around what I think that would mean. If you understand a slow program, you should be able to improve the slow parts and make it faster. If a program is slow but you have no idea how to make it faster, you don't understand the program.
So a cryptographically secure code obfuscator is a function F that takes as input a program P, and outputs another program Q (in other words F(P) = Q), where the following conditions apply:
Anyone heard of something like this?
So here's the key idea around what I think that would mean. If you understand a slow program, you should be able to improve the slow parts and make it faster. If a program is slow but you have no idea how to make it faster, you don't understand the program.
So a cryptographically secure code obfuscator is a function F that takes as input a program P, and outputs another program Q (in other words F(P) = Q), where the following conditions apply:
- P and Q both compute the same function, but Q is slower than P
- it should be computationally hard to improve the performance of Q, given only Q and not P. This can be expressed mathematically by saying, there should not exist an easy-to-compute optimization function W such that if F(P) = Q, W(Q) is faster than Q.
- Calculating F should be possible in polynomial time.
Anyone heard of something like this?