Re: [math-fun] obfuscated programs, moron detection interlude
I certainly have not read the proofs: just this thread, and the article I cited! But it looks as if your observation concerning resource inflation is probably the key --- it's all rather reminiscent of some claims about "universal" models of computation, which turn out to depend on some very dubious encoding scheme being required covertly to do most of the work. I simply don't believe that any practical scheme will encode --- for example --- my prime input into an obfuscated prime before forwarding it to the server; and if it fails to do so, the server cannot possibly factorise it correctly! So I'm afraid my hunch is to side with WDS: there's a gaping hole lurking somewhere. WFL On 2/5/14, Steve Witham <sw@tiac.net> wrote:
Date: Tue, 4 Feb 2014 14:57:18 -0500 From: Warren D Smith <warren.wds@gmail.com>
Date: Wed, 5 Feb 2014 02:34:39 +0000 From: Fred Lunnon <fred.lunnon@gmail.com>
From: Warren D Smith <warren.wds@gmail.com>
--I can write an interpreter WI for interpreting any program written in Warren's Programming Language (WPL). WI works as follows. First, if decrypts the WPL program by public key cryptography with the decryption key 4103943687648904689346189789676897642975685988043769349707438017463179432. Second, it views the result as a BASIC program and runs it. Now. Doesn't the net program (WI+its input) at seem pretty darn obfuscated to you?
Here's the definition of indistinguishability obfuscation:
A program-garbling procedure qualifies as an indistinguishability obfuscator if, whenever two programs that do exactly the same thing pass through the obfuscator, no one is able to tell which garbled program came from which original.
That is, no one can tell which is which by any (tractable) means, including watching and deeply studying the sequences of internal states as the programs run. Watching WI run, we would see the plaintext BASIC program pop out, so that's not very obfuscated.
- - -
From: Fred Lunnon <fred.lunnon@gmail.com>
Most intriguing notion of "homomorphic encryption", of which I knew not: http://en.wikipedia.org/wiki/Homomorphic_encryption
But I'm unconvinced about some the claims apparently being made for it.
Do you mean you've read the proofs? Not that I have.
For example, if I encrypt a large integer and send it off to an insecure factorising server, am I going to receive in return its encrypted factorisation, despite the server being unable to decrypt the input? Hmm ...
That's exactly what I read the wikipedia article to be claiming. -> for certain operations <- I don't know whether factoring can be constructed from those operations.
But if the hard problem inside indistinguishability obfuscation turns out to be truly hard, the answer is a definite "Yes, but." You write a straightforward: input an encrypted message decrypt it with this secret-key cypher factor it encrypt the result with this secret-key cypher output the encrypted result
...which you would compile into the obfuscator's input language and run thru the obfuscator, producing a circuit diagram which you would send to the server in advance. Then you could send it an encrypted number, and get back the encrypted factorization.
BUT, with the current state of the art, the run time is much larger than that of the original, and the circuit size is proportional to that big run time, which makes it impractical to send or store.
--Steve
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The factorisation example may be transformed into a proof that, given a universal insecure server, general-purpose data-obfuscation (or equivalently program-obfuscation) is impossible, however large the resources committed to the encoding process, . For if not, then there is a recursive homomorphism e : |N -> |N (say) such that for every recursive homomorphism f : |N -> {0, 1} [or terminating binary Turing machine, boolean C function etc.] e^(-1)(f(e(x))) = f(x) for all x in |N [ e commutes with all computable f ] . But given any particular input x' in |N , I claim there exists a characteristic function f_x' such that { x | f_(x) = 0 } = {x'} . In principle this is trivial --- simply let f_x' = x - x' --- but such solutions plainly cheat, in some intuitive though at present unspecified sense. More respectable instances reside in tables of "interesting numbers", such as mentioned recently on this list: eg. " f(x) := 0 if x is smallest sum of 2 cubes in 2 distinct ways, 1 otherwise " characterising x' = 1729 . Now given e(x') and (unencoded) f_x' , the server can determine the correct result (encoded or otherwise) only provided e(x') = x' . This true for all x' ; therefore e is the identity mapping. QED The objection might be raised that f should be encoded as well; but the encoder must then be at least as powerful as the server, in order to transform nontrivial f_x' such as that above, or primality testing etc., to equivalent f_x" for distinct and effectively randomly specified x" = e(x') . Indeed, the latter task is probably in general noncomputable; whence the resource inflation troll lurking under the bridge! Presumably the authors were long ago well aware of all this, thought it seems subsequently to have escaped less well-informed commentators. Fred Lunnon On 2/5/14, Fred Lunnon <fred.lunnon@gmail.com> wrote:
I certainly have not read the proofs: just this thread, and the article I cited!
But it looks as if your observation concerning resource inflation is probably the key --- it's all rather reminiscent of some claims about "universal" models of computation, which turn out to depend on some very dubious encoding scheme being required covertly to do most of the work.
I simply don't believe that any practical scheme will encode --- for example --- my prime input into an obfuscated prime before forwarding it to the server; and if it fails to do so, the server cannot possibly factorise it correctly! So I'm afraid my hunch is to side with WDS: there's a gaping hole lurking somewhere.
WFL
On 2/5/14, Steve Witham <sw@tiac.net> wrote:
Date: Tue, 4 Feb 2014 14:57:18 -0500 From: Warren D Smith <warren.wds@gmail.com>
Date: Wed, 5 Feb 2014 02:34:39 +0000 From: Fred Lunnon <fred.lunnon@gmail.com>
From: Warren D Smith <warren.wds@gmail.com>
--I can write an interpreter WI for interpreting any program written in Warren's Programming Language (WPL). WI works as follows. First, if decrypts the WPL program by public key cryptography with the decryption key 4103943687648904689346189789676897642975685988043769349707438017463179432. Second, it views the result as a BASIC program and runs it. Now. Doesn't the net program (WI+its input) at seem pretty darn obfuscated to you?
Here's the definition of indistinguishability obfuscation:
A program-garbling procedure qualifies as an indistinguishability obfuscator if, whenever two programs that do exactly the same thing pass through the obfuscator, no one is able to tell which garbled program came from which original.
That is, no one can tell which is which by any (tractable) means, including watching and deeply studying the sequences of internal states as the programs run. Watching WI run, we would see the plaintext BASIC program pop out, so that's not very obfuscated.
- - -
From: Fred Lunnon <fred.lunnon@gmail.com>
Most intriguing notion of "homomorphic encryption", of which I knew not: http://en.wikipedia.org/wiki/Homomorphic_encryption
But I'm unconvinced about some the claims apparently being made for it.
Do you mean you've read the proofs? Not that I have.
For example, if I encrypt a large integer and send it off to an insecure factorising server, am I going to receive in return its encrypted factorisation, despite the server being unable to decrypt the input? Hmm ...
That's exactly what I read the wikipedia article to be claiming. -> for certain operations <- I don't know whether factoring can be constructed from those operations.
But if the hard problem inside indistinguishability obfuscation turns out to be truly hard, the answer is a definite "Yes, but." You write a straightforward: input an encrypted message decrypt it with this secret-key cypher factor it encrypt the result with this secret-key cypher output the encrypted result
...which you would compile into the obfuscator's input language and run thru the obfuscator, producing a circuit diagram which you would send to the server in advance. Then you could send it an encrypted number, and get back the encrypted factorization.
BUT, with the current state of the art, the run time is much larger than that of the original, and the circuit size is proportional to that big run time, which makes it impractical to send or store.
--Steve
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (1)
-
Fred Lunnon