Towards Constructing Fully Homomorphic Encryption without Ciphertext Noise from Group Theory

Koji Nuida

Paper 2014/097

Towards Constructing Fully Homomorphic Encryption without Ciphertext Noise from Group Theory

Koji Nuida

Abstract

In CRYPTO 2008, one year earlier than Gentry's pioneering \lq\lq bootstrapping'' technique on constructing the first fully homomorphic encryption (FHE) scheme, Ostrovsky and Skeith III had suggested a completely different approach towards achieving FHE. Namely, they showed that the $\mathsf{NAND}$ operator can be realized in some \emph{non-commutative} groups; consequently, in combination with the $\mathsf{NAND}$ operator realized in such a group, homomorphically encrypting the elements of the group will yield an FHE scheme. However, no observations on how to homomorphically encrypt the group elements were presented in their paper, and there have been no follow-up studies in the literature based on their approach. The aim of this paper is to exhibit more clearly what is sufficient and what seems to be effective for constructing FHE schemes based on their approach. First, we prove that it is sufficient to find a surjective homomorphism $\pi \colon \widetilde{G} \to G$ between finite groups for which bit operators are realized in $G$ and the elements of the kernel of $\pi$ are indistinguishable from the general elements of $\widetilde{G}$. Secondly, we propose new methodologies to realize bit operators in some groups, which enlarges the possibility of the group $G$ to be used in our framework. Thirdly, we give an observation that a naive approach using matrix groups would never yield secure FHE due to an attack utilizing the \lq\lq linearity'' of the construction. Then we propose an idea to avoid such \lq\lq linearity'' by using combinatorial group theory, and give a prototypical but still \emph{incomplete} construction in the sense that it is \lq\lq non-compact'' FHE, i.e., the ciphertext size is unbounded (though the ciphertexts are noise-free as opposed to the existing FHE schemes). Completely realizing FHE schemes based on our proposed framework is left as a future research topic.

Note: Update of the content, including a new (but still incomplete) idea towards instantiating the proposed framework

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Minor revision. International Symposium on Mathematics, Quantum Theory, and Cryptography, Mathematics for Industry book series vol.33, Springer, pp.57-78
DOI: 10.1007/978-981-15-5191-8_8
Keywords: public-key cryptography fully homomorphic encryption group-based cryptography
Contact author(s): nuida @ mist i u-tokyo ac jp
History: 2020-10-30: last of 6 revisions; 2014-02-14: received; See all versions
Short URL: https://ia.cr/2014/097
License: CC BY

BibTeX

@misc{cryptoeprint:2014/097,
      author = {Koji Nuida},
      title = {Towards Constructing Fully Homomorphic Encryption without Ciphertext Noise from Group Theory},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/097},
      year = {2014},
      doi = {10.1007/978-981-15-5191-8_8},
      url = {https://eprint.iacr.org/2014/097}
}