19
$\begingroup$

Can anyone help me with the following problem?

I want to find some values $a_i,b_j$ (mod $N$) where $i=1,2,…,K, j=1,2,…,K $ (for example $K=6$), given a list of $K^2$ values that correspond to the differences $a_i-b_j\pmod N$ (for example $N=251$), without knowing the concrete corresponding relation. Since the values $a_i,b_j\pmod N$ are not uniquely defined given the differences $a_i-b_j\pmod N$, we look for any valid assignment of values.

Definitely, trying each permutation of the $K^2$ numbers in the list (totally $K^2!$ possible cases) and then solving the modular equations with $a_i,b_j$ as the variables is infeasible.

In fact, this problem arises in a paper on the cryptanalysis to an early version of NTRU signature scheme (http://eprint.iacr.org/2001/005). However, the author wrote only one sentence “A simple backtrack algorithm finds one solution…” (in Section 3.3) and so can anyone give more explanations? What’s more, the author also mentioned that “every circular shift $\{((a_i+M)\mod N,(b_i+M)\mod N\}_{i=1}^K$ or a swap $(\{(N-1-b_i,N-1-a_i)\}_{i=1}^K)$ results in the same pattern of $a_i-b_j\mod N$” and is this statement helpful?

$\endgroup$
  • 7
    $\begingroup$ Notice that it's impossible to recover $a_i,b_j$, since if you add some constant $C$ to all the numbers, then the differences remain the same. $\endgroup$ – Yuval Filmus Apr 18 '13 at 14:10
  • 1
    $\begingroup$ @Yuval: This is already included in the last sentence of the description. I think only one solution is needed, as several might exist. $\endgroup$ – domotorp Apr 18 '13 at 17:25
  • 2
    $\begingroup$ @Yuval Sorry for not pointing out that the $a_i,b_j$’s should also be taken modular $N$. So there are not infinite solutions. $\endgroup$ – a guest Apr 19 '13 at 2:44
  • $\begingroup$ @domotorp Yes, finding any one of the solutions is OK. $\endgroup$ – a guest Apr 19 '13 at 2:44
  • 1
    $\begingroup$ Maybe the OP could clarify that the $a_i$, $b_j$ are taken modulo $N$ earlier in the post: perhaps in the title or in the first paragraph. The issue with the constant $C$ is also worth mentioning. Both things confused me when I started to read. $\endgroup$ – Juan Bermejo Vega Apr 20 '13 at 17:53
4
$\begingroup$

Here is a suggestion, for $K = 6$ and $N = 251$. We are given a list $a_i - b_j \pmod{N}$. Start by taking one of them, without loss of generality $a_1-b_1$. Without loss of generality $b_1=0$, and we obtain the value of $a_1$. Now take another one, and hope that it is of the form $a_2-b_1$ (this happens with probability $5/35 = 1/7$), and deduce $a_2$.

At this stage, we know $a_1,a_2,b_1$. Our next goal is to look for $a_1-b_j$ for $j \neq 1$. For each candidate $a_i-b_j$, if $i=1$ then $(a_i-b_j)+(a_2-a_1)=a_2-b_j$ should also be on the list. If $i \neq 1$, then the probability that $(a_i-b_j)+(a_2-a_1)$ is also on the list is roughly $33/251$. So if we do find some candidate $a_i-b_j$ for which $(a_i-b_j)+(a_2-a_1)$ is also on the list, then probably $i=1$. In this way, we can recover $b_2$ with some certainty.

At this stage, we know $a_1,a_2,b_1,b_2$. In the same way that we recovered $b_2$, we can recover $a_3$ with reasonable certainty. We can then recover $b_3$ by looking for a candidate $a_i-b_j$ for which $(a_i-b_j)+(a_2-a_1)$ and $(a_i-b_j)+(a_3-a_1)$ are both on the list. Because we have more $a$s, our failure probability goes appreciably down. We continue and find $b_3,a_4,b_4,a_5,b_6,a_6,b_6$.

At any point in this algorithm, we might have guessed something wrong, and this will eventually result in a contradiction (say at some point, there is no good candidate $a_i-b_j$). We then backtrack and try another possibility; if we exhaust all possibilities, we backtrack again, and try another possibility (for a different stage of the algorithm); and so on.

It is a good exercise to actually program this algorithm - that's probably the only way to understand how to implement the backtracking correctly. That's also the only way to tell whether this algorithm works in practice.

$\endgroup$
  • $\begingroup$ Thank you and I'll also code this backtracking to get it more understood. Maybe the author of that original paper used a similar method because he also mentioned "backtrack". $\endgroup$ – a guest Apr 25 '13 at 14:10
  • $\begingroup$ Sorry for forgetting to post my comment to your answer! I also implemented the method you suggested (in C++). The conclusion is that your algorithm works quite well and one of the solutions can be then found very fast (in less than a second on my PC). And this time, I can understand the backtrack procedures better. Thank you very much! $\endgroup$ – a guest May 5 '13 at 7:16
  • $\begingroup$ Why can't I "@Yuval" in my last comment?! Sorry, but I've tried several times. $\endgroup$ – a guest May 5 '13 at 7:23
  • $\begingroup$ Perhaps you could share the code online, so that other people reading the paper will have access to it. $\endgroup$ – Yuval Filmus May 5 '13 at 15:14
5
$\begingroup$

Update: The description below is for a different problem (in which you have all pairwise distances in a set rather than pairwise distances between two distinct sets). I'll leave it up anyway since it is closely related.

This problem is called the beltway problem, and is a special case of the general $d$-torus embedding problem. It is also closely related to the turnpike problem, in which the distances differences are absolute (not modulo some number).

It is not known whether the beltway problem admits a poly-time algorithm. There are various pseudo-poly-time algorithms for related questions. The best reference (alas an old one) is the paper by Lemke, Skiena and Smith.

$\endgroup$
  • 1
    $\begingroup$ I think this problem is different. In the beltway problem we know all pairwise distances, here we only know it between two points that are in different groups. While this seems like less information, it can in fact help to solve the problem. $\endgroup$ – domotorp Apr 18 '13 at 17:24
  • $\begingroup$ Ah yes. it's a bipartite graph. good point. $\endgroup$ – Suresh Venkat Apr 18 '13 at 17:43
  • $\begingroup$ Bipartite graph? Something like. Maybe I should try the problem this way, but I don't have the concrete train of thought now. $\endgroup$ – a guest Apr 19 '13 at 3:03
3
$\begingroup$

Here's an observation that I think gives you a foothold, possibly enough of one to solve the problem.

Suppose we have four differences $a_1-b_1$, $a_1-b_2$, $a_2-b_1$, $a_2-b_2$ that arise as the pairwise differences between two $a$'s and two $b$'s. Call this a quartet of differences. Notice that we have a non-trivial relationship:

$$(a_1-b_1)-(a_1-b_2) = (a_2-b_1)-(a_2-b_2) \pmod N.$$

You can try to use this relationship to identify potential quartets out of the list of $K^2$. For instance, pick four differences out of the list; if they don't satisfy the above relationship, then they definitely don't arise from a quartet structure; if they do satisfy the relationship, they might arise from a quartet.

There are many ways you can take things from here, but I suspect this is going to be enough.

I especially suspect that, for your example parameter settings, the problem is going to be pretty easy, because the above test for recognizing a quartet probably won't have too many false positives. Our of all ${K^2 \choose 4}$ ways of choosing 4 differences from the list, there will be ${K \choose 2}^2$ quartets (which will all satisfy the relationship) and the remainder are non-quartets (which satisfy the relationship with probability $1/N$, heuristically). Therefore we expect to see about $({K^2 \choose 4}-{K \choose 2}^2)/N$ false positives, i.e., 4-tuples that pass the test even though they aren't quartets. For your parameters, this means we have 225 quartets and $(58905-225)/251 \approx 234$ other false positives; so about half of the 4-tuples that pass the test are actually quartets. This means that the above test is a pretty good way to recognize quartets. Once you can recognize quartets, you can really go to town on recovering the structure of the list of differences.

$\endgroup$
  • $\begingroup$ @DW: Thank you, but I'm now wondering the next step after all the possible quartets (totally 225+234=459 ones) are found. Should it be searching for 3 non-overlapping quartets and testing whether they can constitute a possible solution? How to accomplish this efficiently? Maybe not so difficult because there will not be many overlappings. $\endgroup$ – a guest Apr 25 '13 at 14:04
  • $\begingroup$ @aguest, good question! I can't remember what I was thinking at the time. I think I recall thinking one approach could be to start with one quartet, then look for all others that overlap it in 2 differences (e.g., arising from $a_1,a_j,b_1,b_2$ where $j\ne 2$), but I don't know where to go from there (how to filter out false positives). $\endgroup$ – D.W. Apr 25 '13 at 22:07
3
$\begingroup$

Here's a different approach, based upon iteratively finding numbers that cannot appear among $\{a_1,\dots,a_6\}$. Call a set $A$ an over-approximation of the $a$'s if we know that $\{a_1,\dots,a_6\} \subseteq A$. Similarly, $B$ is an overapproximation of the $b$'s if we know that $\{b_1,\dots,b_6\} \subseteq B$. Obviously, the smaller $A$ is, the more useful this over-approximation is, and the same goes for $B$. My approach is based upon iteratively refining these over-approximations, i.e., iteratively reducing the size of these sets (as we rule out more and more values as impossible).

The core of this approach is a method for refinement: given an over-approximation $A$ for the $a$'s and an over-approximation $B$ for the $b$'s, find a new over-approximation $A^*$ for the $a$'s such that $A^* \subsetneq A$. In particular, normally $A^*$ will be smaller than $A$, so this lets us refine the over-approximation for the $a$'s.

By symmetry, essentially the same trick will let us refine our over-approximation for the $b$'s: given an over-approximation $A$ for the $a$'s and an over-approximation $B$ for the $b$'s, it will produce a new over-approximation $B^*$ for the $b$'s.

So, let me tell you how do refinement, then I'll put everything together to get a full algorithm for this problem. In what follows, let $D$ denote the multi-set of differences, i.e., $D=\{a_i-b_j:1 \le i,j \le 6\}$; we'll focus on finding a refined over-approximation $A^*$, given $A,B$.

How to compute a refinement. Consider a single difference $d \in D$. Consider the set $d+B=\{d+y : y \in B\}$. Based on our knowledge that $B$ is an over-approximation of the $b$'s, we know that at least one element of $d+B$ must be an element of $\{a_1,\dots,a_6\}$. Therefore, we can treat each of the elements in $d+B$ as a "suggestion" for a number to possibly include in $A$. So, let's sweep over all differences $d \in D$ and, for each, identify which numbers are "suggested" by $d$.

Now I'm going to observe that the number $a_1$ is sure to be suggested at least 6 times during this process. Why? Because the difference $a_1-b_1$ is in $D$, and when we process it, $a_1$ will be one of the numbers it suggests (since we're guaranteed that $b_1 \in B$, $(a_1-b_1)+B$ will surely include $a_1$). Similarly, the difference $a_1-b_2$ appears somewhere in $D$, and it'll cause $a_1$ to be suggested again. In this way, we see that the correct value of $a_1$ will be suggested at least 6 times. The same holds for $a_2$, and $a_3$, and so on.

