Hidden number problem with the trace and bit security of XTR and LUC

Wen Ching W. Li; Mats Näslund; Igor E. Shparlinski

doi:10.1007/3-540-45708-9_28

Hidden number problem with the trace and bit security of XTR and LUC

Wen Ching W. Li, Mats Näslund, Igor E. Shparlinski

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

19 Scopus citations

Abstract

We consider a certain generalization of the hidden number problem introduced by Boneh and Venkatesan in 1996. Considering the XTR variation of Diffie-Hellman, we apply our results to show security of the log^1/2 p most significant bits of the secret, in analogy to the results known for the classical Diffie-Hellman scheme. Our method is based on bounds of exponential sums which were introduced by Deligne in 1977. We proceed to show that the results are also applicable to the LUC scheme. Here, assuming the LUC function is one-way, we can in addition show that each single bit of the argument is a hard-core bit.

Original language	English (US)
Title of host publication	Advances in Cryptology - CRYPTO 2002 - 22nd Annual International Cryptology Conference, Proceedings
Editors	Moti Yung
Publisher	Springer Verlag
Pages	433-448
Number of pages	16
ISBN (Electronic)	354044050X, 9783540440505
DOIs	https://doi.org/10.1007/3-540-45708-9_28
State	Published - 2002
Event	22nd Annual International Cryptology Conference, CRYPTO 2002 - Santa Barbara, United States Duration: Aug 18 2002 → Aug 22 2002

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2442
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	22nd Annual International Cryptology Conference, CRYPTO 2002
Country/Territory	United States
City	Santa Barbara
Period	8/18/02 → 8/22/02

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-45708-9_28

Cite this

Li, W. C. W., Näslund, M., & Shparlinski, I. E. (2002). Hidden number problem with the trace and bit security of XTR and LUC. In M. Yung (Ed.), Advances in Cryptology - CRYPTO 2002 - 22nd Annual International Cryptology Conference, Proceedings (pp. 433-448). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2442). Springer Verlag. https://doi.org/10.1007/3-540-45708-9_28

Li, Wen Ching W. ; Näslund, Mats ; Shparlinski, Igor E. / Hidden number problem with the trace and bit security of XTR and LUC. Advances in Cryptology - CRYPTO 2002 - 22nd Annual International Cryptology Conference, Proceedings. editor / Moti Yung. Springer Verlag, 2002. pp. 433-448 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{62ee1d379e4141db83c3bac6ac9d46f7,

title = "Hidden number problem with the trace and bit security of XTR and LUC",

abstract = "We consider a certain generalization of the hidden number problem introduced by Boneh and Venkatesan in 1996. Considering the XTR variation of Diffie-Hellman, we apply our results to show security of the log1/2 p most significant bits of the secret, in analogy to the results known for the classical Diffie-Hellman scheme. Our method is based on bounds of exponential sums which were introduced by Deligne in 1977. We proceed to show that the results are also applicable to the LUC scheme. Here, assuming the LUC function is one-way, we can in addition show that each single bit of the argument is a hard-core bit.",

author = "Li, {Wen Ching W.} and Mats N{\"a}slund and Shparlinski, {Igor E.}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 22nd Annual International Cryptology Conference, CRYPTO 2002 ; Conference date: 18-08-2002 Through 22-08-2002",

year = "2002",

doi = "10.1007/3-540-45708-9_28",

language = "English (US)",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "433--448",

editor = "Moti Yung",

booktitle = "Advances in Cryptology - CRYPTO 2002 - 22nd Annual International Cryptology Conference, Proceedings",

address = "Germany",

}

Li, WCW, Näslund, M & Shparlinski, IE 2002, Hidden number problem with the trace and bit security of XTR and LUC. in M Yung (ed.), Advances in Cryptology - CRYPTO 2002 - 22nd Annual International Cryptology Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2442, Springer Verlag, pp. 433-448, 22nd Annual International Cryptology Conference, CRYPTO 2002, Santa Barbara, United States, 8/18/02. https://doi.org/10.1007/3-540-45708-9_28

Hidden number problem with the trace and bit security of XTR and LUC. / Li, Wen Ching W.; Näslund, Mats; Shparlinski, Igor E.
Advances in Cryptology - CRYPTO 2002 - 22nd Annual International Cryptology Conference, Proceedings. ed. / Moti Yung. Springer Verlag, 2002. p. 433-448 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2442).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Hidden number problem with the trace and bit security of XTR and LUC

AU - Li, Wen Ching W.

AU - Näslund, Mats

AU - Shparlinski, Igor E.

PY - 2002

Y1 - 2002

N2 - We consider a certain generalization of the hidden number problem introduced by Boneh and Venkatesan in 1996. Considering the XTR variation of Diffie-Hellman, we apply our results to show security of the log1/2 p most significant bits of the secret, in analogy to the results known for the classical Diffie-Hellman scheme. Our method is based on bounds of exponential sums which were introduced by Deligne in 1977. We proceed to show that the results are also applicable to the LUC scheme. Here, assuming the LUC function is one-way, we can in addition show that each single bit of the argument is a hard-core bit.

AB - We consider a certain generalization of the hidden number problem introduced by Boneh and Venkatesan in 1996. Considering the XTR variation of Diffie-Hellman, we apply our results to show security of the log1/2 p most significant bits of the secret, in analogy to the results known for the classical Diffie-Hellman scheme. Our method is based on bounds of exponential sums which were introduced by Deligne in 1977. We proceed to show that the results are also applicable to the LUC scheme. Here, assuming the LUC function is one-way, we can in addition show that each single bit of the argument is a hard-core bit.

UR - http://www.scopus.com/inward/record.url?scp=84937417839&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84937417839&partnerID=8YFLogxK

U2 - 10.1007/3-540-45708-9_28

DO - 10.1007/3-540-45708-9_28

M3 - Conference contribution

AN - SCOPUS:84937417839

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 433

EP - 448

BT - Advances in Cryptology - CRYPTO 2002 - 22nd Annual International Cryptology Conference, Proceedings

A2 - Yung, Moti

PB - Springer Verlag

T2 - 22nd Annual International Cryptology Conference, CRYPTO 2002

Y2 - 18 August 2002 through 22 August 2002

ER -

Li WCW, Näslund M, Shparlinski IE. Hidden number problem with the trace and bit security of XTR and LUC. In Yung M, editor, Advances in Cryptology - CRYPTO 2002 - 22nd Annual International Cryptology Conference, Proceedings. Springer Verlag. 2002. p. 433-448. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45708-9_28

Hidden number problem with the trace and bit security of XTR and LUC

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this