Growth of the ideal generated by a quadratic Boolean function

Jintai Ding; Timothy J. Hodges; Victoria Kruglov

doi:10.1007/978-3-642-12929-2_2

Growth of the ideal generated by a quadratic Boolean function

Jintai Ding^*, Timothy J. Hodges, Victoria Kruglov

^*Corresponding author for this work

University of Cincinnati

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

5 Citations (Scopus)

Abstract

We give exact formulas for the growth of the ideal Aλ for λ a quadratic element of the algebra of Boolean functions over the Galois field GF(2). That is, we calculate dim A_kλ where A_k is the subspace of elements of degree less than or equal to k. These results clarify some of the assertions made in the article of Yang, Chen and Courtois [22,23] concerning the efficiency of the XL algorithm.

Original language	English
Title of host publication	Post-Quantum Cryptography - Third International Workshop, PQCrypto 2010, Proceedings
Pages	13-27
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-642-12929-2_2
Publication status	Published - 2010
Externally published	Yes
Event	3rd International Workshop on Post-Quantum Cryptography, PQCrypto 2010 - Darmstadt, Germany Duration: 25 May 2010 → 28 May 2010

Publication series

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

Conference

Conference	3rd International Workshop on Post-Quantum Cryptography, PQCrypto 2010
Country/Territory	Germany
City	Darmstadt
Period	25/05/10 → 28/05/10

Access to Document

10.1007/978-3-642-12929-2_2

Cite this

Ding, J., Hodges, T. J., & Kruglov, V. (2010). Growth of the ideal generated by a quadratic Boolean function. In Post-Quantum Cryptography - Third International Workshop, PQCrypto 2010, Proceedings (pp. 13-27). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6061 LNCS). https://doi.org/10.1007/978-3-642-12929-2_2

@inproceedings{2f0b73abd48344ce92ac9cf0d7d3b060,

title = "Growth of the ideal generated by a quadratic Boolean function",

abstract = "We give exact formulas for the growth of the ideal Aλ for λ a quadratic element of the algebra of Boolean functions over the Galois field GF(2). That is, we calculate dim Akλ where Ak is the subspace of elements of degree less than or equal to k. These results clarify some of the assertions made in the article of Yang, Chen and Courtois [22,23] concerning the efficiency of the XL algorithm.",

author = "Jintai Ding and Hodges, {Timothy J.} and Victoria Kruglov",

year = "2010",

doi = "10.1007/978-3-642-12929-2_2",

language = "English",

isbn = "3642129285",

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

pages = "13--27",

booktitle = "Post-Quantum Cryptography - Third International Workshop, PQCrypto 2010, Proceedings",

note = "3rd International Workshop on Post-Quantum Cryptography, PQCrypto 2010 ; Conference date: 25-05-2010 Through 28-05-2010",

}

Ding, J, Hodges, TJ & Kruglov, V 2010, Growth of the ideal generated by a quadratic Boolean function. in Post-Quantum Cryptography - Third International Workshop, PQCrypto 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6061 LNCS, pp. 13-27, 3rd International Workshop on Post-Quantum Cryptography, PQCrypto 2010, Darmstadt, Germany, 25/05/10. https://doi.org/10.1007/978-3-642-12929-2_2

Growth of the ideal generated by a quadratic Boolean function. / Ding, Jintai; Hodges, Timothy J.; Kruglov, Victoria.
Post-Quantum Cryptography - Third International Workshop, PQCrypto 2010, Proceedings. 2010. p. 13-27 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6061 LNCS).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

TY - GEN

T1 - Growth of the ideal generated by a quadratic Boolean function

AU - Ding, Jintai

AU - Hodges, Timothy J.

AU - Kruglov, Victoria

PY - 2010

Y1 - 2010

N2 - We give exact formulas for the growth of the ideal Aλ for λ a quadratic element of the algebra of Boolean functions over the Galois field GF(2). That is, we calculate dim Akλ where Ak is the subspace of elements of degree less than or equal to k. These results clarify some of the assertions made in the article of Yang, Chen and Courtois [22,23] concerning the efficiency of the XL algorithm.

AB - We give exact formulas for the growth of the ideal Aλ for λ a quadratic element of the algebra of Boolean functions over the Galois field GF(2). That is, we calculate dim Akλ where Ak is the subspace of elements of degree less than or equal to k. These results clarify some of the assertions made in the article of Yang, Chen and Courtois [22,23] concerning the efficiency of the XL algorithm.

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

U2 - 10.1007/978-3-642-12929-2_2

DO - 10.1007/978-3-642-12929-2_2

M3 - Conference Proceeding

AN - SCOPUS:77954402021

SN - 3642129285

SN - 9783642129285

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

SP - 13

EP - 27

BT - Post-Quantum Cryptography - Third International Workshop, PQCrypto 2010, Proceedings

T2 - 3rd International Workshop on Post-Quantum Cryptography, PQCrypto 2010

Y2 - 25 May 2010 through 28 May 2010

ER -

Growth of the ideal generated by a quadratic Boolean function

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this