Jump to content

Talk:Naccache–Stern knapsack cryptosystem

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

As the authors themselves point out, other knapsack cryptosystems have not fared so well. Does anyone know of any breaks on this one? The authors issue a challenge (with prize) at the end of their paper, has this prize been claimed?

--Beamishboy 15:37, 28 July 2006 (UTC)[reply]


I am removing the reference to the pohlig-hellman algorithm. I understand that the authors mention it in their original paper; however, no one would use the pohlig-hellman algorithm to generate the roots v_i. The element s is already noted to be coprime with p-1. Thus raising the p_i to the inverse of s modulo p-1 would be sufficient and very fast.

The other reason that I am removing the reference to pohlig-hellman is because it forces the reader to infer that the primes used in the Naccache Stern system are required to have a smooth totient. This, I had to read the original paper before I knew, is not the case at all. In fact, having p-1 smooth makes the system vulnerable DUE TO pohlig-hellman.

--Gtg207u (talk) 20:59, 30 December 2008 (UTC)[reply]