Name
Abstract | ||
|---|---|---|
We present polynomial time algorithms for certain generalizations of the hidden number problem which has played an important role in gaining understanding of the security of commonly suggested one way functions.Namely, we consider an analogue of this problem for a certain class of polynomials over an extension of a finite field; recovering a hidden polynomial given the values of its trace at randomly selected points. Also, we give an algorithm for a variant of the problem in free finite dimensional modules. This result can be helpful for studying security of analogues of the RSA and Diffie-Hellman cryptosystems over such modules.The hidden number problem is also related to the so called black-box field model of computation. We show that simplified versions of the above recovery problems can be used to derive positive results on the computational power of this model. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1007/3-540-45995-2_14 | LATIN |
Keywords | Field | DocType |
hidden polynomial,certain generalization,finite field,extension fields,black-box field model,hidden number problem,polynomial time algorithm,certain class,recovery problem,free finite dimensional module,diffie-hellman cryptosystems,one way function,model of computation | Randomized algorithm,Discrete mathematics,Finite field,Combinatorics,Polynomial,Generalization,Cryptography,Computer science,Cryptosystem,Model of computation,Time complexity | Conference |
Volume | ISSN | ISBN |
2286 | 0302-9743 | 3-540-43400-3 |
Citations | PageRank | References |
3 | 0.41 | 24 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| María Isabel Vasco | 1 | 137 | 16.70 |
| Mats Näslund | 2 | 141 | 21.58 |
| Igor E. Shparlinski | 3 | 1339 | 164.66 |