Learning Nonlinearity of Boolean Functions: An Experimentation with Neural Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929695528845312 |
|---|---|
| author | Ranga, Sriram Chattopadhyay, Nandish Chattopadhyay, Anupam |
| author_facet | Ranga, Sriram Chattopadhyay, Nandish Chattopadhyay, Anupam |
| contents | This paper investigates the learnability of the nonlinearity property of Boolean functions using neural networks. We train encoder style deep neural networks to learn to predict the nonlinearity of Boolean functions from examples of functions in the form of a truth table and their corresponding nonlinearity values. We report empirical results to show that deep neural networks are able to learn to predict the property for functions in 4 and 5 variables with an accuracy above 95%. While these results are positive and a disciplined analysis is being presented for the first time in this regard, we should also underline the statutory warning that it seems quite challenging to extend the idea to higher number of variables, and it is also not clear whether one can get advantage in terms of time and space complexity over the existing combinatorial algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_01060 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Learning Nonlinearity of Boolean Functions: An Experimentation with Neural Networks Ranga, Sriram Chattopadhyay, Nandish Chattopadhyay, Anupam Machine Learning Artificial Intelligence Cryptography and Security This paper investigates the learnability of the nonlinearity property of Boolean functions using neural networks. We train encoder style deep neural networks to learn to predict the nonlinearity of Boolean functions from examples of functions in the form of a truth table and their corresponding nonlinearity values. We report empirical results to show that deep neural networks are able to learn to predict the property for functions in 4 and 5 variables with an accuracy above 95%. While these results are positive and a disciplined analysis is being presented for the first time in this regard, we should also underline the statutory warning that it seems quite challenging to extend the idea to higher number of variables, and it is also not clear whether one can get advantage in terms of time and space complexity over the existing combinatorial algorithms. |
| title | Learning Nonlinearity of Boolean Functions: An Experimentation with Neural Networks |
| topic | Machine Learning Artificial Intelligence Cryptography and Security |
| url | https://arxiv.org/abs/2502.01060 |