On Compression Functions over Small Groups with Applications to Cryptography

arXiv2208.02468MaRDI QIDQ6406941FDOQ6406941

Authors: Koji Nuida 

Publication date: 4 August 2022

Abstract: In the area of cryptography, fully homomorphic encryption (FHE) enables any entity to perform arbitrary computation on encrypted data without decrypting the ciphertexts. An ongoing group-theoretic approach to construct FHE schemes uses a certain "compression" function $F(x)$ implemented by group operators on a given finite group $G$ (i.e., it is given by a sequence of elements of $G$ and variable $x$), which satisfies that $F(1)=1$ and $F(sigma)=F(sigm{a}^2)=sigma$ where $sigmainG$ is some element of order three. The previous work gave an example of such $F$ over $G=S_5$ by just a heuristic approach. In this paper, we systematically study the possibilities of such $F$. We construct a shortest possible $F$ over smaller group $G=A_5$, and prove that no such $F$ exists over other groups $G$ of order up to $60=|A_5|$.

Mathematics Subject Classification ID

Cryptography (94A60) Arithmetic and combinatorial problems involving abstract finite groups (20D60)

This page was built for publication: On Compression Functions over Small Groups with Applications to Cryptography

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6406941)