Improvement of FrodoKEM System by BCH Codes and Minimax Approximation of Sign Function by Composite Polynomial for Homomorphic Comparison

Abstract

In this dissertation, two main contributions are given as; Performance improvement of FrodoKEM using Gray and error-correcting codes (ECCs). Optimal minimax polynomial approximation of sign function by composite polynomial for homomorphic comparison.

First, modification of FrodoKEM using Gray codes and ECCs is studied. Lattice-based scheme is one of the most promising schemes for post-quantum cryptography (PQC). Among many lattice-based cryptosystems, FrodoKEM is a well-known key-encapsulation mechanism (KEM) based on (plain) learning with errors problems and is advantageous in that the hardness is based on the problem of unstructured lattices. Many lattice-based cryptosystems adopt ECCs to improve their performance, such as LAC, Three Bears, and Round5 which were presented in the NIST PQC Standardization Round 2 conference. However, for lattice-based cryptosystems that do not use ring structures such as FrodoKEM, it is difficult to use ECCs because the number of transmitted symbols is small. In this dissertation, I propose a method to apply Gray and ECCs to FrodoKEM by encoding the bits converted from the encrypted symbols. It is shown that the proposed method improves the security level and/or the bandwidth of FrodoKEM, and 192 message bits, 50\% more than the original 128 bits, can be transmitted using one of the modified Frodo-640's.

Second, an optimal minimax polynomial approximation of sign function by a composite polynomial is studied. The comparison function of the two numbers is one of the most commonly used operations in many applications including deep learning and data processing systems. Several studies have been conducted to efficiently evaluate the comparison function in homomorphic encryption schemes which only allow addition and multiplication for the ciphertext. Recently, new comparison methods that approximate sign function using composite polynomial in the homomorphic encryption, called homomorphic comparison operation, were proposed and it was proved that the methods have optimal asymptotic complexity. In this dissertation, I propose new optimal algorithms that approximate the sign function in the homomorphic encryption by using composite polynomials of the minimax approximate polynomials, which are constructed by the modified Remez algorithm. It is proved that the number of required non-scalar multiplications and depth consumption for the proposed algorithms are less than those for any methods that use a composite polynomial of component polynomials with odd degree terms approximating the sign function, respectively. In addition, an optimal polynomial-time algorithm for the proposed homomorphic comparison operation is proposed by using dynamic programming. As a result of numerical analysis, for the case that I want to minimize the number of non-scalar multiplications, the proposed algorithm reduces the required number of non-scalar multiplications and depth consumption by about 33% and 35%, respectively, compared to those for the previous work. In addition, for the case that I want to minimize the depth consumption, the proposed algorithm reduces the required number of non-scalar multiplications and depth consumption by about 10% and 47%, respectively, compared to those for the previous work.

이 학위 논문에서는, 다음 두 가지 내용이 연구되었다.

FrodoKEM을 그레이 부호 및 오류정정부호를 사용하여 개선 동형 비교 연산을 위해 합성 다항식을 사용한 부호 함수의 최적 미니맥스 다항식 근사

먼저, 그레이 부호 및 오류정정부호를 사용하여 FrodoKEM을 변형시키는 방법이 연구되었다. 격자기반암호는 가장 유망한 포스트 양자 암호 스킴이다. 많은 격자기반암호 시스템 중에서 FrodoKEM은 learning with errors (LWE) 문제에 기반을 둔 잘 알려진 키-캡슐화 메커니즘 (KEM) 이며 구조를 갖지 않은 격자 문제에 기반을 둔 어려움을 가진다는 장점이 있다. NIST 포스트 양자 암호 표준화 라운드 2에 발표된 LAC, Three Bears, Round5와 같이 성능 개선을 위해 오류정정부호를 사용하는 많은 암호 시스템들이 있다. 그러나 FrodoKEM과 같이 링 구조를 사용하지 않는 격자기반 암호 시스템에서는 전송되는 심볼 개수가 작기 때문에 오류정정부호를 사용하기 어렵다. 나는 암호화된 심볼로부터 변환된 비트들을 부호화하여 오류정정부호와 그레이 부호를 FrodoKEM에 적용하는 방법을 제안하였다. 제안한 알고리즘은 FrodoKEM의 보안성 레벨 혹은 데이터전송량을 향상하고 기존 128비트보다 50\% 많은 192비트가 변형된 Frodo-640에서 전송될 수 있음을 보여주었다.

두 번째로, 합성 다항식을 사용한 부호 함수의 최적 미니맥스 다항식 근사가 연구되었다. 두 숫자의 비교 함수는 딥러닝 및 데이터 처리 시스템을 포함한 많은 응용에서 가장 많이 사용되는 연산 중 하나이다. 암호문 상에서의 덧셈과 곱셈만 지원하는 동형 암호에서 비교 함수를 효율적으로 계산하는 몇몇 연구가 진행되었다. 동형 암호에서 합성 다항식을 사용하여 부호 함수를 근사하는 비교 방법은 동형 비교 연산이라고 불리는데 최근 새로운 동형 비교 연산 방법이 제안되었고 그 방법이 최적 점근적 복잡도를 가진다는 것이 증명되었다. 본 논문에서 나는 미니맥스 근사다항식의 합성함수를 사용하여 동형암호에서 부호 함수를 근사하는 새로운 최적 알고리즘을 제안한다. 미니맥스 근사 다항식은 modified Remez 알고리즘에 의해 얻을 수 있다. 제안하는 알고리즘은 임의의 부호 함수를 근사하는 홀수 차수 항들을 가진 다항식의 합성 다항식을 사용하는 방법보다 더 적은 넌스칼라 곱 및 뎁스 소모를 사용한다는 것이 증명되었다. 또한, 제안한 동형 비교 연산에 대한 다이나믹 프로그래밍을 사용한 최적 다항시간 알고리즘이 제안되었다. 수치 분석 결과, 넌스칼라 곱 개수를 최소로 할 때, 제안하는 알고리즘은 필요한 넌스칼라 곱 개수와 뎁스 소모를 기존 방법의 필요한 넌스칼라 곱 개수 및 뎁스 소모보다 각각 33%, 35%정도 감소시킨다. 또한, 뎁스 소모를 최소로 할 때, 제안하는 알고리즘은 필요한 넌스칼라 곱 개수와 뎁스 소모를 기존 방법의 필요한 넌스칼라 곱 개수 및 뎁스 소모보다 각각 10%, 47%정도 감소시킨다.