Handle pessimistic cases in the light tDec variant

[piotr-roslaniec]

Design a variation of this scheme that is robust to a pessimistic case.

There's a caveat with the light approach: this works as long as all t requests are ok, but if one of them fails, then all the lagrange coeffs you created and that all the nodes used before the pairing are incorrect

2-of-3
Nodes 1 and 2 --> L1 and L2
Nodes 1 and 3 --> L'1 and L'3
Optimistic: Node 1: C1 = e(L1 * U, Z_1). Node 2: C2 = e(L2 * U, Z_2)
Node 3: C3 = e(U, Z_3)
C1^(L'1/L1) * C3^L'3

Use low-latency (optimistic variant, light variant). If it fails, switch to regular simple tDec.

Refers to #30

[cygnusv]

How to deal with the pessimistic case in the light subvariant?

Say you originally requested decryption shares to nodes 1, 2, and 3. This means that you optimistically assumed that they were going to respond correctly, and you precomputed Lagrange coefficients $\lambda_1, \lambda_2, \lambda_3$. Recall that these values are interdependent, so if the group was different (e.g., nodes 1, 2, and 4), all values will likely vary.

Responses from nodes should be:
$D_1 = e(\lambda_1 \cdot U, Z_1)$
$D_2 = e(\lambda_2 \cdot U, Z_2)$
$D_3 = e(\lambda_3 \cdot U, Z_3)$

But let's say node 3 didn't respond, or response was incorrect/malformed. At this point we could either retry everything with a new set (basically starting over), or we can "downgrade" the responses that we received so we can reuse them. Let's assume we "somehow" got another response from node 4 using the simple variant (*more on this later....). Since the group of responders is now different, the set of Lagrange coefficients should change to $\lambda'_1, \lambda'_2, \lambda'_4$ . We can "fix" responses from 1 and 2 as follows: $D'_1 = D_1^{\lambda'_1 / \lambda_1}$ ; $D'_2 = D_2^{\lambda'_2 / \lambda_2}$
For response $D_4$, since it's already using the simple variant (i.e, no lagrange coefficient was used when requesting), we just have to compute $D'_4 = D_4^{\lambda'_4}$.
Final combination is as usual with the simple variant: $\prod D'_i$

How to get the extra responses in the pessimistic case?

The optimistic case assumes that you're going to get $t$ correct responses, but in the pessimistic case you only got $t - s$ responses (that's it, you're $s$ responses short). There are 2 potential approaches here:

• You can follow an extra round with the simple variant, only for $s$ nodes.
• On the original round, you could account for an extra buffer, so the round looks like $t$ requests with the light approach, plus $b$ requests with the simple. This would work as long as $b > s$.