La cryptographie à base de réseaux euclidiens est un domaine prometteur pour la construction de primitives cryptographiques post-quantiques. Un problème fondamental, lié aux réseaux, est le problème du plus court vecteur (ou SVP, pour Shortest Vector Problem). Ce problème est supposé être difficile à résoudre même avec un ordinateur quantique. Afin d’améliorer l’efficacité des protocoles cryptographiques, on peut utiliser des réseaux structurés, comme par exemple des réseaux idéaux ou des réseaux modules (qui sont une généralisation des réseaux idéaux). La sécurité de la plupart des schémas utilisant des réseaux structurés dépend de la difficulté du problème SVP dans des réseaux modules, mais un petit nombre de schémas peuvent également être impactés par SVP dans des réseaux idéaux. La principale construction pouvant être impactée par SVP dans des réseaux idéaux est la fonction multilinéaire GGH13. Cette fonction multilinéaire est principalement utilisée aujourd’hui pour construire des obfuscateurs de programmes, c’est-à-dire des fonctions qui prennent en entrée le code d’un programme et renvoie le code d’un programme équivalent (calculant la même fonction), mais qui doit cacher la façon dont le programme fonctionne.Dans cette thèse, nous nous intéressons dans un premier temps au problème SVP dans les réseaux idéaux et modules. Nous présentons un premier algorithme qui, après un pre-calcul exponentiel, permet de trouver des vecteurs courts dans des réseaux idéaux plus rapidement que le meilleur algorithme connu pour des réseaux arbitraires. Nous présentons ensuite un algorithme pour les réseaux modules de rang 2, également plus efficace que le meilleur algorithme connu pour des réseaux arbitraires, à condition d’avoir accès à un oracle résolvant le problème du plus proche vecteur dans un réseau fixé. Le pré-calcul exponentiel et l’oracle pour le problème du plus proche vecteurs rendent ces deux algorithmes inutilisables en pratique.Dans un second temps, nous nous intéressons à la fonction GGH13 ainsi qu’aux obfuscateurs qui l’utilisent. Nous étudions d’abord l’impact des attaques statistiques sur la fonction GGH13 et ses variantes. Nous nous intéressons ensuite à la sécurité des obfuscateurs utilisant la fonction GGH13 et proposons une attaque quantique contre plusieurs de ces obfuscateurs. Cette attaque quantique utilise entre autres un algorithme calculant un vecteur court dans un réseau idéal dépendant d’un paramètre secret de la fonction GGH13. / Lattice-based cryptography is a promising area for constructing cryptographic primitives that are plausibly secure even in the presence of quantum computers. A fundamental problem related to lattices is the shortest vector problem (or SVP), which asks to find a shortest non-zero vector in a lattice. This problem is believed to be intractable, even quantumly. Structured lattices, for example ideal lattices or module lattices (the latter being a generalization of the former), are often used to improve the efficiency of lattice-based primitives. The security of most of the schemes based on structured lattices is related to SVP in module lattices, and a very small number of schemes can also be impacted by SVP in ideal lattices.In this thesis, we first focus on the problem of finding short vectors in ideal and module lattices.We propose an algorithm which, after some exponential pre-computation, performs better on ideal lattices than the best known algorithm for arbitrary lattices. We also present an algorithm to find short vectors in rank 2 modules, provided that we have access to some oracle solving the closest vector problem in a fixed lattice. The exponential pre-processing time and the oracle call make these two algorithms unusable in practice.The main scheme whose security might be impacted by SVP in ideal lattices is the GGH13multilinear map. This protocol is mainly used today to construct program obfuscators, which should render the code of a program unintelligible, while preserving its functionality. In a second part of this thesis, we focus on the GGH13 map and its application to obfuscation. We first study the impact of statistical attacks on the GGH13 map and on its variants. We then study the security of obfuscators based on the GGH13 map and propose a quantum attack against multiple such obfuscators. This quantum attack uses as a subroutine an algorithm to find a short vector in an ideal lattice related to a secret element of the GGH13 map.

