-rw-r--r-- 2193 cryptattacktester-20230614/collision_prob.cpp raw
#include "queue_prob.h"
#include "collision_prob.h"

using namespace std;

template <typename big>
bigfloat generic_collision_average(big X,big Y,bigint r,bigfloat p)
{
  vector<bigfloat> phiX = queue_distribution(X,p,r);
  vector<bigfloat> phiY = queue_distribution(Y,p,r);

  bigfloat S = 0;
  bigfloat T = 0;
  for (bigint j = 0;j < r;++j) S += phiX.at(j);
  for (bigint j = 0;j < r;++j) T += phiY.at(j);
  S = 1-S;
  T = 1-T;

  bigfloat result = 0;
  result += (r*(r+1)/2)*S*T;
  for (bigint e = 1;e < r;++e)
    result += phiX.at(e)*(e*(e+1)/2+e*(r-e))*T;
  for (bigint f = 1;f < r;++f)
    result += phiY.at(f)*(f*(f+1)/2+f*(r-f))*S;
  for (bigint e = 1;e < r;++e)
    for (bigint f = 1;f < r;++f)
      if (e+f < r)
        result += phiX.at(e)*phiY.at(f)*e*f;
      else
        result += phiX.at(e)*phiY.at(f)*(e*f-(e+f-r)*(e+f-r-1)/2);

  return result/p;
}

bigfloat collision_average(bigint X,bigint Y,bigint r,bigfloat p)
{
  return generic_collision_average<bigint>(X,Y,r,p);
}

bigfloat collision_average(bigfloat X,bigfloat Y,bigint r,bigfloat p)
{
  return generic_collision_average<bigfloat>(X,Y,r,p);
}

bigfloat collision_lastmatch_prob(bigfloat numsuccesses,bigfloat numinputs,bigfloat numoutputs)
{
  // attack sees numsuccesses of the inputs
  // golden input is found with probability numsuccesses/inputs
  // but maybe other inputs are also found mapping to the same output
  // and maybe attack finds one of those instead: bad collision

  // model input-output mapping as uniform random
  // for each j between 1 and numsuccesses:
  // 1/numinputs chance that golden input is at position j
  // have numsuccesses-j inputs that could get in the way
  // each getting in the way with probability 1/numoutputs
  // so avoid bad collision with probability (1-1/numoutputs)^(numsuccesses-j)
  // total across j: ((1-1/numoutputs)^(numsuccesses-1)+...+(1-1/numoutputs)^1+(1-1/numoutputs)^0)/numinputs
  // i.e. (1-(1-1/numoutputs)^numsuccesses)*numoutputs/numinputs

  bigfloat x = log1p(-1/numoutputs); // log(1-1/numoutputs)
  x *= numsuccesses; // numsuccesses*log(1-1/numoutputs)
  x = -expm1(x); // 1-(1-1/numoutputs)^numsuccesses
  return x*numoutputs/numinputs;
}