Cryptology ePrint Archive: Report 2010/075

A New Scheme for Zero Knowledge Proof based on Multivariate Quadratic Problem and Quaternion Algebra

Mehdi Vasef

Abstract: This paper introduces a new intractable security problem whose intractability is due to the NP completeness of multivariate quadratic problem. This novel problem uses quaternion algebra in conjunction with MQ. Starting with the simultaneous multivariate equations, we transform these equations into simultaneous quaternion based multivariate quadratic equations. A new scheme for computational zero knowledge proof based on this problem is proposed. It is proved that according to black box definition of zero knowledge proof (ZKP) system, the proposed scheme is ZKP. Our proof has two lemmas. The proof is done through two lemmas. In the first lemma it is shown that expected polynomial time machine V * M halts in a polynomial time. In the second lemma, it is showed that the probability ensembles V x L M x * and x L P x , V * x are polynomially indistinguishable. The scheme has low computational overhead and is particularly useful in cryptographic applications such as digital signature and key agreement.

Category / Keywords: public-key cryptography / zero knowledge

Date: received 10 Feb 2010

Contact author: mehdivasef at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20100216:092644 (All versions of this report)

Short URL: ia.cr/2010/075

Discussion forum: Show discussion | Start new discussion