2
$\begingroup$

I have the sets $S_1=\{2,10,20,6\}$ and $S_2=\{25,26,20\}$ and I want to find which numbers sum to make 32. This is very easy by inspection; 6 and 26. It seems similar to the Knapsack problem, but I am no expert.

However, say I have 1000 sets, each with 500 elements such that summing one term from each set always gives you a unique value. This is much harder to inspect and solve, especially if the sets follow a structure that will appear random (they would be constructed from structured sets that have been messed with, and it would be near impossible to guess the mixing and reverse the sets).

So, the only way must be an Exhaustive Search Algorithm. Given my number is 52,485,332, there are $1000^{500}$ possible options to look at. Indeed there will be ways to shorten this search (such as when a set has numbers larger than your target value, you can ignore those numbers). But otherwise you might still be looking at $750^{500}$ possible choices.

So, what is the time complexity of such a search algorithm? $O(n^{k})$, with $n$ the number of sets and $k$ the number of elements in those sets? They have to check "all" possible combinations of terms until one matches the given value.

The main questions seem to be "how many sets are there?" and "how large are the sets?". Indeed, the sets can also all be of various sizes, not just uniform.

I am not a cryptography person; my research just flirts with the idea at hand. Any help would be appreciated.

$\endgroup$
3
  • $\begingroup$ "So, the only way must be an Exhaustive Search Algorithm" - ummm, no, even without any structure in the values, there are significantly more efficient search methods; one that comes immediately to mind takes $O(nm)$ time (where $m$ is the target sum; with $m=52485332$, that looks to be practically solvable). Are you interested, or is your query specifcally about the time taken by the naïve search algorithm? $\endgroup$
    – poncho
    Jul 26 '21 at 16:55
  • $\begingroup$ @poncho thanks for the comment. I wasn't aware there were better methods than a "naïve" search method. I would be interested in the one you suggested - anything you can suggest would be great. $\endgroup$
    – MeBadMaths
    Jul 26 '21 at 17:43
  • $\begingroup$ There are 500^1000 options, not 1000^500 $\endgroup$
    – jjj
    Jul 27 '21 at 16:21
2
$\begingroup$

So, the only way must be an Exhaustive Search Algorithm

