Homomorphic Computation in Reed-Muller Codes and Improvements of Modified pqsigRM

Abstract

In this dissertation, two main contributions are given as; i) homomorphic computation in Reed-Muller (RM) codes and ii) improving Modified pqsigRM with the key size and bit-security.

First, a method of homomorphic computation in RM codes is proposed. With the ongoing developments in artificial intelligence (AI), big data, and cloud services, fully homomorphic encryption (FHE) is being considered as a solution for preserving privacy and security in machine learning systems. Currently, the most of existing FHE schemes are constructed using lattice-based cryptography. In state-of-the-art algorithms, a huge amount of computational resources are required for homomorphic multiplications and the corresponding bootstrapping that is necessary to refresh the ciphertext for a larger number of operations. Therefore, it is necessary to discover a new innovative approach for FHE that can reduce computational complexity for practical applications. Diverse research works, which are not limited to lattice-based cryptography are also needed. The code-based cryptography can be a new solution for this.

In this dissertation, I propose a code-based homomorphic operation scheme in RM codes. It is known that the linear codes are closed under the addition, however, achieving multiplicative homomorphic operations with linear codes has been impossible until now. I strive to solve this problem by proposing a fully homomorphic code scheme that can support both addition and multiplication simultaneously using the RM codes. This can be considered as a preceding step for constructing code-based FHE schemes. I restrict this to the computation of the first order of RM codes. As the order of RM codes increases after multiplication, a bootstrapping technique is required to reduce the order of intermediate RM codes to accomplish a large number of operations. I propose a bootstrapping technique to preserve the order of RM codes after the addition or multiplication by proposing three consecutive linear transformations that create a one-to-one relationship between computations on messages and those on the corresponding codewords in RM codes. Furthermore, I propose some trials of making homomorphic encryption in code-based cryptosystems.

Second, a method of improving the key size and bit-security of Modified pqsigRM is proposed. The importance of post-quantum cryptography (PQC), which is secure against quantum algorithms, is growing larger and larger. pqsigRM is a code-based PQC digital signature scheme that was presented in round 1 of the national institute of standards and technology (NIST)'s PQC standardization process. NIST is a standardization organization in the United States. This scheme was revised as the Modified pqsigRM by removing all known vulnerabilities going through the debates in the NIST PQC standardization process. It has the advantages of an efficient decoding process and small signature sizes. Small signature sizes are very useful in digital signature schemes because signatures should be sent in every signing process. However, it has a problem with large public key sizes.

In this dissertation, I propose a method called Improved Modified pqsigRM to reduce the public key size and improve the exact bit-security of Modified pqsigRM. I change the public key into the systematic form, improve its parameters, and fine-tune the bit-security for each parameter. Thus, I can reduce these to 0.20, 0.40, and 0.23 times public key sizes compared with the Modified pqsigRM parameters for 80, 128, and 256 bit-security levels, respectively. Also, I obtain a larger exact bit-security for these parameters than Modified pqsigRM. Compared with the NIST PQC finalist algorithms Crystals-Dilithium, Falcon, and Sphincs+, the public key sizes are still large, but the signature sizes are the smallest among all for every security level. For 128 bits of classical security, the signature size of the proposed signature scheme is 520 bytes, which corresponds to 0.21 times that of Crystals-Dilithium. Moreover, I calculate the verification cycles compared with the NIST PQC finalist algorithms. The number of average verification cycles is 172,669, which corresponds to 0.53 times that of Crystals-Dilithium, and it is the second smallest among the NIST PQC finalist algorithms.

Furthermore, I propose an enhanced version of these, called Enhanced pqsigRM, considering the attacks using the information set decoding and finding the minimum-weight codewords. What is different from Modified pqsigRM is that it uses the systematic public key, minimizes the secret key, simplifies the usage of the hash function, and improves the security issues. There is a trade-off that the parameters get worse. However, compared with the original Modified pqsigRM, the public key size reduces to 2.0 MB, which is 0.5 times the previous one, and the secret key size reduces to 22,512 bytes, which is 0.0015 times the previous one. Also, it still has the advantages of a small signature size and fast verification cycles. These are very important features in digital signature schemes. The signature size is 1,032 bytes, which corresponds to 0.42 times that of Crystals-Dilithium, and it is the second smallest among the NIST PQC finalist algorithms. The number of average verification cycles is 242,901, which corresponds to about 0.74 times that of Crystals-Dilithium, and it is the second smallest among the NIST PQC finalist algorithms.

이 학위 논문에서는 다음 두 가지의 연구가 이루어졌다: i) Reed-Muller(RM) 부호의 동형 계산 및 ii) Modified pqsigRM의 키 크기 및 비트 보안성 개선.

먼저, RM 부호의 동형 연산 방법을 제안한다. 인공 지능(AI), 빅 데이터 및 클라우드 서비스의 지속적인 개발과 함께 완전 동형 암호(FHE)는 기계 학습 시스템에서 개인 정보 보호 및 보안을 유지하기 위한 해결책으로 고려되고 있다. 현재 대부분의 기존 FHE 체계는 격자 기반 암호화를 사용한다. 최신 알고리즘에서는 동형 곱셈과 더 많은 연산을 위해 암호문을 새로 고치는 데 필요한 해당 부트스트래핑에 엄청난 양의 계산 리소스가 필요하다. 따라서 실제 적용을 위해 계산 복잡도를 줄일 수 있는 FHE에 대한 새로운 혁신적인 접근 방식을 찾는 것이 필요하다. 격자 기반 암호에 국한되지 않는 다양한 연구 또한 필요하다. 부호 기반 암호는 이에 대한 새로운 해결책이 될 수 있다.

