Does a collision oracle for the pigeonhole subset sum problem produce solutions?

Question

I am reading "Efficient Cryptographic Schemes Provably as Secure as Subset Sum" by R. Impagliazzo and M. Naor (paper) and came across the following statement in the proof of Theorem 3.1 (pages 10-11):

Let $\ l(n) = (1-c)n \ $ for $ \ c > 0 \ $ ...

Given $a_1, a_2, \cdots, a_n \in \{0,1\}^{l(n)}$ and a target sum $T$, we construct an input to the collision finding algorithm as follows:

1. Let the collision finding algorithm select a (non-empty) $ s_1 \in \{0,1\}^n $

2. compute $T' = \sum_{i \in s_1} a_i$. Choose a random $j$ such that $j \in s_1$ and define $a_j' = a_j - T' + T$.

3. Give the instance $a_1, a_2, \cdots , a_j', \cdots, a_n$ and $s_1$ to the algorithm that finds collisions. The algorithm attempts to find $s_2$ such that $f_{(a_1, a_2, \cdots, a_j', \cdots, a_n)}(s_2) = T'$.

If the algorithm returns $s_2$ that collides with $s_1$ and $j \notin s_2$, then $s_2$ is a solution to our original problem, since swapping $a_j$ and $a_j'$ does not affect the sum over $s_2$.

Where the emphasis is mine.

Where $f$ concatenates $\stackrel{\rightarrow}{a}$ with the sum of the $a_i$'s:

$$ f( \stackrel{\rightarrow}{ a } , S) = f_{(a_1, a_2, \cdots, a_n)}(S) = \ \stackrel{\rightarrow}{a}, \sum_{i \in S} a_i \mod 2^{l(n)} $$

(taken from the top of page 3 from the same paper).

For the life of me, I don't understand how $s_2$ is a solution to the original instance. Can someone elaborate on what they mean? What am I missing?

The above definition for the subset sum problem is, if I'm not mistaken, just another form of the pigeonhole subset sum problem (i.e. $\sum_j a_j < 2^n -1$ ). If I read the above right, they are claiming that, given an oracle that finds collisions, they can then construct a solution to the original (pigeonhole) subset sum problem but I do not see how this is done. Any help would be appreciated.

Answer 1

The way I understand it is the following.

Note that for $s_1$, $f_\vec{a'}(s_1)=T$ (because the sum was $T'$ and we replaced $a_j$ with $a'_j$ and we know that $j\in s_1$.

Now, they search for a collision, i.e., another $s_2$ such that $j\notin s_2$, but $f_\vec{a'}(s_2)=T$. (is there a typo there, having $T'$ instead?) Now, what is $f_\vec{a}(s_2)$? also $T$, right? since $j\notin s_2$...

Does it help?