Paper 2017/426

FHPKE based on multivariate discrete logarithm problem

Masahiro Yagisawa

Abstract

Previously I proposed fully homomorphic public-key encryption (FHPKE) based on discrete logarithm problem which is vulnerable to quantum computer attacks. In this paper I propose FHPKE based on multivariate discrete logarithm assumption. This encryption scheme is thought to withstand to quantum computer attacks. Though I can construct this scheme over many non-commutative rings, I will adopt the FHPKE scheme based on the octonion ring as the typical example for showing how this scheme is constructed. The multivariate discrete logarithm problem (MDLP) is defined such that given f(x), g(x), h(x) and a prime q, final goal is to find m0, m1, n0, n1∈Fq* where h(x)=f ^m0(g^n0(x))+f ^m1(g^n1(x)) mod q over octonion ring.

Note: As | h(1)| = |g^(-n)(f^m(g^n(1)))|=|f^m(1)|=α^m mod q, I substitute the public key h(X)= g^(-n)(f^m(g^n(X)))mod q to h(X)= f^m0(g^n0(x))+f^m1(g^n1(x)) mod q where α∈Fq* is a calculable parameter and m0, m1, n0, n1∈Fq* are secret parameters. Then it is difficult to obtain the values of m0, m1, n0, n1 from h(X).