<p>The Global System for Mobile Communications (GSM) is the most widely used cellular technology in the world. Approximately 800 million people around the world are using GSM for different purposes, but mostly for voice communication and SMS. For GSM, like many other widely used systems, security is crucial. The security involves mechanisms used to protect the different shareholders, like subscribers and service providers. The aspects of security that this report covers are mainly anonymity, authentication and confidentiality. </p><p>The important aspects of the system that need protection are described, along with the implementation of mechanisms used for the protection. It appears that many of the very valuable aspects of GSM can be attacked. </p><p>The anonymity of a GSM user is compromised resulting in the attacker being able to observe the time, rate, length, sources or destinations of e g calls. Even tracking a subscriber’s movements becomes possible. However, a passive attack is not sufficient to perform these attacks. The attacker needs to mount an active attack using equipment offering base station functionality. </p><p>Authentication is a crucial aspect of a wireless communication system due to the nature of the medium used, i e the radio link that is available to every one and not only the legitimate entities. Even the authentication mechanisms are attacked. It is possible to clone a subscription either by having physical access to the smart card or over the air interface. Cloning a subscription over the air requires base station functionality. </p><p>The most obvious threat against communication systems is eavesdropping on conversations. The privacy of GSM conversations is protected using some version of the A5 algorithm. There are several impressive cryptanalytical attacks against these algorithms, that break the encryption and make it possible to eavesdrop in real-time. Most of these algorithms require, however, extensive computation power and unrealistic quantities of known plaintext, which make it difficult to use them in practice. Difficulties using cryptanalytical attacks to break the confidentiality of GSM calls does not mean that conversations are well protected. Loopholes in the protocols used in GSM make it possible for an outsider, with access to sufficient equipment, to eavesdrop on conversations in real-time. </p><p>In the presence of these threats and vulnerabilities it is justified to wonder whether GSM provides sufficient security for users with very valuable information to communicate. These users may be military organisations, senior management personnel in large companies etc. GSM’s current security model does note provide sufficient protection for these entities. An additional layer of security should be added to the current security model.</p>

A well known birthday paradox is one the most important problems in cryptographic applications. Incremental hash functions or digital signatures in public key cryptography and low-weight parity check equations of LFSRs in stream ciphers are examples of such applications which benet from birthday problem theories to run their attacks. Wagner introduced and formulated the k-dimensional birthday problem and proposed an algorithm to solve the problem in O(k.m^ 1/log k ). The generalized birthday solutions used in some applications to break Knapsack based systems or collision nding in hash functions. The optimized birthday algorithms can solve Knapsack problems of dimension n which is believed to be NP-hard. Its equivalent problem is Subset Sum Problem nds the solution over Z/mZ. The main property for the classication of the problem is density. When density is small enough the problem reduces to shortest lattice vector problem and has a solution in polynomial time. Assigning a variable to each element of the lists, decoding them into a matrix and considering each row of the matrix as an equation lead us to have a multivariate polynomial system of equations and all solution of this type can be a solution for the k- list problem such as F4, F5, another strategy called eXtended Linearization (XL) and sl. We discuss the new approaches and methods proposed to reduce the complexity of the algorithms. For particular cases in over-determined systems, more equations than variables, regarding to have a single solutions Wolf and Thomea work to make a gradual decrease in the complexity of F5. Moreover, his group try to solve the problem by monomials of special degrees and linear equations for small lists. We observe and compare all suggested methods in this

