KR20230161195A

KR20230161195A - 영지식 증명 친화적인 일방향 함수를 이용한 연산 방법, 그리고 이를 구현하기 위한 장치

Info

Publication number: KR20230161195A
Application number: KR1020220060914A
Authority: KR
Inventors: 문덕재; 이주희; 이주영; 손용하; 김성광; 하진철; 손민철; 이병학
Original assignee: 삼성에스디에스 주식회사; 한국과학기술원
Priority date: 2022-05-18
Filing date: 2022-05-18
Publication date: 2023-11-27
Also published as: EP4280539B1; EP4280539A1; US20240007292A1

Abstract

본 개시의 일 실시예에 따른 컴퓨팅 장치에 의해 수행되는 영지식 증명 친화적인 일방향 함수를 이용한 연산 방법은, 일방향 함수의 입력 비트열을 확장 행렬에 입력하여 제1 중간 비트열을 산출하는 단계, 상기 제1 중간 비트열을 소정 개수의 비트열로 분할하고, 상기 분할된 소정 개수의 비트열 각각을 S-box(Substitution-box)에 입력하여 제2 중간 비트열을 산출하는 단계, 및 상기 제2 중간 비트열을 축소 행렬에 입력하여 상기 일방향 함수의 출력 비트열을 출력하는 단계를 포함한다.

Description

영지식 증명 친화적인 일방향 함수를 이용한 연산 방법, 그리고 이를 구현하기 위한 장치{METHOD FOR CALCULATING USING A ZERO KNOWLEDGE PROOF-FRIENDLY ONE-WAY FUNCTION, AND APPARATUS IMPLEMENTING THE SAME METHOD}

본 개시는 영지식 증명 친화적인 일방향 함수를 이용한 연산 방법, 그리고 이를 구현하기 위한 장치에 관한 것으로서, 보다 자세하게는, 전자서명을 수행 시 영지식 증명 친화적인 일방향 함수를 이용하여 연산을 수행하기 위한 영지식 증명 친화적인 일방향 함수를 이용한 연산 방법, 그리고 이를 구현하기 위한 장치에 관한 것이다.

최근에는 RSA, 타원곡선암호 등의 표준 공개키 암호를 해킹할 수 있는 양자컴퓨터의 개발이 앞당겨지면서, 양자컴퓨터의 발명 이후에도 안전한 암호인 양자 내성 암호(Post-Quantum Cryptography, PQC)의 표준화 및 연구가 국제적으로 활발히 진행되고 있다.

영지식 증명(Zero-Knowledge Proof, ZKP) 기반 전자서명은 양자 내성 암호(PQC)를 이용한 전자서명의 일종으로, 2007년 STOC에서 Ishai 등이 제안한 MPC-in-the-Head 패러다임에 뿌리를 두고 있다.

영지식 증명(ZKP) 기반 전자서명의 대표적인 예로서, MPC-in-the-Head 방식의 영지식 증명과 전용 블록암호를 결합한 전자서명인 Picnic이 사용되고 있다.

Picnic과 같이 블록암호를 이용하는 영지식 증명 기반 전자서명은 블록암호의 입출력 한 쌍이 블록암호 비밀키에 대한 일방향 함수값이라는 것을 이용하며, 블록암호의 bitwise AND 연산 또는 S-box 연산과 같은 비선형 연산 개수에 서명크기가 비례하는 방식을 따른다.

블록암호를 이용하는 영지식 증명 기반 전자서명은 대수적 공격에 대한 안전성을 보장하기 위해 여러 번의 다자간 계산(Multi-Party Computation, MPC)을 병렬 수행하게 되는데, 이로 인해 블록암호의 비선형 연산 개수가 증가하게 되어 서명 크기가 매우 커지게 되는 문제점이 있다. 또한, 서명 크기가 커짐에 따라 네트워크 전송 비용이 많이 드는 문제 또한 발생한다.

따라서, 영지식 증명 기반 전자서명을 설계함에 있어, 대수적 공격에 대한 안전성을 보장하면서도 서명 크기를 획기적으로 줄일 수 있는 기술이 요구된다.

본 개시가 해결하고자 하는 기술적 과제는, 영지식 증명 기반 전자서명을 설계함에 있어, 대수적 공격에 대해 안전하면서도 서명 크기를 줄일 수 있는 영지식 증명 친화적인 일방향 함수를 이용한 연산 방법, 그리고 이를 구현하기 위한 장치를 제공하는 것이다.

본 개시가 해결하고자 하는 다른 기술적 과제는, 영지식 증명 기반 전자서명을 설계함에 있어, 비선형 연산 개수가 적은 일방향의 함수를 제공할 수 있는 영지식 증명 친화적인 일방향 함수를 이용한 연산 방법, 그리고 이를 구현하기 위한 장치를 제공하는 것이다.

본 개시가 해결하고자 하는 또 다른 기술적 과제는, 영지식 증명 기반 전자서명을 설계함에 있어, 블록암호가 아닌 일반적인 형태의 일방향 함수를 이용하여 영지식 증명을 수행할 수 있는 영지식 증명 친화적인 일방향 함수를 이용한 연산 방법, 그리고 이를 구현하기 위한 장치를 제공하는 것이다.

본 개시의 기술적 과제들은 이상에서 언급한 기술적 과제들로 제한되지 않으며, 언급되지 않은 또 다른 기술적 과제들은 아래의 기재로부터 본 개시의 기술분야에서의 통상의 기술자에게 명확하게 이해될 수 있을 것이다.

상기 기술적 과제를 해결하기 위한, 본 개시의 일 실시예에 따른 컴퓨팅 장치에 의해 수행되는 영지식 증명 친화적인 일방향 함수를 이용한 연산 방법은, 일방향 함수의 입력 비트열을 확장 행렬에 입력하여 제1 중간 비트열을 산출하는 단계, 상기 제1 중간 비트열을 소정 개수의 비트열로 분할하고, 상기 분할된 소정 개수의 비트열 각각을 S-box(Substitution-box)에 입력하여 제2 중간 비트열을 산출하는 단계, 및 상기 제2 중간 비트열을 축소 행렬에 입력하여 상기 일방향 함수의 출력 비트열을 출력하는 단계를 포함한다.

