The thesis focuses on cryptographic algorithms of low performance devices, and mutual authentication of authentication server and user using smart cards. In the first part of this thesis the cryptography, cryptographic primitives, cryptographic goals, security models and cryptographic algorithms of low performance devices are presented. The second part focuses on low performance devices as RFID tags, NFC technology, microcontrollers and smart cards (.NET cards, java cards, MIFARE cards). The practical part deals with the comparison of chosen low performance devices and measure the time required for encryption and decryption using different cryptographic algorithms on Gemalto .NET Smart Card V2+. This thesis describes and explains the three authentication schemes for mutual authentication of remote server and user using smart cards. The new authentication scheme, which is based on the second related scheme, attempts to eliminate possible security attacks and keeps efficiency. For all four authentication schemes the application is implemented to test required time for authentication of server and user using smart cards.

The cryptographic algorithms are commonly used as a security item today. In some situations, the special device is used to run the cryptographic algorithm, so the data are protected against the attack from the internet. Naturally, the attack can be loaded on the device as well using the side channel attack. The data are under the great danger, because nowadays plenty of power consumption analyses exist. The side channel attack uses knowledge about the cryptographic algoritm and simple or differential analysis. The diploma thesis focuses on the differential power analysis attack for the data published under the DPA contest. This thesis covers different types of analyss and attacks, and describes the new DPACv4.2 implementation. The correlation analysis is presented for the DPACv4.2 and the possible attack is discussed at the conclusion.

