Function whose implementation is difficult (computationaly) to work out

Question

Let's say I've got a function $f$ that takes a single number and returns a number. And I have another function $\mathrm{verify}f$ which takes the input I gave to $f$ and the number returned by $f$ which returns true if the output is the same as $f$ would have returned given the input.

If you know the input and output to $f$ and the function to verify then it is possible to work out what the implementation of $f$ is.

What I'd like to know, is if there exist some function that even if you know the output and the input and the verification function it's impossible to work out what $f$ does.

It feels like these functions must not exist – but I don't know that for sure.

Answer 1

If the function $f$ is computable, then $\mathrm{verify}f$ is computable too: to work out if $y=f(x)$ for some given $x$ and $y$, just compute $f(x)$ and see if it's equal to $y$. That tells you nothing about the implementation of $f$.

The relationship between the difficulty of computing $f$ and $\mathrm{verify}f$ is the essence of the P-vs-NP problem.

Answer 2

There are examples that are vaguely of this sort in cryptography, if you are willing to allow $f$ to also depend upon a key that is kept secret.

If you choose $f$ right, here is what can be achieved. Given many pairs $(x_i,y_i)$ where $y_i=f(k,x_i)$, it can potentially be hard (computationally infeasible) to recover $k$, for someone who has no prior information on $k$. Depending upon your situation, this might or might not be a suitable solution.

Note: This does not contradict the impossibility results in the other answers.

You might also be interested in software obfuscation. Do some reading on the topic, and you'll probably be able to learn more. More detailed questions about obfuscation are probably more likely to reach a knowledgeable audience on Security.SE or Crypto.SE.

Answer 3

It's impossible to have a VerifyF function that will tell you anything about the implementaion of F -- take the simplest function of all; return 0.

Externally, you can not tell difference between:

   return 0;
   return input*0;
   return (randomMemoryLocation!=pi) ? 0 : -1;

In practical terms, this is why some people are dismissive of test driven development. A test does NOT verify that function returns the correct result, it verifies that it did NOT return the INCORRECT result when the test was run.

Whether that is sufficient for your needs is a practical (not theoretical) question. Theoretically, you just can't tell without out being able to examine the function F.

Edit: In fact, it is often the case that different algorithms can be used to produce identical results. This can be used to brute force test the correctness of an implementation, by examining the full range of inputs. This of course is not sufficient if you are concerned about security -- because in that case the algorithm may be sensitive to external factors that do not show up during your testing, even though you covered the entire (visible) input range.

Answer 4

Surprisingly, such functions do exist and are used in public-key digital signatures.

We assume only Bob knows Bob's private key. Bob derives a public key from it, and publishes the public key -- we assume everyone knows Bob's public key.

Let's say I've got a function f that takes a single number and returns a number.

Yes, Bob has a signing function that knows Bob's private key. That signing function takes a single number -- typically the hash of some plaintext message -- and returns a number called a public-key digital signature.

And I have another function verifyf which takes the input I gave to f and the number returned by f which returns true if the output is the same as f would have returned given the input.

Yes, since everyone knows Bob's public key, anyone one the world can use the signature verifying algorithm, which takes the input Bob gave to f -- the hash of some plaintext message; and the number returned by f -- the public-key digital signature -- and also Bob's public key, which everyone knows. The signature verifying algorithm either accepts or rejects the message as an authentic message from Bob.

If you know the input and output to f and the function to verify then it is possible to work out what the implementation of f is.

A signed message from Bob typically contains the plaintext message used as input to Bob's signing function, and also that function's output -- the digital signature.

Most of the details of a signing algorithm are already public, but even if the adversary gets a signed message from Bob, it is widely considered practically impossible to work out exactly what Bob's public key is, or to forge some other message that tricks someone into thinking that other forged message came from Bob.

https://crypto.stackexchange.com/ and https://security.stackexchange.com/ may be better places for asking more detailed questions about such functions.

(I see that D.W. already gave basically the same answer, except without rambling on quite so long :-).

Answer 5

I am a bit uncertain about what you are asking, but I suspect you are looking for zero-knowledge proofs. Here's the basic idea.

Suppose I want to convince you that I know where Elmo is (I hope you know the game) without telling you where Elmo is. I take a big sheet of paper, cut an Elmo-shaped hole in it, cover the puzzle so that the hole is directly above Elmo. You can now verify that I know where Elmo is, but you yourself do not know how to find him.

Translating this to your question we have a function $f$ which finds Elmo, and a verifier $v$ which checks that Elmo can be seen through the hole. There is no way for the verifier to figure out how I found Elmo.

Zero-knowledge proofs are a grown-up form of the same idea. They can be used for security, read the Wikipedia page.