일 실시예로서, 상기 일방향 함수의 입력 비트열 및 출력 비트열의 길이는 N(단, N은 자연수)이고, 상기 제1 중간 비트열 및 상기 제2 중간 비트열의 길이는 M(단, M은 자연수)이되, M은 N의 배수이고, 상기 S-box에 입력되는 비트열의 길이는 L(단, L은 자연수)이되, L은 M의 약수일 수 있다.

일 실시예로서, 상기 S-box는 K개(단, K는 1이상의 자연수)의 서브 S-box를 포함하고, 상기 제2 중간 비트열을 산출하는 단계는, 상기 제1 중간 비트열을 K개의 비트열로 분할하는 단계, 및 상기 분할된 K개의 비트열 각각을 상기 서브 S-box에 입력하는 단계를 포함할 수 있다.

일 실시예로서, 상기 서브 S-box는 32 이상의 길이를 갖는 비트열을 입력 받도록 설정될 수 있다.

일 실시예로서, 상기 서브 S-box는 유한체 상에서의 다항 연산을 수행하는 비선형 함수일 수 있다.

일 실시예로서, 상기 확장 행렬은 MxN 크기를 가지는 바이너리 행렬이고, 상기 축소 행렬은 NxM 크기를 가지는 바이너리 행렬일 수 있다.

상기 확장 행렬을 생성하는 단계를 더 포함하고, 상기 확장 행렬을 생성하는 단계는, 상기 확장 행렬의 제1 번째 행 또는 제1 번째 열을 랜덤 값으로 구성하는 단계, 및 상기 제1 번째 행 또는 제1 번째 열에 대한 순환 시프트(circular shift)를 통해 상기 확장 행렬의 나머지 행 또는 나머지 열을 구성하는 단계를 포함할 수 있다.

일 실시예로서, 상기 축소 행렬을 생성하는 단계를 더 포함하고, 상기 축소 행렬을 생성하는 단계는, 상기 축소 행렬의 제1 번째 행 또는 제1 번째 열을 랜덤 값으로 구성하는 단계, 및 상기 제1 번째 행 또는 상기 제1 번째 열에 대한 순환 시프트(circular shift)를 통해 상기 축소 행렬의 나머지 행 또는 나머지 열을 구성하는 단계를 포함할 수 있다.

일 실시예로서, 상기 확장 행렬 및 상기 축소 행렬의 전체 행 또는 전체 열을 랜덤 값으로 구성하는 단계를 더 포함할 수 있다.

일 실시예로서, 상기 일방향 함수는 단일 라운드로 구성될 수 있다.

일 실시예로서, 상기 일방향 함수의 상기 입력 비트열과 상기 출력 비트열을 이용하여 영지식 증명 기반의 전자서명을 수행하는 단계를 더 포함할 수 있다.

일 실시예로서, 상기 일방향 함수의 상기 입력 비트열과 상기 출력 비트열을 이용하여 영지식 증명 기반의 전자서명을 수행하는 단계는, 상기 입력 비트열과 상기 출력 비트열을 각각 상기 전자서명의 비밀키와 공개키로 설정하는 단계, 및 상기 비밀키와 상기 공개키를 상기 영지식 증명을 위한 증명(prove) 함수에 입력하여, 상기 전자서명을 위한 서명 데이터를 생성하는 단계를 포함할 수 있다.

상기 기술적 과제를 해결하기 위한, 본 개시의 일 실시예에 따른 컴퓨터 판독 가능한 비일시적 기록 매체는, 컴퓨터로 하여금 상기 방법을 수행하도록 하는 컴퓨터 프로그램이 저장된다.

상기 기술적 과제를 해결하기 위한, 본 개시의 일 실시예에 따른 컴퓨팅 장치는, 하나 이상의 프로세서, 상기 프로세서에 의하여 수행되는 컴퓨터 프로그램을 로드(load)하는 메모리, 및 상기 컴퓨터 프로그램을 저장하는 스토리지를 포함하되, 상기 컴퓨터 프로그램은, 일방향 함수의 입력 비트열을 확장 행렬에 입력하여 제1 중간 비트열을 산출하는 동작, 상기 제1 중간 비트열을 소정 개수의 비트열로 분할하고, 상기 분할된 소정 개수의 비트열 각각을 S-box(Substitution-box)에 입력하여 제2 중간 비트열을 산출하는 동작, 및 상기 제2 중간 비트열을 축소 행렬에 입력하여 상기 일방향 함수의 출력 비트열을 출력하는 동작을 수행하기 위한 인스트럭션을 포함한다.

일 실시예로서, 상기 S-box는 K개(단, K는 1이상의 자연수)의 서브 S-box를 포함하고, 상기 제2 중간 비트열을 산출하는 동작은, 상기 제1 중간 비트열을 K개의 비트열로 분할하는 동작, 및 상기 분할된 K개의 비트열 각각을 상기 서브 S-box에 입력하는 동작을 포함할 수 있다.

상기 컴퓨터 프로그램은, 상기 일방향 함수의 상기 입력 비트열과 상기 출력 비트열을 이용하여 영지식 증명 기반의 전자서명을 수행하는 동작을 수행하기 위한 인스트럭션을 더 포함하고, 상기 영지식 증명 기반의 전자서명을 수행하는 동작은, 상기 입력 비트열과 상기 출력 비트열을 각각 상기 전자서명의 비밀키와 공개키로 설정하는 동작, 및 상기 비밀키와 상기 공개키를 상기 영지식 증명을 위한 증명(prove) 함수에 입력하여, 상기 전자서명을 위한 서명 데이터를 생성하는 동작을 포함할 수 있다.

