La cryptographie reposant sur les réseaux Euclidiens est une branche récente de la cryptographie dans laquelle la sécurité des primitives repose sur la difficulté présumée de certains problèmes bien connus dans les réseaux Euclidiens. Le principe de ces preuves est de montrer que réussir une attaque contre une primitive est au moins aussi difficile que de résoudre un problème particulier, comme le problème Learning With Errors (LWE) ou le problème Small Integer Solution (SIS). En montrant que ces problèmes sont au moins aussi difficiles à résoudre qu'un problème difficile portant sur les réseaux, présumé insoluble en temps polynomial, on en conclu que les primitives construites sont sûres. Nous avons travaillé sur l'amélioration de la sécurité et des constructions de primitives cryptographiques. Nous avons étudié la difficulté des problèmes SIS et LWE et de leurs variantes structurées sur les anneaux d'entiers de corps cyclotomiques, et les modules libres sur ceux-ci. Nous avons montré d'une part qu'il existe une preuve de difficulté classique pour le problème LWE (la réduction existante de Regev en 2005 était quantique), d'autre part que les variantes sur les modules sont elles-aussi difficiles. Nous avons aussi proposé deux nouvelles variantes de signatures de groupe dont la sécurité repose sur SIS et LWE. L'une est la première reposant sur les réseaux et ayant une taille et une complexité poly-logarithmique en le nombre d'utilisateurs. La seconde construction permet de plus la révocation d'un membre du groupe. Enfin, nous avons amélioré la taille de certains paramètres dans le travail sur les applications multilinéaires cryptographiques de Garg, Gentry et Halevi. / Lattice-based cryptography is a branch of cryptography exploiting the presumed hardness of some well-known problems on lattices. Its main advantages are its simplicity, efficiency, and apparent security against quantum computers. The principle of the security proofs in lattice-based cryptography is to show that attacking a given scheme is at least as hard as solving a particular problem, as the Learning with Errors problem (LWE) or the Small Integer Solution problem (SIS). Then, by showing that those two problems are at least as hard to solve than a hard problem on lattices, presumed polynomial time intractable, we conclude that the constructed scheme is secure.In this thesis, we improve the foundation of the security proofs and build new cryptographic schemes. We study the hardness of the SIS and LWE problems, and of some of their variants on integer rings of cyclotomic fields and on modules on those rings. We show that there is a classical hardness proof for the LWE problem (Regev's prior reduction was quantum), and that the module variants of SIS and LWE are also hard to solve. We also give two new lattice-based group signature schemes, with security based on SIS and LWE. One is the first lattice-based group signature with logarithmic signature size in the number of users. And the other construction allows another functionality, verifier-local revocation. Finally, we improve the size of some parameters in the work on cryptographic multilinear maps of Garg, Gentry and Halevi in 2013.

This work consists in a performance evaluating of Asymmetrical cryptographic algorithms in embedded platforms used in Wireless Sensor Networks (WSN). The sensor devices have low computing power and energy, therefore safety techniques should not consume large amounts of resources. The asymmetric cryptographic algorithms RSA, ECC and MQQ were evaluated on platforms Desktop, ARM, MSP430 and AVR. The evaluations were performed using the SimpleScalar simulators, Sim-Panalyzer, MSPsim and AVRORA . The evaluation criteria were: processing time, memory usage and processor, as well as energy consumption. The data showed that the algorithm MQQ was more efficient than RSA and ECC algorithms in most assessment criteria, in addition, the ECC algorithm obtained the best results when compared with the RSA algorithm / Esse trabalho consiste na avaliação de desempenho de algoritmos criptográficos assimétrico em plataformas embarcadas usadas em Redes de Sensores Sem Fio (RSSF). Os dispositivos sensores têm baixa capacidade computacional e energética, portanto técnicas de segurança não devem consumir grande quantidade de recursos. Os algoritmos criptográficos assimétricos RSA, ECC e MQQ foram avaliados nas plataformas Desktop, ARM, MSP430 e AVR. A avaliação de desempenho foi realizada com auxílio dos simuladores SimpleScalar, Sim- Panalyzer, MSPsim e AVRORA. Os critérios de avaliação foram: tempo de processamento, uso de memória e processador, além do consumo de energia. Os dados revelaram que o algoritmo MQQ foi mais eficiente que os algoritmos RSA e ECC na maioria dos critérios de avaliação, além disso, o algoritmo ECC obteve os melhores resultados quando comparado com o algoritmo RSA

