Probabilistic Estimation of the Algebraic Degree of Boolean Functions

Recently, our cryptography paper on "Probabilistic estimation of the algebraic degree of Boolean functions" was published in Springer Journal as a result of about 3 years of research: https://lnkd.in/eyEw5pce

𝐀𝐛𝐬𝐭𝐫𝐚𝐜𝐭: 𝘛𝘩𝘦 𝘢𝘭𝘨𝘦𝘣𝘳𝘢𝘪𝘤 𝘥𝘦𝘨𝘳𝘦𝘦 𝘪𝘴 𝘢𝘯 𝘪𝘮𝘱𝘰𝘳𝘵𝘢𝘯𝘵 𝘱𝘢𝘳𝘢𝘮𝘦𝘵𝘦𝘳 𝘰𝘧 𝘉𝘰𝘰𝘭𝘦𝘢𝘯 𝘧𝘶𝘯𝘤𝘵𝘪𝘰𝘯𝘴 𝘶𝘴𝘦𝘥 𝘪𝘯 𝘤𝘳𝘺𝘱𝘵𝘰𝘨𝘳𝘢𝘱𝘩𝘺. 𝘞𝘩𝘦𝘯 𝘢 𝘧𝘶𝘯𝘤𝘵𝘪𝘰𝘯 𝘪𝘯 𝘢 𝘭𝘢𝘳𝘨𝘦 𝘯𝘶𝘮𝘣𝘦𝘳 𝘰𝘧 𝘷𝘢𝘳𝘪𝘢𝘣𝘭𝘦𝘴 𝘪𝘴 𝘯𝘰𝘵 𝘨𝘪𝘷𝘦𝘯 𝘦𝘹𝘱𝘭𝘪𝘤𝘪𝘵𝘭𝘺 𝘪𝘯 𝘢𝘭𝘨𝘦𝘣𝘳𝘢𝘪𝘤 𝘯𝘰𝘳𝘮𝘢𝘭 𝘧𝘰𝘳𝘮, 𝘪𝘵 𝘪𝘴 𝘶𝘴𝘶𝘢𝘭𝘭𝘺 𝘯𝘰𝘵 𝘧𝘦𝘢𝘴𝘪𝘣𝘭𝘦 𝘵𝘰 𝘤𝘰𝘮𝘱𝘶𝘵𝘦 𝘪𝘵𝘴 𝘥𝘦𝘨𝘳𝘦𝘦, 𝘴𝘰 𝘸𝘦 𝘯𝘦𝘦𝘥 𝘵𝘰 𝘦𝘴𝘵𝘪𝘮𝘢𝘵𝘦 𝘪𝘵. 𝘞𝘦 𝘱𝘳𝘰𝘱𝘰𝘴𝘦 𝘢 𝘱𝘳𝘰𝘣𝘢𝘣𝘪𝘭𝘪𝘴𝘵𝘪𝘤 𝘵𝘦𝘴𝘵 𝘧𝘰𝘳 𝘥𝘦𝘤𝘪𝘥𝘪𝘯𝘨 𝘸𝘩𝘦𝘵𝘩𝘦𝘳 𝘵𝘩𝘦 𝘢𝘭𝘨𝘦𝘣𝘳𝘢𝘪𝘤 𝘥𝘦𝘨𝘳𝘦𝘦 𝘰𝘧 𝘢 𝘉𝘰𝘰𝘭𝘦𝘢𝘯 𝘧𝘶𝘯𝘤𝘵𝘪𝘰𝘯 𝘧 𝘪𝘴 𝘣𝘦𝘭𝘰𝘸 𝘢 𝘤𝘦𝘳𝘵𝘢𝘪𝘯 𝘷𝘢𝘭𝘶𝘦 𝘬. 𝘐𝘧 𝘵𝘩𝘦 𝘥𝘦𝘨𝘳𝘦𝘦 𝘪𝘴 𝘪𝘯𝘥𝘦𝘦𝘥 𝘣𝘦𝘭𝘰𝘸 𝘬, 𝘵𝘩𝘦𝘯 𝘧 𝘸𝘪𝘭𝘭 𝘢𝘭𝘸𝘢𝘺𝘴 𝘱𝘢𝘴𝘴 𝘵𝘩𝘦 𝘵𝘦𝘴𝘵, 𝘰𝘵𝘩𝘦𝘳𝘸𝘪𝘴𝘦 𝘧 𝘸𝘪𝘭𝘭 𝘧𝘢𝘪𝘭 𝘦𝘢𝘤𝘩 𝘪𝘯𝘴𝘵𝘢𝘯𝘤𝘦 𝘰𝘧 𝘵𝘩𝘦 𝘵𝘦𝘴𝘵 𝘸𝘪𝘵𝘩 𝘢 𝘱𝘳𝘰𝘣𝘢𝘣𝘪𝘭𝘪𝘵𝘺 𝘥𝘵_𝘬(𝘧), 𝘸𝘩𝘪𝘤𝘩 𝘪𝘴 𝘤𝘭𝘰𝘴𝘦𝘭𝘺 𝘳𝘦𝘭𝘢𝘵𝘦𝘥 𝘵𝘰 𝘵𝘩𝘦 𝘢𝘷𝘦𝘳𝘢𝘨𝘦 𝘯𝘶𝘮𝘣𝘦𝘳 𝘰𝘧 𝘮𝘰𝘯𝘰𝘮𝘪𝘢𝘭𝘴 𝘰𝘧 𝘥𝘦𝘨𝘳𝘦𝘦 𝘬 𝘰𝘧 𝘵𝘩𝘦 𝘱𝘰𝘭𝘺𝘯𝘰𝘮𝘪𝘢𝘭𝘴 𝘸𝘩𝘪𝘤𝘩 𝘢𝘳𝘦 𝘢𝘧𝘧𝘪𝘯𝘦 𝘦𝘲𝘶𝘪𝘷𝘢𝘭𝘦𝘯𝘵 𝘵𝘰 𝘧. 𝘛𝘩𝘦 𝘵𝘦𝘴𝘵 𝘩𝘢𝘴 𝘢 𝘨𝘰𝘰𝘥 𝘢𝘤𝘤𝘶𝘳𝘢𝘤𝘺 𝘰𝘯𝘭𝘺 𝘪𝘧 𝘵𝘩𝘪𝘴 𝘱𝘳𝘰𝘣𝘢𝘣𝘪𝘭𝘪𝘵𝘺 𝘥𝘵_𝘬(𝘧) 𝘰𝘧 𝘧𝘢𝘪𝘭𝘪𝘯𝘨 𝘵𝘩𝘦 𝘵𝘦𝘴𝘵 𝘪𝘴 𝘯𝘰𝘵 𝘵𝘰𝘰 𝘴𝘮𝘢𝘭𝘭. 𝘞𝘦 𝘪𝘯𝘪𝘵𝘪𝘢𝘵𝘦 𝘵𝘩𝘦 𝘴𝘵𝘶𝘥𝘺 𝘰𝘧 𝘥𝘵_𝘬(𝘧) 𝘣𝘺 𝘴𝘩𝘰𝘸𝘪𝘯𝘨 𝘵𝘩𝘢𝘵 𝘪𝘯 𝘵𝘩𝘦 𝘱𝘢𝘳𝘵𝘪𝘤𝘶𝘭𝘢𝘳 𝘤𝘢𝘴𝘦 𝘸𝘩𝘦𝘯 𝘵𝘩𝘦 𝘥𝘦𝘨𝘳𝘦𝘦 𝘰𝘧 𝘧 𝘪𝘴 𝘢𝘤𝘵𝘶𝘢𝘭𝘭𝘺 𝘦𝘲𝘶𝘢𝘭 𝘵𝘰 𝘬, 𝘵𝘩𝘦 𝘱𝘳𝘰𝘣𝘢𝘣𝘪𝘭𝘪𝘵𝘺 𝘸𝘪𝘭𝘭 𝘣𝘦 𝘪𝘯 𝘵𝘩𝘦 𝘪𝘯𝘵𝘦𝘳𝘷𝘢𝘭 (0.288788, 0.5], 𝘢𝘯𝘥 𝘵𝘩𝘦𝘳𝘦𝘧𝘰𝘳𝘦 𝘢 𝘴𝘮𝘢𝘭𝘭 𝘯𝘶𝘮𝘣𝘦𝘳 𝘰𝘧 𝘳𝘶𝘯𝘴 𝘰𝘧 𝘵𝘩𝘦 𝘵𝘦𝘴𝘵 𝘸𝘪𝘭𝘭 𝘣𝘦 𝘴𝘶𝘧𝘧𝘪𝘤𝘪𝘦𝘯𝘵 𝘵𝘰 𝘨𝘪𝘷𝘦, 𝘸𝘪𝘵𝘩 𝘷𝘦𝘳𝘺 𝘩𝘪𝘨𝘩 𝘱𝘳𝘰𝘣𝘢𝘣𝘪𝘭𝘪𝘵𝘺, 𝘵𝘩𝘦 𝘤𝘰𝘳𝘳𝘦𝘤𝘵 𝘢𝘯𝘴𝘸𝘦𝘳. 𝘌𝘹𝘢𝘤𝘵 𝘷𝘢𝘭𝘶𝘦𝘴 𝘰𝘧 𝘥𝘵_𝘬(𝘧) 𝘧𝘰𝘳 𝘢𝘭𝘭 𝘵𝘩𝘦 𝘱𝘰𝘭𝘺𝘯𝘰𝘮𝘪𝘢𝘭𝘴 𝘪𝘯 8 𝘷𝘢𝘳𝘪𝘢𝘣𝘭𝘦𝘴 𝘸𝘦𝘳𝘦 𝘤𝘰𝘮𝘱𝘶𝘵𝘦𝘥 𝘶𝘴𝘪𝘯𝘨 𝘵𝘩𝘦 𝘳𝘦𝘱𝘳𝘦𝘴𝘦𝘯𝘵𝘢𝘵𝘪𝘷𝘦𝘴 𝘭𝘪𝘴𝘵𝘦𝘥 𝘣𝘺 𝘏𝘰𝘶 𝘢𝘯𝘥 𝘣𝘺 𝘓𝘢𝘯𝘨𝘦𝘷𝘪𝘯 𝘢𝘯𝘥 𝘓𝘦𝘢𝘯𝘥𝘦𝘳.

