1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Since there are infinitely many implementations for every function which you can not distinguish by input-output pairs, the question is trivial. What are you really after? $\endgroup$ – Raphael Sep 10 '14 at 10:32
  • $\begingroup$ Are you looking for zero-knowledge proofs by any chance, see en.wikipedia.org/wiki/Zero-knowledge_proof ? The "proofs" usually take the form of some hard computational problem. $\endgroup$ – Andrej Bauer Sep 10 '14 at 23:57
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But if $\mathrm{verify}f$ contains a verification that the value returned by $f$ contains a prime number with $x$ numbers (for example) you can work out that's what the implementation of $f$ does. $\endgroup$ – MattyW Sep 8 '14 at 17:17
  • $\begingroup$ Perhaps we're using "implementation" in different ways. To me, the implementation is, essentially, the algorithm used to compute $f$. Knowing that the function $\mathrm{verify}f$ exists doesn't tell you how to find it and it certainly doesn't tell you what code I wrote to implement the function defined by $f$. $\endgroup$ – David Richerby Sep 8 '14 at 17:25
  • $\begingroup$ I'm explaining myself badly. Specifically it's a question about security - but without certificates or keys. Let's say I have a server that you send numbers to and it gives you numbers back. I give you the code for contacting the server and verifying that you contacted my server. In this code you can change the url but not the verify function. You can implement your own server that still passes the existing verification function because by just examining the verify function you can work out when it will return true for any given input $\endgroup$ – MattyW Sep 8 '14 at 17:59
  • $\begingroup$ I think I've satisfied myself that the question doesn't make any sense. The question comes down to if you have a $\mathrm{verify}f$ that you know the implementation of. But even though you know the implementation it's impossible to work out what value you can give it to make it return true $\endgroup$ – MattyW Sep 8 '14 at 18:03
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 :-).

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.