International Association
for Cryptologic Research

After some discussion with my colleagues, we suspect that the proposed scheme is not transcript secure as it is vulnerable against the averaging attack from Gentry-Szydlo: see section 4.3 from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.3088&rep=rep1&type=pdf A message m is hashed into a ring element c. Then the signature is \\sigma = s*c+p*e over the ring, where s is the signing key, p is a small modular and e is the error follows Gaussian distribution. If you have enough pairs of (c_i, \\sigma_i = s*c_i+p*e_i) you can compute \\sum sigma_i and expect (\\sum e_i) to be close to 0. This is because e_i follows Gaussian distribution, so when you add a lot of samples from Gaussian distribution, you expect the sum to be very focused on 0. So the attacker knows both \\sum c_i and \\sum sigma_i = s*(\\sum c_i) with a non-negligible probability. Let Sigma = \\sum sigma_i and C = \\sum c_i. The pair of (Sigma, C) allows an attacker to forge a signature for a given message m\'. The attacker do the following: 1. c\' = hash(m\') 2. t = c\'/C 3. sigma\' = Sigma * t + p*e Then (c\', sigma\') is a valid signature satisfying verification formula: a*sigma\' = b * c\' mod p Zhenfei Zhang Security Innovation From: 2015-24-11 19:21:31 (UTC)