stefannelson
commented
3 years ago It looks like this problem occurs during certain parameters. Specifically,
- N is prime.
- p, q are relatively prime.
- q >> p. From standard parameters, it appears that p=3 seems to be common so we will fix this parameter for simplicity.
For each of these, I did a check in 'main.py' that generates keys, encrypts, decrypts, and returns a truth value if the original message matches the decrypted message. I ran some tests with the following parameters, each with df, dg, dr = 7,6,5 :
Adjusting N:
N,p,q = 71, 3, 61 returns True.
N,p,q = 199, 3, 61 returns True.
N,p,q = 941, 3, 61 returns True.
N,p,q = 2129, 3, 61 returns True.
Adjusting q:
N,p,q = 167, 3, 61 returns True.
N,p,q = 167, 3, 47 returns True.
N,p,q = 167, 3, 62 raises a 'NotInvertible' error.
The problem appears to be with q. However,
N,p,q = 167, 3, 61 and df,dg,dr = 100,99,98 returns False.
N,p,q = 167, 3, 61 and df,dg,dr = 166,66,5 returns True.
N,p,q = 167, 3, 61 and df,dg,dr = 166,66,35 returns True or False. Probability of failing seems to drop off around dr = 20.
It appears that higher values for how many +- 1 coefficients are inserted in polynomial r affect whether or not encryption/decryption works.
Conclusion: Encryption/Decryption does not appear to work for large trinary polynomials for functions f, g, and r if we have q>61 (otherwise it crashes) and/or dr between 20 and 25 (still runs, but increases likelihood of failing).
In
parameters.py, changing the security level (N,p,q) to any setting other than low (11,3,61) causes a zero divisor error.sympy.polys.polyerrors.NotInvertible: zero divisor.