On Homomorphic Encryption

Probably, one of the most exciting recent developments in the field of cryptography is the emergence of homomorphic encryption which is a type of encryption that allows computations to be performed on encrypted data while it remains encrypted, in other words, without the need to decrypt it first. This means that sensitive data can be kept confidential while still being used by third-parties.

This is achieved through the use of special encryption algorithms that preserve the mathematical structures of the plaintext data, allowing meaningful computations to be performed on the encrypted data while preventing unauthorized access to the actual plaintext data (which is never exposed and remain secure).

This technology is particularly useful in situations where privacy and security are of great importance, such as in the healthcare industry, where patient data must be kept confidential, or in financial services, where sensitive data such as bank account information needs to be processed securely. 

Cryptology vs. Cryptography vs. Cryptanalysis. What's the Difference?

Although the words cryptology, cryptography and cryptanalysis are used interchangeably — strictly speaking — they mean different things. Nowadays, we only use the word cryptography for everything; it's indeed a catch-all for a broad range of intertwined topics. Today’s post not only aims to point out the differences among them but also to show their connections to each other.

To begin with, cryptology is the mathematics, algorithms, and the applications of formulas that underpins cryptography and cryptanalysis. The world of cryptology goes from basic foundations in cryptography (code-making) to modern algebraic cryptanalysis (code-breaking). So, cryptology is clearly divided into two major parts: cryptography and cryptanalysis; with strong connections to each other, which include cryptographic applications, types of cryptography and their algorithms, code-breaking techniques, information theory, number theory and mathematical applications to encrypt data and also break ciphers. 

Curious About Cryptographic Boolean Functions?

In order to have a good understanding of cryptographic Boolean functions, let's get started from scratch, that's, having a look at the very basic concepts. To begin with, all modern computers are composed of very basic logic circuits using very basic gates, called operators which only apply to binary numbers, in other words, 0 and 1. Each type of gate implements a Boolean operation. The finite field ${\mathbb F}_{2}=\{0,1\}$ is also called binary field, and it is of special interest because it is particularly efficient for implementation in hardware or on a binary computer. Using these gates, the rules of Boolean algebra may be applied to design circuits that perform a variety of tasks. For example, integrated circuits. Then, these circuits are all put together to build into more powerful modern computers. 

Do You Want to Be a Cryptographer?

Alan Turing

I've always been interested in information security since 2003, but it wasn't until I enrolled on the cryptography module — while studying for a Master in Advanced Computer Science in England in 2018— that I started getting more keen on the mathematical side of cryptography; perhaps it was in part because I cherish mathematics and had the right cryptography teacher. What's more, I admire Alan Turing since he strove to do good work in difficult conditions during World War II; his work saved millions of lives. All of these things together inspired me to immerse myself in the world of cryptography.