wagner-blind-sig-with-aborts.py

import math

# k is number of parallel sessions in Wagner
max_k = 2**(round(math.sqrt(256))-1)

# For given abort probability compute work required
def abort(p):
    print("abort probability:", p)
    for k in range(3, max_k):
        # nr of expected attempts of an attacker to pick the non-aborted sessions
        expected_attempts = 1.0/(p**k)
        bits = 256
        if expected_attempts > 2**100:
            break
        wagner = k*2**(bits/(1+math.log(k,2)))
        print("parallel sessions:", k, "\t", "work wagner (bits):", round(math.log(wagner,2)), "\t", "expected #attempts (bits):", round(math.log(expected_attempts,2)), "\t", "combined work (bits):", round(math.log(expected_attempts*wagner,2)))


abort(0.5)
print()

abort(1/128.0)
print()
abort(1/512.0)
print()

# abort probability: 0.5
# parallel sessions: 3 	 work wagner (bits): 101 	 expected #attempts (bits): 3 	 combined work (bits): 104
# parallel sessions: 4 	 work wagner (bits): 87 	 expected #attempts (bits): 4 	 combined work (bits): 91
# parallel sessions: 5 	 work wagner (bits): 79 	 expected #attempts (bits): 5 	 combined work (bits): 84
# parallel sessions: 6 	 work wagner (bits): 74 	 expected #attempts (bits): 6 	 combined work (bits): 80
# parallel sessions: 7 	 work wagner (bits): 70 	 expected #attempts (bits): 7 	 combined work (bits): 77
# parallel sessions: 8 	 work wagner (bits): 67 	 expected #attempts (bits): 8 	 combined work (bits): 75
# parallel sessions: 9 	 work wagner (bits): 65 	 expected #attempts (bits): 9 	 combined work (bits): 74
# parallel sessions: 10 	 work wagner (bits): 63 	 expected #attempts (bits): 10 	 combined work (bits): 73
# parallel sessions: 11 	 work wagner (bits): 61 	 expected #attempts (bits): 11 	 combined work (bits): 72
# parallel sessions: 12 	 work wagner (bits): 59 	 expected #attempts (bits): 12 	 combined work (bits): 71
# parallel sessions: 13 	 work wagner (bits): 58 	 expected #attempts (bits): 13 	 combined work (bits): 71
# parallel sessions: 14 	 work wagner (bits): 57 	 expected #attempts (bits): 14 	 combined work (bits): 71
# parallel sessions: 15 	 work wagner (bits): 56 	 expected #attempts (bits): 15 	 combined work (bits): 71
# parallel sessions: 16 	 work wagner (bits): 55 	 expected #attempts (bits): 16 	 combined work (bits): 71
# parallel sessions: 17 	 work wagner (bits): 54 	 expected #attempts (bits): 17 	 combined work (bits): 71
# parallel sessions: 18 	 work wagner (bits): 54 	 expected #attempts (bits): 18 	 combined work (bits): 72
# parallel sessions: 19 	 work wagner (bits): 53 	 expected #attempts (bits): 19 	 combined work (bits): 72
# parallel sessions: 20 	 work wagner (bits): 52 	 expected #attempts (bits): 20 	 combined work (bits): 72
# parallel sessions: 21 	 work wagner (bits): 52 	 expected #attempts (bits): 21 	 combined work (bits): 73
# parallel sessions: 22 	 work wagner (bits): 51 	 expected #attempts (bits): 22 	 combined work (bits): 73
# parallel sessions: 23 	 work wagner (bits): 51 	 expected #attempts (bits): 23 	 combined work (bits): 74
# parallel sessions: 24 	 work wagner (bits): 50 	 expected #attempts (bits): 24 	 combined work (bits): 74
# parallel sessions: 25 	 work wagner (bits): 50 	 expected #attempts (bits): 25 	 combined work (bits): 75
# parallel sessions: 26 	 work wagner (bits): 50 	 expected #attempts (bits): 26 	 combined work (bits): 76
# parallel sessions: 27 	 work wagner (bits): 49 	 expected #attempts (bits): 27 	 combined work (bits): 76
# parallel sessions: 28 	 work wagner (bits): 49 	 expected #attempts (bits): 28 	 combined work (bits): 77
# parallel sessions: 29 	 work wagner (bits): 49 	 expected #attempts (bits): 29 	 combined work (bits): 78
# parallel sessions: 30 	 work wagner (bits): 48 	 expected #attempts (bits): 30 	 combined work (bits): 78
# parallel sessions: 31 	 work wagner (bits): 48 	 expected #attempts (bits): 31 	 combined work (bits): 79
# parallel sessions: 32 	 work wagner (bits): 48 	 expected #attempts (bits): 32 	 combined work (bits): 80
# parallel sessions: 33 	 work wagner (bits): 47 	 expected #attempts (bits): 33 	 combined work (bits): 80
# parallel sessions: 34 	 work wagner (bits): 47 	 expected #attempts (bits): 34 	 combined work (bits): 81
# parallel sessions: 35 	 work wagner (bits): 47 	 expected #attempts (bits): 35 	 combined work (bits): 82
# parallel sessions: 36 	 work wagner (bits): 47 	 expected #attempts (bits): 36 	 combined work (bits): 83
# parallel sessions: 37 	 work wagner (bits): 46 	 expected #attempts (bits): 37 	 combined work (bits): 83
# parallel sessions: 38 	 work wagner (bits): 46 	 expected #attempts (bits): 38 	 combined work (bits): 84
# parallel sessions: 39 	 work wagner (bits): 46 	 expected #attempts (bits): 39 	 combined work (bits): 85
# parallel sessions: 40 	 work wagner (bits): 46 	 expected #attempts (bits): 40 	 combined work (bits): 86
# parallel sessions: 41 	 work wagner (bits): 46 	 expected #attempts (bits): 41 	 combined work (bits): 87
# parallel sessions: 42 	 work wagner (bits): 45 	 expected #attempts (bits): 42 	 combined work (bits): 87
# parallel sessions: 43 	 work wagner (bits): 45 	 expected #attempts (bits): 43 	 combined work (bits): 88
# parallel sessions: 44 	 work wagner (bits): 45 	 expected #attempts (bits): 44 	 combined work (bits): 89
# parallel sessions: 45 	 work wagner (bits): 45 	 expected #attempts (bits): 45 	 combined work (bits): 90
# parallel sessions: 46 	 work wagner (bits): 45 	 expected #attempts (bits): 46 	 combined work (bits): 91
# parallel sessions: 47 	 work wagner (bits): 45 	 expected #attempts (bits): 47 	 combined work (bits): 92
# parallel sessions: 48 	 work wagner (bits): 44 	 expected #attempts (bits): 48 	 combined work (bits): 92
# parallel sessions: 49 	 work wagner (bits): 44 	 expected #attempts (bits): 49 	 combined work (bits): 93
# parallel sessions: 50 	 work wagner (bits): 44 	 expected #attempts (bits): 50 	 combined work (bits): 94
# parallel sessions: 51 	 work wagner (bits): 44 	 expected #attempts (bits): 51 	 combined work (bits): 95
# parallel sessions: 52 	 work wagner (bits): 44 	 expected #attempts (bits): 52 	 combined work (bits): 96
# parallel sessions: 53 	 work wagner (bits): 44 	 expected #attempts (bits): 53 	 combined work (bits): 97
# parallel sessions: 54 	 work wagner (bits): 44 	 expected #attempts (bits): 54 	 combined work (bits): 98
# parallel sessions: 55 	 work wagner (bits): 44 	 expected #attempts (bits): 55 	 combined work (bits): 99
# parallel sessions: 56 	 work wagner (bits): 43 	 expected #attempts (bits): 56 	 combined work (bits): 99
# parallel sessions: 57 	 work wagner (bits): 43 	 expected #attempts (bits): 57 	 combined work (bits): 100
# parallel sessions: 58 	 work wagner (bits): 43 	 expected #attempts (bits): 58 	 combined work (bits): 101
# parallel sessions: 59 	 work wagner (bits): 43 	 expected #attempts (bits): 59 	 combined work (bits): 102
# parallel sessions: 60 	 work wagner (bits): 43 	 expected #attempts (bits): 60 	 combined work (bits): 103
# parallel sessions: 61 	 work wagner (bits): 43 	 expected #attempts (bits): 61 	 combined work (bits): 104
# parallel sessions: 62 	 work wagner (bits): 43 	 expected #attempts (bits): 62 	 combined work (bits): 105
# parallel sessions: 63 	 work wagner (bits): 43 	 expected #attempts (bits): 63 	 combined work (bits): 106
# parallel sessions: 64 	 work wagner (bits): 43 	 expected #attempts (bits): 64 	 combined work (bits): 107
# parallel sessions: 65 	 work wagner (bits): 42 	 expected #attempts (bits): 65 	 combined work (bits): 107
# parallel sessions: 66 	 work wagner (bits): 42 	 expected #attempts (bits): 66 	 combined work (bits): 108
# parallel sessions: 67 	 work wagner (bits): 42 	 expected #attempts (bits): 67 	 combined work (bits): 109
# parallel sessions: 68 	 work wagner (bits): 42 	 expected #attempts (bits): 68 	 combined work (bits): 110
# parallel sessions: 69 	 work wagner (bits): 42 	 expected #attempts (bits): 69 	 combined work (bits): 111
# parallel sessions: 70 	 work wagner (bits): 42 	 expected #attempts (bits): 70 	 combined work (bits): 112
# parallel sessions: 71 	 work wagner (bits): 42 	 expected #attempts (bits): 71 	 combined work (bits): 113
# parallel sessions: 72 	 work wagner (bits): 42 	 expected #attempts (bits): 72 	 combined work (bits): 114
# parallel sessions: 73 	 work wagner (bits): 42 	 expected #attempts (bits): 73 	 combined work (bits): 115
# parallel sessions: 74 	 work wagner (bits): 42 	 expected #attempts (bits): 74 	 combined work (bits): 116
# parallel sessions: 75 	 work wagner (bits): 42 	 expected #attempts (bits): 75 	 combined work (bits): 117
# parallel sessions: 76 	 work wagner (bits): 42 	 expected #attempts (bits): 76 	 combined work (bits): 118
# parallel sessions: 77 	 work wagner (bits): 41 	 expected #attempts (bits): 77 	 combined work (bits): 118
# parallel sessions: 78 	 work wagner (bits): 41 	 expected #attempts (bits): 78 	 combined work (bits): 119
# parallel sessions: 79 	 work wagner (bits): 41 	 expected #attempts (bits): 79 	 combined work (bits): 120
# parallel sessions: 80 	 work wagner (bits): 41 	 expected #attempts (bits): 80 	 combined work (bits): 121
# parallel sessions: 81 	 work wagner (bits): 41 	 expected #attempts (bits): 81 	 combined work (bits): 122
# parallel sessions: 82 	 work wagner (bits): 41 	 expected #attempts (bits): 82 	 combined work (bits): 123
# parallel sessions: 83 	 work wagner (bits): 41 	 expected #attempts (bits): 83 	 combined work (bits): 124
# parallel sessions: 84 	 work wagner (bits): 41 	 expected #attempts (bits): 84 	 combined work (bits): 125
# parallel sessions: 85 	 work wagner (bits): 41 	 expected #attempts (bits): 85 	 combined work (bits): 126
# parallel sessions: 86 	 work wagner (bits): 41 	 expected #attempts (bits): 86 	 combined work (bits): 127
# parallel sessions: 87 	 work wagner (bits): 41 	 expected #attempts (bits): 87 	 combined work (bits): 128
# parallel sessions: 88 	 work wagner (bits): 41 	 expected #attempts (bits): 88 	 combined work (bits): 129
# parallel sessions: 89 	 work wagner (bits): 41 	 expected #attempts (bits): 89 	 combined work (bits): 130
# parallel sessions: 90 	 work wagner (bits): 41 	 expected #attempts (bits): 90 	 combined work (bits): 131
# parallel sessions: 91 	 work wagner (bits): 41 	 expected #attempts (bits): 91 	 combined work (bits): 132
# parallel sessions: 92 	 work wagner (bits): 41 	 expected #attempts (bits): 92 	 combined work (bits): 133
# parallel sessions: 93 	 work wagner (bits): 40 	 expected #attempts (bits): 93 	 combined work (bits): 133
# parallel sessions: 94 	 work wagner (bits): 40 	 expected #attempts (bits): 94 	 combined work (bits): 134
# parallel sessions: 95 	 work wagner (bits): 40 	 expected #attempts (bits): 95 	 combined work (bits): 135
# parallel sessions: 96 	 work wagner (bits): 40 	 expected #attempts (bits): 96 	 combined work (bits): 136
# parallel sessions: 97 	 work wagner (bits): 40 	 expected #attempts (bits): 97 	 combined work (bits): 137
# parallel sessions: 98 	 work wagner (bits): 40 	 expected #attempts (bits): 98 	 combined work (bits): 138
# parallel sessions: 99 	 work wagner (bits): 40 	 expected #attempts (bits): 99 	 combined work (bits): 139
# parallel sessions: 100 	 work wagner (bits): 40 	 expected #attempts (bits): 100 	 combined work (bits): 140

