I hope final thoughts.
These probablity calculations are based on the premise that:
1) The keypairs are random over the population (of potentially 35B keys!)
2) THe HIT generation maintains this random distribution (especially
for DEX HITs which are a fold of the ECDH public key)
Of course this is for the total HIT population for a given algorithm.
It is unlikely that all HITs will be in a single data collection. But
considering this is the age of big data, someone might be interested in
buliding such a database.
Finally, feel free to use these numbers in any paper on HIP.
On 05/05/2014 04:50 PM, Robert Moskowitz wrote:
On 05/05/2014 04:23 PM, Rene Struik wrote:
Hi Bob:
Let me clarify, the quantity p(k,n) below is the probability that k
randomly picked elements taken from an n-set are all different (i.e.,
no collision occurs). You may be looking for the probability of
having at least one collision, which is 1 - p(k,n).
I hope this helps.
that was it. I missed that smallish detail. thanks.
Rene
On 5/5/2014 4:19 PM, Robert Moskowitz wrote:
On 05/05/2014 03:32 PM, Rene Struik wrote:
Hi Bob:
The formula is roughly p(k,n)=1*(1-1/n)*(1-2/n)*...*(1 - {k-1}/n),
which can be approximated as roughly e^{-k^2/(2n)}, where n is the
size of the set one takes uniformly selected samples from and where
k is the number of drawn samples.
I am doing something wrong in LibreCalc with the formula:
=EXP(-(B6^2)/(2*C6))
Where B6 is the cell with K (3.86e+12) and C6 is n (2^96). I am
getting an answer of 99%.
Rene
On 5/5/2014 2:50 PM, Robert Moskowitz wrote:
On 05/04/2014 11:40 AM, Robert Moskowitz wrote:
What population of HIs is needed for a 1%, 10%, 50% probability
of a HIT collision?
I had the math once (like back in '99 or '00) and can't find it
(probably did not survive the Eudora to Thunderbird migration).
Thought I actually had this in a very early draft, but could not
find any such beast. Of course that would have been for HIPv1
HITs, not HIPv2.
Any help on the math would be appreciated. Also does it change
with PK algorithm or key length? (seems not to me).
Using the code at: http://en.wikipedia.org/wiki/Birthday_attack
and compiling and running it via:
http://www.compileonline.com/compile_cpp11_online.php
I get the following probablities for HIT collisions:
First the population of HITs (96 bits of hash) is: 7.9×10²^(8)
Then the probablities of collision are:
.01% 3.98076e+12
.1% 1.25911e+13
1% 3.99066e+13
10% 1.29209e+14
And thus if each person in the world (7B) had 5 endpoints with
HITs on them, the probablity
of a collision would be 10^-6 % (p=e-8, pop=3.98066e+10).
_______________________________________________
Hipsec mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/hipsec
--
email:[email protected] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
--
email:[email protected] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
_______________________________________________
Hipsec mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/hipsec
_______________________________________________
Hipsec mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/hipsec
