# Homomorphic Encryption

2019/08/03

Homomorphic encryption is a form of encryption that allows computation on ciphertexts, generating an encrypted result which, when decrypted, matches the result of the operations as if they had been performed on the plaintext.
–Cite from wikipedia

## 概览 (Overview)

1. Alice 可以给 Bob 钥匙，这当然可行。然而，可能会有一个攻击者 Eve ，他想要偷钱。 她可能会假扮 Bob，或者她会从 Bob 那里偷走手提箱和钥匙。
2. 设计一种新的锁，这种锁比需要钥匙的手提箱更好。这种锁不让任何不是 Alice 的人拿到钱，甚至不让他们知道里面有多少钱。但是它将允许任何有权利的人来计算它。这就是同态加密背后的概念，也是它如此强大的原因。

## 特点 (Properties)

• 延展性(malleability).
同态加密在设计上是具有延展性的。具有延展性的密码 系统指的是任何人都可以拦截密文，将其转换为另外一个密文，然后将其解密为有意义的明文。在密码系统中，延展性通常被认为是不受欢饮的。举个例子，如果你想给你喜欢的人发一句 “I love you”, 有一天你终于有勇气说出这句话，你把它加密发给她。但是这个密文信息在中途被你的情敌给拦截了，当然，他看到的只是密文。但是当你喜欢的人试图解密时，就解密成了 “I hate you ”，这就是为什么延展性通常是不需要的。

## 部分同态加密 (Partially homomorphic cryptosystems)

If the RSA public key is modulus $n$ and exponent $e$, then the encryption of a message $x$ is given by $\varepsilon (x)=x^{e}$ $mod$ $n$. The homomorphic property is then

### ElGamal

In the ElGamal cryptosystem, in a cyclic group $G$ of order $q$ with generator $g$, if the public key is $(G,q,g,h)$, where $h=g^{x}$ , and $x$ is the secret key, then the encryption of a message $m$ is $\varepsilon(m)=(g^{r},m\cdot h^{r})$, for some random $r \in$ {$1,...,q-1$}. The homomorphic property is then

### Paillier

In the Paillier cryptosystem, if the public key is the modulus $m$ and the base $g$,then the encryption of a message $x$ is $\varepsilon(x) = g^{x}r^{m} \ mod \ m^{2}$, for some random $r \in$ {$0,...,m-1$}. The homomorphic property is then