### 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.

Note: I revised expression (20).

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
key agreement protocolmultivariate polynomialsGröbner basesNP complete problemsfinite field
Contact author(s)
tfktyagi2 @ c3-net ne jp
History
2010-10-24: last of 2 revisions
See all versions
Short URL
https://ia.cr/2010/516

CC BY

BibTeX

@misc{cryptoeprint:2010/516,
author = {Masahiro Yagisawa},
title = {Key Agreement Protocols Based on Multivariate Polynomials over Fq},
howpublished = {Cryptology ePrint Archive, Paper 2010/516},
year = {2010},
note = {\url{https://eprint.iacr.org/2010/516}},
url = {https://eprint.iacr.org/2010/516}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.