Paper 2015/879

Computing information on domain parameters from public keys selected uniformly at random

Martin Ekerå

Abstract

The security of many cryptographic schemes and protocols rests on the conjectured computational intractability of the discrete logarithm problem in some group <g> of prime order. Such schemes and protocols require domain parameters that specify <g> and a specific generator g. In this paper we consider the problem of computing information on the domain parameters from public keys selected uniformly at random from <g>. We show that it is not possible to compute any information on the generator g regardless of the number of public keys observed. In the case of elliptic curves E(GF(p)) or E(GF(2^n)) on short Weierstrass form, or E(K) on Edwards form, twisted Edwards form or Montgomery form, where K is a non-binary field, we show how to compute the domain parameters excluding the generator from four keys on affine form. Hence, if the domain parameters excluding the generator are to be kept private, points may not be transmitted on affine form. It is an open question whether point compression is a sufficient requirement. Regardless of whether points are transmitted on affine or compressed form, it is in general possible to create a distinguisher for the domain parameters, excluding the generator, both in the case of the elliptic curve groups previously mentioned, and in the case of multiplicative subgroups of GF(p). We propose that a good method for preventing all of the above attacks may be to use blinding schemes, and suggest new applications for existing blinding schemes originally designed for steganographic applications.