kevinlewi / fhipe Goto Github PK

I would like to ask you what is the maximum length of vector that can be calculated. I tried to generate encryption parameters for a vector of length 1000, but it took too long. Is it theoretically possible to generate encryption parameters of this order of magnitude, and in practice?

In the file "ipe.py", the decrypt algorithm calls solve_dlog_bsgs to find the descrete logorithm:

Line134: return solve_dlog_bsgs(t2, t1, max_innerprod+1)

This function implements the "baby-step, giant-step" algorithm. Its complexity should be O(\sqrt(max_innerprod + 1)), But the function looks like this:

def solve_dlog_bsgs(g, h, dlog_max):
  """
  Attempts to solve for the discrete log x, where g^x = h, using the Baby-Step 
  Giant-Step algorithm. Assumes that x is at most dlog_max.
  """

  alpha = int(math.ceil(math.sqrt(dlog_max))) + 1
  g_inv = g ** -1
  tb = {}
  for i in range(alpha + 1):
    tb[(g ** (i * alpha)).__str__()] = i
    for j in range(alpha + 1):
      s = (h * (g_inv ** j)).__str__()
      if s in tb:
        i = tb[s]
        return i * alpha + j
  return -1

The loop over j in the function is nested inside the loop over i, which means that the function still needs to make as many as \sqrt(max_innerprod + 1) loops. So it's not actually more efficient than function solve_dlog_naive, even though it performs correctly.
From my testing, the correct BSGS algorithm can be achieved by simply unindenting j's loop so that it is parallel to i's loop.

This is just my view and it might not be entirely right. I hope it helps, though.

Hello !
I use fhipe to calculate the inner products of vectors, and it works pretty well if the product is positive.
but when the expected inner product is negative, it cann't find the correct result.

Could you give me some threads on using it to calculate the nenative product?
Thank you very much!