Paper 2015/733

Fully Homomorphic Encryption on Octonion Ring

Masahiro Yagisawa

Abstract

In previous work(2015/474 in Cryptology ePrint Archive), I proposed a fully homomorphic encryption without bootstrapping which has the weak point in the enciphering function. In this paper I propose the improved fully homomorphic encryption scheme on non-associative octonion ring over finite field without bootstrapping technique. I improve the previous scheme by (1) adopting the enciphering function such that it is difficult to express simply by using the matrices and (2) constructing the composition of the plaintext p with two sub-plaintexts u and v. The improved scheme is immune from the “p and -p attack”. The improved scheme is based on multivariate algebraic equations with high degree or too many variables while the almost all multivariate cryptosystems proposed until now are based on the quadratic equations avoiding the explosion of the coefficients. The improved scheme is against the Gröbner basis attack. The key size of this scheme and complexity for enciphering /deciphering become to be small enough to handle.

Note: In previous report 2015/474 in Cryptology ePrint Archive, I proposed “fully homomorphic encryption without bootstrapping” which has the weak point in the enciphering function and is not immune from “p and -p attack”. In this report I propose the improved scheme which overcomes the weak point.