{"push_id":577331822,"size":1,"distinct_size":1,"ref":"refs/heads/master","head":"12c411fad27b37f51b904ae4d3419c279bb29ee7","before":"eb857741c706a433d5696c702795455db7c570ba","commits":[{"sha":"12c411fad27b37f51b904ae4d3419c279bb29ee7","author":{"email":"a48892d6e1c225014bc6a01fc59006b16d3c40da@securityinnovation.com","name":"John M. Schanck"},"message":"Fix incorrect inverse computation modulo (x-1)\n\nIn @897f0371 an error was introduced to the key generation routine that\ncaused a multiple of Phi = (x^N-1)/(x-1) to be added to all inverse\ncalculations. Let 'b' be the output of the inversion-mod-q routine on\ninput f. The effect of the bug is that\n\nb mod (x-1) = k (mod q)\n\nwhere k is related to the number of ones in f^(-1) mod 2. The correct\nvalue for b mod (x-1) is 1.\n\nThe exact value of k is given by T(T(T(T(c)))) where\nT(x) = -x^2 + (2 - N)*x (mod q)\nand c is the number of ones in f^(-1) mod 2. The four-fold\niteration of T is 2-to-1 on Z/qZ, and 1-to-1 on the set of even\nelements of Z/qZ. Since c is odd it can be recovered uniquely from k.\n\nSince h(1) = g(1)*b(1) = 1*k, the ones count of f^(-1) mod 2 is\nleaked through the public key. This gives the adversary a small\nadvantage in some combinatorial attacks.\n\nNote that the correct inverse was always computed modulo Phi, and\nall existing parameter sets use blinding polynomials, r, such that\nr(1) = 0 during encryption. Consequently there are no adverse effects\nother than the leakage of the ones count.","distinct":true,"url":"https://api.github.com/repos/NTRUOpenSourceProject/NTRUEncrypt/commits/12c411fad27b37f51b904ae4d3419c279bb29ee7"}]}