Bent function (original) (raw)
In the mathematical field of combinatorics, a bent function is a special type of Boolean function which is maximally non-linear; it is as different as possible from the set of all linear and affine functions when measured by Hamming distance between truth tables. Concretely, this means the maximum correlation between the output of the function and a linear function is minimal. In addition, the derivatives of a bent function are a balanced Boolean functions, so for any change in the input variables there is a 50 percent chance that the output value will change.
| Property | Value |
|---|---|
| dbo:abstract | In the mathematical field of combinatorics, a bent function is a special type of Boolean function which is maximally non-linear; it is as different as possible from the set of all linear and affine functions when measured by Hamming distance between truth tables. Concretely, this means the maximum correlation between the output of the function and a linear function is minimal. In addition, the derivatives of a bent function are a balanced Boolean functions, so for any change in the input variables there is a 50 percent chance that the output value will change. The maximal nonlinearity means approximating a bent function by an affine (linear) function is hard, a useful property in the defense against linear cryptanalysis. In addition, detecting a change in the output of the function yields no information about what change occurred in the inputs, making the function immune to differential cryptanalysis. Bent functions were defined and named in the 1960s by in research not published until 1976. They have been extensively studied for their applications in cryptography, but have also been applied to spread spectrum, coding theory, and combinatorial design. The definition can be extended in several ways, leading to different classes of generalized bent functions that share many of the useful properties of the original. It is known that V. A. Eliseev and O. P. Stepchenkov studied bent functions, which they called minimal functions, in the USSR in 1962. However, their results have still not been declassified. Bent functions are also known as perfectly nonlinear (PN) boolean functions. Certain functions which are as close as possible to perfect nonlinearity (e.g. for functions of an odd number of bits, or vectorial functions) are known as almost perfectly nonlinear (APN). (en) Une fonction booléenne avec un nombre pair de variables est dite fonction courbe — bent dans la terminologie anglosaxonne — si sa non-linéarité est maximale. Cela correspond à être à distance maximale — pour la distance de Hamming — de l'ensemble des fonctions booléennes linéaires, encore appelé code de Reed et Müller d'ordre 1. On dispose d'une borne générale sur la non-linéarité des fonctions booléennes, mais cette borne ne peut être atteinte que lorsque le nombre de variables est pair. De plus, dans ce cas, on sait construire des fonctions atteignant cette borne, par exemple la fonction est courbe. L'ensemble des fonctions affines formant un espace vectoriel sur le corps à deux éléments, il est facile de voir que si est courbe, toute fonction , avec fonction affine, est également courbe, puisque dans ce cas et sont à la même distance de l'ensemble des fonctions affines. Cet objet mathématique a été introduit par O. Rothaus en 1976 (mais il le connaissait déjà durant les années 1960). Les propriétés hautement non-linéaires des fonctions courbes sont utilisées en cryptologie pour constituer des S-Boxes (tables de substitution) comme dans le chiffrement CAST-128, ce principe a été considéré dès 1992 par C. Adams dans "On immunity against Biham and Shamir's differential cryptanalysis". Une fonction courbe a l'avantage d'avoir un spectre plat (voir transformée de Fourier ou transformation de Hadamard-Walsh), ce qui fait qu'il n'existe pas de «bonne» approximation linéaire. Vu la définition de ces fonctions, cela paraît naturel. Cette caractéristique permet de contrer la cryptanalyse linéaire. Un inconvénient important de ces fonctions est de ne pas être équilibrées : elles ne peuvent pas prendre autant de fois la valeur 0 que la valeur 1. De ce fait, certaines applications sont à exclure car le biais introduit par une fonction courbe rendrait le système de chiffrement vulnérable à des attaques différentes de la cryptanalyse linéaire. D'une certaine manière c'est un problème récurrent dans la conception d'algorithmes de chiffrements symétriques : on ne peut pas simultanément avoir la meilleure résistance à toutes les attaques connues. Les fonctions courbes sont optimales pour la cryptanalyse linéaire, mais pas pour les attaques par corrélation par exemple. (fr) Бент-функция (от англ. bent — «изогнутый, наклонённый», ) — булева функция с чётным числом переменных, для которой расстояние Хэмминга от множества аффинных булевых функций с тем же числом переменных максимально. Бент-функции в этом смысле обладают максимальной степенью нелинейности среди всех функций с данным числом переменных и благодаря этому широко применяются в криптографии для создания шифров, максимально устойчивых к методам линейного и дифференциального криптоанализа. В русскоязычной литературе используется близкий по смыслу термин «максимально нелинейная функция», число переменных таких функций не ограничивается чётными числами. Максимально нелинейная функция с чётным числом переменных является бент-функцией . (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Boolean_functions_like_1000_nonlinearity.svg?width=300 |
| dbo:wikiPageExternalLink | https://archive.org/details/handbookofcombin0000unse/page/337 |
| dbo:wikiPageID | 24465207 (xsd:integer) |
| dbo:wikiPageLength | 23399 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1097443528 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Monomial dbr:Algebraic_normal_form dbr:Degree_of_a_polynomial dbr:Interpolation_attack dbr:Column_vector dbr:Cryptographic_hash_function dbr:Cryptography dbr:Mathematics dbr:Modular_arithmetic dbr:Block_ciphers dbr:Confusion_and_diffusion dbr:Correlation_attack dbr:Correlation_coefficient dbr:Correlation_immunity dbr:Cross-correlation dbr:Equivalence_class dbr:Combinatorial_design dbr:Combinatorics dbr:Hamming_weight dbr:Spread_spectrum dbr:Autocorrelation dbr:CDMA dbr:CRC_Press dbr:Truth_table dbr:HAVAL dbr:Linear_cryptanalysis dbr:Linear_map dbr:Absolute_value dbc:Combinatorics dbc:Symmetric-key_cryptography dbr:Duality_(mathematics) dbr:Finite_field dbr:Balanced_boolean_function dbr:Carlisle_Adams dbr:Differential_cryptanalysis dbr:Gold_code dbr:Grain_(cipher) dbc:Boolean_algebra dbr:Hamming_distance dbr:Boolean_derivative dbr:Prime_number dbr:S-box dbc:Theory_of_cryptography dbr:Kasami_code dbr:Bijection dbr:Coding_theory dbr:Homogeneous_polynomial dbr:Dot_product dbr:Boolean_function dbr:CAST-128 dbr:CAST-256 dbr:Maximum_length_sequence dbr:Walsh_matrix dbr:Walsh_transform dbr:NLFSR dbr:Stafford_Tavares dbr:Stream_cipher dbr:Lexicographical_order dbr:Affine_function dbr:Strict_avalanche_criterion dbr:File:0001_0001_0001_1110_nonlinearity.svg dbr:File:Boolean_functions_like_1000_nonlinearity.svg dbr:Oscar_Rothaus |
| dbp:wikiPageUsesTemplate | dbt:Defn dbt:= dbt:Cite_book dbt:Cite_conference dbt:Cite_journal dbt:Frac dbt:Reflist dbt:Short_description dbt:Sup_sub dbt:Paragraph dbt:Glossary dbt:Glossary_end dbt:Abs |
| dcterms:subject | dbc:Combinatorics dbc:Symmetric-key_cryptography dbc:Boolean_algebra dbc:Theory_of_cryptography |
| rdfs:comment | In the mathematical field of combinatorics, a bent function is a special type of Boolean function which is maximally non-linear; it is as different as possible from the set of all linear and affine functions when measured by Hamming distance between truth tables. Concretely, this means the maximum correlation between the output of the function and a linear function is minimal. In addition, the derivatives of a bent function are a balanced Boolean functions, so for any change in the input variables there is a 50 percent chance that the output value will change. (en) Une fonction booléenne avec un nombre pair de variables est dite fonction courbe — bent dans la terminologie anglosaxonne — si sa non-linéarité est maximale. Cela correspond à être à distance maximale — pour la distance de Hamming — de l'ensemble des fonctions booléennes linéaires, encore appelé code de Reed et Müller d'ordre 1. On dispose d'une borne générale sur la non-linéarité des fonctions booléennes, mais cette borne ne peut être atteinte que lorsque le nombre de variables est pair. De plus, dans ce cas, on sait construire des fonctions atteignant cette borne, par exemple la fonction (fr) Бент-функция (от англ. bent — «изогнутый, наклонённый», ) — булева функция с чётным числом переменных, для которой расстояние Хэмминга от множества аффинных булевых функций с тем же числом переменных максимально. Бент-функции в этом смысле обладают максимальной степенью нелинейности среди всех функций с данным числом переменных и благодаря этому широко применяются в криптографии для создания шифров, максимально устойчивых к методам линейного и дифференциального криптоанализа. (ru) |
| rdfs:label | Bent function (en) Fonction courbe (fr) Бент-функция (ru) Бент-функція (uk) |
| owl:sameAs | freebase:Bent function yago-res:Bent function wikidata:Bent function dbpedia-fr:Bent function dbpedia-ru:Bent function dbpedia-uk:Bent function https://global.dbpedia.org/id/4Y2gc |
| prov:wasDerivedFrom | wikipedia-en:Bent_function?oldid=1097443528&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/0001_0001_0001_1110_nonlinearity.svg wiki-commons:Special:FilePath/Boolean_functions_like_1000_nonlinearity.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Bent_function |
| is dbo:wikiPageRedirects of | dbr:Crooked_function dbr:Hyper-bent_function dbr:Almost_bent_function dbr:Partially_bent_function dbr:Bent_sequence dbr:Semi-bent_function |
| is dbo:wikiPageWikiLink of | dbr:Index_of_cryptography_articles dbr:Lilya_Budaghyan dbr:Logical_conjunction dbr:Combinatorial_design dbr:List_of_Boolean_algebra_topics dbr:Affine_transformation dbr:Balanced_boolean_function dbr:Carlisle_Adams dbr:Jennifer_Seberry dbr:S-box dbr:Hidden_shift_problem dbr:Avalanche_effect dbr:Boolean_function dbr:CAST-128 dbr:Simon_(cipher) dbr:Crooked_function dbr:Hyper-bent_function dbr:Almost_bent_function dbr:Partially_bent_function dbr:Bent_sequence dbr:Semi-bent_function |
| is foaf:primaryTopic of | wikipedia-en:Bent_function |
