3
$\begingroup$

Consider the following problem:

Factorize a $n$-bit integer $c$ knowing that it is the product of two integers with known Hamming weight $h$.

Is there a way to prove that this is still hard? I have parameters $n=1024$ and $h=80$, but am willing to augment $h$ if this turns out to be easy. I think this problem is current-factorization-algorithms-related, since I did not find an easy way to describe the distribution of these type of numbers (my try considered quadratic expressions of dependent Bernoulli trials). So the question may be reformulated: Does this hypothesis helps any of the actual factorization algorithms?

$\endgroup$
1
$\begingroup$

I do not see that the hypothesis helps any of the efficient factorization algorithms: (G)NFS, (MP)QS, ECM, CFRAC, Pollard's p-1, Williams' p+1, Pollard's rho.

I do reserve my opinion on Fermat and friends (that is, shortcuts to trial division managing to avoid most candidates), especially after more consideration of the combinatorial factoring attack in the other answer. Using poncho's technique, we can considerably reduce the possibilities in the low bits of the primes by examining the low bits of $c$. This also works in the high bits. However, so far, I fail to turn this into something that works for $h=80$: we are starting from $>2^{305}$ candidates for a prime and I have not found a way to reduce that enough using knowledge of $c$. But as the saying (attributed to the NSA) goes: attacks only get better; they never get worse.

I doubt that a formal security proof could be made.

$\endgroup$
2
$\begingroup$

I suspect that this might be vulnerable to a combinatorial factoring attack.

In this attack, we look at possible solutions to $pq = n \bmod 2^k$, and then extend $p$ and $q$ one bit to list the possible solutions to $pq = n \bmod 2^{k+1}$

Now, if we have no further information about $p$ and $q$, this turns out to be no more efficient than brute force search (as at each step, the number of possibilities doubles, and we have no way to distinguish likely versus unlikely possibilities).

However, in your scenario, we know that both $p$ and $q$ are strongly biased toward 0 bits, and so it would make sense to order our search to explore the possibilities with $p$ and $q$ being mostly 0 first. The immediately obvious approach would be to keep a list of possible solutions to $pq = n \bmod 2^k$, ordered by hamming weight of $p$ and $q$ (and $k$ somehow); and explore the long solutions with low hamming weight first.

It would seem plausible that this might quickly find a solution if the hamming weight was sufficiently small. How well would it work in practice (and how small is 'small')? I suspect that's something that would need to be experimented with.

$\endgroup$
  • $\begingroup$ I believe that a similar trick also allows to reduce to a small set of possibilities the high-order bits of the primes. I vaguely tried to combine that on both ends to come up with a specialized version of Fermat factoring, but back-of-the-envelope (literally) scribblings have so far ended in: hopelessly slow, for 512-bit primes with 80-bits Hamming weight. It would definitely work if we lowered $h$ to something much smaller. And as the saying (attributed to the NSA) goes: attacks only get better; they never get worse. $\endgroup$ – fgrieu Apr 18 '16 at 17:58
  • 1
    $\begingroup$ With H=80 and 512 bit primes (actually H=78 and 510 unknown bits; we know the setting of the msbit and the lsbit), each bit in both p and q has about 5/6 chance of being a 0. What I hope is that in my combinatorial attack, an incorrect guess will make the later guesses far closer to evenly balanced, and hence they will be rated lower in the ranking of what should be tested next. Will that effect be enough to make the procedure practical? That certainly sounds possible, but far from certain... $\endgroup$ – poncho Apr 18 '16 at 19:01
  • $\begingroup$ Thank you. At this point I may add that my problem comes from a polynomial factorization problem in a cyclotomic ring, whose hardness I need to prove. The fact that actually the bits of p and q were sampled randomly implies a variation of the attack you suggest, that may actually work. All I am saying is that I should have given the hypothesis "both factors were sampled randomly" (say, choose 80 of the 512 bits randomly and set them to 1). By the way, I never stated that the numbers are prime, all we know is that c can be written as a product of such numbers. $\endgroup$ – Tal-Botvinnik Apr 19 '16 at 12:06
  • $\begingroup$ Does this new hypothesis helps in any way? It looks like one can scale the problem, the remaining question is to quantify the candidates at each level. I'll code this today and let you know $\endgroup$ – Tal-Botvinnik Apr 19 '16 at 12:07
  • $\begingroup$ @Tal-Botvinnik: if you're in the ring [x]/x^n-1 (the NTRU ring) or [x]/x^n+1 (the ring used for rLWE), I'm not sure how well this combinatorial attack would work. Over the integers, it exploits the fact that some of the output bits are a function of only a few input bits (e.g. bit 2 of the product depends on only 6 bits of input total). With these rings, that's not true (each input coefficient can potentially affect each output coefficient), and so there's no obvious place for the algorithm to get started. $\endgroup$ – poncho Apr 19 '16 at 12:18

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.