Recently, a dense knapsack public key cryptosystem based on arithmetic in finite fields was developed by Chor-Rivest. Its encryption and decryption procedures are simple and fast. But it takes too long time to generate a knapsack vector because of using discrete logarithms, and the calculation of discrete logarithms can be used for only one person.
To shorten the construction time of the cryptosystem, we propose a knapsack public key cryptosystem in which the knapsack vector can be shared by many people once it is generated. Our system will be based on a generalized version of Bose-Chowla theorem which provides uniqueness of subset sum in finite fields. Our system is secure against the case that one of the private keys is known. Also it is secure against any attack because we use no superincreasing sequences and our knapsack vector is dense enough to foil Lagarias-Odlyzko low density attack.
최근 Chor-Rivest 에 의해 유한 체계내의 산술에 근거한 배낭 공개 키 암호체계가 제시되었다. 이 암호체계는 암호화와 복호화의 과정이 단순하고 빠른 반면에 배낭 계수를 생성하기 위하여 이산 로그(discrete logarithm)의 계산이 필요하다. 이산 로그의 계산은 일반적으로 대단히 어려우며, Chor-Rivest 의 암호체계에서는 각 사용자마다 이산 로그의 계산을 필요로 하므로 암호체계 구축과정이 비효율적이다.
이러한 암호체계 구축과정에 효율성을 기하기 위해, 본 연구에서는 배낭계수를 한 번만 생성하여 많은 사용자에게 제공할 수 있는 배낭 공개 키 암호체계를 제시하였다. 또한, 본 연구에서 Bose-Chowla 정리의 일반적 형태를 제시하였으며, 우리의 암호체계는 이 정리에 기초한다. 이 암호체계는 비밀 키중의 하나가 알려져도 안전하며, 초증가 수열을 사용하지 않고 배낭 계수의 밀도가 높으므로 현재까지의 모든 공격에 대하여 안전하다.
