Cette thèse se propose de remédier à l'absence de formalisme dédié aux preuves de sécurité concrète à travers 3 contributions. Nous présentons d'abord la logique CIL (Computational Indistinguishability Logic), qui permet de raisonner sur les systèmes cryptographiques. Elle contient un petit nombre de règles qui correspondent aux raisonnements souvent utilisés dans les preuves. Leur formalisation est basée sur des outils classiques comme les contextes ou les bisimulations. Deuxièmement, pour plus d'automatisation des preuves, nous avons conçu une logique de Hoare dédiée aux chiffrement asymétrique dans le modèle de l'oracle aléatoire. Elle est appliquée avec succès sur des exemples de schémas existants. Enfin, nous proposons un théorème générique de réduction pour la preuve d'indifférentiabilité d'un oracle aléatoire de fonctions de hachage cryptographiques. La preuve du théorème, formalisée en CIL, en démontre l'applicabilité. Les exemples de Keccak et Chop-Merkle-Damgard illustrent ce résultat. / In this thesis, we address the lack of formalisms to carry out concrete security proofs. Our contributions are threefold. First, we present a logic, named Computational Indistinguishability Logic (CIL), for reasoning about cryptographic systems. It consists in a small set of rules capturing reasoning principles common to many proofs. Their formalization relies on classic tools such as bisimulation relations and contexts. Second, and in order to increase proof automation, it presents a Hoare logic dedicated to asymmetric encryption schemes in the Random Oracle Model that yields an automated and sound verification method. It has been successfully applied to existing encryption schemes. Third, it presents a general reduction theorem for proving indifferentiability of iterative hash constructions from a random oracle. The theorem is proven in CIL demonstrating the usefulness of the logic and has been applied to constructions such as the SHA-3 candidate Keccak and the Chop-MD construction.

Context: Secrecy has kept researchers spanning over centuries engaged in the creation of data protection techniques. With the growing rate of data breach and intervention of adversaries in confidential data storage and communication, efficient data protection has found to be a challenge. Homomorphic encryption is one such data protection technique in the cryptographic domain which can perform arbitrary computations on the enciphered data without disclosing the original plaintext or message. The first working fully homomorphic encryption scheme was proposed in the year 2009 and since then there has been a tremendous increase in the development of homomorphic encryption schemes such that they can be applied to a wide range of data services that demand security. All homomorphic encryption schemes can be categorized as partially homomorphic (PHE), somewhat homomorphic (SHE), leveled Homomorphic (LHE), and fully homomorphic encryption (FHE). Each encryption algorithm has its own importance and usage in different realms of security. DHGV, Paillier, HElib, and FHEW are the algorithms chosen in this study considering their wide usage and scope for further advancement in this subject area. A public-key algorithm named RSA is also chosen for comparison of the impact of HE and PKE (Public-key encryption) algorithm on the CPU and Memory. The utilization of various homomorphic schemes and concepts in the trending cloud storage systems is a prevailing field of research and can be expanded further by knowing the current state-of-the-art of homomorphic encryption. Hence, the necessity of comprehending the knowledge of homomorphic encryption schemes and their aspect in cloud security becomes vital. Objectives: The objective of this study is to analytically assess homomorphic encryption and various homomorphic encryption schemes. A comprehensive investigation on working and performance of the selected HE schemes is another objective of this research. Also, an experiment to run publicly available libraries of DGHV, Paillier, HElib, and FHEW is one of the main objectives. In addition to these, comprehending the impact of HE and PKE on CPU and Memory is also among the objectives of the study. The role and practice of homomorphic encryption in the cloud storage system are among the secondary objectives of this research in terms of securing confidential data. These objectives are set based on the research gap identified by conducting an exhaustive literature review. Methods: The objectives of this study are achieved by adopting the methods exhaustive literature review and experiment. Scientific databases such as IEEE Xplore, ACM Digital Library, Inspec, Springer Link etc. are used and literature is accordingly selected based on the relevance to the research topic. An exhaustive literature review is conducted and extensive bibliographic research is done to accomplish the objective of comprehending the working, applications, significance of homomorphic encryption. Apart from literature review, bibliographic research, an experiment is also conducted to run the publicly available homomorphic encryption libraries to evaluate, compare, and analyze the performance of DGHV, Paillier, HElib, and FHEW schemes. Experiment to run publicly available PKE algorithm is also conducted. Finally, the conclusion and outcome by adopting these research methods for accomplishing the objectives are theoretically presented in detail. Results: By conducting an exhaustive literature review, the importance, working, application of homomorphic encryption and its schemes is discerned. And by conducting an experiment, the impact of HE and PKE is also discerned. Apart from this, the limitations of HE and selected HE schemes along with the distinction between public and private key cryptography is understood by finding and mapping in connection with each other. From the experiment conducted, it is examined that despite the encryption libraries being publicly available for use, the possibility of running and employing few libraries successfully is remarkably low inferring that there is much improvement needed in this cryptographic discipline. Conclusions: From this research, it can be concluded that homomorphic encryption has a wide scope of extending towards efficiency and application in various fields concerned with data protection. It can also me concluded that the experimental assessment of state of the art of few HE schemes libraries that are available online are remarkably impractical for real-time practice. By analyzing the selected ii schemes, it can be concluded few HE schemes do not support any other operations on encrypted data other than addition and multiplication due to which chances of increasing noise for each encryption is relatively high. From the experiment conducted for Paillier encryption (HE) and RSA (PKE) encryption, it is concluded that both the schemes increase linearly with an increase in the input size when CPU and Memory utilization is measured. Apart from these conclusions, it can also be inferred that not all the homomorphic encryption algorithms are IND-CCA1 and IND-CCA2 secure. From this study, it can be deduced that more empirical validation and analysis of HE algorithms is required in terms of their performance and security. In order to address these problems, much research and improvement are required as it inferred from the results of this research that Homomorphic encryption is still in its early stage of development and enormous utility can be anticipated when enhanced correctly.

