Search

KR-20260061009-A - ELECTRONIC DEVICE AND CONTROLLING METHOD THEREOF

KR20260061009AKR 20260061009 AKR20260061009 AKR 20260061009AKR-20260061009-A

Abstract

전자 장치 및 이의 제어 방법이 개시된다. 특히, 전자 장치는 인스트럭션들을 저장하는 메모리, 인스트럭션들을 실행하도록 구성된 프로세서를 포함하고, 프로세서는 제1 평문 행렬 및 제2 평문 행렬을 획득하고, 격자 기반 암호화 방식에 기초하여 제1 평문 행렬을 암호화함으로써, 제1 암호문 행렬을 획득하며, 두 개의 암호문 쌍을 포함하고 두 개의 암호문 쌍 각각은 제1 유형의 행렬 및 제2 유형의 행렬을 포함하는 구조에 기초하여 제2 평문 행렬을 암호화함으로써, 제2 암호문 행렬을 획득하고, 제1 암호문 행렬의 원소들을 기 정의된 가젯 벡터(gadget vector)에 따라 분해함으로써, 복수의 분해 성분(decomposed components)을 획득하고, 복수의 분해 성분과 제2 암호문 행렬의 원소들 사이의 내적 연산에 기초하여, 제1 평문 행렬과 제2 평문 행렬 간 곱셈 결과에 대응되는 출력 암호문을 획득할 수 있다.

Inventors

  • 배영진
  • 앙로 기욤

Assignees

  • 주식회사 크립토랩

Dates

Publication Date
20260506
Application Date
20250930
Priority Date
20241025

