> Please can you clarify, the doc for Wideskies algorithm (slide 16) says that zeta is chosen to be in (Z/N^2 Z)* -- but the code we have in Paillier.java[1] appears to be selecting for (Z/NZ)*
Yes! Slide 22 (formerly slide 16) is wrong; zeta is in (Z/NZ)*. I, or someone else, can update the slides. Good catch. On Tue, Sep 20, 2016 at 4:10 PM, Ellison Anne Williams < [email protected]> wrote: > On Tue, Sep 20, 2016 at 12:10 PM, Tim Ellison <[email protected]> > wrote: > > > On 20/09/16 15:20, Walter Ray-Dulany wrote: > > >> Is this the same as I've seen this written elsewhere as double > stroked Z > > >> subscript N? > > > > > > Most definitely. I write it the way that I do to for historical reasons > > > (mathematical and personal). > > > > Ok, works well in ascii comments too. > > > > >> I assume that, practically, it is better to work with smaller factors > > to make > > >> the math operations faster (but not too small to compromise security) > > and > > >> chunk the message accordingly, rather than working with large > messages. > > > > > > This is precisely what Pirk does. > > > > I guess my question is, does Pirk change the message chunk size > > depending upon the bit length of N? Seems that there is going to be > > some correlation there - if the message length is too small you are > > doing more calculations than necessary. > > > > Is this chunking the DataPartitioner's job? In which case I see the > > built-in partitioners are all going to 8-bit partitions. > > > > No - just to be clear - the message size is independent of the modulus size > (N). The message is broken up into 'chunks' (currently 8 bits in length) > and then 'striped' across the rows of the matrix in order to perform the > encrypted query. This data 'chunking' is the responsibility of the > DataPartitioner in Pirk. There are other dependencies with N in the > parameter selection, but the message size is not one of them. > > > > > >> Whoa, why is g = 1 + N the standard Wideskies g? > > > > > > (1) It works (as I showed above), and (2) it turns out that all such g > > are > > > powers of (1+N). I'm not going to prove that, but it's true. > > > > > > Paillier's paper goes into detail about how the security of the system > is > > > independent of the g one chooses. Since g is public, and since the > > security > > > of the system does not suffer for just choosing the same g every time, > > > Wideskies just says "screw it, we're going with 1+N". > > > > I'm curious, but I'll draw the line there and trust :-) > > > > >> How do you want to receive proposed changes to the PDF, if at all? > I'm > > rephrasing > > >> your version a bit as I go, and quite happy to keep it separate so > > there is > > >> a simple version for those that don't "speak algebra". > > > > > > I've created another issue, PIRK-70, to add the LaTeX beamer doc from > > which > > > I generated the pdf, along with the relevant Pirk images. These docs > will > > > live in the main branch (not the web branch) under contrib. This is in > > > addition to the changes I've made to the PDF to clarify the math > > language. > > > With the TeX there, anyone can edit the doc, if they so choose. Tim, > you > > > could do that, or roll your own in whatever format you like. > > > > Cool, thanks. I'll keep working my way through it as I get a few mins. > > > > Please can you clarify, the doc for Wideskies algorithm (slide 16) says > > that zeta is chosen to be in (Z/N^2 Z)* -- but the code we have in > > Paillier.java[1] appears to be selecting for (Z/NZ)* > > > > [1] > > https://github.com/apache/incubator-pirk/blob/master/ > > src/main/java/org/apache/pirk/encryption/Paillier.java#L257 > > > > Regards, > > Tim > > > > > What do you think? > > > > > > Walter > > > > > > On Tue, Sep 20, 2016 at 8:33 AM, Tim Ellison <[email protected]> > > wrote: > > > > > >> On 19/09/16 18:36, Walter Ray-Dulany wrote: > > >>> Apologies! It's disorienting at first, and most of all when one > > actually > > >>> tries to sit down and do a real example. The version on the slides > was > > >> not > > >>> written in one go, I assure you. > > >>> > > >>> Let's go through, and see what's not working. > > >> > > >> I appreciate your patience Walter. I'm sure this "just makes sense" > to > > >> you, but my brain is hurting trying to keep up :-) > > >> > > >>> ************************** > > >>> > > >>>> I'm trying a very simple example. I'm going to choose, p = 3, q = 5 > > and > > >>> a message m = 42 > > >>> > > >>> Already we're in trouble. p and q are fine; but remember that the > > >> plaintext > > >>> space (let's call it P(N)) is the set of all integers in Z/NZ; that > is, > > >> it > > >>> is all numbers m > > >>> > > >>> 0 <= m < N > > >> > > >> Ah, so understanding the notation was confusing me, which is not going > > >> to help! Is this the same as I've seen this written elsewhere as > double > > >> stroked Z subscript N? > > >> > > >>> You can see already that the m you chose is not in the plaintext > space. > > >>> > > >>> Let's pick a new m to continue with; in this case, let's choose your > m, > > >> but > > >>> mod 15 so that it lies in P(N). Thus, our new m going forward shall > be > > >>> > > >>> m = 12 > > >> > > >> Interesting. That means that the size of message I can encode > directly > > >> using this scheme is related to the bit length of my RSA factors. > > >> > > >> I assume that, practically, it is better to work with smaller factors > to > > >> make the math operations faster (but not too small to compromise > > >> security) and chunk the message accordingly, rather than working with > > >> large messages. > > >> > > >>> ************************** > > >>> > > >>>> I'm going to pick g = 240. I think it needs to be a multiple of N > > that > > >>> is greater than N*N, correct? > > >>> > > >>> No, and this is important. g has to be an element of (Z/(N squared > )Z)* > > >> of > > >>> order a nonzero multiple of N. That sentence is meaningless unless > > you're > > >>> already embedded in the mathematics, so let's go through what it > means, > > >> bit > > >>> by bit. > > >>> > > >>> g must be: > > >>> 1. *an element of (Z/(N squared)Z)**: everything but the outer * on > the > > >>> right just means that 0 <= g < N*N; in this case that means 0 <= g < > > 225. > > >>> The outer * on the right indicates that we only want to take a > certain > > >>> special kind of g: one that is what we call a *unit* mod N*N; that > is, > > it > > >>> means that we require that there exist another element 0<= h < N*N > such > > >>> that g*h = 1 mod N*N. In our current situation, N = p*q is a product > of > > >>> primes, and so N*N = p**2 * q**2, and we can easily characterize G = > > >> (Z/(N > > >>> squared)Z)*: G = { 0<= g < N*N such that neither p nor q divide g}. > So > > as > > >>> long as we pick a g that does not have p or q as a factor, we're good > > for > > >>> this condition (this also includes 0, so really all of my "0 <=" in > > this > > >>> paragraph could have been "0 < "). Another way to characterize G is > to > > >> say > > >>> that it is the set of integers less than N*N that are relatively > prime > > to > > >>> N*N. > > >> > > >> Ok, got that. > > >> > > >>> 2. *of order a nonzero multiple of N*: this is a little trickier. > The > > >>> *order* of an element g of a finite group (which G is) is the least > > >> integer > > >>> k such that g^k = 1 in G. I'm not going to prove it here, but it > turns > > >> out > > >>> that every element of G has finite order (that is, if g is in G, then > > >> there > > >>> exists a finite non-zero k such that g^k = 1), and that it is less > than > > >> or > > >>> equal to the Carmichael number lambda(N*N). That takes care of what > > >> 'order' > > >>> means, and, like I said, order is defined for all g in G. But! We > > >> require a > > >>> special order. Specifically, we only want g in G such that the order > > of g > > >>> is a non-zero multiple of N. We might ask whether we know that such > > >> always > > >>> exists (a good question, since we require it), and we do! Here's a > > quick > > >>> proof of existence, one tied closely to Wideskies: > > >>> > > >>> * Take g = 1 + N (I'm going to prove, all at once, that 1+N is in G > and > > >>> that it has an order that fits the bill). > > >>> * Consider g**N: by the binomial theorem, (1+N)*N = 1 + N*N + other > > terms > > >>> divisible by N*N. This number is equivalent to 1 mod N*N. QED > > >>> > > >>> Ok, great, such g exist, and so we can require that we use one of > them. > > >> But > > >>> you must be careful: you can't just choose any g in G off the street > > and > > >>> expect it will satisfy our requirements. You chose g = 240, which (1) > > >>> bigger than N*N, which isn't what we want, and (2) is divisible by N, > > and > > >>> so even if we take 240 mod N*N, we still aren't in G, much less of > the > > >>> 'right order' (turns out 240, being not relatively prime to N, can > > never > > >> be > > >>> exponentiated to 1 mod N*N). For now, let's just take the standard > > >>> Wideskies g, g = 1 + N = 16. If you want to go through this with a > > >>> different g, give it a shot, but make sure it's got the right kind of > > >> order. > > >> > > >> Whoa, why is g = 1 + N the standard Wideskies g? > > >> > > >> I was following what you said, and thinking, ok I've got to pick a > value > > >> for g that > > >> (i) does not have p or q as a factor, > > >> (ii) 0 <= g < N*N, and > > >> (iii) has multiplicative order that's a non-zero multiple of N > > >> > > >> this is going to take some finding ... then you simply say N + 1 ?! > > >> > > >> I would go through with a different g, but it may take me a while to > > >> sift through and find one without knowing the trick :-) > > >> > > >>> ************************** > > >>> > > >>>> I'll pick zeta = 21. I think it needs to be greater than N. > > >>> > > >>> As in point 2, no. We require zeta to be in (Z/NZ)*, which, similar > to > > >> the > > >>> above, means a number > > >>> > > >>> 0 < zeta < N such that zeta is a unit. > > >>> > > >>> You picked 21; if we take 21 mod N we get zeta = 6, which is not a > unit > > >> (in > > >>> particular it is not relatively prime to p=3). Let's pick the next > > number > > >>> greater than 6 which is in (Z/NZ)*, which is > > >>> > > >>> zeta = 7. > > >> > > >> So apart from the fact that I picked all the numbers incorrectly I was > > >> on the right lines :-) D'oh. > > >> > > >> > > >>> ************************** > > >>> > > >>> Let's see what we've got. > > >>> > > >>> ( (16**12)*(7**15) ) mod 225 = 208. > > >>> > > >>> I will leave it as an exercise to check that the decryption of 208 is > > in > > >>> fact 12. > > >> > > >> I'll get to decryption in a moment. I want to have this encrypt > sorted > > >> first. > > >> > > >>> ************************** > > >>> > > >>> Ok, that's all so far. If the above is still not computing (literally > > or > > >>> metaphorically), I am available to converse one-on-one either over > the > > >>> phone or some other medium (face time or what have you) and only too > > >> happy > > >>> to go over this more. > > >>> > > >>> Let me know, > > >> > > >> Thanks for the offer. I'm happy to demonstrate my ignorance on the > > >> list, and work towards a description that hopefully is useful to > anyone > > >> else coming from the same direction. > > >> > > >> How do you want to receive proposed changes to the PDF, if at all? > I'm > > >> rephrasing your version a bit as I go, and quite happy to keep it > > >> separate so there is a simple version for those that don't "speak > > algebra". > > >> > > >> Regards, > > >> Tim > > >> > > >> > > >>> On Mon, Sep 19, 2016 at 12:13 PM, Tim Ellison <[email protected] > > > > >> wrote: > > >>> > > >>>> On 17/09/16 06:42, wraydulany wrote: > > >>>>> [Pirk 67] - Add Slide Deck to the Website Documentation > > Explaining > > >>>> the Mathematics of Pirk > > >>>> > > >>>> Argh! Walter you are driving me mad! :-) > > >>>> > > >>>> Thank you for putting up the slides, and I really want to grok this, > > but > > >>>> I'm struggling to work through even the simplest of examples. > > >>>> I need the kindergarten version :-( > > >>>> > > >>>> What am I doing wrong? I'm trying a very simple example. I'm going > > to > > >>>> choose, > > >>>> p = 3, q = 5 and a message m = 42 > > >>>> > > >>>> Looking at page 11 on the math_deck.pdf line by line > > >>>> > > >>>> line 2: > > >>>> N = 15. > > >>>> I'm going to pick g = 240. I think it needs to be a multiple of N > > >>>> that is greater than N*N, correct? > > >>>> > > >>>> line 3: > > >>>> I'll pick zeta = 21. I think it needs to be greater than N. > > >>>> > > >>>> Line 4: > > >>>> (240^42 x 21^15) mod 225 = 0 > > >>>> > > >>>> That's suspicious. > > >>>> ...and if I play with my free choices of m, g and zeta I always get > > >> zero. > > >>>> > > >>>> Help! > > >>>> > > >>>> I get the gist of the flow through the deck, but I want to work > > through > > >>>> my own examples from top to bottom. > > >>>> > > >>>> Regards, > > >>>> Tim > > >>>> > > >>> > > >> > > > > > >
