Recursive weights for some Boolean functions
This paper studies degree 3 Boolean functions in n variables which are rotation symmetric, that is, invariant under any cyclic shift of the indices of the variables. These rotation symmetric functions have been extensively studied in the last dozen years or so because of their importance in cryptog...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2012-10-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/jmc-2011-0020 |
| _version_ | 1811182886241435648 |
|---|---|
| author | Brown Alyssa Cusick Thomas W. |
| author_facet | Brown Alyssa Cusick Thomas W. |
| author_sort | Brown Alyssa |
| collection | DOAJ |
| description | This paper studies degree 3 Boolean functions in n variables which are rotation symmetric, that is, invariant under any cyclic shift of the indices of the variables. These rotation symmetric functions have
been extensively studied in the last dozen years or so because of their importance in cryptography. Let denote the (Hamming) weight of the Boolean function f. We extend and simplify results
of Bileschi, Cusick and Padgett, who gave an algorithm for finding a recursion for the sequence
, where
is the cubic rotation symmetric function generated by the monomial We show that the weights for the function
(note this is just the sum of the first terms in the definition of )
satisfy the same recursion as the weights for . We prove the recursion for the weights of by a method based on the work by Bileschi–Cusick–Padgett, but
we are able to avoid a lot of the complications in their proofs. In particular, we do not need the technical notion of “g terms” or the elaborate proof of similarity of certain matrices. |
| first_indexed | 2024-04-11T09:38:03Z |
| format | Article |
| id | doaj.art-c5cf94c0cacf45b4a577ecd05d810731 |
| institution | Directory Open Access Journal |
| issn | 1862-2976 1862-2984 |
| language | English |
| last_indexed | 2024-04-11T09:38:03Z |
| publishDate | 2012-10-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Journal of Mathematical Cryptology |
| spelling | doaj.art-c5cf94c0cacf45b4a577ecd05d8107312022-12-22T04:31:31ZengDe GruyterJournal of Mathematical Cryptology1862-29761862-29842012-10-016210513510.1515/jmc-2011-0020Recursive weights for some Boolean functionsBrown Alyssa0Cusick Thomas W.1Department of Mathematics, University at Buffalo, 244 Math Building, Buffalo, NY 14260, USADepartment of Mathematics, University at Buffalo, 244 Math Building, Buffalo, NY 14260, USAThis paper studies degree 3 Boolean functions in n variables which are rotation symmetric, that is, invariant under any cyclic shift of the indices of the variables. These rotation symmetric functions have been extensively studied in the last dozen years or so because of their importance in cryptography. Let denote the (Hamming) weight of the Boolean function f. We extend and simplify results of Bileschi, Cusick and Padgett, who gave an algorithm for finding a recursion for the sequence , where is the cubic rotation symmetric function generated by the monomial We show that the weights for the function (note this is just the sum of the first terms in the definition of ) satisfy the same recursion as the weights for . We prove the recursion for the weights of by a method based on the work by Bileschi–Cusick–Padgett, but we are able to avoid a lot of the complications in their proofs. In particular, we do not need the technical notion of “g terms” or the elaborate proof of similarity of certain matrices.https://doi.org/10.1515/jmc-2011-0020boolean functionsrotation symmetryhamming weightrecursion |
| spellingShingle | Brown Alyssa Cusick Thomas W. Recursive weights for some Boolean functions Journal of Mathematical Cryptology boolean functions rotation symmetry hamming weight recursion |
| title | Recursive weights for some Boolean functions |
| title_full | Recursive weights for some Boolean functions |
| title_fullStr | Recursive weights for some Boolean functions |
| title_full_unstemmed | Recursive weights for some Boolean functions |
| title_short | Recursive weights for some Boolean functions |
| title_sort | recursive weights for some boolean functions |
| topic | boolean functions rotation symmetry hamming weight recursion |
| url | https://doi.org/10.1515/jmc-2011-0020 |
| work_keys_str_mv | AT brownalyssa recursiveweightsforsomebooleanfunctions AT cusickthomasw recursiveweightsforsomebooleanfunctions |