Claims (13)

  1. 전자 장치에 있어서, 인스트럭션들을 저장하는 메모리; 및 상기 인스트럭션들을 실행하도록 구성된 프로세서; 를 포함하고, 상기 프로세서는, 제1 평문 행렬 및 제2 평문 행렬을 획득하고, 격자 기반 암호화 방식에 기초하여 상기 제1 평문 행렬을 암호화함으로써, 제1 암호문 행렬을 획득하며, 두 개의 암호문 쌍을 포함하고 상기 두 개의 암호문 쌍 각각은 제1 유형의 행렬 및 제2 유형의 행렬을 포함하는 구조에 기초하여 상기 제2 평문 행렬을 암호화함으로써, 제2 암호문 행렬을 획득하고, 상기 제1 암호문 행렬의 원소들을 기 정의된 가젯 벡터(gadget vector)에 따라 분해함으로써, 복수의 분해 성분(decomposed components)을 획득하고, 상기 복수의 분해 성분과 상기 제2 암호문 행렬의 원소들 사이의 내적 연산에 기초하여, 상기 제1 평문 행렬과 상기 제2 평문 행렬 간 곱셈 결과에 대응되는 출력 암호문을 획득하는, 전자 장치.
  2. 제1 항에 있어서, 상기 프로세서는, 상기 제1 평문 행렬의 각 행 또는 각 열을 상기 격자 기반 암호화 방식의 비밀키에 대응되는 수치들과 결합하여, 상기 제1 유형의 행렬 및 상기 제2 유형의 행렬을 포함하는 하나의 암호문 쌍으로 변환함으로써, 상기 제1 암호문 행렬을 획득하는, 전자 장치.
  3. 제2 항에 있어서, 상기 프로세서는, 상기 격자 기반 암호화 방식의 비밀키를 토플리츠 행렬(Toeplitz matrix)로 변환하고, 상기 제1 평문 행렬의 각 행 또는 각 열을 상기 토플리츠 행렬과 곱하여 제2 유형의 행렬을 생성하고, 상기 제2 유형의 행렬 및 상기 제1 유형의 행렬을 결합하여 암호문 쌍을 형성함으로써, 상기 제1 암호문 행렬을 획득하는, 전자 장치.
  4. 제1 항에 있어서, 상기 프로세서는, 상기 두 개의 암호문 쌍 중 제1 암호문 쌍이 상기 제2 평문 행렬에 대응되고, 상기 두 개의 암호문 쌍 중 제2 암호문 쌍이 상기 격자 기반 암호화 방식의 비밀키와 상이한 보조 비밀키 및 상기 제2 평문 행렬의 곱에 대응되도록, 상기 제2 암호문 행렬을 획득하는, 전자 장치.
  5. 제1 항에 있어서, 상기 프로세서는, 상기 두 개의 암호문 쌍 각각에 포함되는 상기 제1 유형의 행렬이 상기 제2 평문 행렬 또는 상기 보조 비밀키와 상기 제2 평문 행렬의 곱에 대응되고, 상기 두 개의 암호문 쌍 각각에 포함되는 상기 제2 유형의 행렬이 상기 격자 기반 암호화 방식의 비밀키에 대응되도록, 상기 제2 암호문 행렬을 획득하는, 전자 장치.
  6. 제5 항에 있어서, 상기 프로세서는, 상기 제2 평문 행렬의 각 원소를 토플리츠 행렬과 곱하여 상기 제2 유형의 행렬을 생성하고, 상기 생성된 상기 제2 유형의 행렬과 상기 제1 유형의 행렬을 결합하여 상기 제1 암호문 쌍을 획득하고, 상기 제2 평문 행렬의 각 원소와 상기 보조 비밀키의 곱을 상기 토플리츠 행렬과 곱하여 상기 제2 유형의 행렬을 생성하고, 상기 생성된 상기 제2 유형의 행렬과 상기 제1 유형의 행렬을 결합하여 상기 제2 암호문 쌍을 획득하며, 상기 제1 암호문 쌍 및 상기 제2 암호문 쌍을 포함하는 상기 제2 암호문 행렬을 획득하는, 전자 장치.
  7. 제1 항에 있어서, 상기 프로세서는, 상기 제1 암호문 행렬의 원소들을 상기 가젯 벡터의 자리수 성분에 따라 분해하여 상기 복수의 분해 성분을 획득하고, 상기 복수의 분해 성분 각각에 대하여, 상기 제2 암호문 행렬에 포함되는 상기 제1 유형의 행렬 및 상기 제2 유형의 행렬과 각각 내적 연산을 수행하여 두 내적 결과를 포함하는 순서쌍을 형성하고, 상기 순서쌍들을 결합함으로써, 상기 출력 암호문을 획득하는, 전자 장치.
  8. 제1 항에 있어서, 상기 프로세서는, 상기 제2 평문 행렬을 암호화하기 전에, 상기 제2 평문 행렬의 원소들에 공통적으로 적용되는 공통 모듈러스 및 상기 제2 평문 행렬의 상기 원소들을 구분하는 복수의 블록 각각에 대응되는 복수의 개별 모듈러스에 기초하여, 상기 제2 평문 행렬의 상기 원소들을 하나의 평문으로 결합하는 패킹을 수행하고, 상기 패킹된 제2 평문 행렬을 암호화하여 상기 제2 암호문 행렬을 획득하는, 전자 장치.
  9. 제8 항에 있어서, 상기 프로세서는, 상기 제2 평문 행렬의 상기 원소들이 상기 공통 모듈러스에 대하여는 0으로 표현되고, 상기 제2 평문 행렬의 상기 원소들이 상기 복수의 개별 모듈러스 각각에 대하여는 상기 공통 모듈러스가 곱해진 원소 값으로 표현되도록, 상기 제2 평문 행렬에 대한 패킹을 수행하는, 전자 장치.
  10. 제8 항에 있어서, 상기 복수의 개별 모듈러스는 서로소 관계를 가지도록 설정되는, 전자 장치.
  11. 제8 항에 있어서, 상기 프로세서는, 상기 출력 암호문이 획득된 후, 상기 출력 암호문에 대한 모듈러스 연산을 수행하여, 상기 공통 모듈러스에 대응되는 값과 상기 복수의 개별 모듈러스 각각에 대응되는 값들을 추출하고, 상기 추출된 값들에 기초하여 상기 제1 평문 행렬과 상기 제2 평문 행렬 간 곱셈 결과를 상기 복수의 블록 각각에 대응되도록 분리하여 획득하는, 전자 장치.
  12. 전자 장치를 제어하는 방법에 있어서, 제1 평문 행렬 및 제2 평문 행렬을 획득하는 단계; 격자 기반 암호화 방식에 기초하여 상기 제1 평문 행렬을 암호화함으로써 제1 암호문 행렬을 획득하는 단계; 두 개의 암호문 쌍을 포함하고 상기 두 개의 암호문 쌍 각각은 제1 유형의 행렬 및 제2 유형의 행렬을 포함하는 구조에 기초하여 상기 제2 평문 행렬을 암호화함으로써 제2 암호문 행렬을 획득하는 단계; 상기 제1 암호문 행렬의 원소들을 기 정의된 가젯 벡터에 따라 분해하여 복수의 분해 성분을 획득하는 단계; 및 상기 복수의 분해 성분과 상기 제2 암호문 행렬의 원소들 사이의 내적 연산에 기초하여, 상기 제1 평문 행렬과 상기 제2 평문 행렬 간 곱셈 결과에 대응되는 출력 암호문을 획득하는 단계를 포함하는, 방법.
  13. 전자 장치를 제어하는 방법을 실행하는 프로그램을 포함하는 비일시적 컴퓨터 판독 가능 기록매체에 있어서, 상기 전자 장치를 제어하는 방법은, 제1 평문 행렬 및 제2 평문 행렬을 획득하는 단계; 격자 기반 암호화 방식에 기초하여 상기 제1 평문 행렬을 암호화함으로써 제1 암호문 행렬을 획득하는 단계; 두 개의 암호문 쌍을 포함하고 상기 두 개의 암호문 쌍 각각은 제1 유형의 행렬 및 제2 유형의 행렬을 포함하는 구조에 기초하여 상기 제2 평문 행렬을 암호화함으로써 제2 암호문 행렬을 획득하는 단계; 상기 제1 암호문 행렬의 원소들을 기 정의된 가젯 벡터에 따라 분해하여 복수의 분해 성분을 획득하는 단계; 및 상기 복수의 분해 성분과 상기 제2 암호문 행렬의 원소들 사이의 내적 연산에 기초하여, 상기 제1 평문 행렬과 상기 제2 평문 행렬 간 곱셈 결과에 대응되는 출력 암호문을 획득하는 단계를 포함하는, 컴퓨터 판독 가능 기록매체.

