Reduction from Module-SIS to Ring-SIS and Sampling Reduction in Multi-Key Homomorphic Encryption by Reusing Error

Abstract

In this dissertation, four contributions are given as i) the reduction from module short integer solution problem (MSIS) to ring-short integer solution problem (RSIS), ii) the improved reduction from MSIS to RSIS, iii) the introduction to the variant of RLWE (Re-RLWE) and the hardness of Re-RLWE, and iv) the variant of the compact multi-key homomorphic encryption (ReCMK-HE) based on Re-RLWE. First, we propose the reduction from MSIS to RSIS under some condition on RSIS. To demonstrate this reduction, we derive two reductions. We first show that there is a reduction from RSISqk,mk,βk to RSISq,m,β. Second, we propose the reduction from MSISqk,mk,β1 to RSISq,m,β under some norm constraint of RSIS. Combining these two results implies that RSIS for a specified modulus and the number of samples is more difficult than MSIS under norm constraint of RSIS, which provides the range of possible module rank for MSIS. Second, we propose the improved reduction from MSIS to RSIS. To prove this reduction, we show that RSIS is more difficult than MSIS with the same modulus and ring dimension under some constraint of RSIS. Also, we show that through the reduction from MSIS to RSIS with the same modulus, the rank of the module is extended as much as the number of instances of RSIS from half of the number of instances of RSIS. Next, we show that MSIS is more difficult than MSIS defined in the previous one. Also, we propose that MSIS with the modulus prime qk is more difficult than MSIS with the composite modulus c, such that c is divided by q. Through the three reductions, we conclude that RSIS with the modulus q is more difficult than MSIS with the composite modulus c. Third, we propose the variant of RLWE, denoted by Re-RLWE by reusing the error x as a secret when generating the RLWE sample (a, b = a·s+x). That is, the Re-RLWE sample is generated in the form (a, b = a· s+x, c = a·x+e). To define this problem, we define the Re-RLWE distribution and prove the hardness of Re-RLWE. Lastly, we propose the variant of the compact multi-key homomorphic encryption ReCMK-HE based on Re-RLWE. This scheme has the modified multiplication keys and the modified rotation keys with the reduced size of key compared to the original CMK-HE.

이 학위 논문에서는 i) 모듈-짧은 정수해 문제 (MSIS) 에서 환-짧은 정수해 문제 (RSIS) 로의 환원방법, ii) 모듈-짧은 정수해 문제 (MSIS)에서 환-짧은 정수해 문 제 (RSIS)로의 향상된 환원방법, iii) 변형된 RLWE의 도입과 그 어려움, iv) 변형된 RLWE를 기반으로 한 변형된 compact-다중 키 동형 암호 (CMK-HE)에 대한 방법들 이 연구되었다. 첫 번째로 RSIS의 특정 조건 하에서 MSIS에서 RSIS로의 환원을 제안한다. 이 환원을 보이기 위해, 두가지의 환원 방법을 보인다. 먼저 RSISqk,mk,βk 문제에서 RSISq,m,β로의 환원을 보인다. 그리고 RSIS의 특정 조건 하에서 MSISqk,mk,β′ 문제에서 RSISqk,mk,βk문제로의 환원을 보인다. 두 결과를 통해 RSIS 문제가 MSIS의 문제보다 특정 조건 하에서 더욱 어렵다고 할 수 있고, 환원된 MSIS가 가능한 Rank 의 범위를 제공한다. 두 번째로, 기본의 MSIS 문제에서 RSIS로의 환원보다 더욱 향상된 방법을 제시한다. RSIS문제와 같은 modulus와 같은 환-차원을 가지는 MSIS문제보다 RSIS의 문제가 더 어려움을 제안한다. 이 방법을 통해 기존의 MSIS가 가능한 Rank의 범위를 2배가량 증가시킬 수 있다. 그리고 첫 번째 방법에서 사용된 MSIS보다 두 번째 방법에서 사용된 MSIS가 더욱 어려움을 보였다. 또한, 소수 modulus를 갖는 MSIS이 합성수 modulus를 갖는 MSIS보다 더 어렵다는 것을 제안한다. 이 방법들을 통해 소수 modulus를 갖는 RSIS가 합성수 modulus를 갖는 MSIS보다 더 어렵다고 말할 수 있다. 세 번째로, RLWE 샘플에서 사용된 에러를 재사용한 새로운 문제인 Re-RLWE를 제안한다. 이 문제를 정의하기 위해 Re-RLWE분포를 정의하고, 그 어려움을 증명한다. 마지막으로, Re-RLWE기반의변형된compact다중 키 동형암호를제안한다.이 암호시스템은 변형된 곱셈키와 변형된 회전키들을 가지며, 기존의 compact 다중 키 동형암호와 비교하여 키의 크기가 감소함을 보일 수 있다.