Pronalaženje Booleovih funkcija maksimalne nelinearnosti evolucijskim računanjem

master's thesis

• Title (english): Evolutionary Computation Based Search for Maximal Nonlinearity Boolean Functions
• Author: Kristijan Vulinović
• Mentor: Marko Čupić (mentor)
• Committee member: Marko Čupić (predsjednik povjerenstva)
• Committee member: Željka Mihajlović (član povjerenstva)
• Committee member: Alan Jović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2019-09-23, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Booleove funkcije sastavni su element kriptografskih algoritama. Kako bi se povećala otpornost na napade linearnom kriptoanalizom, od posebnog je značaja svojstvo nelinearnosti Booleove funkcije. Booleove funkcije zadanog broja varijabli i maksimalne nelinearnosti nazivaju se Bent-funkcije, dok su sa stajališta primjene u kriptografskim algoritmima od posebnog interesa Booleove funkcije koje dodatno imaju i svojstvo balansiranosti.

U okviru ovog diplomskog rada proučeni su heuristički pristupi pronalaženja Booleovih funkcija maksimalne nelinearnosti te balansiranih Booleovih funkcija maksimalne nelinearnosti. Implementirani su i međusobno uspoređeni optimizacijski postupci temeljeni na simuliranom kaljenju, genetskom algoritmu i genetskom programiranju. Uspoređeni su i različiti načini prikazivanja Booleovih funkcija, poput zapisa u obliku tablice istinitosti te algebarskog zapisa, kao i razne funkcije izračuna dobrote rješenja u evolucijskim algoritmima. Dodatno je predložen i analiziran novi način pretrage traženih funkcija, temeljen na analizi Walsh koeficijenata funkcije.

Abstract (english)

Boolean functions represent a crucial element for designing cryptographic algorithms. In order to resist against linear cryptanalysis attack, it is essential for Boolean functions to have high nonlinearity. Bent functions are Boolean functions with maximal possible nonlinearity for a given number of variables. For the usage in cryptographic algorithms it is additionally important for functions to be balanced.

This thesis is based upon researching heuristic search methods for maximal nonlinear Boolean functions and maximal nonlinear balanced Boolean functions. Solutions based on simulated annealing, genetic algorithms and genetic programming are implemented and compared. The impact of different function representations, such as truth tables and algebraic notation is also analyzed, together with various fitness functions. Finally, a new method based on the analysis of Walsh coefficients for finding nonlinear functions is proposed.

• Keywords: Booleove funkcije; nelinearnost; heuristička optimizacija; evolucijski algoritmi
• Keywords (english): Boolean Functions; Nonlinearity; Heuristic Optimization; Evolutionary Algorithms
• Language: croatian
• URN:NBN: urn:nbn:hr:168:748295
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2020-01-07 23:05:05