cryptdb中paillier同态加密算法的使用

1.paillier同态加密算法

1.1Paillier加密系统

Paillier加密系统，是1999年Paillier发明的概率公钥加密系统。基于复合剩余类的困难问题。该加密算法是一种同态加密，满足加法和乘法同态。

1.2密钥生成

随机选择两个大质数p和q满足$gcd(pq,(p-1)(q-1)=1$,这个属性是保证两个质数长度相等。计算 $n=pq$和$\lambda =lcm(p-1,q-1)$。选择随机整数，使得满足n整除g的阶。定义$L(x)=(x-1)/n$计算$\mu =(L(g^{\lambda }\mathrm{m}\mathrm{o}\mathrm{d}{n}^2){)}^{-1}\mathrm{m}\mathrm{o}\mathrm{d}n$公钥为 $(n,g)$私钥为$(\lambda ,\mu )$

1.3加密

m为原文$(0\le m<n)$选择随机数$r(0<r<n,r\in Z_{n^2}^{\ast })$，且$gcd(r,n)=1$加密：$c=g^m\ast r^n\mathrm{m}\mathrm{o}\mathrm{d}{n}^2$

1.4解密

解密：$m=L(c^{\lambda }\mathrm{m}\mathrm{o}\mathrm{d}{n}^2)\ast \mu \mathrm{m}\mathrm{o}\mathrm{d}n$

1.5 同态属性

加法同态(两个密文的乘积将解密为它们相应的明文之和) $$D(E(m_1)\ast E(m_2)\mathrm{m}\mathrm{o}\mathrm{d}{n}^2)=m_1+m_2\mathrm{m}\mathrm{o}\mathrm{d}n$$

同态倍增 $$D(E(m_1{)}^{m_2}\mathrm{m}\mathrm{o}\mathrm{d}{n}^2)=m_1{m}_2\mathrm{m}\mathrm{o}\mathrm{d}n$$

2.cryptdb中paillier同态加密算法的使用

2.1 SQL语句加密

在SQL语句加密过程中，cryptdb会根据SQL语句动态的选择洋葱进行加密，如图。cryptdb中使用paillier算法来实现HOM层的加密和同态加法。 如执行select sum(id) from user;语句时，就会使用洋葱Onion Add进行加密。在HOM洋葱层中进行加密

Item * HOM::encrypt(const Item &ptext, uint64_t IV) const { if (true == waiting) { this->unwait(); } const ZZ enc = sk->encrypt(ItemIntToZZ(ptext)); return ZZToItemStr(enc); }

HOM中调用加密函数sk->encrypt(ItemIntToZZ(ptext))，实际使用paillier算法的加密函数进行加密

ZZ Paillier::encrypt(const ZZ &plaintext) { auto i = rqueue.begin(); if (i != rqueue.end()) { ZZ rn = *i; rqueue.pop_front(); return (PowerMod(g, plaintext, n2) * rn) % n2; } else { ZZ r = RandomLen_ZZ(nbits) % n; return PowerMod(g, plaintext + n*r, n2); } }

Onion Add加密完成后，最终得到加密后的SQL语句

2.2执行加密SQL

SQL服务端接收到加密后的SQL语句，开始执行SQL命令，会调用udf中的方法，如

// udf/edb.cc char * cryptdb_agg(UDF_INIT *const initid, UDF_ARGS *const args, char *const result, unsigned long *const length, char *const is_null, char *const error) { agg_state *const as = reinterpret_cast<agg_state *>(initid->ptr); BytesFromZZ(static_cast<uint8_t *>(as->rbuf), as->sum, Paillier_len_bytes); *length = Paillier_len_bytes; return static_cast<char *>(as->rbuf); } my_bool cryptdb_agg_add(UDF_INIT *const initid, UDF_ARGS *const args, char *const is_null, char *const error) { //cerr << "in agg_add \n"; agg_state *const as = reinterpret_cast<agg_state *>(initid->ptr); if (!as->n2_set) { //cerr << "n2 length is " << args->lengths[1] << "\n"; //cerr << "n2 first byte is " << (int)args->args[1][0] << "\n"; ZZFromBytes(as->n2, reinterpret_cast<const uint8_t *>(args->args[1]), args->lengths[1]); //cerr << "n2 is " << as->n2 << "\n"; as->n2_set = 1; } ZZ e; if (NULL == args->args[0]) { e = to_ZZ(1); } else { ZZFromBytes(e, reinterpret_cast<const uint8_t *>(args->args[0]), args->lengths[0]); } //cerr << "element to add " << e << "\n"; MulMod(as->sum, as->sum, e, as->n2); //cerr << "sum so far " << as->sum << "\n"; return true; }

此处调用paillier算法的MulMod(as->sum, as->sum, e, as->n2)方法实现密文的同态加法。

2.3密文结果解密

SQL服务端执行完命令后，返回密文结果。cryptdb会根据加密时的洋葱层进行解密，调用对应洋葱层的解密函数实现解密。

//main/rewrite_main.cc Item * decrypt_item_layers(Item *const i, const FieldMeta *const fm, onion o, uint64_t IV) { assert(!i->is_null()); Item *dec = i; const OnionMeta *const om = fm->getOnionMeta(o); assert(om); const auto &enc_layers = om->layers; for (auto it = enc_layers.rbegin(); it != enc_layers.rend(); ++it) { dec = (*it)->decrypt(dec, IV); LOG(cdb_v) << "dec okay"; } return dec; }

(*it)->decrypt(dec, IV)方法会调用对应洋葱层的解密方法。

// main/CryptoHandlers.cc Item * HOM::decrypt(Item * const ctext, uint64_t IV) const { if (true == waiting) { this->unwait(); } const ZZ enc = ItemStrToZZ(ctext); const ZZ dec = sk->decrypt(enc); LOG(encl) << "HOM ciph " << enc << "---->" << dec; return ZZToItemInt(dec); }

sk->decrypt(enc)具体调用paillier算法里的解密函数

ZZ Paillier_priv::decrypt(const ZZ &ciphertext) const { ZZ mp = (Lfast(PowerMod(ciphertext % p2, fast ? a : (p-1), p2), pinv, two_p, p) * hp) % p; ZZ mq = (Lfast(PowerMod(ciphertext % q2, fast ? a : (q-1), q2), qinv, two_q, q) * hq) % q; ZZ m, pq; pq = 1; CRT(m, pq, mp, p); CRT(m, pq, mq, q); return m; }

解密后获得明文结果