Orientador: Julio Cesar López Hernández / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-27T12:14:05Z (GMT). No. of bitstreams: 1 Pietz_Franz_M.pdf: 27442530 bytes, checksum: 1648252389eb63cf26ca0525be124bda (MD5) Previous issue date: 2014 / Resumo: A criptografia visual é um método de compartilhamento de segredos proposto por Naor em Shamir no artigo ''Criptografia Visual'' de 1994. Nele, uma imagem secreta é dividida em um conjunto de parcelas, sendo necessário sobrepor um número mínimo de parcelas para decodificarmos o segredo visualmente, sem nenhum tipo de dispositivo ou cálculo criptográfico; e analisando as parcelas isoladamente, não é possível recuperar nenhuma informação sobre a imagem secreta original. O esquema é considerado seguro e pode ser comparado com as cifras de one-time-pad, também chamadas de cifras perfeitas, devido à dificuldade do atacante obter o segredo ou parte dele. Existem propostas para a utilização de criptografia visual em protocolos de autenticação, como autenticação de transações bancárias e verificação de legitimidade de produtos. Entretanto, esse método possui problemas como definição do segredo recuperado, baixo contraste e desvios de alinhamento, que é o problema mais sensível. Nossa proposta mostra como utilizar um dispositivo móvel, como smartphone ou tablet, para realizar o alinhamento automático de parcelas e auxiliar o usuário no processo de recuperação de segredos encriptados utilizando criptografia visual. Para isso, utilizamos a câmera do dispositivo móvel para torná-lo uma ''transparência'' e técnicas de análise de imagens para localizar uma parcela exibida em um monitor ou impressa na embalagem de um produto, e sobrepô-la com uma parcela presente no dispositivo móvel, permitindo a visualização do segredo recuperado na tela do dispositivo. A utilização de um dispositivo móvel traz vantagens imediatas, como facilidade para a entrega de parcelas no momento da transação, sem necessidade de guardar informação previamente / Abstract: Visual cryptography is a secret sharing method proposed by Naor and Shamir in the paper ''Visual Cryptography'', in 1994. It split a secret image into a set of shares, so that we need to stack a minimum number of shares to visually decode the secret image without the help of hardware or computation, and analyzing the shares alone is not possible to obtain any information about the secret image. The scheme is considered safe and can be compared to the one-time-pad cyphers, also called perfect cyphers, due to the difficulty of an attacker to obtain the secret or part of it. There are proposals to use visual cryptography in authentication protocols, such as in bank transactions and product's legitimacy verification. But these methods have problems with recovered secret's definition, low contrast and misalignment of the shares, which is the most sensitive. Our proposal shows how to use a mobile device, such as smartphone or tablet, to perform automatic alignment of the shares and to assist a user to recover a secret encrypted using visual cryptography. For this, we use the device camera to turn it into a ''transparency'' and image analysis techniques to locate a share that can be displayed on a monitor or printed on the packaging of a product, and overlay it with a second share present on the mobile device, allowing the visualization of the recovered secret on the device's display. Using a mobile device brings immediate advantages, such as easy delivery of shares at the transaction's time, without having to store information in advance / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Os sistemas criptográficos de chave pública amplamente utilizados hoje em dia tem sua segurança baseada na suposição da intratabilidade dos problemas de fatoração de inteiros e do logaritmo discreto, sendo que ambos foram demonstrados inseguros sob o advento dos computadores quânticos. Sistemas criptográficos baseados em Multivariáveis Quadráticas (MQ) utilizam como base o problema MQ, que consiste em resolver um sistema de equações polinomiais multivariáveis quadráticas sobre um corpo finito. O problema MQ foi provado como sendo NP-completo e até hoje não se conhece algoritmo, nem mesmo quântico, de tempo polinomial que possa resolver o problema, fazendo com que sistemas criptográficos baseados nesta primitiva mereçam ser investigados e desenvolvidos como reais candidatos a proverem nossa criptografia pós-quântica. Durante a CRYPTO\'2011 Sakumoto, Shirai e Hiwatari introduziram dois novos protocolos de identificação baseados em polinômios multivariáveis quadráticos, os quais chamamos de MQID-3 e MQID-5, e que em especial e pela primeira vez, tem sua segurança reduzida apenas ao problema MQ. Baseados nestas propostas iremos apresentar uma versão aprimorada do protocolo MQID-3 na qual teremos uma redução da comunicação necessária em aproximadamente 9%. / The public-key cryptography widely used nowadays have their security based on the assumption of the intractability of the problems of integer factorization and discrete logarithm, both of which were proven unsafe in the advent of quantum computers. Cryptographic systems based on Multivariate Quadratic polynomials (MQ) are based on the MQ problem, which consists in solve a system of multivariate quadratic polynomials over a finite field. The MQ problem has been proven NP-complete and so far no polynomial time algorithm is known, not even quantum, which would resolve this problem, making worthwhile to be investigated and developed as a real candidate to provide post-quantum cryptography. In CRYPTO\'2011 Sakumoto, Shirai and Hiwatari introduced two new identification protocols based on multivariate quadratic polynomials, which we call MQID-3 and MQID-5, in particular, for the first time, their security is based only on the MQ problem. Using these proposals, we will present an improved version of the protocol MQID-3 that reduces communication by approximately 9%.