So, let $A^*$ be the set of numbers $a^*$ that have been suggested at least 6 times. This is sure to be an over-approximation of the $a$'s, by the above comments.

As an optimization, we can filter out all suggestions that are not present in $A$ immediately: in other words, we can treat the difference $d$ as suggesting all of the values $(d+B)\cap A$. This ensures that we will have $A^* \subseteq A$. We are hoping that $A^*$ is strictly smaller than $A$; no guarantees, but if all goes well, maybe it will be.

Putting this together, the algorithm to refine $A,B$ to yield $A^*$ is as follows:

  1. Let $S = \cup_{d \in D} (d+B)\cap A$. This is the multi-set of suggestions.

  2. Count how many times each value appears in $S$. Let $A^*$ be the set of values that appear at least 6 times in $S$. (This can be implemented efficiently by building an array $a$ of 251 initially, initially all zero, and each time the number $s$ is suggested, you increment $a[s]$; at the end you sweep through $a$ looking for elements whose value is 6 or larger)

A similar method can be built to refine $A,B$ to get $B^*$. You basically reverse things above and flip some signs: e.g., instead of $d+B$, you look at $-d+A$.

How to compute an initial over-approximation. To get our initial over-approximation, one idea is to assume (wlog) that $b_1=0$. It follows that each value $a_i$ must appear somewhere among $D$, thus the list of differences $D$ can be used as our initial over-approximation for the $a$'s. Unfortunately, this doesn't give us a very useful over-approximation for the $b$'s.