O crescimento acelerado de negócios voltado para Internet aumenta significativamente a necessidade por mecanismos que possam garantir a confidencialidade dos dados, fornecendo ferramentas para autenticidade e irretratabilidade dos usuários em qualquer meio de comunicação, mesmo em equipamentos que possuem recursos computacionais limitados, como um telefone celular, por exemplo. Este trabalho apresenta um esquema de criptografia que utiliza os dados pessoais para geração de chave e cifração, chamado Criptografia Baseada na Identidade, sem necessidade de um certificado digital. São apresentados diversos modelos de cifração, assinatura, acordo de chaves, bem como principais características, diferenças operacionais e respectivos aspectos relevantes de segurança. Algumas aplicabilidades como busca de dados cifrados, por exemplo, são implementadas, para melhor entendimento das operações e fases envolvidas. Os comparativos de custos computacionais das operações envolvidas destacam o esquema de assinatura de Barreto et al. (2005) e esquema de acordo de chave Mc- Cullagh e Barreto (2004b). São descritos também os pré-requisitos de um ambiente criptográfico baseado na identidade, o qual permite realizar as operações de cifração, assinatura e acordo de chaves com menor custo computacional possível. / The accelerated growth of Internet-based business increase significantly the need for mechanisms that can guarantee the data confidentiality, providing tools for authenticity and non-repudiation users in any medium of communication, even with computer resources becoming increasingly scarce, eg into a cell phone. This paper describes an encryption scheme that uses personal data for key generation and encryption, called the Identity Based Encryption, without need for a digital certificate. Various encryption schemes, signature, key agreement are shown, and its main characteristics, operational differences and their respective relevant aspects of security. Some aplicabilities such as encrypted data search, for example, are implemented, for better understanding of the operations and stages involved. The comparative computataional costs of operations highlight the Barreto et al. (2005) signature scheme and McCullagh e Barreto (2004b) key agreement scheme. They are also described, the prerequisites of an Identity-based cryptography environment, which allows to perform the operations of encryption, signing and key agreement with lower computational cost possible.

O crescimento acelerado de negócios voltado para Internet aumenta significativamente a necessidade por mecanismos que possam garantir a confidencialidade dos dados, fornecendo ferramentas para autenticidade e irretratabilidade dos usuários em qualquer meio de comunicação, mesmo em equipamentos que possuem recursos computacionais limitados, como um telefone celular, por exemplo. Este trabalho apresenta um esquema de criptografia que utiliza os dados pessoais para geração de chave e cifração, chamado Criptografia Baseada na Identidade, sem necessidade de um certificado digital. São apresentados diversos modelos de cifração, assinatura, acordo de chaves, bem como principais características, diferenças operacionais e respectivos aspectos relevantes de segurança. Algumas aplicabilidades como busca de dados cifrados, por exemplo, são implementadas, para melhor entendimento das operações e fases envolvidas. Os comparativos de custos computacionais das operações envolvidas destacam o esquema de assinatura de Barreto et al. (2005) e esquema de acordo de chave Mc- Cullagh e Barreto (2004b). São descritos também os pré-requisitos de um ambiente criptográfico baseado na identidade, o qual permite realizar as operações de cifração, assinatura e acordo de chaves com menor custo computacional possível. / The accelerated growth of Internet-based business increase significantly the need for mechanisms that can guarantee the data confidentiality, providing tools for authenticity and non-repudiation users in any medium of communication, even with computer resources becoming increasingly scarce, eg into a cell phone. This paper describes an encryption scheme that uses personal data for key generation and encryption, called the Identity Based Encryption, without need for a digital certificate. Various encryption schemes, signature, key agreement are shown, and its main characteristics, operational differences and their respective relevant aspects of security. Some aplicabilities such as encrypted data search, for example, are implemented, for better understanding of the operations and stages involved. The comparative computataional costs of operations highlight the Barreto et al. (2005) signature scheme and McCullagh e Barreto (2004b) key agreement scheme. They are also described, the prerequisites of an Identity-based cryptography environment, which allows to perform the operations of encryption, signing and key agreement with lower computational cost possible.