도 1은 본 개시의 일 실시예에 따른 영지식 증명 친화적인 일방향 함수를 이용한 연산 방법을 설명하기 위한 순서도이다.
도 2는 도 1에 도시된 일부 단계의 세부 프로세스를 설명하기 위한 순서도이다.
도 3은 본 개시의 몇몇 실시예에 따른 영지식 증명 친화적인 일방향 함수를 구성하는 전체 프로세스를 도시한 예이다.
도 4는 도3의 전체 프로세스의 각 단계에서 계산되는 일방향 함수 구성을 위한 산출식의 예이다.
도 5는 본 개시의 몇몇 실시예에 따른 확장 행렬을 생성하는 방법을 설명하기 위한 순서도이다.
도 6은 본 개시의 몇몇 실시예에 따른 축소 행렬을 생성하는 방법을 설명하기 위한 순서도이다.
도 7은 본 개시의 몇몇 실시예에 따른 전자서명을 수행하는 방법을 설명하기 위한 순서도이다.
도 8은 본 개시의 몇몇 실시예에 따른 전자서명을 위한 세 가지 알고리즘 수행 시 입출력 값을 보여주는 예이다.
도 9는 본 개시의 일 실시예에 따른 방법들을 구현할 수 있는 예시적인 컴퓨팅 장치의 하드웨어 구성도이다.

이하, 첨부된 도면을 참조하여 본 개시의 바람직한 실시 예들을 상세히 설명한다. 본 개시의 이점 및 특징, 그리고 그것들을 달성하는 방법은 첨부되는 도면과 함께 상세하게 후술되어 있는 실시예들을 참조하면 명확해질 것이다. 그러나 본 개시의 기술적 사상은 이하의 실시예들에 한정되는 것이 아니라 서로 다른 다양한 형태로 구현될 수 있으며, 단지 이하의 실시예들은 본 개시의 기술적 사상을 완전하도록 하고, 본 개시가 속하는 기술분야에서 통상의 지식을 가진 자에게 본 개시의 범주를 완전하게 알려주기 위해 제공되는 것이며, 본 개시의 기술적 사상은 청구항의 범주에 의해 정의될 뿐이다.

각 도면의 구성요소들에 참조부호를 부가함에 있어서, 동일한 구성요소들에 대해서는 비록 다른 도면상에 표시되더라도 가능한 한 동일한 부호를 가지도록 하고 있음에 유의해야 한다. 또한, 본 개시를 설명함에 있어, 관련된 공지 구성 또는 기능에 대한 구체적인 설명이 본 개시의 요지를 흐릴 수 있다고 판단되는 경우에는 그 상세한 설명은 생략한다.

다른 정의가 없다면, 본 명세서에서 사용되는 모든 용어(기술 및 과학적 용어를 포함)는 본 개시가 속하는 기술분야에서 통상의 지식을 가진 자에게 공통적으로 이해될 수 있는 의미로 사용될 수 있다. 또 일반적으로 사용되는 사전에 정의되어 있는 용어들은 명백하게 특별히 정의되어 있지 않는 한 이상적으로 또는 과도하게 해석되지 않는다. 본 명세서에서 사용된 용어는 실시예들을 설명하기 위한 것이며 본 개시를 제한하고자 하는 것은 아니다. 본 명세서에서, 단수형은 문구에서 특별히 언급하지 않는 한 복수형도 포함한다.

또한, 본 개시의 구성 요소를 설명하는 데 있어서, 제1, 제2, A, B, (a), (b) 등의 용어를 사용할 수 있다. 이러한 용어는 그 구성 요소를 다른 구성 요소와 구별하기 위한 것일 뿐, 그 용어에 의해 해당 구성 요소의 본질이나 차례 또는 순서 등이 한정되지 않는다. 어떤 구성 요소가 다른 구성요소에 "연결", "결합" 또는 "접속"된다고 기재된 경우, 그 구성 요소는 그 다른 구성요소에 직접적으로 연결되거나 또는 접속될 수 있지만, 각 구성 요소 사이에 또 다른 구성 요소가 "연결", "결합" 또는 "접속"될 수도 있다고 이해되어야 할 것이다.

명세서에서 사용되는 "포함한다 (comprises)" 및/또는 "포함하는 (comprising)"은 언급된 구성 요소, 단계, 동작 및/또는 소자는 하나 이상의 다른 구성 요소, 단계, 동작 및/또는 소자의 존재 또는 추가를 배제하지 않는다.

이하, 본 개시의 몇몇 실시예들에 대하여 첨부된 도면에 따라 상세하게 설명한다.

도 1은 본 개시의 일 실시예에 따른 영지식 증명 친화적인 일방향 함수를 이용한 연산 방법을 설명하기 위한 순서도이다.

본 개시의 실시예에 따른 영지식 증명 친화적인 일방향 함수를 이용한 연산 방법은 도 9에 도시되어 있는 컴퓨팅 장치(100)에 의하여 실행될 수 있다. 본 실시예에 따른 방법을 실행하는 상기 컴퓨팅 장치(100)는 응용 프로그램 실행 환경을 구비한 컴퓨팅 장치일 수 있다. 컴퓨팅 장치(100)는 예컨대, PC, 서버, 노트북, 스마트 폰 등 연산 기능을 수행할 수 있는 장치일 수 있다.

본 개시의 실시예에 따른 방법에 포함되는 일부 동작의 수행 주체에 대한 기재가 생략될 수 있으며, 그러한 경우 그 주체는 상기 컴퓨팅 장치(100)임을 유의한다.

이하에서 설명되는 본 개시의 실시예에 의하면, 블록 암호의 형태가 아닌 영지식 증명(Zero-Knowledge Proof, ZKP) 친화적인 일방향 함수를 구성할 수 있다.

먼저, 동작 S11에서, 컴퓨팅 장치(100)는 일방향 함수의 입력 비트열을 확장 행렬에 입력하여 제1 중간 비트열을 산출한다.

일 실시예로서, 입력 비트열의 길이가 N(단, N은 자연수)이고, 확장 행렬이 MxN 크기(단, M은 자연수이면서 N의 배수)를 가지는 바이너리(binary) 행렬로 구현되는 경우, 확장 행렬에 입력되는 입력 비트열의 길이(N)가 확장되어 길이가 M인 제1 중간 비트열이 산출될 수 있다.