A better approach is to additionally guess the value of one of the $a$'s. In other words, we assume (wlog) that $b_1=0$, and use $A=D$ as our initial over-approximation of the $a$'s. Then, we guess which one of these 36 values is indeed one of the $a$'s, say $a_1$. That then gives us an over-approximation $B=a_1-D$ for the $b$'s. We use this initial over-approximation $A,B$, then iteratively refine it until convergence, and test whether the result is correct. We repeat up to 36 times, with 36 different guesses at $a_1$ (on average 6 guesses should be enough) till we find one that works.

A full algorithm. Now we can have a full algorithm to compute $a_1,\dots,a_6,b_1,\dots,b_6$. Basically, we derive an initial over-approximation for $A$ and $B$, then iteratively refine.

  1. Make a guess: For each $z \in D$, guess that $a_1=z$. Do the following:

    1. Initial over-approximation: Define $A=D$ and $B=z-D$.

    2. Iterative refinement: Repeatedly apply the following until convergence:

      • Refine $A,B$ to get a new over-approximation $B^*$ of the $b$'s.
      • Refine $A,B^*$ to get a new over-approximation $A^*$ of the $a$'s.
      • Let $A:= A^*$ and $B:= B^*$.
    3. Check for success: If the resulting sets $A,B$ each have size 6, test whether they are a valid solution to the problem. If they are, stop. If not, continue with the loop over candidate values of $z$.

