# Quasi-linear time fully homomorphic encryption using p-adic ring homomorphism

I recently encountered a breakthrough in FHE crypto, which claims to have a literally quasi-linear time FHE without any "lambda" factor in the keys and no noise in the cipher-text.

This fully homomorphic encryption works like for addition like $E(m_1)·E(m_2) = E(m_1+m_2)$ and for multiplication like $E(m_1)^{m_2} = E(m_1·m_2)$ ; they say they achieved it using p-adic exponential.

My Question is: What is exactly p-adic exponential?

-

## migrated from crypto.stackexchange.comDec 4 '12 at 13:24

This question came from our site for software developers, mathematicians and others interested in cryptography.

What you describe is not fully homomorphic. Notice that $m_2$ in the second equation is not encrypted. –  mikeazo Dec 2 '12 at 23:00
Hasn't he defined it in P1.3? Were you looking for more than that? –  Amzoti Dec 4 '12 at 13:42
A warning about the paper: it doesn't sound like the author knows much about crypto. There's the misrepresentation of FHE that Mike pointed out; in addition, he claims his system is Informationally Secure (which is impossible for any public key system); he claims that a message cannot be uniquely decrypted; if this were true, this would imply that someone with the private key cannot decrypt it. His claim of $O(n \log n)$ time is also bogus. I would approach this system only with extreme caution. –  poncho Dec 4 '12 at 15:39

## 1 Answer

To answer the question (and ignoring the fluff), the $p$-adic exponential is a partial function on the $p$-adic numbers defined by the power series

$$\exp(x) = \sum_{i=0}^{\infty} \frac{x^n}{n!}$$

This power series converges if and only if $x$ is a $p$-adic integer divisible by $p$. It satisfies many of the properties you'd expect. For example, $\exp(x+y) = \exp(x) \exp(y)$, and it has an inverse, the $p$-adic logarithm.

If you're not familiar with the $p$-adic numbers, we can approximate them with modular arithmetic. If $x$ is an integer such that $x \equiv 0 \pmod p$, then the above power series also makes sense in the arithmetic of integers modulo $p^n$. For an example with the $3$-adic logarithm:

\begin{align} \exp(3) &\equiv 1 + 3 + \frac{9}{2} + \frac{27}{6} + \cdots& \pmod{27} \\ &\equiv 1 + 3 + \frac{9}{2} + \frac{9}{2} + 0& \pmod{27} \\ &\equiv 1 + 3 + 9 \cdot 14 + 9 \cdot 14 & \pmod{27} \\ &\equiv 13& \pmod{27} \end{align}

Note the remaining terms (indicated by $\cdots$) are all divisible by $27$, which is why I replaced withm with $0$ in the above calculation. And that $2$ and $14$ are inverses modulo $27$: i.e. $2 \cdot 14 \equiv 1 \pmod{27}$.

-