다음으로, 동작 S12에서, 컴퓨팅 장치(100)는 제1 중간 비트열을 소정 개수의 비트열로 분할하고, 분할된 소정 개수의 비트열 각각을 S-box(Substitution box)에 입력하여 제2 중간 비트열을 산출한다. 여기서, S-box는 1개 이상의 서브 S-box로 구성될 수 있다.

도 2를 참조하면, 동작 S12는 제1 중간 비트열을 K개(단, K는 1 이상의 자연수)의 비트열로 분할하는 동작 S121과, 분할된 K개의 비트열 각각을 K개의 서브 S-box 각각에 입력하는 동작 S122를 포함할 수 있다. 이때, 동작 S122에서, 분할된 K개의 비트열은 각각 높은 차수를 갖는 K개의 대형 서브 S-box 각각에 입력될 수 있다. 예로서, 각 서브 S-box는 최소한 32 이상의 길이를 갖는 비트열을 입력 받도록 설정될 수 있다. 본 실시예에서 사용되는 서브 S-box의 개수(K)는 1이상이되, 영지식 증명에 기반한 전자서명의 크기가 임계치보다 커지지 않도록 서브 S-box의 최대 제한 개수가 미리 설정될 수 있다.

기존의 블록암호를 사용하는 영지식 증명에서는, 낮은 차수를 갖는 여러 개의 소형 S-box가 사용되고 테이블 참조 방식으로 S-box 연산이 수행되지만, 본 실시예와 같이 높은 차수의 대형 S-box가 사용되는 경우, S-box 연산은 테이블 참조 방식이 아닌 유한체 상에서의 다항 연산 방식으로 구현될 수 있다.

일 실시예로서, 동작 S122에서 사용되는 서브 S-box는 아래의 [수학식 1]과 같이 유한체 상에서의 다항 연산을 수행하는 비선형 함수로 정의될 수 있다. 이때, 다항 연산을 수행 시 암호학적으로 성질이 안전한 역연산(inverse operation)이 사용될 수 있다.

[수학식 1]

상기와 같이 동작 S122에서, 분할된 K개의 비트열 각각이 서브 S-box에 입력되면, 서브 S-box에 의한 다항 연산을 통해 길이가 M인 제2 중간 비트열이 출력될 수 있다.

다음으로, 동작 S13에서, 컴퓨팅 장치(100)는 제2 중간 비트열을 축소 행렬에 입력하여 일방향 함수의 출력 비트열을 출력한다.

