Paper: clarification on number of decryption shares to wait for

[rphmeier]

Not sure if this is the right place to post this, but I'm poking through the latest version of the paper at https://eprint.iacr.org/2016/199.pdf

and I am confused by the instruction in step 3 of Figure 1 (HoneyBadgerBFT) to wait to receive at least f + 1 decryption shares for each ciphertext.

Since TPKE.Dec holds the responsibility of identifying invalid decryption shares, I assume that up to f of the received f + 1 shares can be invalid. f + 1 valid shares are required for decryption, so in this case decryption would fail and the honest node running the protocol won't be in agreement with others who decrypted successfully.

It seems that a fix would be either a clarification of the language to either one of the following:

• wait for receipt of 2f potentially invalid decryption shares
• wait for f valid shares (which necessitates a TPKE.ShareValid(C, i, S_i) -> bool)

In the first case, there are a maximum of f invalid shares, leaving you with f valid shares to be combined with a locally generated share known to be valid for a total of f + 1.

In the second case the f valid shares are combined with the local share.

The second option to me seems more practical because it exits as soon as enough valid shares are collected instead of waiting unnecessarily.

[amiller]

Thanks! I will soon batch all the improvements to the paper suggested by issues in this repository :) Yes this needs clarification in the paper. It also needs clarification in the code. See issue #11. The main idea is that the code optimistically tries to decrypt given f+1 shares. If decryption fails, then the shares can be individually checked, which is more expensive, but at least it "incriminates" a node.

[rphmeier]

Gotcha. I tackled it in my newborn Rust version using a promise that resolves as soon as f+1 good shares have been received.

Another caveat I ran into was that a bad ciphertext requires broadcasting of a "Bad" message (although I guess that's implicitly covered with broadcast of False when DecShare outputs that), and an honest player would have to wait for either f + 1 of those or f + 1 valid decryption shares.