Analysis. Will this work? Will it eventually converge on $A=\{a_1,\dots,a_6\}$ and $B=\{b_1,\dots,b_6\}$, or will it get stuck without completely solving the problem? The best way to find out is probably to test it. However, for your parameters, yes, I expect it will be effective.

If we use method #1, as long as $|A|,|B|$ are not too large, heuristically I expect the sizes of the sets to monotonically shrink. Consider deriving $A^*$ from $A,B$. Each difference $d$ suggests $|B|$ values; one of them correct, and the other $|B|-1$ can be treated (heuristically) as random numbers. If $x$ is a number that does not appear among the $a$'s, what is the probability that it survives the filtering and is added to $A^*$? Well, we expect $a$ to be suggested about $(|B|-1) \times 36/251$ times in total (on average, with standard deviation about the square root of that). If $|B|\le 36$, the probability that a wrong $x$ survives the filtering should be about $p=0.4$ or so (using the normal approximation for the binomial, with continuity correction). (The probability is smaller if $|B|$ is smaller; e.g., for $|B|=30$, I expect $p\approx 0.25$.) I expect the size of $A^*$ to be about $p (|A|-6) + 6$, which will strictly improve the over-approximation since it is strictly smaller than $|A|$. For instance, if $|A|=|B|=36$, then based upon these heuristics I expect $|A^*|\approx 18$, which is a big improvement over $|A|$.

Therefore, I predict that the running time will be very fast. I expect about 3-5 iterations of refinement to be enough for convergence, typically, and about 6 guesses at $z$ should probably be enough. Each refinement operation involves maybe a few thousand memory reads/writes, and we do that maybe 20-30 times. So, I expect this to be very fast, for the parameters you specified. However, the only way to find out for sure is to try it and see if it works well or not.

$\endgroup$
  • $\begingroup$ @DW: Thank you very much for your long answer and the effort you took to type so many words!!! According to your description, your algorithm here is quite correct. And I’m going to code it to test the efficiency right now. $\endgroup$ – a guest Apr 25 '13 at 13:52
  • $\begingroup$ @DW: Hi, I’ve implemented your description in C++. The algorithm runs fast and the refinement step does reduce the sizes of original sets $A$ and $B$. However, the convergence seems to be not so perfect. In fact, for each guess $z\in D$, the final sizes of $A^*$ and $B^*$ are still more than 10 according to my record output by the program. The most frequent number of existing elements when $A^*$ (and $B^*$) can not be improved by further repetitions of refinement is 11, but I can hardly see a number below 10. However, this has made the problem solvable by trying each 6-elements chosen from $\endgroup$ – a guest Apr 27 '13 at 8:38
  • $\begingroup$ @DW: (Cotinued)final $A^*$ and $B^*$ for each guess $z$ (although I didn’t implement the last step on my PC). The total amount computation will be about $2^{20}$, I estimate. Thank you very much! $\endgroup$ – a guest Apr 27 '13 at 8:39
  • $\begingroup$ Sorry, but my last comment is too long, and I have to split it into two. $\endgroup$ – a guest Apr 27 '13 at 8:49

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.