본 논문에서는 RM 부호를 통해 부호 기반 동형 연산 기법을 제안한다. 선형 부호는 덧셈에 대해 닫힌 것으로 알려져 있지만 선형 부호에서 곱셈 동형 연산을 달성하는 것은 지금까지 불가능했다. 나는 RM 부호를 사용하여 덧셈과 곱셈을 동시에 지원할 수 있는 완전 동형 부호 체계를 제안하여 이 문제를 해결하려고 노력한다. 이는 부호 기반 FHE 방식을 구축하기 위한 선행 단계라고 할 수 있다. 나는 이것을 1차 RM 부호의 연산으로 제한한다. 곱셈 후 RM 부호의 차수가 증가하게 되는데 이 과정의 RM 부호의 차수를 줄여 많은 수의 연산을 수행하는 부트스트래핑 기법이 필요하다. 나는 메시지에 대한 연산과 RM 부호의 해당 부호어에 대한 연산 사이에 일대일 관계를 생성하는 3개의 연속적인 선형 변환을 제안하여 덧셈 또는 곱셈 후 RM 부호의 차수를 보존하는 부트스트래핑 기술을 제안한다. 추가적으로, 부호 기반 암호에서의 동형 암호를 위한 몇 가지 시도들도 제안한다.

두 번째로는, Modified pqsigRM 방식의 키 크기 및 비트 보안 개선 방안을 제안한다. 양자 알고리즘에도 안전한 포스트 양자 암호 (PQC)의 중요성이 점점 커지고 있다. pqsigRM은 국립 표준 기술 연구소 (NIST)의 PQC 표준화 과정의 1라운드에서 제시된 부호 기반 PQC 디지털 서명 체계이다. NIST는 미국의 표준화 기구이다. 이 체계는 NIST PQC 표준화 프로세스에서 논의를 거쳐 알려진 모든 취약점을 제거하여 Modified pqsigRM으로 개정되었다. 그 장점으로는 효율적인 복호화 과정과 작은 서명 크기가 있다. 모든 서명 과정에서 서명을 보내야 하기 때문에 작은 서명 크기는 전자 서명 체계에서 매우 유용하다. 그러나 공개 키 크기가 크다는 문제가 있다.

본 논문에서는 Modified pqsigRM의 공개 키 크기를 줄이고 구체적인 비트 보안을 향상시키는 방법을 제안한다. 공개 키를 체계적인 형태로 변경하고 매개변수를 개선하며 각 매개변수에 대한 비트 보안을 미세 조정한다. 따라서 80, 128 및 256 비트의 보안 수준에 대해서 Modified pqsigRM 매개변수에 비해 각각 0.20, 0.40 및 0.23배 작은 공개 키 크기로 줄일 수 있다. 또한 이러한 매개변수에 대해 Modified pqsigRM보다 더 큰 값의 구체적인 비트 보안을 얻는다. NIST PQC 최종 알고리즘들 Crystals-Dilithium, Falcon, 그리고 Sphincs+와 비교할 때 공개 키 크기는 여전히 크지만 서명 크기는 모든 보안 레벨에 대해 가장 작다. 128 비트의 기존 보안에 대해 제안하는 서명 방식의 서명 크기는 520 바이트로 Crystals-Dilithium의 0.21 배에 해당한다. 또한 NIST PQC 최종 후보 알고리즘과 비교하여 검증 싸이클 수를 계산한다. 검증 싸이클 수의 평균 값은 172,669로 Crystals-Dilithium의 그것의 0.53 배에 해당하며 이것은 네 개의 NIST PQC 최종 알고리즘들 중에 두 번째로 작다.

추가적으로, 정보 집합 복호화 및 부호어의 최소 무게를 계산하는 공격을 고려하여 Enhanced pqsigRM이라고 하는 향상된 버전을 제안한다. Modified pqsigRM과의 차이점은 체계적인 공개 키를 사용하고 비밀 키를 최소화하며 해시 기능을 단순화하고 보안 문제를 개선하는 것이다. 매개 변수 값이 안 좋아진다는 트레이드 오프가 있다. 하지만, Modified pqsigRM에 비해 공개키 크기는 0.5배인 2.0 MB로 줄어들고, 비밀키 크기는 0.0015배인 22,512 바이트로 줄어든다. 또한, 서명 크기가 작고 검증 주기가 빠르다는 장점이 여전히 존재한다. 이들은 디지털 서명 체계에서 매우 중요한 기능이다. 서명 크기는 1,032 바이트로 Crystals-Dilithium의 0.42 배에 해당하며 이것은 네 개의 NIST PQC 최종 알고리즘들 중에 두 번째로 작다. 평균 검증 싸이클 수는 242,901로 Crystals-Dilithium의 약 0.74배에 해당하며 이것은 네 개의 NIST PQC 최종 알고리즘들 중에 두 번째로 작다.