Submitted by Ricardo Cedraz Duque Moliterno (ricardo.moliterno@uefs.br) on 2015-10-20T23:41:57Z No. of bitstreams: 1 Disserta??o-Danilo-Vers?o-final-p?s-banca .pdf: 11564872 bytes, checksum: 0a0388f802ddac466fce74bea4b02895 (MD5) / Made available in DSpace on 2015-10-20T23:41:57Z (GMT). No. of bitstreams: 1 Disserta??o-Danilo-Vers?o-final-p?s-banca .pdf: 11564872 bytes, checksum: 0a0388f802ddac466fce74bea4b02895 (MD5) Previous issue date: 2015-08-19 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior - CAPES / Recently Wireless Sensor Networks have gained attention of researchers and industry around the world, such that many projects and solutions have been developed for various scenarios and applications. Such networks are formed by small sensor nodes with low processing power, few memory and few energy. Thus, resources are scarce, particularly energy, where, in most cases these nodes are powered by batteries, which is a crucial point in the network design. A kind of sensor network in which camera-enabled sensors are inserted are call Wireless Visual Sensor Networks. Because of this, these networks become able to recover large quantities of environment information which may to be interesting for several applications. However, in general, sensor networks are very vulnerable due to the nature of the communication and due also to the sensor nodes are, sometimes, in remote, hostile and hard to reach areas. Moreover, the sensor nodes are potentially inexpensive devices that can be easily purchased or designed by others to attack the network. So to mitigate these vulnerabilities, research in security area for such networks are required. However, traditional security mechanisms lead to very overhead of computing and communication can compromise the network performance when they are adopted. Thinking about it, this master's thesis aims to propose a new paradigm to ensure security for wireless visual sensor networks, being presented through a theoretical mathematical model to perform differentiation of areas in the monitoring environment to then considering the particularities of the application monitoring to provide security at different levels. Called Adaptive Encryption, this theoretical model can be used for various applications requiring different security assurances for different network locations, implying providing security at acceptable levels while consuming less network resources, above all energy. / Recentemente as Redes de Sensores Sem Fio t?m ganhado a aten??o de pesquisadores, da ind?stria e do meio acad?mico ao redor do mundo todo, de modo que muitos projetos e solu??es t?m sido desenvolvidas para diversos cen?rios e aplica??es. Essas redes s?o formadas por pequenos n?s sensores com pouco poder de processamento, mem?ria e energia. Sendo assim, os recursos s?o bastante escassos, principalmente energia, onde, na maioria das vezes estes n?s s?o alimentados por baterias, sendo este um ponto crucial no projeto da rede. Um tipo de rede de sensores em que os n?s possuem c?meras de v?deo embutidas s?o chamadas de Redes de Sensores Visuais Sem Fio. Devido a isso, tais redes se tornam capazes de recuperar grandes quantidades de informa??es do ambiente o que pode ser interessante para diversas aplica??es. Todavia, de forma geral, as redes de sensores s?o muito vulner?veis devido a natureza da comunica??o e devido tamb?m aos n?s sensores estarem, algumas vezes, em locais remotos, hostis e de dif?cil acesso. Al?m disso, os n?s sensores s?o dispositivos potencialmente baratos que podem ser facilmente adquiridos ou projetados por terceiros a fim de atacar a rede. Ent?o, visando atenuar essas vulnerabilidades, pesquisas na ?rea de seguran?a para tais redes s?o necess?rias. Contudo, os mecanismos de seguran?a tradicionais geram muito sobrecarga de computa??o e comunica??o podendo comprometer o desempenho da rede quando s?o adotados. Pensando nisso, este trabalho de mestrado tem como objetivo propor um novo paradigma para garantir seguran?a para redes de sensores visuais sem fio, sendo apresentado atrav?s um modelo matem?tico te?rico para realizar diferencia??o de ?reas no ambiente de monitoramento para, ent?o, considerando as particularidades da aplica??o de monitoramento, prover seguran?a em diferentes n?veis. Chamado de Criptografia Adaptativa, este modelo te?rico pode ser utilizado por diversas aplica??es que necessitem de garantias de seguran?a diferenciadas para diferentes locais da rede, o que implica em prover seguran?a em n?veis aceit?veis consumindo menos recursos da rede, principalmente energia.

