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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
ECCelliptic curvedomain parametersdiscrete logarithmDiffie-Hellman
Contact author(s)
martin ekera @ mil se
History
2015-09-13: received
Short URL
https://ia.cr/2015/879
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/879,
      author = {Martin Ekerå},
      title = {Computing information on domain parameters from public keys selected uniformly at random},
      howpublished = {Cryptology ePrint Archive, Paper 2015/879},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/879}},
      url = {https://eprint.iacr.org/2015/879}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.