Threshold decryption seems to not actually work?

[Vagabond]

When we were implementing the threshold decryption routines for erlang_tpke https://github.com/helium/erlang-tpke by following what the python code did, we noticed that threshold decryption seemed to succeed regardless of the inputs. We eventually re-implemented all the threshold decryption routines according to the Baek and Zhang paper and finally our property based tests started passing (we do negative testing with duplicate shares, shares generated with the wrong key and shares for the wrong message).

I don't have specific changes to suggest here, nor the time to assemble them, but I'm pretty convinced your threshold decrypt, as implemented, ends up being a no-op.

The commit where I reworked our implementation to follow the paper, not the python implementation is here:

https://github.com/helium/erlang-tpke/commit/b2bd3c8e0bf5e1bbeab541baf395418b896f4204

Later commits annotate all those functions with the specific math from the paper(s).

I realize this is not intended to be a production quality implementation, but people should be aware that the threshold decryption doesn't work as advertised and they should not rely on the python implementation of it.

Thanks again for all your work and let me know if there's any more information I can provide.

[amiller]

Thanks for this report. From a quick glance, it does look at least like verify_share is not called from anything in the repo right now (dev branch).

For now I added a negative test case, and added verification of each share in combine_shares.
b28b8359011e019f9ef94f7efe03bfc87f3de1ed

It would be more efficient to optimistically compute the decryption and then check it, only verifying each share if the overall decryption fails. #11 The right thing to do for now seems to be to err on the side of caution and reduce it to a performance issue.

[Vagabond]

I think the breakage is more fundamental than that, I had to rewrite decrypt_share, combine_shares and verify share quite drastically to get them to pass my property tests. The python code varied drastically from the paper.

[sbellem]

This issue was moved to initc3/HoneyBadgerBFT-Python#46

/cc @amiller @Vagabond