Cette thèse présente des résultats appartenant aux trois thèmes fondamentaux de la cryptographie à clé publique : l’intégrité, l’authentification et la confidentialité. Au sein de chaque thème nous concevons des nouvelles primitives et améliorons des primitives existantes. Le premier chapitre, dédié à l’intégrité, introduit une preuve non-interactive de génération appropriée de clés publiques RSA et un protocole de co-signature dans lequel tout irrespect de l’équité laisse automatiquement la partie lésée en possession d’une preuve de culpabilité incriminant la partie tricheuse. Le second chapitre, ayant pour sujet l’authentification, montre comme une mesure de temps permet de raccourcir les engagements dans des preuves à divulgation nulle et comment des biais, introduits à dessin dans le défi, permettent d’accroitre l’efficacité de protocoles. Ce chapitre généralise également le protocole de Fiat-Shamir à plusieurs prouveurs et décrit une fraude très sophistiquée de cartes-à-puce illustrant les dangers de protocoles d’authentification mal-conçus. Au troisième chapitre nous nous intéressons à la confidentialité. Nous y proposons un cryptosystème à clé publique où les hypothèses de complexité traditionnelles sont remplacées par un raffinement du concept de CAPTCHA et nous explorons l’application du chiffrement-pot-de-miel au langage naturel. Nos dernières contributions concernent le chiffrement basé sur l’identité (IBE). Nous montrerons comment ajouter des fonctions d’émission à l’IBE hiérarchique et comment l’IBE permet de réduire la fenêtre temporelle de risque lors de la diffusion de mises à jour logicielles. / This thesis presents new results in three fundamental areas of public-key cryptography: integrity, authentication and confidentiality. In each case we design new primitives or improve the features of existing ones. The first chapter, dealing with integrity, introduces a non-interactive proof for proper RSA public key generation and a contract co-signature protocol in which a breach in fairness provides the victim with transferable evidence against the cheater. The second chapter, focusing on authentication, shows how to use time measurements to shorten zeroknowledge commitments and how to exploit bias in zero-knowledge challenges to gain efficiency. This chapter also generalizes Fiat-Shamir into a one-to-many protocol and describes a very sophisticated smart card fraud illustrating what can happen when authentication protocols are wrongly designed. The third chapter is devoted to confidentiality. We propose public-key cryptosystems where traditional hardness assumptions are replaced by refinements of the CAPTCHA concept and explore the adaptation of honey encryption to natural language messages. Our final contributions focus on identity-based encryption (IBE) showing how to add broadcast features to hierarchical IBE and how to use IBE to reduce vulnerability exposure time of during software patch broadcast.

