现代密码学(中山大学)Lecture14Lecture11.ppt

构造同态加密算法一直是密码学领域的一个重要课题，以往人们只找到一些部分实现这种操作的方法。而2009年9月Craig Gentry）从数学上提出了“全同态加密”的可行方法，即可以在不解密的条件下对加密数据进行任何可以在明文上进行的运算，使这项技术取得了决定性的突破。人们正在此基础上研究更完善的实用技术，这对信息技术产业具有重大价值。 Craig Gentry. Fully Homomorphic Encryption Using Ideal Lattices. In the 41st ACM Symposium on Theory of Computing (STOC), 2009 A homomorphic symmetric encryption Shared secret key: odd number p To encrypt a bit m: Choose at random large q, small r Output c = pq + 2r + m Ciphertext is close to a multiple of p m = LSB of distance to nearest multiple of p To decrypt c: Output m = (c mod p) mod 2 2r+m much smaller than p Why is this homomorphic? c1=q1p+2r1+m1, c2=q2p+2r2+m2 c1+c2 = (q1+q2)p + 2(r1+r2) + (m1+m2) 2(r1+r2)+(m1+m2) still much smaller than p ?c1+c2 mod p = 2(r1+r2) + (m1+m2) c1 x c2 = (c1q2+q1c2-q1q2)p  + 2(2r1r2+r1m2+m1r2) + m1m2 2(2r1r2+…) still much smaller than p ?c1xc2 mod p = 2(2r1r2+…) + m1m2 现代密码学Modern Cryptography 张方国 中山大学信息科学与技术学院 isszhfg@mail.sysu.edu.cn 第十一讲 公钥密码学（二） Rabin加密 ElGamal加密 Pailler加密方案 同态加密 The Rabin System Theorem. Let n=pq be the product of two distinct odd primes p, q. If , then has no solutions or exactly four solutions. (ii) Let r, s be a solution of , respectively, then the four solutions of are (aps+bqr); -(aps+bqr); (aps-bqr); -(aps-bqr), where a, b satisfy ap+bq=1. (iii) If , then is a solution of The Rabin System Set-up of the Rabin System Choose two distinct primes p, q s.t.  and put n=pq. Encryption function The Rabin System Encryption algorithm: Have to solve to find m! Decryption algorithm: step 1: Find a, b s.t. ap+bq=1 using the Euclidean algorithm. step 2: put step 3: Compute The Rabin System Claim: are four roots of  and m is one of these four. Chose one which  makes sense! The Rabin System Theorem :