# abort probability: 0.0078125
# parallel sessions: 3 	 work wagner (bits): 101 	 expected #attempts (bits): 21 	 combined work (bits): 122
# parallel sessions: 4 	 work wagner (bits): 87 	 expected #attempts (bits): 28 	 combined work (bits): 115
# parallel sessions: 5 	 work wagner (bits): 79 	 expected #attempts (bits): 35 	 combined work (bits): 114
# parallel sessions: 6 	 work wagner (bits): 74 	 expected #attempts (bits): 42 	 combined work (bits): 116
# parallel sessions: 7 	 work wagner (bits): 70 	 expected #attempts (bits): 49 	 combined work (bits): 119
# parallel sessions: 8 	 work wagner (bits): 67 	 expected #attempts (bits): 56 	 combined work (bits): 123
# parallel sessions: 9 	 work wagner (bits): 65 	 expected #attempts (bits): 63 	 combined work (bits): 128
# parallel sessions: 10 	 work wagner (bits): 63 	 expected #attempts (bits): 70 	 combined work (bits): 133
# parallel sessions: 11 	 work wagner (bits): 61 	 expected #attempts (bits): 77 	 combined work (bits): 138
# parallel sessions: 12 	 work wagner (bits): 59 	 expected #attempts (bits): 84 	 combined work (bits): 143
# parallel sessions: 13 	 work wagner (bits): 58 	 expected #attempts (bits): 91 	 combined work (bits): 149
# parallel sessions: 14 	 work wagner (bits): 57 	 expected #attempts (bits): 98 	 combined work (bits): 155

# abort probability: 0.001953125
# parallel sessions: 3 	 work wagner (bits): 101 	 expected #attempts (bits): 27 	 combined work (bits): 128
# parallel sessions: 4 	 work wagner (bits): 87 	 expected #attempts (bits): 36 	 combined work (bits): 123
# parallel sessions: 5 	 work wagner (bits): 79 	 expected #attempts (bits): 45 	 combined work (bits): 124
# parallel sessions: 6 	 work wagner (bits): 74 	 expected #attempts (bits): 54 	 combined work (bits): 128
# parallel sessions: 7 	 work wagner (bits): 70 	 expected #attempts (bits): 63 	 combined work (bits): 133
# parallel sessions: 8 	 work wagner (bits): 67 	 expected #attempts (bits): 72 	 combined work (bits): 139
# parallel sessions: 9 	 work wagner (bits): 65 	 expected #attempts (bits): 81 	 combined work (bits): 146
# parallel sessions: 10 	 work wagner (bits): 63 	 expected #attempts (bits): 90 	 combined work (bits): 153
# parallel sessions: 11 	 work wagner (bits): 61 	 expected #attempts (bits): 99 	 combined work (bits): 160