import json,math,itertools
from fractions import Fraction
SLUG='secure-aggregation-dropout';KIND='Constructed analytical model; not a measured benchmark'
def recovery(n,t,p):return sum(math.comb(n,k)*p**k*(1-p)**(n-k) for k in range(t,n+1))
def reconstruct(shares,q):
    result=0
    for x,y in shares:
        numerator=denominator=1
        for z,_ in shares:
            if z!=x:numerator=numerator*(-z)%q;denominator=denominator*(x-z)%q
        result=(result+y*numerator*pow(denominator,-1,q))%q
    return result

def run():
    checks=[];cases=0
    for n in (4,7,10):
        for t in (1,n//2+1,n):
            for p in (Fraction(0),Fraction(1,2),Fraction(4,5),Fraction(1)):
                enumeration=sum((p**sum(mask)*(1-p)**(n-sum(mask)) for mask in itertools.product((0,1),repeat=n) if sum(mask)>=t),Fraction(0))
                assert enumeration==recovery(n,t,p)
                cases+=1
    checks.append(dict(name='Binomial tail versus all survivor subsets',passed=True,cases=cases,detail='Exact rational probabilities including zero and one survival endpoints.'))
    q=257;s=42;a=17;b=91;shares=[(x,(s+a*x+b*x*x)%q) for x in range(1,6)]
    subsets=list(itertools.combinations(shares,3))
    assert all(reconstruct(pair,q)==s for pair in subsets)
    checks.append(dict(name='Threshold reconstruction for all three-share subsets',passed=True,cases=len(subsets),detail='Degree-two polynomial over F257, five shares.'))
    y1,y2=shares[0][1],shares[1][1];counts=[]
    for candidate in range(q):
        count=0
        for aa in range(q):
            bb=(y1-candidate-aa)%q
            if (candidate+2*aa+4*bb)%q==y2:count+=1
        counts.append(count)
    assert counts==[1]*q
    checks.append(dict(name='Two shares leave every secret possible',passed=True,cases=q,detail='For each of 257 candidate secrets enumerate all first coefficients and derive the second; exactly one polynomial fits.'))
    inputs=[3,5,7,11,13]
    masked=[]
    for i,value in enumerate(inputs):
        masked.append((value+sum(i+j+1 for j in range(i+1,5))-sum(i+j+1 for j in range(i)))%q)
    assert sum(masked)%q==sum(inputs)%q
    residual=sum(i+4+1 for i in range(4))
    assert sum(masked[:4])%q!=sum(inputs[:4])%q
    assert (sum(masked[:4])-residual)%q==sum(inputs[:4])%q
    checks.append(dict(name='Mask cancellation and dropout residual',passed=True,cases=3,detail='Deterministic public masks illustrate algebra only, not a secure protocol.'))
    assert sum([3,5,7,11])-sum([5,7,11])==3
    checks.append(dict(name='Overlapping aggregate disclosure counterexample',passed=True,cases=1,detail='Fixed inputs allow differencing even with cohort sizes four and three.'))
    ps=[i/20 for i in range(10,21)];colluders=list(range(8))
    figures=[dict(id='dropout-threshold',title='Recovery under independent survival',x_label='Client survival probability',y_label='Recovery probability',series=[dict(name=f'Threshold {t} of 10',x=ps,y=[recovery(10,t,p) for p in ps]) for t in (5,7,9)],caption='Exact binomial tails under identical independent survival; not an adversarial-dropout guarantee.',assumptions=['Ten enrolled clients','Threshold valid shares suffice','No correlated failures or malicious phase behavior'],kind=KIND),dict(id='unknown-summands',title='Collusion reduces unknown contributions',x_label='Colluding accepted participants',y_label='Unknown contributors',series=[dict(name='Seven accepted participants',x=colluders,y=[7-c for c in colluders])],caption='Counting unknown summands after known colluder inputs are subtracted. One unknown is directly exposed by the output; count is not a privacy parameter.',assumptions=['Accepted set fixed at seven','Colluders reveal their inputs','Auxiliary information may further reduce ambiguity'],kind=KIND)]
    return dict(slug=SLUG,checks=checks,figures=figures,result_summary=dict(recovery_n10_t7_p08=float(recovery(10,7,Fraction(4,5))),unknown_when_accepted7_colluding3=4,overlapping_full_sum=26,overlapping_subset_sum=23,disclosed_contribution=3,candidate_secrets_with_two_shares=257))
if __name__=='__main__':print(json.dumps(run(),indent=2))