일 실시예로서, 동작 S12에서 S-box 연산을 통해 산출된 제2 중간 비트열의 길이가 M((단, M은 자연수이면서 N의 배수)이고, 축소 행렬이 NxM 크기를 가지는 바이너리(binary) 행렬로 구현되는 경우, 축소 행렬에 입력되는 제2 중간 비트열의 길이(M)가 축소되어 길이가 N인 출력 비트열이 출력될 수 있다.

이때, 일방향 함수의 출력 비트열의 길이는 동작 S11에서 입력된 일방향 함수의 입력 비트열과 동일한 길이(N)를 가지도록 설정될 수 있다. 일방향 함수의 출력 비트열의 길이를 입력 비트열의 길이보다 크게 설정하는 것도 가능하긴 하나, 이 경우 대수적 공격에 대한 안전성은 더 높아지지만 S-box 연산의 개수가 늘어나게 되므로 서명의 크기를 크게 줄이지 못하게 된다. 따라서, 대수적 공격에 대한 안전성을 확보하고 서명의 크기를 줄이기 위해, 일방향 함수의 입력 비트열과 출력 비트열의 길이를 동일하게 설정하도록 한다.

상기와 같이 동작 S11 내지 동작 S13을 수행함에 의해 블록암호의 형태가 아닌 영지식 증명 친화적인 일방향 함수를 단일 라운드로 구성할 수 있다.

상기와 같은 본 개시의 실시예에 따른 방법에 의하면, 영지식 증명 친화적인 일방향 함수를 구성함에 의해, 대수적 공격에 대한 안전성을 보장하면서도 비선형 연산을 수행하는 S-box의 개수를 최소화하여 전자서명의 서명 크기를 획기적으로 줄일 수 있다. 이로부터, 영지식 증명 기반 전자서명을 수행 시 발생되는 네트워크 전송 비용 또한 절감할 수 있다.

도 3은 본 개시의 몇몇 실시예에 따른 영지식 증명 친화적인 일방향 함수를 구성하는 전체 프로세스를 도시한 예이다. 도 3에 도시된 전체 프로세스의 각 단계는 도 1에서 설명한 동작 S11 내지 동작 S13에 대응하는 것으로 구체적인 실시예를 통해 설명하기로 한다. 도 3의 전체 프로세스의 각 단계에서 계산을 위해 사용되는 산출식은 도 4를 참조할 수 있다.

먼저, 컴퓨팅 장치(100)는 영지식 증명 친화적인 일방향 함수를 구성하기 위해, 아래와 같이 몇몇의 파라미터 및 행렬을 사전에 설정할 수 있다.

: 일방향 함수의 입출력 비트열의 길이

확장된 제1 중간 비트열의 길이로, 의 배수

: S-box의 입출력 비트열의 길이로, 의 약수

: x 의 binary 행렬

여기서, 파라미터 은 전자서명의 서명 크기를 최소로 하면서도 대수적 공격에 대한 안전성을 보장하도록 최적의 값으로 설정될 수 있다. 예로서, 은 의 2배수로 설정되고, 은 최대16 이하로 설정될 수 있다.

컴퓨팅 장치(100)는 길이가 인 일방향 함수의 입력 비트열(31)을 확장 행렬()(32)에 입력하여 길이가 인 제1 중간 비트열(state1)(33)을 계산할 수 있다.

다음으로, 컴퓨팅 장치(100)는 제1 중간 비트열(state1)(33)을 개의 길이가 인 비트열로 분할(331)하고, 분할된 각각의 비트열()을 개의 서브 S-box(341, 342, 343, 344)에 입력하여 길이가 인 제2 중간 비트열(state 2)(35)을 계산할 수 있다. 이때, 각 서브 S-box(341, 342, 343, 344)는 유한체 상에서의 다항 연산을 수행하는 비선형 함수일 수 있다.

마지막으로, 컴퓨팅 장치(100)는 길이가 인 제2 중간 비트열(state 2)(35)을 축소 행렬()(36)에 입력하여 길이가 인 일방향 함수의 출력 비트열(37)을 계산할 수 있다.

예를 들어, 컴퓨팅 장치(100)는 양자 컴퓨터를 이용한 공격에 대해 안전성을 확보할 수 있도록 파라미터의 값을 와 같이 설정할 수 있다. 이 경우, 컴퓨팅 장치(100)는 길이가 128인 입력 비트열을 입력하여 길이가 128인 출력 비트열이 출력되도록 하는 일방향 함수를 구성할 수 있다. 이때, 컴퓨팅 장치(100)는 일방향 함수를 구성하기 위해, 입출력 비트열의 길이가 64()인 4개의 서브 S-box(341, 342, 343, 344)을 사용할 수 있다.

상기 실시예에 의하면, 높은 차수를 가지는 대형 S-box를 최소 개수만큼 사용하여 비선형 연산의 개수를 줄임에 의해 전자서명의 서명 크기를 줄이는 효과를 제공할 수 있다.

도 5는 본 개시의 몇몇 실시예에 따른 확장 행렬을 생성하는 방법을 설명하기 위한 순서도이다. 도 5에서는 도1의 동작 S11 내지 동작 S13을 수행하기 위해 사전에 확장 행렬을 생성하는 동작의 흐름을 설명하도록 한다.

도 5를 참조하면, 도 1의 동작 S11은 확장 행렬을 생성하는 동작 S111 및 동작 S112를 포함할 수 있다. 즉, 일방향 함수의 입력 비트열을 확장 행렬에 입력하여 입력 비트열보다 길이가 더 큰 제1 중간 비트열을 산출하기 위해, 확장 행렬을 미리 생성할 수 있다.

일 실시예로서, 동작 S111에서, 확장 행렬의 제1 번째 행 또는 제1 번째 열을 랜덤 값으로 구성하고, 동작 S112에서, 제1 번째 행 또는 제1 번째 열에 대한 순환 시프트(circular shift)를 통해 확장 행렬의 나머지 행 또는 나머지 열을 구성할 수 있다.

예로서, 도 3에서 확장 행렬()(32)을 생성하기 위해, (32)의 1행을 랜덤 값으로 구성하고, (32)의 i번째 행을 (i-1)번째 행을 오른쪽으로 한 칸 이동시킨 벡터로 구성할 수 있다(단, 2≤i≤m). 즉, (32)의 2행부터 m행까지는 바로 이전의 행을 오른쪽으로 이동시키는 방식을 순차적으로 적용하여, 결과적으로 값들이 순환 시프트(circular shift)되는 형태의 행렬을 구성할 수 있다.

도 6은 본 개시의 몇몇 실시예에 따른 축소 행렬을 생성하는 방법을 설명하기 위한 순서도이다. 도 6에서는 도1의 동작 S11 내지 동작 S13을 수행하기 위해 사전에 축소 행렬을 생성하는 동작의 흐름을 설명하도록 한다.

도 6을 참조하면, 도 1의 동작 S13은 축소 행렬을 생성하는 동작 S131 및 동작 S132를 포함할 수 있다. 즉, S-box 로부터 산출된 제2 중간 비트열을 축소 행렬에 입력하여 제2 중간 비트열보다 길이가 더 작은 일방향 함수의 출력 비트열을 출력하기 위해, 축소 행렬을 미리 생성할 수 있다.

일 실시예로서, 동작 S131에서, 축소 행렬의 제1 번째 행 또는 제1 번째 열을 랜덤 값으로 구성하고, 동작 S132에서, 제1 번째 행 또는 제1 번째 열에 대한 순환 시프트(circular shift)를 통해 축소 행렬의 나머지 행 또는 나머지 열을 구성할 수 있다.

예로서, 도 3에서 축소 행렬()(36)을 생성하기 위해, (36)의 1열을 랜덤 값으로 구성하고, (36)의 i번째 열을 (i-1)번째 열을 아래쪽으로 한 칸 이동시킨 벡터로 구성할 수 있다(단, 2≤i≤m). 즉, (36)의 2열부터 m열까지는 바로 이전의 열을 아래쪽으로 이동시키는 방식을 순차적으로 적용하여, 결과적으로 값들이 순환 시프트(circular shift)되는 형태의 행렬을 구성할 수 있다. 이와 같이 순환 시프트를 통해 행렬을 구성하는 방식은 입력되는 정보량이 출력 시 그대로 유지되도록 하는 효과를 제공할 수 있다.

상기와 같이 도 5 및 도 6에서는 확장 행렬 및 축소 행렬을 생성하기 위해, 1행 또는 1열을 랜덤 값으로 구성하고 나머지 행 또는 열을 순환 시프트를 통해 구성하는 방식을 설명하였으나, 이러한 방식에 한정되는 것은 아니다.

일 실시예로서, 확장 행렬 및 축소 행렬을 생성 시, 전체 행 또는 전체 열을 랜덤 값으로 구성하는 방식을 적용할 수도 있다.

도 7은 본 개시의 몇몇 실시예에 따른 전자서명을 수행하는 방법을 설명하기 위한 순서도이다. 도 7을 참조하면, 도1에서 동작 S11 내지 동작 S13을 수행하여 영지식 증명 친화적인 일방향 함수가 구성되면, 이를 이용하여 전자서명을 수행하는 동작 S14이 추가적으로 수행될 수 있다.

일 실시예로서, 동작 S14에서, 컴퓨팅 장치(100)는 일방향 함수의 입력 비트열과 출력 비트열을 이용하여 영지식 증명 기반의 전자서명을 수행할 수 있다.

이때, 동작 S14는, 입력 비트열과 출력 비트열을 각각 전자서명의 비밀키와 공개키로 설정하는 동작 S141, 및 비밀키와 공개키를 영지식 증명을 위한 증명(prove) 함수에 입력하여, 전자서명을 위한 서명 데이터를 생성하는 동작 S142를 포함할 수 있다.

일 실시예로서, 도 8을 참조하면, 일방향 함수의 입력 비트열과 출력 비트열을 이용하여 영지식 증명 기반의 전자서명을 수행하기 위해, 세 가지 알고리즘이 순차적으로 수행될 수 있다. 전자 서명의 세 가지 알고리즘은 예컨대, 키 생성 파트(82), 서명 생성 파트(83), 및 키 검증 파트(84)로 구성될 수 있다.

예로서, 길이가 n인 입력 비트열(x)을 입력하여 길이가 n인 출력 비트열(y)을 출력하도록 하는 영지식 증명 친화적인 일방향 함수 F(x)가 구성되면, 집합 L(y, x)(81)에 대하여 키 생성 파트(82), 서명 생성 파트(83), 및 키 검증 파트(84)가 순차적으로 수행될 수 있다.

먼저, 키 생성 파트(82)에서, 컴퓨팅 장치(100)는 안전성 파라미터 에 대해 길이가 n인 랜덤 값을 입력 비트열(x)로 생성하고, 이를 이용하여 전자 서명의 비밀키(sk)와 공개키(pk)를 설정할 수 있다. 이때, 입력 비트열(x)이 전자 서명의 비밀키(sk)로 설정되고, 일방향 함수의 출력 비트열(y=F(x))이 전자 서명의 공개키(pk)로 설정될 수 있다.

다음으로, 서명 생성 파트(83)에서, 컴퓨팅 장치(100)는 앞서 키 생성 파트(82)에서 설정된 비밀키(sk)와 공개키(pk)를 메시지(m)과 함께 영지식 증명을 위한 증명 함수(ZK.Prove)에 입력하여, 전자 서명을 위한 서명 데이터()를 생성할 수 있다.

마직막으로, 키 검증 파트(84)에서, 컴퓨팅 장치(100)는 앞서 서명 생성 파트(83)에서 생성된 서명 데이터()와 공개키(pk)를 영지식 검증을 위한 검증 함수(ZK.Verify)에 입력하여 검증 결과값을 출력할 수 있다. 이때, 검증 결과값은 0 또는 1로 출력되고, 검증 결과값이 1인 경우 검증자(Verifier)가 비밀키(sk)를 모른 상태에서 서명을 생성하는데 성공했음을 의미한다.

상기와 같은 본 개시의 실시예에 의하면, 영지식 증명 기반 전자 서명을 생성함에 있어, 영지식 증명 친화적인 일방향 함수를 구성함에 의해 대수적 공격에 대해 안전하면서도 서명 크기를 획기적으로 줄이는 효과를 제공할 수 있다.

도 9는 본 발명의 몇몇 실시예에 따른 방법들을 구현할 수 있는 예시적인 컴퓨팅 장치의 하드웨어 구성도이다. 도 9에 도시된 바와 같이, 컴퓨팅 장치(100)는 하나 이상의 프로세서(101), 버스(107), 네트워크 인터페이스(102), 프로세서(101)에 의하여 수행되는 컴퓨터 프로그램(105)을 로드(load)하는 메모리(103)와, 컴퓨터 프로그램(105)를 저장하는 스토리지(104)를 포함할 수 있다. 다만, 도 9에는 본 발명의 실시예와 관련 있는 구성요소들 만이 도시되어 있다. 따라서, 본 발명이 속한 기술분야의 통상의 기술자라면 도 9에 도시된 구성요소들 외에 다른 범용적인 구성 요소들이 더 포함될 수 있음을 알 수 있다.

프로세서(101)는 컴퓨팅 장치(100)의 각 구성의 전반적인 동작을 제어한다. 프로세서(101)는 CPU(Central Processing Unit), MPU(Micro Processor Unit), MCU(Micro Controller Unit), GPU(Graphic Processing Unit) 또는 본 발명의 기술 분야에 잘 알려진 임의의 형태의 프로세서 중 적어도 하나를 포함하여 구성될 수 있다. 또한, 프로세서(101)는 본 발명의 다양한 실시예들에 따른 방법/동작을 실행하기 위한 적어도 하나의 애플리케이션 또는 프로그램에 대한 연산을 수행할 수 있다. 컴퓨팅 장치(100)는 하나 이상의 프로세서를 구비할 수 있다.

메모리(103)는 각종 데이터, 명령 및/또는 정보를 저장한다. 메모리(103)는 본 발명의 다양한 실시예들에 따른 방법/동작들을 실행하기 위하여 스토리지(104)로부터 하나 이상의 프로그램(105)을 로드(load) 할 수 있다. 예를 들어, 컴퓨터 프로그램(105)이 메모리(103)에 로드 되면, 로직(또는 모듈)이 메모리(103) 상에 구현될 수 있다. 메모리(103)의 예시는 RAM이 될 수 있으나, 이에 한정되는 것은 아니다.

버스(107)는 컴퓨팅 장치(100)의 구성 요소 간 통신 기능을 제공한다. 버스(107)는 주소 버스(Address Bus), 데이터 버스(Data Bus) 및 제어 버스(Control Bus) 등 다양한 형태의 버스로 구현될 수 있다.

네트워크 인터페이스(102)는 컴퓨팅 장치(100)의 유무선 인터넷 통신을 지원한다. 네트워크 인터페이스(102)는 인터넷 통신 외의 다양한 통신 방식을 지원할 수도 있다. 이를 위해, 네트워크 인터페이스(102)는 본 발명의 기술 분야에 잘 알려진 통신 모듈을 포함하여 구성될 수 있다.

스토리지(104)는 하나 이상의 컴퓨터 프로그램(105)을 비임시적으로 저장할 수 있다. 스토리지(104)는 플래시 메모리 등과 같은 비휘발성 메모리, 하드 디스크, 착탈형 디스크, 또는 본 발명이 속하는 기술 분야에서 잘 알려진 임의의 형태의 컴퓨터로 읽을 수 있는 기록 매체를 포함하여 구성될 수 있다.

컴퓨터 프로그램(105)은 본 발명의 다양한 실시예들에 따른 방법/동작들이 구현된 하나 이상의 인스트럭션들(instructions)을 포함할 수 있다. 컴퓨터 프로그램(105)이 메모리(103)에 로드 되면, 프로세서(101)는 상기 하나 이상의 인스트럭션들을 실행시킴으로써 본 발명의 다양한 실시예들에 따른 방법/동작들을 수행할 수 있다.

일 실시예로서, 컴퓨터 프로그램(105)는, 일방향 함수의 입력 비트열을 확장 행렬에 입력하여 제1 중간 비트열을 산출하는 동작, 상기 제1 중간 비트열을 소정 개수의 비트열로 분할하고, 상기 분할된 소정 개수의 비트열 각각을 S-box(Substitution-box)에 입력하여 제2 중간 비트열을 산출하는 동작, 및 상기 제2 중간 비트열을 축소 행렬에 입력하여 상기 일방향 함수의 출력 비트열을 출력하는 동작을 수행하기 위한 인스트럭션을 포함할 수 있다.

지금까지 도 1 내지 도 9를 참조하여 본 발명의 다양한 실시예들 및 그 실시예들에 따른 효과들을 언급하였다. 본 발명의 기술적 사상에 따른 효과들은 이상에서 언급한 효과들로 제한되지 않으며, 언급되지 않은 또 다른 효과들은 아래의 기재로부터 통상의 기술자에게 명확하게 이해될 수 있을 것이다.

지금까지 설명된 본 발명의 기술적 사상은 컴퓨터가 읽을 수 있는 매체 상에 컴퓨터가 읽을 수 있는 코드로 구현될 수 있다. 상기 컴퓨터로 읽을 수 있는 기록 매체는, 예를 들어 이동형 기록 매체(CD, DVD, 블루레이 디스크, USB 저장 장치, 이동식 하드 디스크)이거나, 고정식 기록 매체(ROM, RAM, 컴퓨터 구비 형 하드 디스크)일 수 있다. 상기 컴퓨터로 읽을 수 있는 기록 매체에 기록된 상기 컴퓨터 프로그램은 인터넷 등의 네트워크를 통하여 다른 컴퓨팅 장치에 전송되어 상기 다른 컴퓨팅 장치에 설치될 수 있고, 이로써 상기 다른 컴퓨팅 장치에서 사용될 수 있다.

이상에서, 본 발명의 실시예를 구성하는 모든 구성 요소들이 하나로 결합되거나 결합되어 동작하는 것으로 설명되었다고 해서, 본 발명의 기술적 사상이 반드시 이러한 실시예에 한정되는 것은 아니다. 즉, 본 발명의 목적 범위 안에서라면, 그 모든 구성요소들이 하나 이상으로 선택적으로 결합하여 동작할 수도 있다.

도면에서 동작들이 특정한 순서로 도시되어 있지만, 반드시 동작들이 도시된 특정한 순서로 또는 순차적 순서로 실행되어야만 하거나 또는 모든 도시 된 동작들이 실행되어야만 원하는 결과를 얻을 수 있는 것으로 이해되어서는 안 된다. 특정 상황에서는, 멀티태스킹 및 병렬 처리가 유리할 수도 있다. 더욱이, 위에 설명한 실시예들에서 다양한 구성들의 분리는 그러한 분리가 반드시 필요한 것으로 이해되어서는 안 되고, 설명된 프로그램 컴포넌트들 및 시스템들은 일반적으로 단일 소프트웨어 제품으로 함께 통합되거나 다수의 소프트웨어 제품으로 패키지 될 수 있음을 이해하여야 한다.

이상 첨부된 도면을 참조하여 본 발명의 실시예들을 설명하였지만, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자는 그 기술적 사상이나 필수적인 특징을 변경하지 않고서 본 발명이 다른 구체적인 형태로도 실시될 수 있다는 것을 이해할 수 있다. 그러므로 이상에서 기술한 실시예들은 모든 면에서 예시적인 것이며 한정적인 것이 아닌 것으로 이해해야만 한다. 본 발명의 보호 범위는 아래의 청구범위에 의하여 해석되어야 하며, 그와 동등한 범위 내에 있는 모든 기술 사상은 본 발명에 의해 정의되는 기술적 사상의 권리범위에 포함되는 것으로 해석되어야 할 것이다.

Claims

컴퓨팅 장치에 의해 수행되는 방법에 있어서,
일방향 함수의 입력 비트열을 확장 행렬에 입력하여 제1 중간 비트열을 산출하는 단계;
상기 제1 중간 비트열을 소정 개수의 비트열로 분할하고, 상기 분할된 소정 개수의 비트열 각각을 S-box(Substitution-box)에 입력하여 제2 중간 비트열을 산출하는 단계; 및
상기 제2 중간 비트열을 축소 행렬에 입력하여 상기 일방향 함수의 출력 비트열을 출력하는 단계를 포함하는,
영지식 증명 친화적인 일방향 함수를 이용한 연산 방법.
제1 항에 있어서,
상기 일방향 함수의 입력 비트열 및 출력 비트열의 길이는 N(단, N은 자연수)이고,
상기 제1 중간 비트열 및 상기 제2 중간 비트열의 길이는 M(단, M은 자연수)이되, M은 N의 배수이고,
상기 S-box에 입력되는 비트열의 길이는 L(단, L은 자연수)이되, L은 M의 약수인,
영지식 증명 친화적인 일방향 함수를 이용한 연산 방법.
제1 항에 있어서,
상기 S-box는 K개(단, K는 1이상의 자연수)의 서브 S-box를 포함하고,
상기 제2 중간 비트열을 산출하는 단계는,
상기 제1 중간 비트열을 K개의 비트열로 분할하는 단계; 및
상기 분할된 K개의 비트열 각각을 상기 서브 S-box에 입력하는 단계를 포함하는,
영지식 증명 친화적인 일방향 함수를 이용한 연산 방법.
제3 항에 있어서,
상기 서브 S-box는 유한체 상에서의 다항 연산을 수행하는 비선형 함수인,
영지식 증명 친화적인 일방향 함수를 이용한 연산 방법.
제2 항에 있어서,
상기 확장 행렬은 MxN 크기를 가지는 바이너리 행렬이고,
상기 축소 행렬은 NxM 크기를 가지는 바이너리 행렬인,
영지식 증명 친화적인 일방향 함수를 이용한 연산 방법.
제5 항에 있어서,
상기 확장 행렬을 생성하는 단계를 더 포함하고,
상기 확장 행렬을 생성하는 단계는,
상기 확장 행렬의 제1 번째 행 또는 제1 번째 열을 랜덤 값으로 구성하는 단계; 및
상기 제1 번째 행 또는 제1 번째 열에 대한 순환 시프트(circular shift)를 통해 상기 확장 행렬의 나머지 행 또는 나머지 열을 구성하는 단계를 포함하는,
영지식 증명 친화적인 일방향 함수를 이용한 연산 방법.
제5 항에 있어서,
상기 축소 행렬을 생성하는 단계를 더 포함하고,
상기 축소 행렬을 생성하는 단계는,
상기 축소 행렬의 제1 번째 행 또는 제1 번째 열을 랜덤 값으로 구성하는 단계; 및
상기 제1 번째 행 또는 상기 제1 번째 열에 대한 순환 시프트(circular shift)를 통해 상기 축소 행렬의 나머지 행 또는 나머지 열을 구성하는 단계를 포함하는,
영지식 증명 친화적인 일방향 함수를 이용한 연산 방법.
제5 항에 있어서,
상기 확장 행렬 및 상기 축소 행렬의 전체 행 또는 전체 열을 랜덤 값으로 구성하는 단계를 더 포함하는,
영지식 증명 친화적인 일방향 함수를 이용한 연산 방법.
제1 항에 있어서,
상기 일방향 함수는 단일 라운드로 구성되는,
영지식 증명 친화적인 일방향 함수를 이용한 연산 방법.
제1 항에 있어서,
상기 일방향 함수의 상기 입력 비트열과 상기 출력 비트열을 이용하여 영지식 증명 기반의 전자서명을 수행하는 단계를 더 포함하는,
영지식 증명 친화적인 일방향 함수를 이용한 연산 방법.
제10 항에 있어서,
상기 일방향 함수의 상기 입력 비트열과 상기 출력 비트열을 이용하여 영지식 증명 기반의 전자서명을 수행하는 단계는,
상기 입력 비트열과 상기 출력 비트열을 각각 상기 전자서명의 비밀키와 공개키로 설정하는 단계; 및
상기 비밀키와 상기 공개키를 상기 영지식 증명을 위한 증명(prove) 함수에 입력하여, 상기 전자서명을 위한 서명 데이터를 생성하는 단계를 포함하는,
영지식 증명 친화적인 일방향 함수를 이용한 연산 방법.
컴퓨터로 하여금 제1 항 내지 제11 항 중 어느 한 항의 방법을 수행하도록 하는 컴퓨터 프로그램이 저장된,
컴퓨터 판독 가능한 비일시적 기록 매체.
컴퓨팅 장치에 있어서,
하나 이상의 프로세서;
상기 프로세서에 의하여 수행되는 컴퓨터 프로그램을 로드(load)하는 메모리; 및
상기 컴퓨터 프로그램을 저장하는 스토리지를 포함하되,
상기 컴퓨터 프로그램은,
일방향 함수의 입력 비트열을 확장 행렬에 입력하여 제1 중간 비트열을 산출하는 동작,
상기 제1 중간 비트열을 소정 개수의 비트열로 분할하고, 상기 분할된 소정 개수의 비트열 각각을 S-box(Substitution-box)에 입력하여 제2 중간 비트열을 산출하는 동작, 및
상기 제2 중간 비트열을 축소 행렬에 입력하여 상기 일방향 함수의 출력 비트열을 출력하는 동작을 수행하기 위한 인스트럭션을 포함하는,
컴퓨팅 장치.
제13 항에 있어서,
상기 일방향 함수의 입력 비트열 및 출력 비트열의 길이는 N(단, N은 자연수)이고,
상기 제1 중간 비트열 및 상기 제2 중간 비트열의 길이는 M(단, M은 자연수)이되, M은 N의 배수이고,
상기 S-box에 입력되는 비트열의 길이는 L(단, L은 자연수)이되, L은 M의 약수인,
컴퓨팅 장치.
제13 항에 있어서,
상기 S-box는 K개(단, K는 1이상의 자연수)의 서브 S-box를 포함하고,
상기 제2 중간 비트열을 산출하는 동작은,
상기 제1 중간 비트열을 K개의 비트열로 분할하는 동작; 및
상기 분할된 K개의 비트열 각각을 상기 서브 S-box에 입력하는 동작을 포함하는,
컴퓨팅 장치.
제15 항에 있어서,
상기 서브 S-box는 유한체 상에서의 다항 연산을 수행하는 비선형 함수인,
컴퓨팅 장치.
제14 항에 있어서,
상기 확장 행렬은 MxN 크기를 가지는 바이너리 행렬이고,
상기 축소 행렬은 NxM 크기를 가지는 바이너리 행렬인,
영지식 증명 친화적인 일방향 함수를 이용한 연산 방법.
컴퓨팅 장치.
제13 항에 있어서,
상기 컴퓨터 프로그램은,
상기 일방향 함수의 상기 입력 비트열과 상기 출력 비트열을 이용하여 영지식 증명 기반의 전자서명을 수행하는 동작을 수행하기 위한 인스트럭션을 더 포함하고,
상기 영지식 증명 기반의 전자서명을 수행하는 동작은,
상기 입력 비트열과 상기 출력 비트열을 각각 상기 전자서명의 비밀키와 공개키로 설정하는 동작, 및
상기 비밀키와 상기 공개키를 상기 영지식 증명을 위한 증명(prove) 함수에 입력하여, 상기 전자서명을 위한 서명 데이터를 생성하는 동작을 포함하는,
컴퓨팅 장치.