<p dir="ltr">This thesis presents an in depth study and evaluation of a class of secure multiparty protocols that enable execution of a confidential software program $\mathcal{P}$ owned by Alice, on confidential data $\mathcal{D}$ owned by Bob, without revealing anything about $\mathcal{P}$ or $\mathcal{D}$ in the process. Our initial adverserial model is an honest-but-curious adversary, which we later extend to a malicious adverarial setting. Depending on the requirements, our protocols can be set up such that the output $\mathcal{P(D)}$ may only be learned by Alice, Bob, both, or neither (in which case an agreed upon third party would learn it). Most of our protocols are run by only two online parties which can be Alice and Bob, or alternatively they could be two commodity cloud servers (in which case neither Alice nor Bob participate in the protocols' execution - they merely initialize the two cloud servers, then go offline). We implemented and evaluated some of these protocols as prototypes that we made available to the open source community via Github. We report our experimental findings that compare and contrast the viability of our various approaches and those that already exist. All our protocols achieve the said goals without revealing anything other than upper bounds on the sizes of program and data.</p><p><br></p>

We study the problem of secure key establishment. We critically examine the security models of Bellare and Rogaway (1993) and Canetti and Krawczyk (2001) in the computational complexity approach, as these models are central in the understanding of the provable security paradigm. We show that the partnership definition used in the three-party key distribution (3PKD) protocol of Bellare and Rogaway (1995) is flawed, which invalidates the proof for the 3PKD protocol. We present an improved protocol with a new proof of security. We identify several variants of the key sharing requirement (i.e., two entities who have completed matching sessions, partners, are required to accept the same session key). We then present a brief discussion about the key sharing requirement. We identify several variants of the Bellare and Rogaway (1993) model. We present a comparative study of the relative strengths of security notions between the several variants of the Bellare-Rogaway model and the Canetti-Krawczyk model. In our comparative study, we reveal a drawback in the Bellare, Pointcheval, and Rogaway (2000) model with the protocol of Abdalla and Pointcheval (2005) as a case study. We prove a revised protocol of Boyd (1996) secure in the Bellare-Rogaway model. We then extend the model in order to allow more realistic adversary capabilities by incorporating the notion of resetting the long-term compromised key of some entity. This allows us to detect a known weakness of the protocol that cannot be captured in the original model. We also present an alternative protocol that is efficient in both messages and rounds. We prove the protocol secure in the extended model. We point out previously unknown flaws in several published protocols and a message authenticator of Bellare, Canetti, and Krawczyk (1998) by refuting claimed proofs of security. We also point out corresponding flaws in their existing proofs. We propose fixes to these protocols and their proofs. In some cases, we present new protocols with full proofs of security. We examine the role of session key construction in key establishment protocols, and demonstrate that a small change to the way that session keys are constructed can have significant benefits. Protocols that were proven secure in a restricted Bellare-Rogaway model can then be proven secure in the full model. We present a brief discussion on ways to construct session keys in key establishment protocols and also prove the protocol of Chen and Kudla (2003) secure in a less restrictive Bellare-Rogaway model. To complement the computational complexity approach, we provide a formal specification and machine analysis of the Bellare-Pointcheval-Rogaway model using an automated model checker, Simple Homomorphism Verification Tool (SHVT). We demonstrate that structural flaws in protocols can be revealed using our framework. We reveal previously unknown flaws in the unpublished preproceedings version of the protocol due to Jakobsson and Pointcheval (2001) and several published protocols with only heuristic security arguments. We conclude this thesis with a listing of some open problems that were encountered in the study.

Tendering is a method for entering into a sales contract. Numerous electronic tendering systems have been established with the intent of improving the efficiency of the tendering process. Although providing adequate security services is a desired feature in an e-tendering system, current e-tendering systems are usually designed with little consideration of security and legal compliance. This research focuses on designing secure protocols for e-tendering systems. It involves developing methodologies for establishing security requirements, constructing security protocols and using formal methods in protocol security verification. The implication is that it may prove suitable for developing secure protocols in other electronic business domains. In depth investigations are conducted into a range of issues in relation to establishing generic security requirements for e-tendering systems. The outcomes are presented in a form of basic and advanced security requirements for e-tendering process. This analysis shows that advanced security services are required to secure e-tender negotiation integrity and the submission process. Two generic issues discovered in the course of this research, functional difference and functional limitations, are fundamental in constructing secure protocols for tender negotiation and submission processes. Functional difference identification derives advanced security requirements. Functional limitation assessment defines how the logic of generic security mechanisms should be constructed. These principles form a proactive analysis applied prior to the construction of security protocols. Security protocols have been successfully constructed using generic cryptographic security mechanisms. These protocols are secure e-tender negotiation integrity protocol suite, and secure e-tender submission protocols. Their security has been verified progressively during the design. Verification results show that protocols are secure against common threat scenarios. The primary contribution of this stage are the procedures developed for the complex e-business protocol analysis using formal methods. The research shows that proactive analysis has made this formal security verification possible and practical for complex protocols. These primary outcomes have raised awareness of security issues in e-tendering. The security solutions proposed in the protocol format are the first in e-tendering with verifiable security against common threat scenarios, and which are also practical for implementation. The procedures developed for securing the e-tendering process are generic and can be applied to other business domains. The study has made improvements in: establishing adequate security for a business process; applying proactive analysis prior to secure protocol construction; and verifying security of complex e-business protocols using tool aided formal methods.

Είναι ευρέως αποδεκτό ότι η ασφάλεια δεδομένων έχει ήδη ξεκινήσει να διαδραματίζει κεντρικό ρόλο στον σχεδιασμό μελλοντικών συστημάτων τεχνολογίας πληροφορίας (IT – Information Technology). Μέχρι πριν από λίγα χρόνια, ο υπολογιστής αποτελούσε την κινητήρια δύναμη της ψηφιακής επικοινωνίας. Πρόσφατα, ωστόσο, έχει γίνει μια μετατόπιση προς τις εφαρμογές τεχνολογίας πληροφορίας που υλοποιούνται σαν ενσωματωμένα συστήματα. Πολλές από αυτές τις εφαρμογές στηρίζονται σε μεγάλο βαθμό σε μηχανισμούς ασφαλείας, περιλαμβάνοντας την ασφάλειας για ασύρματα τηλέφωνα, φαξ, φορητούς υπολογιστές, συνδρομητική τηλεόραση, καθώς και συστήματα προστασίας από αντιγραφή για audio / video καταναλωτικά προϊόντα και ψηφιακούς κινηματογράφους. Το γεγονός ότι ένα μεγάλο μέρος των ενσωματωμένων εφαρμογών είναι ασύρματο, καθιστά το κανάλι επικοινωνίας ιδιαίτερα ευάλωτο και φέρνει στο προσκήνιο την ανάγκη για ακόμη μεγαλύτερη ασφάλεια. Παράλληλα με τα ενσωματωμένα συστήματα, η εκρηκτική ανάπτυξη των ψηφιακών επικοινωνιών έχει επιφέρει πρόσθετες προκλήσεις για την ασφάλεια. Εκατομμύρια ηλεκτρονικές συναλλαγές πραγματοποιούνται κάθε μέρα, και η ταχεία ανάπτυξη του ηλεκτρονικού εμπορίου κατέστησε την ασφάλεια ένα θέμα ζωτικής σημασίας για πολλές καταναλωτές. Πολύτιμες επιχειρηματικές ευκαιρίες , καθώς επίσης και πολλές υπηρεσίες πραγματοποιούνται κάθε μέρα μέσω του Διαδικτύου και πλήθος ευαίσθητων δεδομένων μεταφέρονται από ανασφαλή κανάλια επικοινωνίας σε όλο τον κόσμο. Η επιτακτική ανάγκη για την αντιμετώπιση αυτών των προβλημάτων, κατέστησε πολύ σημαντική την συμβολή της κρυπτογραφίας, και δημιούργησε μια πολύ υποσχόμενη λύση, με την οποία ενσωματωμένα συστήματα σε συνδυασμό με κρυπτογραφικά πρωτόκολλα, θα μπορούσαν να μας οδηγήσουν στην εξασφάλιση των επιθυμητών αποτελεσμάτων. Στην παρούσα εργασία, παρουσιάζουμε την υλοποίηση ενός ενσωματωμένου συστήματος, εμπλουτισμένο με κρυπτογραφικά πρωτόκολλα, που ουσιαστικά μεταμορφώνει έναν κοινό ηλεκτρονικό υπολογιστή σε ένα ισχυρό Crypto System PC, και έχει σαν κύρια αρμοδιότητα να μπορεί να επικοινωνεί με ένα υπολογιστικό σύστημα και να στέλνει πληροφορίες για την κατάσταση του μέσω ασφαλούς σύνδεσης διαδικτύου σε κάποιον απομακρυσμένο υπολογιστή ελέγχου/καταγραφής συμβάντων σε ώρες που δεν είναι εφικτή η παρουσία εξειδικευμένου προσωπικού για τον έλεγχο του. Αξιολογούμε την απόδοση του και την λειτουργία του με την εκτέλεση διάφορων πειραμάτων, ενώ επίσης προτείνουμε λύσεις για πιο ιδανικές και αποδοτικές συνθήκες λειτουργίας για μελλοντικές εφαρμογές. / It is widely recognized that data security already plays a central role in the design of future IT systems.Until a few years ago, the PC had been the major driver of the digital economy. Recently, however, there has been a shift towards IT applications realized as embedded systems.Many of those applications rely heavily on security mechanisms, including security for wireless phones, faxes, wireless computing, pay-TV, and copy protection schemes for audio/video consumer products and digital cinemas. Note that a large share of those embedded applications will be wireless, which makes the communication channel especially vulnerable and the need for security even more obvious. In addition to embedded devices, the explosive growth of digital communications also brings additional security challenges. Millions of electronic transactions are completed each day, and the rapid growth of eCommerce has made security a vital issue for many consumers. Valuable business opportunities are realized over the Internet and megabytes of sensitive data are transferred and moved over insecure communication channels around the world. The urgent need to face these problems has made the contribution of cryptography very important , and created a very promising solution, in which embedded systems in combination with cryptographic protocols, could lead us to obtain the desired results. In this paper, we present the implementation of an embedded system, enriched with cryptographic protocols, which turns a common computer into a powerful Crypto System PC, and has as its primary responsibility to be able to communicate with a computer system and send information for its situation through secure internet connections to a remote computer which is responsible for recording of events, when there is not qualified staff to control the computer system. We evalauate its performance and operation, by executing various experiments and we also suggest solutions for more optimal and efficient operating conditions for future applications.

Private set intersection(PSI) is a two party protocol where both parties possess a private set and at the end of the protocol, one party (client) learns the intersection while other party (server) learns nothing. Motivated by some interesting practical applications, several provably secure and efficient PSI protocols have appeared in the literature in recent past. Some of the proposed solutions are secure in the honest-but-curious (HbC) model while the others are secure in the (stronger) malicious model. Security in the latter is traditionally achieved by following the classical approach of attaching a zero knowledge proof of knowledge (ZKPoK) (and/or using the so-called cut-and-choose technique). These approaches prevent the parties from deviating from normal protocol execution, albeit with significant computational overhead and increased complexity in the security argument, which includes incase of ZKPoK, knowledge extraction through rewinding. We critically investigate a subset of the existing protocols. Our study reveals some interesting points about the so-called provable security guarantee of some of the proposed solutions. Surprisingly, we point out some gaps in the security argument of several protocols. We also discuss an attack on a protocol when executed multiple times between the same client and server. The attack, in fact, indicates some limitation in the existing security definition of PSI. On the positive side, we show how to correct the security argument for the above mentioned protocols and show that in the HbC model the security can be based on some standard computational assumption like RSA and Gap Diffie-Hellman problem. For a protocol, we give improved version of that protocol and prove security in the HbC model under standard computational assumption. For the malicious model, we construct two PSI protocols using deterministic blind signatures i.e., Boldyreva’s blind signature and Chaum’s blind signature, which do not involve ZKPoK or cut-and-choose technique. Chaum’s blind signature gives a new protocol in the RSA setting and Boldyreva’s blind signature gives protocol in gap Diffie-Hellman setting which is quite similar to an existing protocol but it is efficient and does not involve ZKPoK.

Quantum cryptography is arguably the most successfully applied area of quantum information theory. In this work, We invsetigate the role of quantum indistinguishability in random number generation, quantum temporal correlations, quantum nonlocality and counterfactuality for quantum cryptography. We study quantum protocols for key distribution, and their security in the conventional setting, in the counterfactual paradigm, and finally also in the device-independent scenario as applied to prepare-and-measure schemes. We begin with the interplay of two essential non-classical features like quantum indeterminism and quantum indistinguishability via a process known as bosonic stimulation is discussed. It is observed that the process provides an efficient method for macroscopic extraction of quantum randomness. Next, we propose two counterfactual cryptographic protocols, in which a secret key bit is generated even without the physical transmission of a particle. The first protocol is semicounterfactual in the sense that only one of the key bits is generated using interaction-free measurement. This protocol departs fundamentally from the original counterfactual key distribution protocol in not encoding secret bits in terms of photon polarization. We discuss how the security in the protocol originates from quantum single-particle non-locality. The second protocol is designed for the crypto-task of certificate authorization, where a trusted third party authenticates an entity (e.g., bank) to a client. We analyze the security of both protocols under various general incoherent attack models. The next part of our work includes study of quantum temporal correlations. We consider the use of the Leggett-Garg inequalities for device-independent security appropriate for prepare-and-measure protocols subjected to the higher dimensional attack that would completely undermine standard BB84. In the last part, we introduce the novel concept of nonlocal subspaces constructed using the graph state formalism, and propose their application for quantum information splitting. In particular, we use the stabilizer formalism of graph states to construct degenerate Bell operators, whose eigenspace determines the nonlocal subspace, into which a quantum secret is encoded and shared among an authorized group of agents, or securely transmitted to a designated secret retriever. The security of our scheme arises from the monogamy of quantum correlations. The quantum violation of the Bell-type inequality here is to its algebraic maximum, making this approach inherently suitable for the device-independent scenario.

L'avènement de l'informatique quantique permet de réétudier les primitives cryptographiques avec une sécurité inconditionnelle, c'est à dire sécurisé même contre des adversaires tout puissants. En 1984, Bennett et Brassard ont construit un protocole quantique de distribution de clé. Dans ce protocole, deux joueurs Alice et Bob coopèrent pour partager une clé secrète inconnue d'une tierce personne Eve. Ce protocole a une sécurité inconditionnelle et n'a pasd'équivalent classique.Dans ma thèse, j'ai étudié les primitives cryptographiques à deux joueurs où ces joueurs ne se font pas confiance. J'étudie principalement le pile ou face quantique et la mise-en-gage quantique de bit. En informatique classique, ces primitivessont réalisables uniquement avec des hypothèses calculatoires, c'est-à-dire en supposant la difficulté d'un problème donné. Des protocoles quantiques ont été construits pour ces primitives où un adversaire peut tricher avec une probabilité constante strictement inférieure à 1, ce qui reste impossible classiquement. Néanmoins, Lo et Chau ont montré l'impossibilité de créer ces primitives parfaitement même en utilisant l'informatique quantique. Il reste donc à déterminer quelles sont les limites physiques de ces primitives.Dans une première partie, je construis un protocole quantique de pile ou face où chaque joueur peut tricher avec probabilité au plus 1/racine(2) + eps pour tout eps > 0. Ce résultat complète un résultat de Kitaev qui dit que dans un jeu de pile ou face quantique, un joueur peut toujours tricher avec probabilité au moins 1/racine(2). J'ai également construit un protocole de mise-en-gage de bit quantique optimal où un joueur peut tricher avec probabilité au plus 0,739 + eps pour tout eps > 0 puis ai montré que ce protocole est en fait optimal. Finalement, j'ai dérivé des bornes inférieures et supérieures pour une autre primitive: la transmission inconsciente, qui est une primitive universelle.Dans une deuxième partie, j'intègre certains aspects pratiques dans ces protocoles. Parfois les appareils de mesure ne donnent aucun résultat, ce sont les pertes dans la mesure. Je construis un protocole de lancer de pièce quantique tolérant aux pertes avec une probabilité de tricher de 0,859. Ensuite, j'étudie le modèle dispositif-indépendant où on ne suppose plus rien sur les appareils de mesure et de création d'état quantique.Finalement, dans une troisième partie, j'étudie ces primitives cryptographiques avec un sécurité computationnelle. En particulier, je fais le lien entre la mise en gage de bit quantique et les protocoles zero-knowledge quantiques. / Quantum computing allows us to revisit the study of quantum cryptographic primitives with information theoretic security. In 1984, Bennett and Brassard presented a protocol of quantum key distribution. In this protocol, Alice and Bob cooperate in order to share a common secret key k, which has to be unknown for a third party that has access to the communication channel. They showed how to perform this task quantumly with an information theoretic security; which is impossible classically.In my thesis, I study cryptographic primitives with two players that do not trust each other. I study mainly coin flipping and bit commitment. Classically, both these primitives are impossible classically with information theoretic security. Quantum protocols for these primitives where constructed where cheating players could cheat with probability stricly smaller than 1. However, Lo, Chau and Mayers showed that these primitives are impossible to achieve perfectly even quantumly if one requires information theoretic security. I study to what extent imperfect protocols can be done in this setting.In the first part, I construct a quantum coin flipping protocol with cheating probabitlity of 1/root(2) + eps for any eps > 0. This completes a result by Kitaev who showed that in any quantum coin flipping protocol, one of the players can cheat with probability at least 1/root(2). I also constructed a quantum bit commitment protocol with cheating probability 0.739 + eps for any eps > 0 and showed that this protocol is essentially optimal. I also derived some upper and lower bounds for quantum oblivious transfer, which is a universal cryptographic primitive.In the second part, I study some practical aspects related to these primitives. I take into account losses than can occur when measuring a quantum state. I construct a Quantum Coin Flipping and Quantum Bit Commitment protocols which are loss-tolerant and have cheating probabilities of 0.859. I also construct these primitives in the device independent model, where the players do not trust their quantum device. Finally, in the third part, I study these cryptographic primitives with information theoretic security. More precisely, I study the relationship between computational quantum bit commitment and quantum zero-knowledge protocols.

Cette thèse étudie deux aspects d'interaction entre deux joueurs dans le modèle du calcul et de la communication quantique.Premièrement, elle étudie deux primitives cryptographiques quantiques, des briques de base pour construire des protocoles cryptographiques complexes entre deux joueurs, comme par exemple un protocole d'identification. La première primitive est la ``mise en gage quantique". Cette primitive ne peut pas être réalisée de manière inconditionnellement sûre, mais il possible d'avoir une sécurité lorsque les deux parties sont soumis à certaines contraintes additionnelles. Nous étudions cette primitive dans le cas où les deux joueurs sont limités à l'utilisation d'états et d'opération gaussiennes, un sous-ensemble de la physique quantique central en optique, donc parfaitement adapté pour la communication via fibres optiques. Nous montrons que cette restriction ne permet malheureusement pas la réalisation de la mise en gage sûre. Pour parvenir à ce résultat, nous introduisons la notion de purification intrinsèque, qui permet de contourner l'utilisation du théorème de Uhlman, en particulier dans le cas gaussien. Nous examinons ensuite une primitive cryptographique plus faible, le ``tirage faible à pile ou face'', dans le modèle standard du calcul quantique. Carlos Mochon a donné une preuve d'existence d'un tel protocole avec un biais arbitrairement petit. Nous donnons une interprétation claire de sa preuve, ce qui nous permet de la simplifier et de la raccourcir grandement.La seconde partie de cette thèse concerne l'étude de méthodes pour prouver des bornes inférieures dans le modèle de la complexité en requête. Il s'agit d'un modèle de complexité central en calcul quantique dans lequel de nombreux résultats majeurs ont été obtenus. Dans ce modèle, un algorithme ne peut accéder à l'entrée uniquement en effectuant des requêtes sur chacun des bits de l'entrée. Nous considérons une extension de ce modèle dans lequel un algorithme ne calcule pas une fonction, mais doit générer un état quantique. Cette généralisation nous permet de comparer les différentes méthodes pour prouver des bornes inférieures dans ce modèle. Nous montrons d'abord que la méthode par adversaire ``multiplicative" est plus forte que la méthode ``additive". Nous montrons ensuite une réduction de la méthode polynomiale à la méthode multiplicative, ce qui permet de conclure à la supériorité de la méthode par adversaire multiplicative sur toutes les autres méthodes. Les méthodes par adversaires sont en revanche souvent difficiles à utiliser car elles nécessite le calcul de normes de matrices de très grandes tailles. Nous montrons comment l'étude des symétries d'un problème simplifie grandement ces calculs. Enfin, nous appliquons ces formules pour prouver la borne inférieure optimale du problème INDEX-ERASURE un problème de génération d'état quantique lié au célèbre problème GRAPH-ISOMORPHISM. / This dissertation studies two different aspects of two-player interaction in the model of quantum communication and quantum computation.First, we study two cryptographic primitives, that are used as basic blocks to construct sophisticated cryptographic protocols between two players, e.g. identification protocols. The first primitive is ``quantum bit commitment''. This primitive cannot be done in an unconditionally secure way. However, security can be obtained by restraining the power of the two players. We study this primitive when the two players can only create quantum Gaussian states and perform Gaussian operations. These operations are a subset of what is allowed by quantum physics, and plays a central role in quantum optics. Hence, it is an accurate model of communication through optical fibers. We show that unfortunately this restriction does not allow secure bit commitment. The proof of this result is based on the notion of ``intrinsic purification'' that we introduce to circumvent the use of Uhlman's theorem when the quantum states are Gaussian. We then examine a weaker primitive, ``quantum weak coin flipping'', in the standard model of quantum computation. Mochon has showed that there exists such a protocol with arbitrarily small bias. We give a clear and meaningful interpretation of his proof. That allows us to present a drastically shorter and simplified proof.The second part of the dissertation deals with different methods of proving lower bounds on the quantum query complexity. This is a very important model in quantum complexity in which numerous results have been proved. In this model, an algorithm has restricted access to the input: it can only query individual bits. We consider a generalization of the standard model, where an algorithm does not compute a classical function, but generates a quantum state. This generalization allows us to compare the strength of the different methods used to prove lower bounds in this model. We first prove that the ``multiplicative adversary method'' is stronger than the ``additive adversary method''. We then show a reduction from the ``polynomial method'' to the multiplicative adversary method. Hence, we prove that the multiplicative adversary method is the strongest one. Adversary methods are usually difficult to use since they involve the computation of norms of matrices with very large size. We show how studying the symmetries of a problem can largely simplify these computations. Last, using these principles we prove the tight lower bound of the INDEX-ERASURE problem. This a quantum state generation problem that has links with the famous GRAPH-ISOMORPHISM problem.