**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

[ Cryptology ePrint archive ]