La cryptographie a été un facteur clé pour permettre la vente de services et du commerce par Internet. Le cloud computing a amplifié cette révolution et est devenu un service très demandé grâce à ses avantages comme : puissance de calcul importante, services à bas coûts, rendement, évolutivité, accessibilité et disponibilité. Parallèlement à la hausse de nouveaux business, des protocoles pour des calculs sécurisés ont aussi émergé. Le but de cette thèse est de contribuer à la sécurité des protocoles d’Internet existants en fournissant une analyse de la source aléatoire de ces protocoles et en introduisant des protocoles mieux adaptés pour les environnements des cloud computing. Nous proposons de nouvelles constructions en améliorant l'efficacité des solutions actuelles afin de les rendre plus accessibles et pratiques. Nous fournissons une analyse de sécurité détaillée pour chaque schéma avec des hypothèses raisonnables. Nous étudions la sécurité du cloud computing à différents niveaux. D'une part, nous formalisons un cadre pour analyser quelques-uns des générateurs de nombres pseudo-aléatoires populaires à ce jour qui sont utilisés dans presque chaque application cryptographique. D'autre part, nous proposons deux approches efficaces pour des calculs en cloud. Le premier permet à un utilisateur de partager publiquement son secret de haute entropie avec des serveurs différents pour plus tard le récupérer par interaction avec certains de ces serveurs en utilisant seulement son mot de passe et sans données authentifiées. Le second permet à un client d'externaliser à un serveur une base de données en toute sécurité, qui peut être recherchée et modifiée ultérieurement. / Cryptography has been a key factor in enabling services and products trading over the Internet. Cloud computing has expanded this revolution and it has become a highly demanded service or utility due to the advantages of high computing power, cheap cost of services, high performance, scalability, accessibility as well as availability. Along with the rise of new businesses, protocols for secure computation have as well emerged. The goal of this thesis is to contribute in the direction of securing existing Internet protocols by providing an analysis of the sources of randomness of these protocols and to introduce better protocols for cloud computing environments. We propose new constructions, improving the efficiency of current solutions in order to make them more accessible and practical. We provide a detailed security analysis for each scheme under reasonable assumptions. We study the security in a cloud computing environment in different levels. On one hand, we formalize a framework to study some popular real-life pseudorandom number generators used in almost every cryptographic application. On the other, we propose two efficient applications for cloud computing. The first allows a user to publicly share its high-entropy secret across different servers and to later recover it by interacting with some of these servers using only his password without requiring any authenticated data. The second, allows a client to securely outsource to a server an encrypted database that can be searched and modified later.

Le chiffrement fonctionnel est une technique émergente en cryptographie dans laquelle une autorité toute puissante est capable de distribuer des clés permettant d’effectuer des calculs sur des données chiffrées de manière contrôlée. La mode dans ce domaine est de construire des schémas qui sont aussi expressifs que possible, c’est-à-dire du chiffrement fonctionnel qui permet l’évaluation de n’importe quel circuit. Ces contributions délaissent souvent l’efficacité ainsi que la sécurité. Elles reposent sur des hypothèses fortes, très peu étudiées, et aucune construction n’est proche d’être pratique. Le but de cette thèse est d’attaquer ce défi sous un autre angle : nous essayons de construire des schémas de chiffrement fonctionnel les plus expressifs que nous le pouvons en se basant sur des hypothèses standards, tout en conservant la simplicité et l’efficacité des constructions. C’est pourquoi nous introduisons la notion de chiffrement fonctionnel pour l’évaluation de produits scalaires, où les messages sont des vecteurs ~x, et l’autorité peut transmettre des clés correspondants à des vecteurs ~y qui permettent l’évaluation du produit scalaire h~x, ~yi. Cette fonctionnalité possède immédiatement des applications directes, et peut aussi être utilisé dans d’autres constructions plus théoriques, leproduit scalaire étant une opération couramment utilisée. Enfin, nous présentons deux structures génériques pour construire des schémas de chiffrement fonctionnels pour le produit scalaire, ainsi que des instanciations concrètes dont la sécurité repose sur des hypothèses standards. Nous comparons aussi les avantages et inconvénients de chacune d’entre elles. / Functional encryption is an emerging framework in which a master authority can distribute keys that allow some computation over encrypted data in a controlled manner. The trend on this topic is to try to build schemes that are as expressive possible, i.e., functional encryption that supports any circuit evaluation. These results are at the cost of efficiency and security. They rely on recent, not very well studied assumptions, and no construction is close to being practical. The goal of this thesis is to attack this challenge from a different angle: we try to build the most expressive functional encryption scheme we can get from standard assumption, while keeping the constructions simple and efficient. To this end, we introduce the notion of functional encryption for inner-product evaluations, where plaintexts are vectors ~x, and the trusted authority delivers keys for vectors ~y that allow the evaluation of the inner-product h~x, ~yi. This functionality already offers some direct applications, and it can also be used for theoretical constructions, as inner-product is a widely used operation. Finally, we present two generic frameworks to construct inner-product functional encryption schemes, as well as some concrete instantiations whose security relies on standard assumptions. We also compare their pros and cons.

