Cheating on the multi-exponentiation argument In the second part of the challenge,
it generates a cheating permutation πcheat, which isn’t actually a permutation, as follows:
πcheat(1) = x + x
2
πcheat(2) = 0
πcheat(3) = x
3
πcheat(4) = x
4
.
The attacker then runs the multi-exponentiation argument from Section 4 of BG
exactly as given, except for the following changes.
• It sets
ρ = −ρ1x − (ρ1 + ρ
0
1
)x
2 + x
2
ρ
0
2 − ρ3x
3 − ρ4x
4
. (2)
(See Appendix A.1 for why this works.)
• It treats ~cB = comck (B~
1; s1), comck (B~
2, s2) as a commitment to
πcheat = ((x + x
2
, 0)(x
3
, x4
)).
• It computes commitment openings ~s for πcheat using Equation 1 and the random
values s1 and s2.
This produces a proof that passes verification, though the election outcome has been
changed. An example transcript, which passess verification, is attached with this report.
Nothing in our analysis suggests that this problem was intro- duced deliberately. It is entirely consistent with a naive implementation of a complex cryptographic protocol by well-intentioned people who lacked a full understanding of its security assumptions and other important details. Of course, if someone did want to introduce an opportunity for manipulation, the best method would be one that could be explained away as an accident if it was found. We simply do not see any evidence either way.”
Why does a scheme like this exist?
To cheat
Holy shit. I hate proofs but looks pretty legit. Possibly Hammer and Scorecard used this?
Cheating on the multi-exponentiation argument In the second part of the challenge, it generates a cheating permutation πcheat, which isn’t actually a permutation, as follows: πcheat(1) = x + x 2 πcheat(2) = 0 πcheat(3) = x 3 πcheat(4) = x 4 . The attacker then runs the multi-exponentiation argument from Section 4 of BG exactly as given, except for the following changes. • It sets ρ = −ρ1x − (ρ1 + ρ 0 1 )x 2 + x 2 ρ 0 2 − ρ3x 3 − ρ4x 4 . (2) (See Appendix A.1 for why this works.) • It treats ~cB = comck (B~ 1; s1), comck (B~ 2, s2) as a commitment to πcheat = ((x + x 2 , 0)(x 3 , x4 )). • It computes commitment openings ~s for πcheat using Equation 1 and the random values s1 and s2. This produces a proof that passes verification, though the election outcome has been changed. An example transcript, which passess verification, is attached with this report.
“Source of the problem
Nothing in our analysis suggests that this problem was intro- duced deliberately. It is entirely consistent with a naive implementation of a complex cryptographic protocol by well-intentioned people who lacked a full understanding of its security assumptions and other important details. Of course, if someone did want to introduce an opportunity for manipulation, the best method would be one that could be explained away as an accident if it was found. We simply do not see any evidence either way.”
Fucking academics can be the worst Pollyannas!