Description

전자 장치 및 이의 제어 방법{ELECTRONIC DEVICE AND CONTROLLING METHOD THEREOF} 본 개시는 전자 장치 및 전자 장치를 제어하는 방법에 관한 것으로서, 암호문 상태에서 행렬곱을 수행할 수 있는 전자 장치 및 이의 제어 방법에 관한 것이다. 최근 동형암호(homomorphic encryption)가 다양한 데이터 처리 환경에 적용되면서, 암호화된 상태에서 행렬 연산을 수행하려는 요구가 커지고 있다. 동형암호는 평문을 복호화하지 않고도 연산을 가능하게 하지만, 연산의 복잡도가 높고 오류 항이 누적되기 때문에 효율적인 구현이라는 중요한 해결 과제를 안고 있다. 특히, 동형암호에 있어서는 다수의 데이터를 포함하는 행렬 연산을 암호문 상태에서 처리하려는 경우, 연산량과 메모리 사용량이 기하급수적으로 증가하는 문제를 직면하게 된다. 이와 같은 상황에서, 암호문 상태에서 행렬과 행렬을 곱하는 암호문-암호문 행렬곱(CCMM, Ciphertext-Ciphertext Matrix Multiplication)은 가장 기본적이면서도 중요한 문제 중 하나로 대두되었다. 그러나, 종래 기술에서는 CCMM을 직접 수행하지 않고, 일반적으로 평문-평문 행렬곱(PPMM, Plaintext-Plaintext Matrix Multiplication)으로 환원한 뒤 회전(rotation)과 키 스위칭(key switching)을 반복적으로 수행하는 방식이 사용되고 있는데, 이러한 방식에 대해서는 연산 효율성이 현저히 떨어진다는 한계가 지적되고 있다. 특히, 키 스위칭 과정은 수학적으로 복잡한 NTT(Number Theoretic Transform) 연산을 포함하므로 연산량과 지연을 크게 증가시킨다. 또한, 키 교환에 필요한 부가 키를 미리 준비해야 하므로 시스템의 메모리 사용량이 증가하고, 관리 측면에서도 부담이 커진다. 따라서 종래 기술은 연산 효율성과 자원 소모, 그리고 안정성 측면에서 한계를 가지고 있다. 본 개시에 따른 상기 측면 및 기타 측면, 특징 및 장점은 첨부된 도면과 함께 설명되는 이하의 상세한 설명으로부터 더욱 명백해질 것이다. 도 1은 본 개시의 일 실시 예에 따른 전자 장치의 구성을 간략하게 나타내는 도면, 도 2는 본 개시의 일 실시 예에 따른 제1 암호문의 획득 과정, 제2 암호문의 획득 과정 및 출력 암호문의 획득 과정에 관련된 동작을 상세하게 설명하기 위한 도면, 도 3은 본 개시의 일 실시 예에 따른 평문 행렬 패킹에 대해 설명하기 위한 도면, 그리고, 도 4는 본 개시의 일 실시 예에 따른 전자 장치의 제어 방법을 나타내는 흐름도이다. 본 실시 예들은 다양한 변환을 가할 수 있고 여러 가지 실시 예를 가질 수 있는바, 특정 실시 예들을 도면에 예시하고 상세한 설명에 상세하게 설명하고자 한다. 그러나 이는 특정한 실시 형태에 대해 범위를 한정하려는 것이 아니며, 본 개시의 실시 예의 다양한 변경(modifications), 균등물(equivalents), 및/또는 대체물(alternatives)을 포함하는 것으로 이해되어야 한다. 도면의 설명과 관련하여, 유사한 구성요소에 대해서는 유사한 참조 부호가 사용될 수 있다. 본 개시를 설명함에 있어서, 관련된 공지 기능 혹은 구성에 대한 구체적인 설명이 본 개시의 요지를 불필요하게 흐릴 수 있다고 판단되는 경우 그에 대한 상세한 설명은 생략한다. 덧붙여, 하기 실시 예는 여러 가지 다른 형태로 변형될 수 있으며, 본 개시의 기술적 사상의 범위가 하기 실시 예에 한정되는 것은 아니다. 오히려, 이들 실시 예는 본 개시를 더욱 충실하고 완전하게 하고, 당업자에게 본 개시의 기술적 사상을 완전하게 전달하기 위하여 제공되는 것이다. 본 개시에서 사용한 용어는 단지 특정한 실시 예를 설명하기 위해 사용된 것으로, 권리범위를 한정하려는 의도가 아니다. 단수의 표현은 문맥상 명백하게 다르게 뜻하지 않는 한, 복수의 표현을 포함한다. 본 개시에서, "가진다," "가질 수 있다," "포함한다," 또는 "포함할 수 있다" 등의 표현은 해당 특징(예: 수치, 기능, 동작, 또는 부품 등의 구성요소)의 존재를 가리키며, 추가적인 특징의 존재를 배제하지 않는다. 본 개시에서, "A 또는 B," "A 또는/및 B 중 적어도 하나," 또는 "A 또는/및 B 중 하나 또는 그 이상"등의 표현은 함께 나열된 항목들의 모든 가능한 조합을 포함할 수 있다. 예를 들면, "A 또는 B," "A 및 B 중 적어도 하나," 또는 "A 또는 B 중 적어도 하나"는, (1) 적어도 하나의 A를 포함, (2) 적어도 하나의 B를 포함, 또는 (3) 적어도 하나의 A 및 적어도 하나의 B 모두를 포함하는 경우를 모두 지칭할 수 있다. 본 개시에서 사용된 "제1," "제2," "첫째," 또는 "둘째,"등의 표현들은 다양한 구성요소들을, 순서 및/또는 중요도에 상관없이 수식할 수 있고, 한 구성요소를 다른 구성요소와 구분하기 위해 사용될 뿐 해당 구성요소들을 한정하지 않는다. 어떤 구성요소(예: 제1 구성요소)가 다른 구성요소(예: 제2 구성요소)에 "(기능적으로 또는 통신적으로) 연결되어((operatively or communicatively) coupled with/to)" 있다거나 "접속되어(connected to)" 있다고 언급된 때에는, 상기 어떤 구성요소가 상기 다른 구성요소에 직접적으로 연결되거나, 다른 구성요소(예: 제3 구성요소)를 통하여 연결될 수 있다고 이해되어야 할 것이다. 반면에, 어떤 구성요소(예: 제1 구성요소)가 다른 구성요소(예: 제2 구성요소)에 "직접 연결되어" 있다거나 "직접 접속되어" 있다고 언급된 때에는, 상기 어떤 구성요소와 상기 다른 구성요소 사이에 다른 구성요소(예: 제3 구성요소)가 존재하지 않는 것으로 이해될 수 있다. 본 개시에서 사용된 표현 "~하도록 구성된(또는 설정된)(configured to)"은 상황에 따라, 예를 들면, "~에 적합한(suitable for)," "~하는 능력을 가지는(having the capacity to)," "~하도록 설계된(designed to)," "~하도록 변경된(adapted to)," "~하도록 만들어진(made to)," 또는 "~를 할 수 있는(capable of)"과 바꾸어 사용될 수 있다. 용어 "~하도록 구성된(또는 설정된)"은 하드웨어적으로 "특별히 설계된(specifically designed to)" 것만을 반드시 의미하지 않을 수 있다. 대신, 어떤 상황에서는, "~하도록 구성된 장치"라는 표현은, 그 장치가 다른 장치 또는 부품들과 함께 "~할 수 있는" 것을 의미할 수 있다. 예를 들면, 문구 "A, B, 및 C를 수행하도록 구성된(또는 설정된) 프로세서"는 해당 동작을 수행하기 위한 전용 프로세서(예: 임베디드 프로세서), 또는 메모리 장치에 저장된 하나 이상의 소프트웨어 프로그램들을 실행함으로써, 해당 동작들을 수행할 수 있는 범용 프로세서(generic-purpose processor)(예: CPU 또는 application processor)를 의미할 수 있다. 실시 예에 있어서 '모듈' 혹은 '부'는 적어도 하나의 기능이나 동작을 수행하며, 하드웨어 또는 소프트웨어로 구현되거나 하드웨어와 소프트웨어의 결합으로 구현될 수 있다. 또한, 복수의 '모듈' 혹은 복수의 '부'는 특정한 하드웨어로 구현될 필요가 있는 '모듈' 혹은 '부'를 제외하고는 적어도 하나의 모듈로 일체화되어 적어도 하나의 프로세서로 구현될 수 있다. 한편, 도면에서의 다양한 요소와 영역은 개략적으로 그려진 것이다. 따라서, 본 발명의 기술적 사상은 첨부한 도면에 그려진 상대적인 크기나 간격에 의해 제한되지 않는다. 이하에서는 첨부한 도면을 참고하여 본 개시에 따른 실시 예에 대하여 본 개시가 속하는 기술 분야에서 통상의 지식을 가진 자가 용이하게 실시할 수 있도록 상세히 설명한다. 도 1은 본 개시의 일 실시 예에 따른 전자 장치(100)의 구성을 간략하게 나타내는 도면이다. 도 1에 도시된 바와 같이, 전자 장치(100)는 메모리(110) 및 프로세서(120)를 포함할 수 있다. 다만, 도 1에 도시된 바와 같은 구성들은 예시적인 것에 불과할 뿐이며, 본 개시를 실시함에 있어 도 1에 도시된 바와 같은 구성에 더하여 새로운 구성이 추가되거나 일부 구성이 생략될 수 있음은 물론이다. 예를 들어, 전자 장치(100)는 외부 장치와의 통신을 수행할 수 있는 통신 인터페이스(WiFi 모듈, Bluetooth 모듈, 무선 통신 모듈, NFC 모듈 및 UWB(Ultra-Wide Band) 모듈 등), 사용자 입력을 수신할 수 있는 입력 인터페이스(예: 마이크, 터치 스크린 등), 다양한 정보를 출력할 수 있는 출력 인터페이스(예: 디스플레이, 스피커 등) 등을 더 포함할 수 있다. 메모리(110)에는 전자 장치(100)에 관한 적어도 하나의 인스트럭션(instruction)이 저장될 수 있다. 그리고, 메모리(110)에는 전자 장치(100)를 구동시키기 위한 O/S(Operating System)가 저장될 수 있다. 또한, 메모리(110)에는 본 개시의 다양한 실시 예들에 따라 전자 장치(100)가 동작하기 위한 각종 소프트웨어 프로그램이나 애플리케이션이 저장될 수도 있다. 그리고, 메모리(110)는 플래시 메모리(Flash Memory) 등과 같은 반도체 메모리나 하드디스크(Hard Disk) 등과 같은 자기 저장 매체 등을 포함할 수 있다. 구체적으로, 메모리(110)에는 본 개시의 다양한 실시 예에 따라 전자 장치(100)가 동작하기 위한 각종 소프트웨어 모듈이 저장될 수 있으며, 프로세서(120)는 메모리(110)에 저장된 각종 소프트웨어 모듈을 실행하여 전자 장치(100)의 동작을 제어할 수 있다. 즉, 메모리(110)는 프로세서(120)에 의해 액세스되며, 프로세서(120)에 의한 데이터의 독취/기록/수정/삭제/갱신 등이 수행될 수 있다. 한편, 본 개시에서 메모리(110)라는 용어는 메모리(110), 프로세서(120) 내 롬, 램 또는 전자 장치(100)에 장착되는 메모리 카드(예를 들어, micro SD 카드, 메모리 스틱)를 포함하는 의미로 사용될 수