## CryptoDB

### Igor E. Shparlinski

#### Publications

**Year**

**Venue**

**Title**

2005

EPRINT

Elliptic Curves with Low Embedding Degree
Abstract

Motivated by the needs of the {\it pairing based cryptography\/}, Miyaji, Nakabayashi and Takano have suggested a construction of so-called MNT elliptic curves with low embedding degree. We give some heuristic arguments which suggest that there are only about $z^{1/2+o(1)}$ of MNT curves with complex multiplication discriminant up to $z$. We also show that there are very few finite fields over which elliptic curves with small embedding degree and small complex multiplication discriminant may exist (regardless of the way they are constructed).

2003

EPRINT

Hidden Number Problem in Small Subgroups
Abstract

Boneh and Venkatesan have proposed a polynomial time algorithm for
recovering a "hidden" element $\alpha \in \F_p$, where $p$ is prime, from rather short strings of the most significant bits of the residue of $\alpha t$ modulo $p$ for several randomly chosen $t\in \F_p$. Gonz{\'a}lez Vasco and the first author have recently extended this result to subgroups of $\F_p^*$ of order at least $p^{1/3+\varepsilon}$ for all $p$ and to subgroups of order at least $p^\varepsilon$ for almost all $p$. Here we introduce a new modification in the scheme which amplifies the uniformity of distribution of the `multipliers' $t$ and thus extend this result to subgroups of order at least $(\log p)/(\log \log p)^{1-\varepsilon}$ for all primes $p$. As in the above works, we give applications of our result to the bit security of the Diffie--Hellman secret key starting with subgroups of very small size, thus including all cryptographically interesting subgroups.

2002

EPRINT

Secure Bilinear Diffie-Hellman Bits
Abstract

The Weil and Tate pairings are a popular new
gadget in cryptography and have found many applications,
including identity-based cryptography.
In particular, the pairings have been used for key exchange
protocols.
This paper studies the bit security of keys obtained
using protocols based on pairings (that is,
we show that obtaining certain bits of the common key
is as hard as computing the entire key).
These results are valuable as they give insight into
how many ``hard-core'' bits can be obtained from
key exchange using pairings.

2000

EPRINT

On the Security of Diffie--Hellman Bits
Abstract

Boneh and Venkatesan have recently proposed a polynomial time
algorithm for recovering a "hidden" element $\alpha$ of a finite field $\F_p$ of $p$ elements from rather short strings of the most significant bits of the remainder modulo $p$ of $\alpha t$ for several
values of $t$ selected uniformly at random from $\F_p^*$. We use some
recent bounds of exponential sums to generalize this algorithm to the case when $t$ is selected from a quite small subgroup of $\F_p^*$.
Namely, our results apply to subgroups of size at least
$p^{1/3+ \varepsilon}$ for all primes $p$ and to subgroups of size at
least $p^{\varepsilon}$ for almost all primes $p$, for any fixed
$\varepsilon >0$.
We also use this generalization to improve (and correct)
one of the statements of the aforementioned work about the
computational security of the most significant bits of the
Diffie--Hellman key.

2000

EPRINT

Security of Polynomial Transformations of the Diffie--Hellman Key
Abstract

D. Boneh and R. Venkatesan have recently proposed an approachto proving that a reasonably small portions of most significant bits of the Diffie-Hellman key modulo a prime are as secure the the whole key. Some further improvements and generalizations have been obtained by I. M. Gonzales Vasco and I. E. Shparlinski. E. R. Verheul has obtained certain analogies of these results in the case of Diffie--Hellman keys in extensions of finite fields, when an oracle is given to compute a certain polynomial function of the key, for example, the trace in the background field. Here we obtain some new results in this direction concerning the case of so-called "unreliable" oracles.

2000

EPRINT

Security of the Most Significant Bits of the Shamir Message Passing Scheme
Abstract

Boneh and Venkatesan have recently proposed a polynomial time
algorithm for recovering a ``hidden'' element $\alpha$ of a
finite field $\F_p$ of $p$ elements from rather short
strings of the most significant bits of the remainder
mo\-du\-lo $p$ of $\alpha t$ for several values of $t$ selected uniformly
at random from $\F_p^*$. Unfortunately the applications to the
computational security of most significant bits
of private keys of some finite field exponentiation based cryptosystems
given by Boneh and Venkatesan are not quite correct. For the Diffie-Hellman
cryptosystem the
result of Boneh and Venkatesan has been corrected and
generalized in our recent paper.
Here a similar analysis is given for the Shamir message passing scheme.
The results depend on some bounds
of exponential sums.

#### Program Committees

- Eurocrypt 2012
- PKC 2012
- Crypto 2009
- PKC 2009
- PKC 2007
- Eurocrypt 2005
- Eurocrypt 2004
- PKC 2002

#### Coauthors

- William D. Banks (1)
- Dan Boneh (1)
- Don Coppersmith (1)
- Steven D. Galbraith (1)
- Herbie J. Hopkins (1)
- Arjen K. Lenstra (2)
- Wen-Ching W. Li (1)
- Daniel Lieman (1)
- Florian Luca (2)
- Oscar García Morchon (1)
- Mats Näslund (3)
- Phong Q. Nguyen (2)
- Ronald Rietman (1)
- Ludo Tolhuizen (1)
- Maria Isabel Gonzalez Vasco (3)
- William Whyte (1)
- Arne Winterhof (2)