In this thesis we obtain several interesting algebraic properties of the operations used in the block cipher IDEA which are important for cryptographic analyzes. We view each of these operations as a function from $mathbb Z_{2}^n times mathbb Z_{2}^n to mathbb Z_{2}^n$. By fixing one of variables $v(z)=mathbf Z$ in $mathbb Z_{2}^n times mathbb Z_{2}^n$, we define functions $mathbf {f}_z$ and $mathbf {g}_z$ from $mathbb Z_{2}^n$ to $mathbb Z_{2}^n$ for the addition $BIGboxplus$ and the multiplication $BIGodot$ operations, respectively. We first show that the nonlinearity of $mathbf {g}_z$ remains the same under some transformations of $z$. We give an upper bound for the nonlinearity of $mathbf {g}_{2^k}$, where $2leq k &lt / n-1$. We list all linear relations which make the nonlinearity of $mathbf {f}_z$ and $mathbf {g}_z$ zero and furthermore, we present all linear relations for $mathbf {g}_z$ having a high probability. We use these linear relations to derive many more linear relations for 1-round IDEA. We also devise also a new algorithm to find a set of new linear relations for 1-round IDEA based on known linear relations. Moreover, we extend the largest known linear class of weak keys with cardinality $2^{23}$ to two classes with cardinality $2^{24}$ and $2^{27}$. Finally, we obtain several interesting properties of the set $ { ({mathbf X},{mathbf X} BIGoplus {mathbf A}) in mathbb Z_2^n times mathbb Z_2^n ,|, (mathbf {X}BJoin {mathbf Z})BIGoplus( ({mathbf X} BIGoplus {mathbf A} ) BJoin mathbf {Z} ) = {mathbf B} }$ for varying ${mathbf A}, {mathbf B}$ and ${mathbf Z}$ in $mathbb Z_2^n$, where $BJoin in { BIGodot,BIGboxplus }$. By using some of these properties, we present impossible differentials for 1-round IDEA and Pseudo-Hadamard Transform.

Recent years have witnessed several real threats to the most widely used hash functions which are generally inspired from MD4, such as MD5, RIPEMD, SHA0 and SHA1. These extraordinary developments in cryptanalysis of hash functions brought the attention of the cryptology researchers to the alternative designs. Tiger is an important type of alternative hash functions and is proved to be secure so far as there is no known collision attack on the full (24 rounds) Tiger. It is designed by Biham and Anderson in 1995 to be very fast on modern computers. In two years some weaknesses have been found for Tiger-hash function. First, in FSE 006 Kelsey and Lucks found a collision for 16-17 rounds of Tiger and a pseudo-near-collision for 20 rounds. Then, Mendel et al extended this attack to find 19-round collision and 22-round pseudo-near-collision. Finally in 2007, Mendel and Rijmen found a pseudo-near-collision for the full Tiger. In this work, we modify the attack of Kelsey and Lucks slightly and present the exact values of the differences used in the attack. Moreover, there have been several cryptanalysis papers investigating the randomness properties of the designed hash functions under the encryption modes. In these papers, related-key boomerang and related-key rectangle attacks are performed on MD4,MD5, HAVAL and SHA. In this thesis, we introduce our 17,19 and 21-round related-key boomerang and rectangle distinguishers to the encryption mode of Tiger.

Time Memory Trade O (TMTO) is a cryptanalytic method that aims to develop an attack which has a lower memory complexity than lookup table and a lower online time complexity than exhaustive search. TMTO methods are widely studied in the literature and used for inverting various cryptosystems. We focus on the design and the analysis of TMTO on symmetric ciphers in this thesis. Firstly, the summary of the random mapping statistics from the view point of TMTO is presented. We also recalculate some expected values with a simpler approach than the existing proofs. Then, we propose some variant constructions and also present three new distinguishers based on random mappings. Next, we provide a detailed analysis of the success rate of two main improvements of the attack / Distinguished Point Method and Rainbow Method. Finally, we discuss the adjustment of the parameters to achieve a high success rate. To support our theoretical framework, we also present empirical results of our analysis to actual ciphers.

One of the most important cryptographic primitives is the concept of block ciphers which yields confidentiality for data transmission in communication. Therefore, to be sure that confidentiality is provided, it is necessary to analyse the security of block ciphers by investigating their resistance to existing attacks. For this reason, related-key attacks gain much popularity in recent years and have been applied to many block ciphers with weak key schedules. In this work, our main motivation is to cover types of related-key attacks on block ciphers and exemplify them. For years, cryptanalysts have been investigating the security of the block cipher XTEA and proposed several attacks on the cipher. First in FSE&#039 / 02, Moon et al. presented a 14-round impossible differential attack on XTEA. Then in ICISC&#039 / 03, Hong et al. proposed a 15-round differential attack and a 23-round truncated differential attack on XTEA. In FSE&#039 / 04, Ko et al. proposed a 27-round related-key truncated differential attack on XTEA. Afterwards, in Vietcrypt&#039 / 06, Lee et al. proposed a 34-round related-key rectangle attack on XTEA. Finally in 2008, Lu improved this attack to a related-key rectangle attack on 36-round XTEA which is the best attack on XTEA in terms of the number of attacked rounds. In this thesis, we also analyse differential properties of both structure and key schedule of XTEA block cipher and introduce our 25-round related-key impossible differential distinguisher for XTEA.

