**Key Agreement Protocols Based on Multivariate Polynomials over Fq**

*Masahiro Yagisawa*

**Abstract: **In this paper we propose new key agreement protocols based on multivariate polynomials over finite field Fq. We concretely generate the multivariate polynomial F(X)\in Fq[x1,..,xn] such that F(X)=\sum^m_{i=1} ki[Ai(X)^d+ Ai(X)^{d-1}+ ..+ Ai(X)] where Ai(X) =ai1x1+…+ainxn ,coefficients ki , aij\in Fq (i=1,..,m:j=1,..,n) and variables X=(x1,..,xn)^T \in Fq[x1,..,xn]^n. The common key K(X) has the form such that K(X)=\sum^m_{i=1}hi F((bi1x1,...,binxn)^T) where hi ,bij\in Fq (i=1,..,m:j=1,..,n) to be the temporary secret keys of the partner . Our system is immune from the Gröbner bases attacks because obtaining coefficients of F(X) to be secret keys arrives at solving the multivariate algebraic equations, that is, one of NP complete problems .Our protocols are also thought to be immune from the differential attacks because of the equations of high degree.

**Category / Keywords: **public-key cryptography / key agreement protocol, multivariate polynomials, Gröbner bases, NP complete problems, finite field

**Date: **received 7 Oct 2010, last revised 24 Oct 2010

**Contact author: **tfktyagi2 at c3-net ne jp

**Available format(s): **PDF | BibTeX Citation

**Note: **I revised expression (20).

**Version: **20101024:072856 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]