Forward Secure Signature Schemes Supporting Multi-user Aggregation

Abstract

As a solution to mitigate the key exposure problems in the digital signature, the forward security has been proposed. The forward security guarantees the integrity of the messages generated in the past despite leaks of a current time period secret key by evolving a secret key on each time period. However, there is no forward secure signature scheme whose all metrics have constant complexities. Furthermore, existing works do not support flexible multi-user aggregation of signatures. In this paper, we propose a forward secure multi-aggregate signature scheme utilizing recursive zk-SNARKs (zero-knowledge Succinct Non-interactive ARguments of Knowledge), whose all metrics including size and time have $O(1)$. The proposed forward secure signature scheme can aggregate signatures generated by not only a single user but also multiple users flexibly. The security of the proposed scheme is formally proven under zero-knowledge assumption and random oracle model.|전자서명의 키 유출로 인한 문제를 완화하기 위해 전방향 안전서명이 제안되었다. 전방향 안전성은 비밀키를 각 시간 주기마다 갱신하면서 현재시점의 서명키 유출에도 과거에 생성된 메세지에 대한 무결성을 보장한다. 그러나, 현재까지 모든 알고리즘이 시간주기와 무관한 복잡도를 가지는 서명 방법은 존재하지 않는다. 게다가, 기존의 연구들은 유연한 다중사용자 서명의 집계를 지원하지 않는다. 따라서 본 논문에서는 재귀 zk-SNARKs(zero-knowledge Succinct Non-interactive ARguments of Knowledge)를 활용하여 모든 알고리즘이 $O(1)$ 시간복잡도 및 공간복잡도를 가지는 다중 집계 전방향 안전서명을 제안한다. 제안하는 전방향 안전서명 방법은 단일 사용자 뿐만 아니라 다중 사용자의 서명들을 유연하게 집계할 수 있다. 또한 위 방법론의 안전성은 영지식 증명 가정 및 랜덤 오라클 가정 하에서 증명되었다.