The rapid growth in multimedia based Internet systems and applications like video telephony, video on demand, network based DVD recorders and IP television has created a substantial need for multimedia security. One of the important requirements for multimedia security is transmission of the digital multimedia content in a secure manner using encryption for protecting it from eavesdropping. The simplest way of encrypting multimedia content is to consider the two-dimensional/three-dimensional image/video stream as an one-dimensional stream and to encrypt the entire content using standard block ciphers like AES, DES, IDEA or RC4 or using a stream cipher. The method of encrypting the entire multimedia content is considered as a naive encryption approach. Even though the naive encryption approach provides the desired security requirements, it imposes a large overhead on the multimedia codex. This is due to the size of the multimedia content, and also due to real time requirements of transmission and rendering. Hence, lightweight encryption schemes are gaining popularity for multimedia encryption. Lightweight Encryption schemes are based on the principle “Encrypt minimal and induce maximum noise". Lightweight encryption schemes are designed to take the structure of the multimedia content into consideration. In our work we analyze some of the existing lightweight encryption schemes for digital images and video. The analysis is done based on the amount of security, scalability and effect on compression. A detailed study of some of the existing lightweight encryption schemes is also done by designing cryptanalysis schemes. The cryptanalysis schemes are designed using image noise clearing algorithms and pixel prediction techniques. The designed cryptanalysis schemes reduce the amount of noise introduced by the corresponding lightweight encryption schemes considerably. Based on our analysis of existing lightweight encryption schemes, we propose a set of more robust lightweight encryption schemes for images and video. The proposed lightweight encryption schemes are secure, scalable, and do not degrade the compression achieved. In our work, we also propose a few enhancements to JPEG image compression for achieving more compression, without compromising on the quality. The enhancements to the JPEG compression are extensions of the pixel prediction techniques used in the proposed cryptanalysis schemes.

