Nslots size

[keerthic]

I wanted to know,How is this Nslots calculated.Because when i tried to encrypt a file greater than 280 bytes.it does not happen.Is 280 the limit size of the file?. My input parameters were. m=0 p=3001 r=1 L=16 c=3 w=64 d=0 security=128.

[rohitkhera]

nslots is calculated throughcChinese remaindering of the "aggregate" plaintext ring (typically this is F_2[X]/(Phi_m(X)) corresponding to p=2 r=1) , i.e. the number irreducible factors of the m'th cyclotomic polynomial mod p^r - refer to Smart and Vercauteren's "Homomorphic SIMD operations" for some details.

Rohit Date: Mon, 11 Aug 2014 23:40:54 -0700 From: notifications@github.com To: HElib@noreply.github.com Subject: [HElib] Nslots size (#30)

I wanted to know,How is this Nslots calculated.Because when i tried to encrypt a file greater than 280 bytes.it does not happen.Is 280 the limit size of the file?.

My input parameters were.

m=0

p=3001

r=1

L=16

c=3

w=64

d=0

security=128.

— Reply to this email directly or view it on GitHub.

[strizhov]

Following up the question. I have a vector of plaintext values of size 10000. What would be the params to have nslots around 10000? Cheers.

[shaih]

The parameters to get 10000 slots are so big that you probably don't want to use them.. Certainly none of the parameters in our pre-computed tables get there, the typical values are a few hundred slots. A better option would be to work with smaller cipehrtexts with somewhere between 500 to 1000 slots, and use a vector of those.

It would be nice to have a class above our EncryptedArray and Ctxt classes that implements a vector with arbitrary number of slots using many ciphertexts. This should not be very hard, maybe one week of work, but I don't know if/when I'll get to do it.

[rohitkhera]

I had a question about constructing a vector of Encryted Array classes mentioned by shaih above. Since the cyclotomic polynomial (with field extension Q(zeta_m)) for the plaintext ring splits mod p into L linear factors, Gal(Q(zeta_m)/Q) will permute across the L roots of the polynomial. If we now construct a 2 element vector of plaintext ring instances A_p each with L slots, We need a Galois group with 2L automorphisms to encompass permutations across the two instances which doesn't seem possible. I'm assuming that each EncryptedArray class contains just a single instance of the plaintext ring A_p consisting of L slots. Also, I understand the relationship of Gal(Q(zeta_m)/Q) and Z[X] / (X^m-1), but I'm confused about the relationship between this Galois group and the plaintext ring A_p. thanks

[shaih]

I'm assuming that each EncryptedArray class contains just a single instance of the plaintext ring A_p consisting of L slots.

That is correct.

But HElib can hide the algebra from you, giving you the abstraction of a linear array of L slots per ciphertext (even if the algebra gives some other hypercube structure). Then you can build on top of it procedures to concatenate (say) two such arrays to get a vector of size 2L. This is done regardless of the algebra, just like you can implement a 128-bit shift on top of two registers that have native 64-bit shift operations.

(But the hypercube->linear-array comes at a cost, so HElib also gives you access to the underlying hypercube structure so that you can build more efficient routines if you know what you are doing.)

I'm confused about the relationship between this Galois group and the plaintext ring A_p.

I'm not sure what the question is. The algebraic ("native") plaintext space is integer polynomials modulo both p^r (the plaintext space modulus) and Phi_m(X) (the m'th cyclotomic polynomial).

But again HElib would typically hide it from you, giving you an abstraction of vectors of plaintext elements from some extension field/ring of Z_{p^r} (using the class EncryptedArray). E.g., if the plaintext space modulus is a prime p, and p has order d in Z_m^*, then you can get a vector of L=phi(m)/d elements in the field GF(p^d) (or any sub-field of GF(p^d) that you want).

[rohitkhera]

OK, thanks, I actually just read relevant parts of the GHS paper "Fully Homomorphic Encryption with Polylog Overhead" which provides the lemma for permutations over hyper-rectangles in terms of compositions of L-Add, L-Mult and L-Permute. The second question toward the end of my post was some confusion on my part since I have seen the plaintext space described in the literature as A_(p^r) which is integer polynomials modulo both p^r (the plaintext space modulus) and Phi_m(X). But in other parts of the literature I think I have seen this equated with Q(zeta_m)/Q, so I thought the literature was somehow implying an isomorphism of fields between the Q(zetam)/Q and A(p^r) which cannot hold since the latter is a ring and not a field. This brings me to another thought which is why is the BGV plaintext space described as A(p^r) at all instead of something like a Z(p^r). I' guessing that this is because A(p^r) offers a "bridge" to cyclotomic fields and their associated permutation groups which may have better computational properties such as transitivity etc. ?