A New Identification Scheme based on Syndrome Decoding Problem with Provable Security against Quantum Adversaries

Abstract

Recently, in order to guarantee security against quantum adversaries, several identification (ID) schemes based on computational problems which are supposed to be hard even for quantum computers have been proposed. However, their security are only proven against non-quantum adversaries. In this paper, we proposed a novel four-pass code-based identification scheme. By using quantum random oracle model, we provide a security proof for our scheme against quantum adversaries which aim to impersonate the prover under concurrent active attacks, based on the hardness assumption of syndrome decoding (SD) problem. Our security proof is interesting in its own right, since it only requires a non-programmable quantum random oracle, in contrast to existing security proofs of digital signatures generated from ID scheme via Fiat-Shamir transform which require programmable quantum random oracles.

Keywords

• identification scheme
• post-quantum
• quantum rando