A general construction for monoid-based knapsack protocols
This work provides a generalized construction for knapsack protocols, which is incremental as it builds upon existing methods to offer potential efficiency gains in cryptographic applications.
The authors tackled the problem of generalizing the knapsack protocol by Naccache and Stern, presenting a new framework that enables the construction of similar protocols with comparable security, and demonstrated a concrete example using extension fields of finite fields for improved computational efficiency while maintaining information rate and key size.
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.