Reviving Identification Scheme Based on Isomorphism of Polynomials with Two Secrets: a Refined Theoretical and Practical Analysis


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A    No.5    pp.787-798
Publication Date: 2018/05/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.787
Type of Manuscript: PAPER
Category: Cryptography and Information Security
post-quantum cryptography,  Isomorphism of Polynomials,  multivariate cryptography,  identification scheme,  zero knowledge proof,  

Full Text: PDF(628.6KB)>>
Buy this Article

The isomorphism of polynomials with two secret (IP2S) problem is one candidate of computational assumptions for post-quantum cryptography. The idea of identification scheme based on IP2S is firstly introduced in 1996 by Patarin. However, the scheme was not described concretely enough and no more details are provided on how to transcribe the idea into a real-world implementation. Moreover, the security of the scheme has not been formally proven and the originally proposed security parameters are no longer secure based on the most recent research. In this paper, we propose a concrete identification scheme based on IP2S with the idea of Patarin as the starting point. We provide formal security proof of the proposed scheme against impersonation under passive attack, sequential active attack, and concurrent active attack. We also propose techniques to reduce the implementation cost such that we are able to cut the storage cost and average communication cost to an extent that under parameters for the standard 80-bit security, the scheme is implementable even on the lightweight devices in the current market.