This doctoral thesis approaches the problem of designing versatile architectures for cryptographic hardware. By the term versatile we define hardware architectures capable of supporting a variety of arithmetic operations and algorithms useful in cryptography, with no need to reconfigure the internal interconnections of the integrated circuit. A versatile architecture could offer considerable benefits to the end-user. By embedding a variety of crucial operations in a common architecture, the user is able to switch seamlessly the underlying cryptographic protocols, which not only gives an added value in the design from flexibility but also from practicality point of view. The total cost of a cryptographic application can be also benefited; assuming a versatile integrated circuit which requires no additional circuitry for other vital operations (for example input–output converters) it is easy to deduce that the total cost of development and fabrication of these extra components is eliminated, thus reducing the total production cost. We follow a systematic approach for developing and presenting the proposed versatile architectures. First, an in-depth analysis of the algorithms of interest is carried out, in order to identify new research areas and weaknesses of existing solutions. The proposed algorithms and architectures operate on Galois Fields GF of the form GF(p) for integers and GF(2^n) for polynomials. Alternative number representation systems such as Residue Number System (RNS) for integers and Polynomial Residue Number System (PRNS) for polynomials are employed. The mathematical validity of the proposed algorithms and the applicability of RNS and PRNS in the context of cryptographic algorithms is also presented. The derived algorithms are decomposed in a way that versatile structures can be formulated and the corresponding hardware is developed and evaluated. New cryptanalytic properties of the proposed algorithms against certain types of attacks are also highlighted. Furthermore, we try to approach a fundamental problem in Very Large Scale Integration (VLSI) design, that is the problem of evaluating and comparing architectures using models independent from the underlying fabrication technology. We also provide generic methods to evaluate the optimal operation parameters of the proposed architectures and methods to optimize the proposed architectures in terms of speed, area, and area x speed product, based on the needs of the underlying application. The proposed methodologies can be expanded to include applications other than cryptography. Finally, novel algorithms based on new mathematical and design problems for the crucial operation of modular multiplication are presented. The new algorithms preserve the versatile characteristics discussed previously and it is proved that, along with existing algorithms in the literature, they may forma large family of algorithms applicable in cryptography, unified under the common frame of the proposed versatile architectures. / Η παρούσα διατριβή άπτεται του θέματος της ανάπτυξης ευέλικτων αρχιτεκτονικών κρυπτογραφίας σε ολοκληρωμένα κυκλώματα υψηλής ολοκλήρωσης (VLSI). Με τον όρο ευέλικτες ορίζονται οι αρχιτεκτονικές που δύνανται να υλοποιούν πλήθος βασικών αριθμητικών πράξεων για την εκτέλεση κρυπτογραφικών αλγορίθμων, χωρίς την ανάγκη επαναπροσδιορισμού των εσωτερικών διατάξεων στο ολοκληρωμένο κύκλωμα. Η χρήση ευέλικτων αρχιτεκτονικών παρέχει πολλαπλά οφέλη στο χρήστη. Η ενσωμάτωση κρίσιμων πράξεων απαραίτητων στη κρυπτογραφία σε μια κοινή αρχιτεκτονική δίνει τη δυνατότητα στο χρήστη να εναλλάσσει το υποστηριζόμενο κρυπτογραφικό πρωτόκολλο, εισάγοντας έτσι χαρακτηριστικά ευελιξίας και πρακτικότητας, χωρίς επιπρόσθετη επιβάρυνση του συστήματος σε υλικό. Αξίζει να σημειωθεί πως οι εναλλαγές αυτές δεν απαιτούν τη παρέμβαση του χρήστη. Σημαντική είναι η συνεισφορά μιας ευέλικτης αρχιτεκτονικής και στο κόστος μιας εφαρμογής. Αναλογιζόμενοι ένα ολοκληρωμένο κύκλωμα που μπορεί να υλοποιεί αυτόνομα όλες τις απαραίτητες πράξεις ενός αλγόριθμου χωρίς την εξάρτηση από εξωτερικά υποσυστήματα (π.χ. μετατροπείς εισόδου–εξόδου), είναι εύκολο να αντιληφθούμε πως το τελικό κόστος της εκάστοτε εφαρμογής μειώνεται σημαντικά καθώς μειώνονται οι ανάγκες υλοποίησης και διασύνδεσης επιπρόσθετων υποσυστημάτων στο ολοκληρωμένο κύκλωμα. Η ανάπτυξη των προτεινόμενων αρχιτεκτονικών ακολουθεί μια δομημένη προσέγγιση. Διενεργείται εκτενής μελέτη για τον προσδιορισμό γόνιμων ερευνητικών περιοχών και εντοπίζονται προβλήματα και δυνατότητες βελτιστοποίησης υπαρχουσών κρυπτογραφικών λύσεων. Οι νέοι αλγόριθμοι που αναπτύσσονται αφορούν τα Galois πεδία GF(p) και GF(2^n) και χρησιμοποιούν εναλλακτικές αριθμητικές αναπαράστασης δεδομένων όπως το αριθμητικό σύστημα υπολοίπων (Residue Number System (RNS)) για ακέραιους αριθμούς και το πολυωνυμικό αριθμητικό σύστημα υπολοίπων (Polynomial Residue Number System (PRNS)) για πολυώνυμα. Αποδεικνύεται η μαθηματική τους ορθότητα και βελτιστοποιούνται κατά τέτοιο τρόπο ώστε να σχηματίζουν ευέλικτες δομές. Αναπτύσσεται το κατάλληλο υλικό (hardware) και διενεργείται μελέτη χρήσιμων ιδιοτήτων των νέων αλγορίθμων, όπως για παράδειγμα νέες κρυπταναλυτικές ιδιότητες. Επιπρόσθετα, προσεγγίζουμε στα πλαίσια της διατριβής ένα βασικό πρόβλημα της επιστήμης σχεδιασμού ολοκληρωμένων συστημάτων μεγάλης κλίμακας (Very Large Scale Integration (VLSI)). Συγκεκριμένα, προτείνονται μέθοδοι σύγκρισης αρχιτεκτονικών ανεξαρτήτως τεχνολογίας καθώς και τρόποι εύρεσης των βέλτιστων συνθηκών λειτουργίας των προτεινόμενων αρχιτεκτονικών. Οι μέθοδοι αυτές επιτρέπουν στον σχεδιαστή να παραμετροποιήσει τις προτεινόμενες αρχιτεκτονικές με βάση τη ταχύτητα, επιφάνεια, ή το γινόμενο ταχύτητα x επιφάνεια. Οι προτεινόμενες μεθοδολογίες μπορούν εύκολα να επεκταθούν και σε άλλες εφαρμογές πέραν της κρυπτογραφίας. Τέλος, προτείνονται νέοι αλγόριθμοι για τη σημαντικότατη για την κρυπτογραφία πράξη του πολλαπλασιασμού με υπόλοιπα. Οι νέοι αλγόριθμοι ενσωματώνουν από τη μία τις ιδέες των ευέλικτων δομών, από την άλλη όμως βασίζονται σε νέες ιδέες και μαθηματικά προβλήματα τα οποία προσπαθούμε να προσεγγίσουμε και να επιλύσουμε. Αποδεικνύεται πως είναι δυνατή η ενοποίηση μιας μεγάλης οικογένειας αλγορίθμων για χρήση στην κρυπτογραφία, υπό τη στέγη των προτεινόμενων μεθοδολογιών για ευέλικτο σχεδιασμό.

