I want to learn whether or no there is a cryptographic primitive,scheme assumption that is based on the following hard problem if it is hard . By hard we mean that we have a polynomial adversary: The attacker obtains a number $\sigma$ . In order to reverse engineer that or to go one step further for the cryptanalysis she needs to break that number in a set of numbers $m_{1}, m_{2}, m_{3}, \ldots, m_{n} : \sum_{i=1}^{n}m_{i}=\sigma$ . How hard is that problem?

  • $\begingroup$ The question makes little sense. An infinite amount of such $m$'s exists, and it's trivial to find any one that works. Did you have an additional condition on the $m$'s? For instance if $\sigma = 1059458$ you can let $m_1 = 1059457$ and $m_2 = 1$, problem solved. Multiplication would be more interesting, but then it's just the factorization problem. $\endgroup$ – Thomas Jun 8 '12 at 10:15
  • $\begingroup$ yes i have something else: let $n$ be chosen randomly by a PRG which is indistinguishable from a real random generator $\endgroup$ – curious Jun 8 '12 at 10:25
  • $\begingroup$ $n$? The number of integers in which to partition $\sigma$? How large can $n$ be? The problem seems trivial, I have trouble following your train of thought - but you may have omitted an important piece of information (so before I post an answer I just want to make sure I'm answering the right question). $\endgroup$ – Thomas Jun 8 '12 at 10:27
  • $\begingroup$ yes it is the number of integers in which $\sigma$ is partitioned. So the hardness of this lies to how big $n$ can be? The bigger the harder. Is there a formulation in mathematics for this? Could this be a subset problem: given a set of elements $X$ is there a subset $N$ whose sum equals 0 ? In my case i do not even know the set $X$ and the sum equals something else. So it's even harder than subset sum? Or i am wrong? $\endgroup$ – curious Jun 8 '12 at 10:33
  • $\begingroup$ The problem is that the addition operator is far too "malleable" (for lack of a better word) for this purpose. It is effortless to partition any integer, no matter how big, into any $n$ "parts" which sum up to the initial integer, with no restrictions. As the problem is formulated now, you can make all $m$'s except the first one zero, and let the first one be $\sigma$ (or if zero is disallowed, use 1 instead and adjust the first one accordingly). $\endgroup$ – Thomas Jun 8 '12 at 10:38

From what could gather from the chat yesterday, you are looking into a scheme that implements some kind of locality preserving hashing. Let me first explain how I understood the scheme you are describing:

Given a feature extractor $E : \{0,1\}^* \rightarrow {\{0,1\}^k}^n$ (i.e. given a message $m$ it extracts $n$ features of lenth $k$) and a cryptographic hash function $\mathcal{H} : \{0,1\}^* \rightarrow \{0,1\}^{8l}$ the scheme proceeds as follows:

  1. On input message $m$, extract features $f_1,\ldots,f_n \gets E(m)$.
  2. For each feature $f_i$ compute the hash $h_{i,1}||\ldots||h_{i,l} \gets \mathcal{H}(f_i)$.
  3. For each $j \in \{1,\ldots,l\}$ compute $T_j := \sum\limits_{i=1}^n f_{i,j}$. (For some reson, from here on, we view bytes as signed.)
  4. Compute $F_j = \left\{\begin{array}{ll} 0&\text{if }T_j < 0\\1&\text{otherwise}\end{array}\right.$.
  5. Output $F=F_1||\ldots||F_l$.

Now your main question was, how hard is it, given only $F$ (or $T$) to reconstruct the original hash values. And, does this have anything to do with the subset sum problem.

The answer is, it has absolutely nothing to do with the subset sum problem but it is statistically infeasible to reconstruct the original hash values.

In step 4 bitstrings of length $8$ are compressed to single bits. Now this step in not one way (in a cryptographic sense) because it is trivial to find a preimage (if the bit is 1, choose a random positive number). However, if you want the original input, as there are $2^7=128$ possible preimages, you would have to guess, which one the input was. Considering that you've got $l$ such blocks (and assuming that the $T_i$ are uniformly distributed) you have a chance of about $2^{-7l}$ to guess all the $T_i$s.

Now suppose you had the $T_i$. This is where your question about the subset sum problem comes in. The thing is, if you only give the algorithm the $T_i$ and not the set of numbers, there are two possibilities. Either, you have not fixed the set, then the problem is trivial (choose $n-1$ random numbers and compute the last number by subtracting all those from $T_i$), or you do fix the set, but do not tell the algorithm what it is. In this case, the problem is basically "Guess the set of size $n$ I'm thinking about.", which is statistically infeasible, if your cannot trivially be guessed.

So in summary, given $F$ or $T$ it is infeasible to reconstruct the original hash values (and therefore also the original message) given that the entropy of the messages is not ridiculously small. However it might very well be possible to find a message $m'$ for which the resulting hash $F'$ will collide with $F$.

| improve this answer | |
  • $\begingroup$ I guess you wanted to say that there are $2^8$ possible preimages for a bruteforce from step 5 to step 4 $\endgroup$ – curious Jun 9 '12 at 9:53
  • 1
    $\begingroup$ $2^7$ actually, as there are $2^8$ input values divided between two outputs $\endgroup$ – Maeher Jun 9 '12 at 10:18

Well, the problem "given a finite set $A$ of integers, is there a subset that sums to a target value $B$" is known as the Subset Sum problem; it is known to be hard. Specifically, the decisional problem (is there such a sum) is NP-complete, and the computational problem (find the subset) is NP-hard.

That means that if you could solve large instances of this problem quickly, you could use that to solve a lot of interesting problems quickly, including just about any problem in crypto (finding AES keys given plaintext/ciphertext, factoring numbers, etc).

Because of this, assuming this is a hard problem would appear to be a fairly safe assumption.

On the other hand, it's not at all clear problem your problem statement that this is the problem you're relying on. You are you "add each index of them and construct a table"; what do you mean $n_1[0]$? If this is bit 0 of message digest $n_0$ and you're adding all the bits 0's from the message digests to form bit 0 of $T$, then you're not relying on subset problem at all; you're relying on the related problem that uses bitwise exclusive or -- that problem is known to be easy.

| improve this answer | |
  • 2
    $\begingroup$ It should also be noted that being NP-hard only means that some cases of the problem are hard to solve, not that all or even most of them are. In particular, there are plenty of easy instances of the subset sum problem (such as any instance where $A$ contains both $X$ and $B-X$). For crypto, it's not enough to have a problem that is known to be sometimes hard; we also need a way to generate instances of it that are each extremely likely to be among the hard ones. $\endgroup$ – Ilmari Karonen Jun 9 '12 at 13:31
  • $\begingroup$ @poncho yes exactly.I add not exactly bit 0 but whatever it is at position 0 at all the digests.This could be byte, 2bytes, ans so on.Why this is not subset sum?Knowing the sum give me from which number this is has been made $\endgroup$ – curious Jun 10 '12 at 16:56
  • 1
    $\begingroup$ @curious: this is not formally the subset sum problem, and there is no blatantly obvious way to solve an instance of the subset-sum problem with an oracle that can solve your problem. On the other hand, if you specify the full sum of each bit (and not just the lsbit of the sum), then it turns out (I have a marvelous proof that won't fit in the margin of this comment) that that problem is NP-complete as well (which means that you can solve the subset sum problem with this; it's just that the transform is nonobvious). $\endgroup$ – poncho Jun 10 '12 at 22:57

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.