Recently, several key reuse attacks against Ding Key Exchange, NewHope and other lattice-based key exchange schemes using Peikert's key reconciliation mechanism were suggested. But all known key reuse attacks are designed for two-party setting instead of group key exchange. On the other hand, all previous known lattice-based group key exchanges are designed for static setting.
This paper is organized in three folds.
We present the first key reuse attack called {one, two}-neighbour attack against lattice-based group key exchanges, namely Ding $et$ $al$.'s group key exchange scheme in 2012 and Apon $et$ $al$.'s group key exchange scheme from PQCrypto 2019.
We consider that the adversary manipulates {one or two} neighbour parties $P_{N-2}$ (and $P_{N-3}$ for two-neighbour attack) of the last party $P_{N-1}$ to recover the secret key of the last party $P_{N-1}$ among $N$ parties.
We also suggest several constructions of dynamic group key exchange protocols that could be instantiated by lattice.
As a countermeasure of our attack, we design the first key-reusable group key exchange based on {lattice}. where GKE protocol $\Pi_\textsf{GKE}$ is {key-reusable} if the protocol participants of $\Pi_\textsf{GKE}$ can re-use their public key.
By adopting existing pasteurization technique for two-party key exchange from lattice, our protocol becomes resistant to known key reuse attacks. We give a rigorous proof of our protocol in the random oracle model. Our underlying dynamic group key exchange protocol is the modification of Dutta-Barua protocol in RLWE setting.
최근 키 재사용 공격에 의해 Ding Key Exchange, NewHope 뿐 아니라 Peikert의 키 조정 메커니즘을 이용한 래티스 기반 키 교환 방식에 대한 다양한 공격 논문이 제안되었다. 그러나 기존의 키 재사용 공격의 경우 양자간 키 교환 방식에 대한 공격만을 고려하여 그룹 키 교환 프로토콜에 대해서는 같은 가정으로 적용하기가 어려운 단점이 있다. 한편, 기존의 래티스 기반 그룹 키 교환 방식은 정적 환경에서 제안되었으며 동적 환경을 고려하지 않았다.
본 논문에서는 기존 래티스 기반 그룹 키 교환 방식에 대한 새로운 키 재사용 공격 방식인 {one, two}-neighbour 공격에 대해서 소개하고 2012년 Ding 등이 제안한 그룹 키 교환 방식, 2019년 Apon 등이 제안한 그룹 키 교환 방식이 이러한 키 재사용 공격으로 공격 가능하다는 것을 제시하였다. 이 때 공격자는 파티 $P_{N-1}$의 비밀키를 얻기 위해 파티 $P_{N-2}$과 $P_{N-3}$을 조작 가능하다고 가정한다.
또한 본 논문에서는 래티스 연산에서도 동적 환경에서 그룹 간의 키 교환이 가능한 다양한 그룹 키 교환 방식 설계 모델을 제시 및 구현하였으며, 키 재사용 공격에 대한 대응책으로 Pasteurization 기법을 이용하여 각 참여자의 공개키를 다시 랜덤화 시켜서 키 재사용이 가능한 동적 그룹 키 교환 방식의 설계를 Dutta-Barua 프로토콜을 이용하여 동적 환경에서 RLWE 문제를 기반으로 설계 및 랜덤 오라클 모델 상에서 증명하였다.
