the difference between {DGTp([x]p0), . . . , DGTp([x]pL−1)} and {DGTp0([x]p0), . . . , DGTpL−1([x]pL−1)}.
DevinRen opened this issue · 2 comments
In your paper 'Faster Homomorphic Encryption over GPGPUs via hierarchical DGT'，I'm not sure about one thing.
In 3.3 Polynomial representation and memory locality, Another design decision, very common to HE implementations, is the selection of a special prime p for the transform, the same for all RNS residues [15,17, 3]. For instance, let x be a polynomial, and {p0, . . . , pL−1} a set of L pairwise co-primes. . The usual design works with the set of transformed residues{DGTp([x]p0), . . . , GTp([x]pL−1)}.
and later ,Thus, in this representation, the set of residues is {DGTp0([x]p0), . . . , DGTpL−1([x]pL−1)}
I'm not sure about the difference between {DGTp([x]p0), . . . , DGTp([x]pL−1)} and {DGTp0([x]p0), . . . , DGTpL−1([x]pL−1)}.
Hi @DevinRen ,
When we mention "usual design" we are referring to the use of a special prime, p, to apply the DGT and a set of coprimes (p_0, . . . , p_{L−1}) to decompose polynomials using the RNS. Notice that p can be, for instance, a Mersennes or a Solinas prime, and p_i is any prime, not necessarily equal to p. So, there is no connection between DGT's and RNS' domain.
In our work, we propose that you should use the same prime p_i to compute the DGT for the i-th residue. So, the DGT and RNS domains are defined by the same prime and this prime changes from residue to residue.
For ''In our work, we propose that you should use the same prime p_i to compute the DGT for the i-th residue. So, the DGT and RNS domains are defined by the same prime and this prime changes from residue to residue.'',i have a question.
I thought of two different ideas，and i want to know which one is right?
Parameter:
prime to compute the DGT is ~p
prime to rns residue is pi ,{p0, . . . , pL−1}
q=product of {p0, . . . , pL−1}
N=Number of polynomial terms
Ideas:
A.the ~p don't change , a special prime,and pi *pi N<~p.
The process of polynomial multiplication is
two poly x(Rq) and y(Rq) ，after rns , get( x0(Rp0),...,xL-1(RpL−1) ) and ( y0(Rp0),...,yL-1(RpL−1) ), after L parallel DGT mul IDGT（for all DGT,IDGT the prime is a special prime ,~p=0xFFFFFFFF00000001)
after crt, get a poly xy(Rq).
B.the ~p can change,there are several ~p({~p0, . . . , ~pL−1} ) for several DGT , and also prime to rns residue is {~p0, . . . , ~pL−1} .
but i know only one ~p=0xFFFFFFFF00000001，and if this situation is right，What are the other prime ~p that can be used？