As I mentioned in my comment, there are practical methods for nonhuge values of $m$ (and $m=52485332$ is not huge). Here is the outline of one such method (which assumes all the sets consist of nonnegative integers):

  • We have an array $A_{n, m+1}$; each element of the array $A_{a, b}$ will note how we can generate the sum $b$ from the first $a$ sets (or $\perp$ if no such way has been found yet).

  • Initialize all elements $A$ to $\perp$

  • For $i := 1$ to $n$ search the elements $A_{i-1}$ for non-$\perp$ element (and for $i=1$, the 0th element is treated as the only non-$\perp$ element. For each such element $A_{i-1, x}$, set $A_{i, x + S_{i,j}}$ to $j$ (for each element $S_{i,j}$ of the set $S_i$) If $x + S_{i,j} > m$, ignore it.

  • Finally, if $A_{n,m} = \perp$, there is no subset that leads to the sum $m$. If it is anything else, we can recover the terms by backtracking through the array $A$.

This should be a practical algorithm for recovering the terms given the parameters you have specified.

$\endgroup$
12
  • $\begingroup$ In the question it was stated that summing always gives a unique value. This means there are 1000^500 different results, so we musst assume we're talking about m in this magnitude as well. This algorithm will "never" finish then $\endgroup$
    – jjj
    Jul 26 '21 at 20:37
  • $\begingroup$ @jjj: the question also states "Given my number is 52,485,332"; I had assumed they were listing their $m$ value; if not, what is "my number"? $\endgroup$
    – poncho
    Jul 26 '21 at 20:53
  • 1
    $\begingroup$ I guess the author of the question is not aware of the fact that the uniqueness will result in most numbers of the set alone will be much larger that theis sum. And removing them would drastically reduce the problem $\endgroup$
    – jjj
    Jul 26 '21 at 21:01
  • $\begingroup$ Thank you both for your answers and comments. I am not versed in the details of Cryptography so sorry for the confusion my post has caused. The fact I thought 52,485,332 was "huge" shows my ignorance haha. To clarify; all the sets are non-negative integers. Taking a value from each set and summing them will always guarantee a unique element. $\endgroup$
    – MeBadMaths
    Jul 27 '21 at 11:40
  • $\begingroup$ By "my number" I meant the term I encoded (something I didn't state - sorry!). Say I have got a message and encoded it through these sets. The resulting number is 52,485,332 (or maybe even bigger!). The Search Algorithm's job is to find which unique values across the 1000 sets sum to make this number. From there you can decode the message. The 1000 sets act as a public key. So, if it's easy to crack that's an issue. Hope that helps. @jjj could you explain your last comment more? I don't think I follow, sorry $\endgroup$
    – MeBadMaths
    Jul 27 '21 at 11:44
1
$\begingroup$

This is more an answer to why the uniqueness of the sums effects the size so much that the case for $52485332$ becomes trivial (its way to long for a comment).

When all sums must be unique, then they must result in different integers. Because there are $500^{1000}$ possible sums, there are also $500^{1000}$ different integer results for that. the lowest case would be all integers from $0$ to $500^{1000}-1$.

For Example,

$S_1 = \{0, 1, 2, ..., 499\}$

$S_2 = \{0, 500, 1000, ..., 249500\}$

$S_3 = \{0, 250000, 500000, ..., 124750000\}$

...

$S_{1000} = \{0, 500^{999}, 2*500^{999}, ..., 499*500^{999}\}$

would be a way to ensure the uniqueness of the result. As you can see, The Numbers get really large really fast.

In this particular example its easy to find the result (just always choose the largest number that fits from last to first set). Even most numbers is $S_3$ are greater than $52485332$ and can therefore be ignored.

You would probably want relatively random values in your sets. In this case the range of the values have to be at least slightly larger.

However, it is highly unlikely that any value is lower or equal to $52485332$ (when you uniformly choose $500000$ values out of $500^{1000}$)

Dynamic programming, as @poncho suggested, really only works for small numbers and its performance is not that much better than exhaustive search (linear difference in the number of sets), because the sub-sums, that can be reused are unique, the advantage of not looking at other possibilities is not there. Runtime should be same order as exhaustive search. Only improvement is to aboard when values are to large or small to reach the target, but for reasonable targets that is not much of an advantage.

On could easily reduce the subset sum problem or knapsack problem to this one by just using the same set as many times as the number you want to sum to. Problem with this is that this is not a polynomial time reduction ant therefore not sufficient to proof if problem is NP hard.

$\endgroup$
7
  • $\begingroup$ Thank you for the response. The example of the sets you gave is one I know well and is the most basic of these sets. But, from there you can "mess" this set up in a way that is entirely unrecoverable without extra information (the private key). The resulting "messed up" sets will be seemingly random and will generate a vveerryy large range of sets. I agree that the given 52485332 is wwaayy too small - didn't really think that through haha. But, say my value was of a sufficient size that tracked properly with the "random" sets - I assume that makes this problem harder to solve? $\endgroup$
    – MeBadMaths
    Jul 27 '21 at 14:25
  • $\begingroup$ @MeBadMaths The number of ways to mess this up are relatively limited (if possible at all). For example when you split {0, 1, 2, 3, 0, 4, 8, 12} (smaller example same structure) into two sets of size 4, then there is only one way to do this (ignoring order of sets and order inside the sets) $\endgroup$
    – jjj
    Jul 27 '21 at 14:46
  • $\begingroup$ It is possible to "mess" these sets up, but it gets more and more huge as you get larger and larger values. Let $N=\prod_{j=1}^n |S_{j}|$, then take $d>N$. Take $r$ such that $r$ and $d$ are co-prime, and take $0\leq t_1,t_2,\dots,t_n<N$. Now define the set; $T_j=r(S_j+t_j)$(mod $d$). As long as these conditions are met, summing a value from each $T_j$ will result in a unique value. You can further "mess" these sets up in a similar way. The private key would contain $d,r,t_j$ and the $S_j$ sets, while the public key would have only $T_j$ - I swear the sets would be suitably random looking $\endgroup$
    – MeBadMaths
    Jul 27 '21 at 15:41
  • $\begingroup$ @MeBadMaths Ok, yes your right. I thought you just wanted to swap the elements, not modify them. I verified that your formula holds and is indeed not distinguishable from random values. I'll adjust the last part of my answer $\endgroup$
    – jjj
    Jul 27 '21 at 16:13
  • $\begingroup$ thank you for all your comments and answers - and sorry for my poor explanation. I've not used these forums before to such an extent so I am still new to how to format questions etc. I really appreciate your support. Definitely not looking to prove NP haha. Your input has helped nevertheless. Last question would be; is the order of extensive search $O(n^k)$ as I assumed in my post, or $O(k^n)$? Or is it something else? Thank you again $\endgroup$
    – MeBadMaths
    Jul 27 '21 at 17:01

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.