3
$\begingroup$

I just read the Wiki article for Simon's Problem but I don't fully understand it because I don't follow the symbolic notation used to describe functions (I am not a computer scientist).

Can someone just briefly explain it in simple language, like is it just XOR'ing two binary strings and trying to isolate each string? Also, if this problem is known to take exponential time to solve, why isn't it being used as a cryptographic primitive?

$\endgroup$
  • 1
    $\begingroup$ Quantum algorithms are probably not the place to start learning about algorithms. If you are coming from an cryptography angle, note that there is Cryptography. (Asking for "simple English" explanations of mathematical things is often a fool's errand.) $\endgroup$ – Raphael Jan 6 '14 at 6:22
  • $\begingroup$ @Raphael: I'm not interested in the quantum angle to this problem, just the classical version and its potential applications to cryptography. I can't cross-post now but it's a moot point, I already have a good enough answer. $\endgroup$ – William Hird Jan 6 '14 at 15:35
7
$\begingroup$

I think there are really three issues buried in your question.

  1. What's Simon's Problem?
  2. What's a plain english description of the function involved in Simon's Problem?
  3. Why isn't this problem a cryptographic primitive?

I can't really speak to 3 as cryptography is not my area. I can take a crack at 1 and 2 for you though. The distinction between 1 and 2 is, I think, important.

Simon's problem is one of discovering the parameter to a function given a black-box to that function and some basic information about the function. So, an algorithm to solve this problem takes as its input a black-box to a function and gives a output a binary string. Our goal is to reduce the number of queries to that black box. I think people tend to miss this point and focus on the internals of the function itself.

All we know about the function $f$ is that our black-box can compute it for us in constant, $O(1)$, time, and that if $f(x) = f(y)$, then either $x=y$ or $x \oplus y = s$. We want to know the value of $s$. A brute force, classical computing solution might give you a better feel for the problem. Here it is:

  1. Feed all $n$ bit binary strings to the black-box and save each input-output pair to a table.
  2. If no two inputs produce the same output then it must be the case that the parameter $s$ is $n$ bit $0$. Otherwise, two inputs will produce the same output and $s$ is the result of XOR'ing those inputs together.

In the worst case, we have to query all $2^n$ inputs leading to $O(2^n)$ query complexity.

Querying the black-box is at the heart of Simon's problem. We need not concern ourselves with how to construct the black-box, i.e. how to compute $f$, as that is not what the problem is about. I don't believe that Simon's problem is practically useful beyond the fact that it helps establish some complexity results about Quantum Computers. It's main significance is that it was an inspiration for Peter Shor's factoring algorithm.

$\endgroup$
3
$\begingroup$

What the article means by

$$f : \{0,1\}^n \rightarrow \{0,1\}^n$$

is that the input and output of the function is a binary string of length $n$.

As for the problem itself, the idea is that we have such a function $f$ with the added property that there is a special string $s$ such that for any two binary strings of length $n$, if the function gives the same result when passed either of them, they are either (1) equal or (2) give $s$ when XOR'ed together. The actual problem is: given the function (as a black box), find what $s$ is.

I can't say for certain why this isn't used as a cryptographic primitive, but there's at least one potential reason that I can see: we haven't taken into account the time it takes to actually construct such a function in the first place. If making such a function is equally (or even more) difficult; then it's much easier to imagine why it wouldn't be used.

$\endgroup$
  • $\begingroup$ Now that I understand the problem, it is actually trivial to construct such a function, thank you, you just made my day! $\endgroup$ – William Hird Jan 6 '14 at 2:23

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.