Paper 2005/347

Knapsack Diffie-Hellman: A New Family of Diffie-Hellman

Song Han, Elizabeth Chang, and Tharam Dillon

Abstract

Diffie-Hellman problems have been widely involved in the design of various cryptographic protocols. Its general family is based on the discrete logarithm over a finite field. Since 2000, its another family which is based on elliptic curve discrete logarithm as well as bilinear pairing, e.g. Weil or Tate pairing, has been attracted significant studies. Thereafter, various cryptographic protocols have been proposed using Diffie-Hellman problem associated with bilinear pairings. This paper we will present a new family of Diffie-Hellman problem by utilizing subset sum problem. It is named as Knapsack Diffie-Hellman Problems with bilinear pairings. We will propose a number of definitions on the family and then analyze their relationships.