a typo in PPA comments

[vingstar]

Hi, This is a great implementation of PPA. But there is a tiny typo here: https://github.com/ladnir/cryptoTools/blob/534e348fef5c3b70e9f40b74d7e27ca2784ed77b/cryptoTools/Circuit/BetaLibrary.cpp#L1036

I think this should be 'G[i] = G[i:0] = G[i:j] ^ G[j-1:0] & P[i:j]' with 'P[j:0]' replaced with 'P[i:j]'.

PS: Maybe some more notes for others to understand why your elegant implementation works: In textbook, the prefix in PPA is updated as: G[i:j] = G[i:k] + P[i:k]G[k-1:j]. So, G[i]=G[i:0] = G[i:j] + P[i:j]G[j-1:0]. The '+' is 'OR' and '' is 'AND'. But this will require us to introduce another costly 'AND' operation since we need to implement 'OR' with 'AND' in MPC scenario. Generally, 'G[i:j] + P[i:j]G[j-1:0]' is not equivalent to 'G[i:j] ^ G[j-1:0] & P[i:j]', when all of them are '1'. But the bad case will not occur here since we have constraints: G=X AND Y, and P=X XOR Y. So we are safe to use G[i:j] ^ G[j-1:0] & P[i:j], in which only one ADD is used.

[ladnir]

yeah, shouldn't it be

G[i] = G[i:0] 
     = G[i:j]  or (G[j-1:0] & P[j:i]) 
     = G[i:j] xor (G[j-1:0] & P[j:i])

since we generate if

 * * * * * * * * * * 
 0         j       i
           ^ gens  ^
or
 ^ gens  ^ ^ props ^

[vingstar]

Yes, your illustration for 'or' is right.

Maybe I'm too long-winded. What I want to emphasize is: If G[i:j] = 1, G[j-1:0] =1, and P[j:i] = 1, then 1 = G[i:j] or (G[j-1:0] & P[j:i]) while 0 = G[i:j] xor (G[j-1:0] & P[j:i]). But this case will not occur since G[i:j] and P[j:i] can not be 1 at the same time by their definition. So we can safely replace the 'OR' to 'XOR' to get:

G[i:j] or (G[j-1:0] & P[j:i]) = G[i:j] xor (G[j-1:0] & P[j:i])

[ladnir]

Gotcha. Yeah seems we agree. Thanks for pointing this out. Glad you find it useful.

[vingstar]

Thanks! I close this issue since this is fixed.