Hierarchical Identity-Based Signature with Designated Aggregator from Lattices

기술 요약: 격자 기반의 지정된 집합자를 갖는 계층적 식별자 기반 서명

문제 정의
대규모 계층 구조 조직(예: 대학교, 정부 기관, 기업)에서 다양한 수준의 다수 사용자로부터 발생하는 데이터를 인증하는 것은 상당한 과제를 안겨줍니다. 전통적인 공개 키 인프라(PKI)는 인증 기관(CA)에 의존하며, 이는 상당한 관리 오버헤드를 발생시킵니다. 식별자 기반 암호(IBC)는 식별자를 공개 키로 사용하여 인증서 문제를 해결하지만, 표준 식별자 기반 서명(IBS) 방식은 일반적으로 단일한 개인 키 생성기(PKG)에 의존합니다. 이러한 중앙 집중화는 성능 병목 현상과 단일 장애점(single point of failure)을 생성하여, 크고 분산된 계층 구조에는 부적합하게 만듭니다. 또한, 계층 내의 수많은 사용자가 데이터에 서명해야 할 때, 각 사용자의 개별 서명을 저장하고 검증하는 것은 시간, 공간 및 대역폭 측면에서 비효전적입니다. 기존의 계층적 식별자 기반 서명(HIBS) 방식은 종종 수론적 가정(예: 이산 로그 문제)에 의존하여 양자 공격에 취약하거나, 여러 계층의 브랜치로부터 오는 서명을 하나의 압축된 증거로 집합(aggregation)하는 기능이 부족합니다.

방법론
저자들은 양자 내성 보안을 제공하는 격자(Lattices) 상에서 구축된 지정된 집합자를 갖는 계층적 식별자 기반 서명(HIBS-DA) 방식을 제안합니다. 이 방법론은 세 가지 핵심 구성 요소를 통합합니다:

1. 계층적 키 위임: 시스템은 루트 PKG가 $t$개의 레벨까지 키 생성을 위임하는 트리 구조를 활용합니다. 자식 엔티티는 부모의 트랩도어를 노출하지 않으면서 트랩도어 구조를 보존하는 BasisDelegation 알고리즘(BasisDel 구체적 적용)을 사용하여 부모의 비밀 키로부터 자신의 비밀 키를 유도합니다.
2. 격자 기반 암호: 본 방식은 단기 정수 해(Short Integer Solution, SIS) 문제의 어려움에 기반합니다. 이 방식은 공용 행렬과 짧은 트랩도어 기저를 생성하기 위한 TrapGen, 서명(짧은 벡터)을 생성하기 위한 SamplePre, 그리고 가역 행렬을 생성하기 위한 SampleRwithBasis와 같은 알고리즘을 채택합니다.
3. 지정된 집합(Designated Aggregation): 여러 서명의 검증 효율성을 해결하기 위해, 본 방식은 지정된 집합자를 도입합니다. 이 엔티티는 특정 계층 레벨 $k$에 있는 $N$명의 사용자로부터 개별 서명을 수집합니다. **중국인 나머지 정리(CRT)**를 사용하여, 집합자는 이 서명들을 하나의 압축된 집합 서명으로 결합합니다. 핵심 단계는 결과 집합 서명이 짧고 유효하게 유지되도록, 결합된 벡터를 $N$명 사용자와 관련된 격자들의 교집합 위로 투영하는 것입니다.

주요 기여

• 최초의 격자 기반 HIBS-DA 구축: 본 논문은 격자 가정을 기반으로 한 HIBS-DA 방식의 첫 번째 구축 사례임을 주장하며, 기존 문헌의 공백을 메웁니다.
• 형식적 구문 및 보안 모델: 저자들은 Setup, Derive, Sign, Verify, Aggregate, AggregateVerify의 6가지 알고리즘으로 구성된 HIBS-DA 프레임워크를 공식적으로 정의합니다. 또한 **적응적 식별자 및 선택 메시지 공격에 대한 존재적 위조 불가능성(EUF-ID-CMA)**을 기반으로 보안 모델을 설정합니다.
• 보안 증명: 본 방식은 SIS 문제가 계산적으로 불가능하다는 가정하에 안전함이 증명되었습니다. 증명은 환원법(reductionist approach)을 사용하여, 집합 서명을 위조할 수 있는 확률적 다항 시간(PPT) 공격자가 있다면 SIS 문제를 해결할 수 있음을 보여줍니다.
• 효율성 분석: 본 논문은 포괄적인 복잡도 분석을 제공하여, 본 방식이 비대화형(zero round complexity)이며 개별 서명을 검증하는 것에 비해 통신 및 검증 비용을 크게 줄여줌을 입증합니다.

결과

• 정확성: 본 방식은 개별 서명이 유효함을 보장하며, 집합된 서명이 특정 계층 레벨의 모든 하위 메시지와 식별자를 정확하게 인증함을 보장합니다.
• 보안성: 본 구축은 다양한 식별자와 메시지에 대한 키 추출 및 서명 오라클에 접근할 수 있는 공격자로부터도 위조를 방어하는 EUF-ID-CMA 보안을 달성합니다.
• 복잡도 지표:
  • 통신: 총 통신 복잡도는 약 $O((tm^2 + Nm)\lceil \log_2 q \rceil)$ 비트이며, 여기서 $t$는 계층 깊이, $N$은 서명자 수, $m, n, q$는 격자 파라미터입니다. 이는 $N$개의 개별 서명을 전송하는 것과 비교하여 상당한 감소를 나타냅니다.
  • 연산: Setup 단계의 복잡도는 $\tilde{O}(n^2)$이고, Derive는 $\tilde{O}(k \cdot m^3)$이며, Sign과 Verify는 각각 $\tilde{O}(m^2)$ 및 $O(m^2)$입니다. Aggregate는 CRT를 위한 $O(Nm)$과 샘플링을 위한$\tilde{O}(m^2)$를 포함합니다. AggregateVerify는 $O(Nm^2)$를 요구합니다.
  • 라운드 복잡도: 본 방식은 비대화형으로, 핵심 서명 및 집합 과정에서 제로 라운드의 통신을 요구합니다.

의의
본 논문은 HIBS-DA를 구조화된 다중 소스 데이터 인증이 필요한 현대의 대규모 분산 시스템을 위한 실질적인 솔루션으로 포지셔닝합니다. 계층적 키 관리와 서명 집합을 결리함으로써, 본 방식은 기존 IBS의 확장성 문제와 PKI의 인증서 오버헤드를 해결합니다. 결정적으로, 격자에 기반한 구축을 통해 본 방식은 양자 내성 보안을 제공하여 e-거버넌스, 보안 데이터 공유, 기업 경영과 같은 분야의 미래 핵심 인프라를 보호하기에 적합합니다. 저자들은 본 방식이 단 하나의 압축된 서명을 사용하여 계층의 여러 브랜치로부터 오는 문서들을 효율적으로 인증할 수 있게 함으로써, 계산 및 통신 오버헤드를 최소화한다고 강조합니다.