# 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?

-

4
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

2
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}$.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 23, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.939504861831665, "perplexity_flag": "middle"}