Σε αυτή τη Μεταπτυχιακή Διπλωματική Εργασία γίνεται μία προσπάθεια κατασκευής ασφαλέστερων block ciphers (Κεφ.1). Αρχικώς παρουσιάζουμε αναλυτικά το θεωρητικό υπόβαθρο της Γραμμικής Κρυπτανάλυσης (Κεφ.2) και της Διαφορικής Κρυπτανάλυσης (Κεφ.3). Στη συνέχεια, προχωρούμε σε μια εφαρμογή της Γραμμικής και Διαφορικής Κρυπτανάλυσης στον αλγόριθμο CAST-128 (Κεφ.4), που είναι ένας σύγχρονος block cipher αλγόριθμος. Στο Κεφ.5 αναφερόμαστε στις σχεδιαστικές παραμέτρους ενός block cipher (S-box Design, Framework Κρυπτογραφήματος, Key Schedule και Round Function). Η συμβολή μας συνίσταται στην κατασκευή κρυπτογραφικά ασφαλών S-boxes με τη χρήση Bent συναρτήσεων και συναρτήσεων Maiorana και η μελέτη της μη γραμμικότητας του προκύπτοντος κρυπτοσυστήματος (Κεφ.6). Στο τελευταίο κεφάλαιο (Κεφ.7) αναφερόμαστε στις μελλοντικές προεκτάσεις και στο ερευνητικό πλάνο που έχουμε θέσει με αφετηρία αυτή τη Μεταπτυχιακή Διπλωματική Εργασία. Στο Παράρτημα Α παραθέτουμε τον Κώδικα Υλοποίησης της κατασκευής των S-boxes. / In this Master Thesis we make an attempt to construct secure block ciphers (Chap.1). First of all, we present in details the theoretical background of Linear Cryptanalysis (Chap.2) and Differential Cryptanalysis (Chap.3). Then we apply Linear and Differential Cryptanalysis in CAST-128 algorithm (Chap.4), which is a modern block cipher algorithm. In Chap.5 we present the design parameters of a block cipher (S-box Design, Feistel Framework, Key Schedule and Round Function). Our contribution is the construction of cryptographically secure S-boxes using Bent Functions and Maiorana Functions and also we study the non-linearity of the constructed cryptosystem (Chap.6). In the last Chapter (Chap.7) we present our future research plan, based on this Master Thesis. The Source Code of the S-boxes construction can be found in Appendix A.