Transcript 投影片 1
The Bit Security of
Paillier’s Encryption
Scheme
Advisor: Hsueh-I Lu
B89902016 紀緯傑
B89902088 蔡碩展
B89902092 謝旺叡
B89902100 陳育成
Reference
The Bit Security of Paillier’s Encryption
Scheme
Dario Catalano, Rosario Gennaro, and Nick
Howgrave-Graham, Euro Crypt ‘01
Public-Key Cryptosystems Based on
Composite Degree Residuosity Classes
Pascal Paillier, Euro Crypt ’99
Topics
Preliminaries
Hardness of the Least Significant Bit
Simultaneous Security of Many Bits
Conclusion
Preliminaries
N = pq is an RSA modulus,a group Z*N2.
Let g є Z*N2 be an element whose order is a
nonzero multiple of N
Thus given g, for an element ω є Z*N2,there exists
(c,z) є ZN × ZN2 s.t. ω= gczN mod N2
(c is the class of ω relative to g,denoted
Classg(ω) )
Preliminaries (continued)
Lemma of Paillier’s scheme
If the order of g is a nonzero multiple of n
then
є
g
is bijective.
Class [n, g] is random-self-reducible over
w
Definition 1
Computing the function Classg(·) is hard if
for every probabilistic poly-time algorithm
A,there exists a negligible function negl()
s.t.
Lemma 1
Let N be a random n-bit RSA modulus,
yZn*, c an even element of Zn and g an
element in B. Then, denoting z = 2-1 mod
N,
(gc * yN)z = (g(c/2) * y’N) mod N2
for some y’Zn*
Definition
Computing Classg() is B-hard if,
probabilistic polynomial time algo A
a negligible function negl()
c [0…B]
Pr[A(N, g, w) = c] < negl(n)
Theorem 1
Let N be a random n-bit RSA modulus,
and let the functions Eg(·, ·)
and Classg(·) be de.ned as above. If the
function Classg(·) is hard (see De.nition
1), then the predicate lsb(·) is hard for it.
Perfect Case--破()
ComputeClass(O, w, g,N)
1. z = 2^-1 mod N
2. c = ()
3. for i = 0 to n = |N|
4. x = O(g,w)
5. c = c|x
6. if (x==1) then
7. w = w · g^-1 mod N^2 (bit zeroing)
8. w = w^z mod N^2 (bit shifting)
9. return c
Theorem 2
Let N be a random n-bit RSA modulus;
B=2b , where b = log B = ω(log n). If the
function Classg() is B-hard then it has n-b
simultaneously hard-core bits
Theorem 3
M is an m-bit odd integer, G is a group with
respect to the operation of multiplication.
Let f: ZM→G be a one-way,trapdoor isomorphic
function
(i.e.f (a+b mod M) = f (a) · f (b) G)
If f is hard to invert when its input belongs to the
closed interval [0…B], with B=2b,then f has m-b
simultaneously hard bits.
Application to Secure Encryption
OUR SOLUTION
RSA modulus N, size = 1024
Message M, size = 128
Plain RSA
FROM Strong Security Proofs for RSA and
Rabin bits
Hide only one bit
We need 128 exponentiations
Application to Secure Encryption
BLUM-GOLDWASSER(RSA/Rabin)
FROM Proc. Of Crypto ‘84
Pay the O (m / log n)
Remark
We need only O (m / k), k=w (log n)
For longer messages, we may catch up with
the other scheme