  We present a generalized version of the knapsack protocol proposed by D.
Naccache and J. Stern at the Proceedings of Eurocrypt (1997). Our new framework
will allow the construction of other knapsack protocols having similar security
features. We will outline a very concrete example of a new protocol using
extension fields of a finite field of small characteristic instead of the prime
field Z/pZ, but more efficient in terms of computational costs for
asymptotically equal information rate and similar key size.