Dans cette thèse, nous étudions les preuves à divulgation nulle de connaissance, une primitive cryptographique permettant de prouver une assertion en ne révélant rien de plus que sa véracité, et leurs applications au calcul sécurisé. Nous introduisons tout d’abord un nouveau type de preuves à divulgation nulle, appelées arguments implicites à divulgation nulle, intermédiaire entre deux notions existantes, les preuves interactives et les preuves non interactives à divulgation nulle. Cette nouvelle notion permet d’obtenir les mêmes bénéfices en terme d’efficacité que les preuves non-interactives dans le contexte de la construction de protocoles de calcul sécurisé faiblement interactifs, mais peut être instanciée à partir des mêmes hypothèses cryptographiques que les preuves interactives, permettant d’obtenir de meilleures garanties d’efficacité et de sécurité. Dans un second temps, nous revisitons un système de preuves à divulgation nulle de connaissance qui est particulièrement utile dans le cadre de protocoles de calcul sécurisé manipulant des nombres entiers, et nous démontrons que son analyse de sécurité classique peut être améliorée pour faire reposer ce système de preuve sur une hypothèse plus standard et mieux connue. Enfin, nous introduisons une nouvelle méthode de construction de systèmes de preuves à divulgation nulle sur les entiers, qui représente une amélioration par rapport aux méthodes existantes, tout particulièrement dans un modèle de type client-serveur, où un client à faible puissance de calcul participe à un protocole de calcul sécurisé avec un serveur à forte puissance de calcul. / In this thesis, we study zero-knowledge proofs, a cryptographic primitive that allows to prove a statement while yielding nothing beyond its truth, and their applications to secure computation. Specifically, we first introduce a new type of zero-knowledge proofs, called implicit zero-knowledge arguments, that stands between two existing notions, interactive zeroknowledge proofs and non-interactive zero-knowledge proofs. Our new notion provides the same efficiency benefits than the latter when used to design roundefficient secure computation protocols, but it can be built from essentially the same cryptographic assumptions than the former, which allows to get improved efficiency and security guarantees. Second, we revisit a zero-knowledge proof system that is particularly useful for secure computation protocols manipulating integers, and show that the known security analysis can be improved to base the proof system on a more wellstudied assumption. Eventually, we introduce a new method to build zero-knowledge proof systems over the integers, which particularly improves over existing methods in a client-server model, where a weak client executes a secure computation protocol with a powerful server.

This Master's thesis „Secure communication and data protection in the internet of things“ is dealing with crypthografy and crypthographic libraries, which are compared with eachother according to supporting algorithm and standard. For comparing therewere used following libraries: openSSL, wolfSSL, nanoSSL and matrixSSL. Practical part of the thesis is focused on testing the productivity of each ciphers and protocols of openSSL and wolfSSL libraries on RaspberryPi 2 device. Further, the thesis shows the design of communication scenario client-server in the Internet of Things (IoT). Simple authentication protocol client-server was implemented and simulated on RaspberryPi 2 device.