일반기술

엔티알유 암호화 및 복호화를 위한 다항식 컨볼루션 연산방법

본 발명은 NTRU 암호화 및 복호화에서 사용될 수 있는 다항식 컨볼루션 연산 방법으로서, NTRU 암호화 및 복호화에서, 제1 다항식('공개 키' 또는 '암호문'에 해당함)과 임의선택 가능한 제2 다항식과의 컨볼루션(convolution) 연산 방법에 있어서, (1) 임의선택 가능한 상기 제2 다항식의 계수들을 이진 계수('0' 또는 '1')들로 선택하는 제1 단계와, (2) 상기 제1 단계에서 선택된 상기 이진 계수들을 나열한 비트스트링에서, 2개의 '1'을 포함하고, 상기 2개의 '1' 사이에 소정의 개수 이하의 '0'을 포함하는 단순 패턴(simple pattern)들을 '1'을 서로 공유하지 않도록 검색하는 제2 단계와, (3) 상기 제2 단계에서 검색된 단순 패턴들을, 포함하고 있는 '0'의 개수에 따라 분류하는 제3 단계와, (4) 상기 제3 단계에서 분류된 각각의 단순 패턴에 대하여, 상기 제1 다항식의 계수들과 발생될 수 있는 모든 조합 값들을 미리 계산하여 그 값을 저장하는 제4 단계와, (5) 상기 제1 다항식과 상기 제2 다항식의 컨볼루션 연산에서, 특정 단순 패턴이 사용되는 경우에, 상기 제4 단계에서 상기 특정 단순 패턴에 대응하여 저장된 값을 참조하는 것에 의해 계산을 대신하는 제5 단계를 포함하는 것을 그 구성상의 특징으로 한다. 본 발명의 다항식 컨볼루션 연산 방법에 따르면, 임의선택 가능한 다항식의 계수들을 이진 계수들로 선택한 후, 상기 선택된 계수들에서 그 사이에 소정의 개수 이하의 '0'을 갖는 2개의 '1'을 포함하는 단순 패턴들을 '1'을 서로 공유하지 않도록 검색하여 그에 대응하는 모든 조합 값들을 미리 계산하여 저장해 두고, 실제 컨볼루션 연산에서 단순 패턴이 사용되는 경우 미리 저장된 값을 참조하는 것에 의해 덧셈 계산을 대신함으로써, NTRU 암호화 및 복호화에서의 다항식 컨볼루션 연산의 속도를 대폭 향상시킬 수 있다.