From dawagner@tucson.princeton.edu Fri Dec  2 23:38:45 EST 1994
Article: 30780 of sci.crypt
Newsgroups: sci.crypt
Path: princeton!tucson.princeton.edu!dawagner
From: dawagner@tucson.princeton.edu (David A. Wagner)
Subject: Factoring given a hint
Message-ID: <1994Dec3.043528.5432@Princeton.EDU>
Summary: Gotta love LLL basis reduction...
Originator: news@hedgehog.Princeton.EDU
Sender: news@Princeton.EDU (USENET News System)
Nntp-Posting-Host: tucson.princeton.edu
Organization: Princeton University
Date: Sat, 3 Dec 1994 04:35:28 GMT
Lines: 77

In email, Don Coppersmith succinctly summarized a
problem that's recently been discussed here:

You're trying to factor n=pq, and you're given a
"hint" s = ap+b.  You're given a bound on b.  Can
you use this information to factor n?  Does it help
to have several hints?

[Here the variable a is chosen randomly from the
uniform distribution on {0,1,...,q-1} and b is
distributed uniformly over its range, but they
are kept secret from the attacker.]

Don Coppersmith mentioned in his email that he can
factor n if b = O(n^{1/6}).  By using multiple
"hints", I think I can factor n given the bound
b = O(n^c) for any fixed c < 1/2.  I'm assuming
that n is a RSA modulus, so p ~= q ~= n^{1/2}.

[My post a while back was mistaken: I don't think
that the continued fractions algorithm helps at all,
unless b = O(1) or p >> q.]

In the special case b = O(n^{1/4}), I need 5 hints.
This means there is a ciphertext-only attack on
David Colston's QPK scheme requiring 5 ciphertexts...
[Yes, I know Don Coppersmith already demolished the
QPK scheme by finding the message from only one known
ciphertext, but maybe my post will be of independent
interest.]

Let me state one result from Lagarias, Crypto '83.
Set

S = (s_1/n, s_2/n, ..., s_m/n)
A = (a_1, a_2, ..., a_m).

Call A an "unusually good" simultaneous diophantine
approximation to S if

|q s_j/n - a_j| < n^{-d}	for j=1,2,...,m

for some fixed d > 1/m.

Lagarias gives a theorem which says that if S has an
"unusually good" diophantine approximation, the
approximation is essentially unique, and can be found
in polynomial time by the LLL basis reduction algorithm.

The notation I've used should be suggestive.  If we
have the bound b = O(n^c) for some c < 1/2, then

|q s_j/n - a_j| = |b_j/p| = O(n^{-d})

where d = 1/2 - c; so if d > 1/m, A will be an "unusually
good" diophantine approximation to S, and we will be able
to find A (thus finding p and factoring n) in polytime.

Now observe that if m > 1/(1/2 - c), then we will have
d > 1/m.  Therefore if m > 1/(1/2 - c), m "hints" are
enough to factor n.

In the case of QPK, c = 1/4, so m = 5 should work fine.

[Didn't Secure Voice also have the option to use your
PGP private key with the QPK algorithm?  I don't have
the original posting here, but if so, I wouldn't let
Secure Voice *near* my PGP private key...]

I think this is just a simple application of a theorem
stated in Lagarias's paper; but I'm *certainly* no
expert on basis reduction, and I don't have any software
that will let me test my approach.  So I hope you'll
correct me if my reasoning is flawed...

-------------------------------------------------------------------------------
David Wagner                                             dawagner@princeton.edu