How hard is to find the operators of an addition knowing the sum of them?

Question

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?

Answer 1

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$.

Answer 2

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.