How to obtain the unknown values $a_i,b_j$ given an unordered list of $a_i-b_j\mod N$?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.