Search

Orientador: Ricardo Dahab Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Um grafo G admite um 3-fluxo se existe uma orientação de G e uma atribuição de pesos em {1, 2} às arestas de G tal que, para todo vértice v do grafo, a soma dos pesos das arestas entrando em v é igual à soma dos pesos das arestas saindo de v. A conjetura dos 3-fluxos de Tutte afirma que todo grafo 4-aresta-conexo admite um 3-fluxo. Uma versão equivalente dessa conjetura é perguntar se todo grafo 2-aresta-conexo com no máximo três cortes de aresta de tamanho três admite um 3-fluxo. Nosso objetivo é caracterizar quais grafos com até quatro cortes de aresta de tamanho três admitem um 3-fluxo, para algumas classes restritas de grafos. Nós focamos em grafos com até seis vértices de grau ímpar. Nós provamos uma caracterização completa para grafos com até quatro vértices de grau ímpar e uma caracterização parcial para grafos com seis vértices de grau ímpar Abstract: A graph G admits a 3-flow if there exists an orientation of G and an assignment of weights in {1, 2} to the edges of G such that, for every vertex v of G, the sum of the weights of the edges entering v is equal to the sum of the weights of the edges leaving v. Tutte's 3-flow conjecture states that every 4-edge-connected graph admits a 3-flow. An equivalent formulation of this conjecture states that every 2-edge-connected graph with at most three edge cuts of size three admits a 3-flow. Our objective is to characterize which graphs with up to four edge cuts of size three admit a 3-flow, for some classes of graphs. We focus on graphs with at most six vertices of odd degree. We prove a characterization for graphs with up to four vertices of odd degree and a partial characterization for graphs with up to six vertices of odd degree Mestrado Ciência da Computação Mestre em Ciência da Computação CAPES 329145/2019-01

Orientador: Sueli Irene Rodrigues Costa Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica Resumo: Neste trabalho estudamos parâmetros de reticulados que são relevantes para aplicações na chamada criptografia pós-quântica, em sistemas importantes como LWE e SIS. São analisados o parâmetro de suavização, particularmente nos reticulados mais densos conhecidos em suas dimensões, bem como reticulados ideais e reticulados q-ários Abstract: In this work we study lattice parameters which are relevant for applications on the so called post-quantum cryptography, in important systems such as LWE and SIS. We analyzed the smoothing parameter, particularly for the densest known lattices in their dimensions, as well as ideal lattices and q-ary lattices Mestrado Matemática Mestre em Matemática CNPQ 131290/2018-5

Orientador: Paulo Lício de Geus Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: O resumo poderá ser visualizado no texto completo da tese digital Abstract: The complete abstract is available with the full electronic document Mestrado Ciência da Computação Mestre em Ciência da Computação

Orientador: Ricardo Dahab Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Na área de Segurança da Informação, controle de acesso diz respeito á habilidade de permitir ou negar a utilização de determinados recursos, sejam eles informações, dispositivos, serviços etc., por parte de um indivíduo. Protocolos de identificação correspondem a algoritmos criptográficos que permitem verificar, com certo grau de confiança, se a alegação de um indivíduo a respeito de sua identidade é verdadeira. Dessa forma, pode-se prover acesso controlado e conceder privilégios de utilização de recursos somente a entidades ou indivíduos cuja identidade tenha sido comprovada. Algoritmos baseados em reticulados, de uma forma geral, têm despertado particular interesse em aplicações criptográficas, devido à sua provável resistência a ataques empregando computadores quânticos, ao contrário dos criptossistemas baseados em problemas da Teoria dos Números. Por esse motivo, nos _últimos anos, tem-se buscado desenvolver protocolos de identificação cuja segurança esteja relacionada a problemas envolvendo reticulados. Neste trabalho, foram abordadas as principais propostas recentes de protocolos de identificação baseados em reticulados. Além da apresentação dos algoritmos, é feita uma análise comparativa entre protocolos selecionados, incorporando dados experimentais de execução. A etapa de implementação aqui apresentada tem também como finalidade suprir a ausência de resultados experimentais para essa categoria de protocolos, no sentido de iniciar um processo de validação para uso dos algoritmos em aplicações práticas. Questões como possibilidades de otimização e expectativas para o futuro da área também são discutidas Abstract: One of the main concerns of the field of Information Security is access control, which refers to the restriction of access to several kinds of resources, such as data, places, devices, services and others. Identification schemes are cryptographic algorithms that allow verifying with some level of certainty if an identity claim is legitimate. Therefore, such schemes make possible to provide access control and grant privileges only to authorized individuals whose identities have been previously verified. Lattice-based algorithms are particularly interesting as the cryptography community believes them to remain secure even to quantum computers attacks, as opposite to some cryptosystems used today based on Number Theory problems. For this reason, identification schemes based on lattices have received growing attention lately. In this work, we address the main recent developments of lattice-based identification schemes. After introducing the algorithms, we make a comparative analysis of the selected schemes, using experimental data collected from our own implementation of the algorithms. The implementation phase also aims to help validating these schemes for practical use, since to this date there were practically no experimental results available. Other issues, like optimization possibilities and the future of the area, are also addressed in this work Mestrado Ciência da Computação Mestra em Ciência da Computação

Orientadores: Maurício Ferreira Magalhães, Jussi Kangasharju Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação Resumo: A segurança da informação é responsável pela proteção das informações contra o acesso nãoautorizado, uso, modificação ou a sua destruição. Com o objetivo de proteger os dados contra esses ataques de segurança, vários protocolos foram desenvolvidos, tais como o Internet Protocol Security (IPSEC) e o Transport Layer Security (TLS), provendo mecanismos de autenticação, integridade e confidencialidade dos dados para os usuários. Esses protocolos utilizam o endereço IP como identificador de hosts na Internet, tornando-o referência e identificador no estabelecimento de conexões seguras para a troca de dados entre aplicações na rede. Com o advento da Web e o aumento exponencial do consumo de conteúdos, como vídeos e áudios, há indícios da migração gradual do uso predominante da Internet, passando da ênfase voltada para a conexão entre hosts para uma ênfase voltada para a obtenção de conteúdo da rede, paradigma esse conhecido como information-centric networking. Nesse paradigma, usuários buscam por documentos e recursos na Internet sem se importarem com o conhecimento explícito da localização do conteúdo. Como consequência, o endereço IP que previamente era utilizado como ponto de referência do provedor de dados, torna-se meramente um identificador efêmero do local onde o conteúdo está armazenado, resultando em implicações para a autenticação correta dos dados. Nesse contexto, a simples autenticação de um endereço IP não garante a autenticidade dos dados, uma vez que o servidor identificado por um dado endereço IP não é necessariamente o endereço do produtor do conteúdo. No contexto de redes orientadas à informação, existem propostas na literatura que possibilitam a autenticação dos dados utilizando somente o conteúdo propriamente dito, como a utilização de assinaturas digitais por bloco de dado e a construção de árvores de hash sobre os blocos de dados. A ideia principal dessas abordagens é atrelar uma informação do provedor original do conteúdo nos blocos de dados transportados, por exemplo, uma assinatura digital, possibilitando a autenticação direta dos dados com o provedor, independentemente do host onde o dado foi obtido. Apesar do mecanismo citado anteriormente possibilitar tal verificação, esse procedimento é muito oneroso do ponto de vista de processamento, especialmente quando o número de blocos é grande, tornando-o inviável de ser utilizado na prática. Este trabalho propõe um novo mecanismo de autenticação utilizando árvores de hash com o objetivo de prover a autenticação dos dados de forma eficiente e explícita com o provedor original e, também, de forma independente do host onde os dados foram obtidos. Nesta tese, propomos duas técnicas de autenticação de dados baseadas em árvores de hash, chamadas de skewed hash tree (SHT) e composite hash tree (CHT), para a autenticação de dados em redes orientadas à informação. Uma vez criadas, parte dos dados de autenticação é armazenada em um plano de segurança e uma outra parte permanece acoplada ao dado propriamente dito, possibilitando a verificação baseada no conteúdo e não no host de origem. Além disso, essa tese apresenta o modelo formal, a especificação e a implementação das duas técnicas de árvore de hash para autenticação dos dados em redes de conteúdo através de um plano de segurança. Por fim, esta tese detalha a instanciação do modelo de plano de segurança proposto em dois cenários de autenticação de dados: 1) redes Peer-to-Peer e 2) autenticação paralela de dados sobre o HTTP Abstract: Information security is responsible for protecting information against unauthorized access, use, modification or destruction. In order to protect such data against security attacks, many security protocols have been developed, for example, Internet Protocol Security (IPSec) and Transport Layer Security (TLS), providing mechanisms for data authentication, integrity and confidentiality for users. These protocols use the IP address as host identifier on the Internet, making it as a reference and identifier during the establishment of secure connections for data exchange between applications on the network. With the advent of the Web and the exponential increase in content consumption (e.g., video and audio), there is an evidence of a gradual migration of the predominant usage of the Internet, moving the emphasis on the connection between hosts to the content retrieval from the network, which paradigm is known as information-centric networking. In this paradigm, users look for documents and resources on the Internet without caring about the explicit knowledge of the location of the content. As a result, the IP address that was used previously as a reference point of a data provider, becomes merely an ephemeral identifier of where the content is stored, resulting in implications for the correct authentication data. In this context, the simple authentication of an IP address does not guarantee the authenticity of the data, because a hosting server identified by a given IP address is not necessarily the same one that is producing the requested content. In the context of information-oriented networks, some proposals in the literature proposes authentication mechanisms based on the content itself, for example, digital signatures over a data block or the usage of hash trees over data blocks. The main idea of these approaches is to add some information from the original provider in the transported data blocks, for example, a digital signature, enabling data authentication directly with the original provider, regardless of the host where the data was obtained. Although the mechanism mentioned previously allows for such verification, this procedure is very costly in terms of processing, especially when the number of blocks is large, making it unfeasible in practice. This thesis proposes a new authentication mechanism using hash trees in order to provide efficient data authentication and explicitly with the original provider, and also independently of the host where the data were obtained. We propose two techniques for data authentication based on hash trees, called skewed hash tree (SHT) and composite hash tree (CHT), for data authentication in information-oriented networks. Once created, part of the authentication data is stored in a security plane and another part remains attached to the data itself, allowing for the verification based on content and not on the source host. In addition, this thesis presents the formal model, specification and implementation of two hash tree techniques for data authentication in information-centric networks through a security plane. Finally, this thesis details the instantiation of the security plane model in two scenarios of data authentication: 1) Peer-to-Peer and 2) parallel data authentication over HTTP Doutorado Engenharia de Computação Doutor em Engenharia Elétrica

Orientador: Ricardo Dahab Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: A criptografia de chave pública está cada vez mais presente nos sistemas computacionais, provendo a estes diversas propriedades de segurança, dentre as quais: confidencialidade, integridade, autenticidade e irretratabilidade. O modelo de criptografia de chave pública explicitamente certificado é o mais comumente empregado, e compreende uma infraestrutura de chave pública (PKI) composta por procedimentos, hardware, software e pessoal administrativo para a sua operação. Tal infraestrutura é complexa e onerosa, o que torna o seu uso proibitivo em diversas situações. Neste trabalho foram abordados paradigmas de criptografia de chave pública alternativos ao paradigma PKI, com foco no paradigma sem certificados. Dentro deste paradigma, e com ênfase em segurança demonstrável, foram estudados os esquemas de cifrassinatura, os quais provêem eficientemente e simultaneamente as propriedades da encriptação de chave pública com as propriedades da assinatura digital: confidencialidade, integridade, autenticidade e irretratabilidade. Este trabalho tem como contribuições: (i) ataque contra a propriedade de indistinguibilidade do IBSC McCullagh-Barreto [MB04], (ii) proposta de correção do esquema CLSC Barbosa-Farshim [BF08], o qual havia sido quebrado por Selvi et al [SVR10b], (iii) exposição sistemática sobre segurança demonstrável, criptografia de chave pública sem certificados e cifrassinatura sem certificados Abstract: Public-key cryptography is ever more present on computational systems, providing them several security properties, including: confidentiality, integrity, authenticity and nonrepudiation. The explicitly certified public-key cryptography model is the most commonly employed one, and it consists of a public-key infrastructure (PKI) which requires procedures, hardware, software and management personnel for its operations. Such infrastructure is complex and costly, making its use prohibitive in many cenarios. This work approached alternative paradigms for public-key cryptography, with focus on the certificateless paradigm. On this paradigm, and with emphasis on provable security, we studied signcryption schemes, which provide efficiently and simultaneously the properties of public-key encryption with those of digital signature: confidentiality, integrity, authenticity and non-repudiation. This work has the following contributions: (i) attack against the indistinguishability property of IBSC McCullagh-Barreto [MB04] (ii) correction for the CLSC Barbosa- Farshim [BF08], which had been broken by Selvi et al [SVR10b], (iii) systematic exposition about provable security, certificateless public-key cryptography and certificateless signcryption Mestrado Ciência da Computação Mestre em Ciência da Computação

Orientador: Júlio César Lopez Hernández Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: O advento da criptografia assimétrica ou de chave pública possibilitou a aplicação de criptografia em novos cenários, como assinaturas digitais e comércio eletrônico, tornando-a componente vital para o fornecimento de confidencialidade e autenticação em meios de comunicação. Dentre os métodos mais eficientes de criptografia assimétrica, a criptografia de curvas elípticas destaca-se pelos baixos requisitos de armazenamento para chaves e custo computacional para execução. A descoberta relativamente recente da criptografia baseada em emparelhamentos bilineares sobre curvas elípticas permitiu ainda sua flexibilização e a construção de sistemas criptográficos com propriedades inovadoras, como sistemas baseados em identidades e suas variantes. Porém, o custo computacional de criptossistemas baseados em emparelhamentos ainda permanece significativamente maior do que os assimétricos tradicionais, representando um obstáculo para sua adoção, especialmente em dispositivos com recursos limitados. As contribuições deste trabalho objetivam aprimorar o desempenho de criptossistemas baseados em curvas elípticas e emparelhamentos bilineares e consistem em: (i) implementação eficiente de corpos binários em arquiteturas embutidas de 8 bits (microcontroladores presentes em sensores sem fio); (ii) formulação eficiente de aritmética em corpos binários para conjuntos vetoriais de arquiteturas de 64 bits e famílias mais recentes de processadores desktop dotadas de suporte nativo à multiplicação em corpos binários; (iii) técnicas para implementação serial e paralela de curvas elípticas binárias e emparelhamentos bilineares simétricos e assimétricos definidos sobre corpos primos ou binários. Estas contribuições permitiram obter significativos ganhos de desempenho e, conseqüentemente, uma série de recordes de velocidade para o cálculo de diversos algoritmos criptográficos relevantes em arquiteturas modernas que vão de sistemas embarcados de 8 bits a processadores com 8 cores Abstract: The development of asymmetric or public key cryptography made possible new applications of cryptography such as digital signatures and electronic commerce. Cryptography is now a vital component for providing confidentiality and authentication in communication infra-structures. Elliptic Curve Cryptography is among the most efficient public-key methods because of its low storage and computational requirements. The relatively recent advent of Pairing-Based Cryptography allowed the further construction of flexible and innovative cryptographic solutions like Identity-Based Cryptography and variants. However, the computational cost of pairing-based cryptosystems remains significantly higher than traditional public key cryptosystems and thus an important obstacle for adoption, specially in resource-constrained devices. The main contributions of this work aim to improve the performance of curve-based cryptosystems, consisting of: (i) efficient implementation of binary fields in 8-bit microcontrollers embedded in sensor network nodes; (ii) efficient formulation of binary field arithmetic in terms of vector instructions present in 64-bit architectures, and on the recently-introduced native support for binary field multiplication in the latest Intel microarchitecture families; (iii) techniques for serial and parallel implementation of binary elliptic curves and symmetric and asymmetric pairings defined over prime and binary fields. These contributions produced important performance improvements and, consequently, several speed records for computing relevant cryptographic algorithms in modern computer architectures ranging from embedded 8-bit microcontrollers to 8-core processors Doutorado Ciência da Computação Doutor em Ciência da Computação

Orientador: Julio César López Hernández Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Os algoritmos de resumo criptográfico são uma importante ferramenta usada em muitas aplicações para o processamento seguro e eficiente de informações. Na década de 2000, sérias vulnerabilidades encontradas em funções de resumo tradicionais, como o SHA-1 e o MD5, levou a comunidade a repensar o desenvolvimento da criptanálise destes algoritmos e projetar novas estratégias para a sua construção. Como resultado, o instituto NIST anunciou em novembro de 2007 um concurso público para o desenvolvimento de um novo padrão de funções de resumo, o SHA-3, contando com a participação de autores de todo o mundo. Esta dissertação foca nos aspectos da implementação em software de alguns algoritmos submetidos no concurso SHA-3, buscando compreender a forma como os autores desenvolveram a questão do custo computacional de seus projetos em diversas plataformas, além de entender os novos paradigmas de implementação introduzidos pela tecnologia presente nos processadores atuais. Como consequência, propusemos novas técnicas algorítmicas para a implementação em software de alguns algoritmos, como o Luffa e o Keccak, levando aos mesmos melhorias significativas de desempenho Abstract: Hash algorithms are an important tool of cryptography used in many applications for secure and efficient information processing. During the 2000 decade, serious vulnerabilities found at some traditional hash functions like SHA-1 and MD5 prompted the cryptography community to review the advances in the cryptanalysis of these algorithms and their design strategies. As a result, on November, 2007, NIST announced a public competition to develop a new cryptographic hash function, the SHA-3, which involved competitors throughout the world. This work focuses on the software implementation aspects of some of the SHA-3 submitted algorithms, seeking to comprehend how the authors resolved the computational cost issues at distinct platforms and to understand the new paradigms introduced by the present processors technology. As a consequence, we proposed new algorithmic techniques for the software implementation of Luffa and Keccak hash algorithms, improving their performance significantly Mestrado Teoria da Computação Mestre em Ciência da Computação

Orientador: José Plínio de Oliveira Santos Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatisitca e Computação Cientifica Resumo: Neste trabalho apresentaremos novas provas bijetivas para identidades relacionadas a partições em partes pares e distintas, generalizações das identidades de Rogers-Ramanujan entre outras. Porém o objetivo principal será trabalhar com sobrepartições de inteiros, dando a estes uma nova interpretação em termos de matrizes de três linhas. Exibiremos provas bijetivas para algumas classes de sobrepartições, apresentaremos um novo resultado que basicamente é identificar uma sobrepartição com partições planas; sendo este o principal resultado deste trabalho. No final apresentaremos algumas aplicações da representação de partição via matrizes de duas linhas: fórmulas fechadas para algumas classes destas partições. Abstract: In this work, we present new bijective proofs for identities related to partitions into distinct even parts, generalizations of Rogers-Ramanujan identities, among others. The basic aim is to work with overpartitions of integers, give a new interpretation in terms of three-line matrices. We will show bijective proofs for some classes of overpartitions. We will present a new result that is how to identify an overpartition (with some particularities) with plane partitions; which is one of the most important results. At the end we will present some applications of the representation of a partition as a two-line array: closed formulaes for some classes of these partitions. Doutorado Análise Combinatória Doutor em Matemática Aplicada

Orientador: Flavio Keidi Miyazawa Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Nesta tese, estudamos versões de teoria dos jogos dos problemas de empacotamento de itens e balanceamento de carga. Consideramos que a implementação de um algoritmo centralizado de controle é inviável, fazendo com que as entidades participantes do sistema ajam de maneira egoísta. Assim, a escolha egoísta de estratégias pelas entidades pode ou não levar a um estado estável do sistema, chamado de equilíbrio de Nash. Dependendo das condições definidas pelo modelo utilizado, devemos embutir certas regras para as entidades, contanto que as entidades tenham incentivo de utilizá-las e que, além disso, façam com que o sistema alcance um equilíbrio de Nash. Os principais resultados desta tese são relativos ao tempo de convergência para o equilíbrio de Nash, ou seja, buscamos saber quantas vezes os agentes mudam suas estratégias até alcançarem o equilíbrio de Nash, seja agindo de maneira completamente egoísta ou seguindo certas regras. Para o jogo de empacotamento de itens, apresentamos limitantes teóricos para o tempo de convergência, olhando ambos os casos de atualizações seqüenciais ou simultâneas das estratégias. Para o jogo de balanceamento de carga consideramos um modelo distribuído assíncrono com entidades heterogêneas, apresentando algumas regras que as entidades devem seguir e realizamos simulações para comparar as regras apresentadas Abstract: In this thesis, we study game-theorical versions of the bin packing and load balancing problems. We consider that the implementation of a centralized controller algorithm is not feasible, making the entities that participate in the system act in a selfish way. Thus, the selfish choice of the strategies by the entities may or may not lead to a stable state of the system, called Nash equilibrium. Depending on the conditions defined by the considered model, we must build certain rules for entities, provided that the entities have incentive to use them and also make the system reach a Nash equilibrium. The main results of this thesis are related to the convergence time to Nash equilibrium, i.e., we seek to know how many times the agents change their strategies until they reach a Nash equilibrium, whether they act in a completely selfish way or follow certain rules. For the bin packing game, we present theoretical bounds for the convergence time, considering both the cases of sequential or simultaneous updates of the strategies. For the load balancing game, we consider an asynchronous distributed model with heterogeneous entities, presenting some rules that the entities must follow and we carry out simulations to compare the presented rules Doutorado Teoria da Computação Doutor em Ciência da Computação

Orientador: Paulo Lício de Geus Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Existe uma grande quantidade de configurações presentes em sistemas atuais e gerir essas configurações é um trabalho árduo para qualquer administrador de sistema. Inúmeras configurações podem ser definidas para uma só máquina e as combinações entre elas implicam de forma significativa no seu desempenho. A partir do momento que um sistema em pleno funcionamento pára de funcionar, algo em sua estrutura pode ter mudado. Este cenário é comum no processo de desenvolvimento de software onde o código fonte pode deixar de compilar ou ainda uma funcionalidade pode se perder. Controladores de versão são usados para reverter o estado do código para uma data anterior, solucionando o problema. Verificadores de Integridade são utilizados para detectar estas mudanças, porém não possuem mecanismos específicos para recuperação. Este estudo propõe e implementa uma arquitetura integrada que combina verificação de integridade e mecanismos de recuperação. Foram executados testes para determinar a sobrecarga total deste método, além de estudos de caso para verificar a sua eficiência de recuperação Abstract: Current computer systems have a huge number of configurations that are hard to manage. The combinations of system configurations can impact on performance and behavior. From the moment that a system stops working correctly it is remarkable that something has changed. That is in common in software development, where changes made by the programmer may result in some features no longer working or the project not compiling anymore. Revision control systems can recover a previous state of the source code through revision mechanisms. Integrity checking is used to catch file modifications, however this technique does nothing toward recovering those files. This study proposes and implements an integrated architecture that combines integrity checking and restoring mechanisms. Tests were executed in order to measure the load imposed by the solution. In addition, analysis of three case studies shows the efficiency of the adopted solution Mestrado Segurança de Computadores

Orientador: Ricardo Dahab Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Os protocolos de trocas justas foram propostos como solução para o problema da troca de itens virtuais, entre duas ou mais entidades, sem que haja a necessidade de confiança entre elas. A popularização da internet criou uma crescente classe de usuários leigos que diariamente participam de transações de troca, como comercio eletrônico (e-commerce), internet banking, redes ponto-a-ponto (P2P), etc. Com tal demanda por justiça, e preciso garantir que os protocolos de trocas justas recebam a mesma atenção acadêmica dedicada aos protocolos clássicos. Neste contexto, fazem-se necessárias diretrizes de projeto, ferramentas de verificação, taxonomias de ataques e quaisquer outros artefatos que possam auxiliar na composição de protocolos sem falhas. Neste trabalho, apresentamos um estudo sobre o problema de trocas justas e o atual estado da arte das soluções propostas, bem como a possibilidade de criar, a partir de técnicas para a verificação formal e detecção de falhas em protocolos clássicos, metodologias para projeto e correção de protocolos de trocas justas. Abstract: Fair exchange protocols were first proposed as a solution to the problem of exchanging digital items, between two or more entities, without forcing them to trust each other. The popularization of the internet resulted in an increasing amount of lay users, which constantly participate in exchange transactions, such as electronic commerce (ecommerce), internet banking, peer-to-peer networks (P2P), etc. With such demand for fairness, we need to ensure that fair exchange protocols receive the same amount of attention, from academia, as classic protocols do. Within this context, project guideliness are needed, and so are verification tools, taxonomies of attack, and whatever other artifacts that may help correct protocol design. In this work we present a study on the fair exchange problem and the current state-of-the-art of proposed solutions, as well as a discussion on the possibility of building, from currently available formal verification and attack detection techniques for classic protocols, methods for fair exchange protocols design and correction. Mestrado Ciência da Computação Mestre em Ciência da Computação

Orientador: Ricardo Dahab Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Nesta tese é apresentada uma visão do campo de Assinaturas de Chave Pública sem Certificados (CL-PKC), resultado final de pesquisa empreendida durante o mestrado do autor na Universidade Estadual de Campinas. A abordagem aqui contida tem como principal base a Segurança Demonstrável; analisamos os modelos de segurança de CL-PKC, os esquemas já propostos na literatura, e suas demonstrações de segurança. Contribuímos também alguns novos resultados para a área, especificamente: o estudo da aplicabilidade do Lema da Bifurcação 'a esquemas de CL-PKC (§ 4.3.3); o algumas pequenas otimizações a esquemas seguros (§ 4.4.1); o demonstração de segurança para um esquema cuja segurança ainda era um problema em aberto (§ 4.4.2); o explicação de falhas em demonstrações de segurança de alguns esquemas (§ 4.4.4, § 4.4.5, § 4.4.7); o um ataque desconhecido a um esquema anteriormente suposto seguro (§ 4.4.4); o proposta de um modelo de segurança para agregação de assinaturas no modelo CLPKC (§ 5.4); o proposta de um novo esquema de assinaturas CL-PKC que permite agregação, assim como sua prova de segurança (§ 5.2) Abstract: In this thesis is presented a broad view of the field of Certificateless Public Key Signatures (CL-PKC), final result of the research undertaken by the author during his masters at the Campinas State University. Our approach is strongly based on the ideas behind Provable Security; we analyze the security models for CL-PKC, all schemes available in the literature, and their security proofs. We also contribute a few novel results, namely: o applicability of the Forking Lemma in the CL-PKC paradigm (§ 4.3.3); o small optimizations to secure schemes (§ 4.4.1); o security proof for a scheme whose security was an open problem (§ 4.4.2); o investigation of the problems in the security proofs of a few schemes (§ 4.4.4, § 4.4.5, § 4.4.7); o an attack on a scheme previously thought to be secure (§ 4.4.4); o proposal of a security model for aggregation of signatures in the CL-PKC paradigm (§ 5.4); o proposal of a new scheme for Certificateless Signatures that allows aggregation, along with its security proof (§ 5.2) Mestrado Sistemas de Computação Mestre em Ciência da Computação

Orientadores: Eliane Martins, Ricardo de Oliveira Anido Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Neste trabalho apresentamos uma proposta de geração de ataques para testes de protocolos de segurança. O objetivo é detectar vulnerabilidades de um protocolo, que um atacante pode explorar para causar falhas de segurança. Nossa proposta usa um injetor de falhas para emular um atacante que possui total controle do sistema de comunicação. Como o sucesso dos testes depende principalmente dos ataques injetados, nós propomos uma abordagem baseada em modelos para a geração de ataques. O modelo representa ataques conhecidos e reportados do protocolo sob teste. A partir deste modelo, cenários de ataque são gerados. Os cenários estão em um formato que é independente do injetor de falhas usado. Usando refinamentos e transformações, pode-se converter a descrição do cenário de ataque em scripts específicos do injetor de falhas. A proposta pode ser completamente apoiada por ferramentas de software. Nós ilustramos o uso da proposta com um estudo de caso, um protocolo de segurança para dispositivos móveis Abstract: We present an attack injection approach for security protocols testing. The goal is to uncover protocol vulnerabilities that an attacker can exploit to cause security failures. Our approach uses a fault injector to emulate an attacker that has control over the communication system. Since the success of the tests depends greatly on the attacks injected, we propose a model-based approach for attack generation. The model represents reported known attacks to the protocol under test. From this model, attack scenarios are generated. The scenarios are in a format that is independent of the fault injector used. Using refinements and transformations, the abstract scenario specification can be converted to the specific fault injector scripts. The approach can be completely supported by tools. We illustrate the use of the approach in a case study, a security protocol for mobile devices Mestrado Tolerâcia a Falhas Mestre em Ciência da Computação

Orientador: Ricardo Dahab Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: A criptografia baseada em identidades representa uma alternativa ao modelo de certificação digital, exigindo menor esforço para solucionar o problema de autenticidade da chave pública, mas perdendo a custódia da chave privada, que será gerada por uma autoridade de confiança. O modelo de criptografia sem certificados soluciona o problema da custódia da chave privada sem a utilização de certificados digitais. Neste modelo, o usuário tem a posse de uma parte da chave privada e com isso a chave pública passa a ser constituída de uma parte gerada pela autoridade de confiança e uma parte gerada pelo usuário. A cifrassinatura é uma primitiva criptográfica que reúne as vantagens do ciframento e da assinatura em uma única operação, permitindo maior eficiência e segurança. A literatura possui diversas propostas de ciframento sem certificados e assinatura sem certificados, mas não tem uma proposta genérica de cifrassinatura sem certificados. Este trabalho propõe um protocolo de cifrassinatura sem certificados eficiente, que pode ser implementado usando dois emparelhamentos bilineares. Considerando a importância de emparelhamentos bilineares para a construção do protocolo proposto, este trabalho apresenta os conceitos matemáticos necessários para a obtenção de emparelhamentos bilineares eficientes e resistentes a ataques ao problema do logaritmo discreto sobre a curva elíptica e sobre o corpo de extensão resultante do cálculo do emparelhamento bilinear. São apresentados também algoritmos eficientes para aritmética de precisão arbitrária, aritmética de curvas elípticas e cálculo de emparelhamentos. Além disso, são discutidos modelos formais de segurança, como por exemplo o modelo do oráculo aleatório. Finalmente, o modelo de criptografia baseada em identidades e o modelo de criptografia sem certificados são discutidos e com isso é possível apresentar a proposta de cifrassinatura sem certificados e argumentar que esta proposta _e segura e eficiente Abstract: Identity based cryptography is an alternative to digital certification, which requires less computational effort to solve the problem of public key authenticity. On the other hand, identity based cryptography has the problem of key escrow, because the private key is generated by a trust authority. The certificateless cryptography model solves the key escrow problem without digital certificates. In this model, the user computes a parcial private key that is used to compose the entire private key. In the same way, the public key has two parts: one generated by the user and the other generated by the trust authority. Signcryption is a cryptographic primitive that has the advantages of encryption and signature together in a single operation, allowing the construction of secure and efficient protocols. The literature has many certificateless encryption and certificateless signature protocols, but there is no generic and efficient certificateless signcryption scheme. This work proposes an efficient certificateless signcryption protocol, that can be implemented with just two bilinear pairings. Considering the importance of bilinear pairings for the construction of the proposed protocol, this work presents the mathematical concepts for efficient bilinear pairings, that can resist against discrete logarithm atacks on the elliptic curve and on the extension field. This works also presents efficient algorithms for big number arithmetic, elliptic curve arithmetic and the Miller algorithm for pairings. It also presents formal security models, such as the random oracle model. Finally, identity based cryptography and certificateless cryptography models are defined and the proposed certificateless signcryption scheme is presented and we argue that it is secure and eficient, although no formal proof is given Mestrado Criptografia Mestre em Ciência da Computação

Orientador: Ricardo Dahab Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Redes de Sensores Sem Fio (RSSFs) são compostas em sua maioria por pequenos nós sensores dotados de recursos extremamente limitados. Estes, por sua vez, se comunicam com o mundo externo através de nós poderosos chamados de sorvedouros ou estações rádio base. RSSFs são empregadas com o objetivo de monitorar regiões, oferecendo dados sobre a área monitorada para o resto do sistema. Tais redes podem ser utilizadas para diferentes aplicações, tais como operações de resgate em áreas de conflito/desastre, espionagem industrial e detecção de exploração ilegal de recursos naturais. Em RSSFs existem aplicações críticas nas quais propriedades de segurança são de vital importância. Segurança, por sua vez, é comumente alavancada através de esquemas de distribuição de chaves. A maioria dos padrões de distribuição de chaves presentes na literatura, todavia, não são apropriados para RSSFs: métodos baseados em esquemas de chave pública convencionais, devido aos seus requisitos de processamento e banda; chaves de grupo, em função das suas vulnerabilidades de segurança; e chaves par-a-par (pairwise), por causa da baixa escalabilidade. Um outro dado é que há uma vasta gama de arquiteturas propostas para RSSFs e que uma mesma técnica de distribuição de chaves pode ser a melhor para uma, mas não para outra, visto que diferentes arquiteturas de rede exibem padrões de comunicação distintos. Em outras palavras, não existe uma panacéia, e mecanismos de distribuição de chaves para RSSFs devem, portanto, levar em consideração as idiossincrasias das arquiteturas para as quais são projetadas. Tudo isso torna extremamente difícil e desafiadora a tarefa de dotar RSSFs de segurança. O objetivo deste trabalho foi propor soluções de distribuição de chaves que, concomitantemente, (i) fossem compatíveis com os recursos dos sensores e (ii) considerassem as particularidades das arquiteturas para as quais são propostas. Como será mostrado ao longo desta tese, iniciamos nosso trabalho com soluções personalizadas para certas arquiteturas de RSSFs e evoluímos para soluções flexíveis em que a segurança é alavancada de forma não interativa - o que é ideal para este tipo de rede. Até onde sabemos, nosso trabalho é pioneiro em soluções de segurança para RSSFs hierárquicas e em distribuição de chaves de forma autenticada e não interativa, usando Criptografia Baseada em Identidade, neste tipo de rede. Abstract: Wireless sensor networks (WSNs) are ad hoc networks comprised mainly of small sensor nodes with limited resources and one or more base stations, which are much more powerful laptop-class nodes that connect the sensor nodes to the rest of the world. WSNs are used for monitoring purposes, providing information about the area being monitored to the rest of the system. Application areas range from battlefield reconnaissance and emergency rescue operations to surveillance and environmental protection. There are also critical WSN applications in which security properties are of paramount importance. Security, in turn, is frequently bootstrapped through key distribution schemes. Most of the key distribution techniques, however, are ill-suited to WSNs: public key based distribution, because of its processing and bandwidth requirements; global keying, because of its security vulnerabilities; complete pairwise keying, because of its memory requirements. It is worth noting, however, that a large number of WSN architectures have been proposed and a key distribution solution that is well suited to one architecture is likely not to be the best for another, as different network architectures exhibit different communication patterns. In other words, there is no panacea and the design of a key distribution scheme must therefore be driven by the peculiarities of the WSN architecture in question. This all makes extremely hard and challenging the objective of securing WSNs. In this work, we aimed at proposing key distribution schemes that are both (i) lightweight and (ii) able to fulfill architecture-specific needs. As it will be shown throughout this thesis, we began our work with customized solutions for certain types of WSNs and then, subsequently, turned our attention to more flexible solutions, where security is bootstrapped in a non-interactive way through the use of Identity-Based Cryptography. Doutorado Teoria da Computação Doutor em Ciência da Computação

Orientador: Jacques Wainer Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Esta dissertação apresenta um modelo discricionário de delegação que permite controlar a formação de cadeias de delegações, tanto através da limitação no comprimento de tais cadeias, como através da definição de condições para utilização e aceitação de novas delegações. Juntamente com o mecanismo de delegação proposto, é apresentado um mecanismo de revogação que considera o máximo comprimento de cada cadeia de delegações, e a relação de força entre delegações, permitindo assim que os sujeitos existentes permaneçam com o maior conjunto de direitos após uma revogação. Uma das principais vantagens em relação à definição de condições associadas à cada delegação é possibilidade de reforçar restrições por conteúdo e contexto. Enquanto o controle de acesso por conteúdo permite que o acesso a determinado objeto, ou recurso, seja controlado com base em atributos e características do próprio objeto em questão, o controle de acesso por contexto considera características de contexto relativas ao sistema como um todo, ou referentes ao contexto em que o usuário solicitou determinado acesso. Será apresentado um mecanismo que permite a utilização deste tipo de informação na definição de condições em delegações. Será apresentado um mecanismo para definição de proibições, que torna possível proibir que usuários utilizem determinadas direitos, mesmo que estes usuários tenham recebido, tais direitos através de delegaçõesde outros usuários do sistema. Através da utilização de condições também é possível a definição de delegações temporais, que são delegações que devem ser consideradas válidas somente durante determinados períodos de tempo, ou enquanto condições de dependência em relação a outras delegações forem atendidas, como será discutido. Finalmente, será apresentado um arcabouço de um servidor de autorizações, que permitiu avaliar o modelo proposto. Neste arcabouço foram implementados os principais algoritmos apresentados, e foi formulada uma arquitetura unificada para criação e revogação de delegações, bem como para verificação de autorizações Abstract: This thesis presents a model of delegation that makes it possible to control the creation of delegation chains, both by limiting the lenght of such chains, and by defining restrictions for the use and acceptance of new delegations. Together with the proposed delegation mechanism, it is presented a revocation mechanism that considers the maximum length of each delegation chain, and the strength relation between delegations, allowing the existing subjects to retain the maximum set of rights after a revocation. One of the biggest advantages regarding the definition of conditions associated with each delegation is the possibility of enforcing context and content based restrictions. While the content based access control allows the access to a specific object to be controlled based on its attributes and characteristics, the context based access control considers context information related to the system as a whole, or regarding the context in which a user made an access request. It will be presented a mechanism that allows the use of this type of information in the definition of conditions in delegations. A prohibition mechanism will be presented, which prevents users from using certain rights, even though these users have received such rights through other users delegations. As it will be discussed, it is also possible, through the use of conditions, to define temporal delegations, which are delegations that must be considered valid only during specific periods of time, or while dependency condition regarding other delegations are met. Finally, it will be presented a prototype of an authorization server, that was used to validate the proposed model. In this prototype, the main algorithms were implemented, and a unified architecture was formulated both for the creation and recation of delegations, as well as for the verification of authorizations Mestrado Mestre em Ciência da Computação

Orientador: Sueli Irene Rodrigues Costa Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica Resumo: Este trabalho está dividido em duas partes. A primeira e dedicada ao problema de encontrar o menor vetor não nulo de um reticulado. Este é um problema de alta complexidade computacional e que tem grande interesse tanto para a Teoria dos Códigos, como para diversas outras áreas. Esse mínimo está associado a performance do reticulado em termos da codificação: quanto maior for a razão entre este mínimo e o determinante do reticulado, melhor e a distribuição dos pontos no espaço (alta densidade de empacotamento). Nesta tese demos ênfase ao caso especial dos reticulados obtidos por uma projeção ortogonal do reticulado n-dimensional dos inteiros na direção de seus elementos. Tais reticulados estão associados ao problema de codificação contínua fonte/canal. Mostramos nos casos tri e quadridimensionais em que condições podemos garantir reticulados bons, ou seja, com alta densidade de empacotamento. Neste processo foram também construídos dois novos algoritmos, um para cálculo da base de Minkowski de um reticulado e outro específico para a busca da norma mínima do reticulado-projeção. Na segunda parte trabalhamos com grafos em toros planares que são quocientes de reticulados, os quais são isomorfos a grafos circulantes. Estabelecemos a conexão entre estes códigos esféricos rotulados por grupos cíclicos e códigos perfeitos na métrica de Lee. A partir de tal associação foram também obtidos resultados sobre o gênero 1 e a determinação do dos gênero de uma classe especial de grafos circulantes que tem número arbitrariamente grande de conexões (grau) Abstract: The research developed here is related and inspired by problems in coding theory. It is presented in two parts. In the first we focus on the search for the minimum nonvanishing vector of a lattice, specially in the case of a projection of the ndimensional integer lattice in the direction of one of its vectors. This is a problem of high computational complexity which is related to the search for efficient joint sourcechannel continuous coding. In the second part we deal with flat torus graphs generated by a quotient of lattices and which are labeled by a a cyclic group of isometries. We show that any circulant graph is isomorphic to one of these graphs and hence associated to a spherical code. Through these isomorphism a complete classification of circulant graphs of genus one and the genus of an arbitrarily high order class of circulant graphs is obtained. Doutorado Geometria Topologia Doutor em Matemática

Orientador: Julio Cesar Lopez Hernandez Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Em diversos cenários, é desejável que não apenas o conteúdo de uma comunicação seja preservado, mas também a identidade dos seus participantes. Satisfazer esta propriedade requer mecanismos diferentes dos comumente utilizados para fornecer sigilo e autenticidade. Neste trabalho, a problemática da comunicação anônima na Internet é abordada a partir do projeto e implementação de componentes específicos para este fim. Em particular, são apresentados um componente para roteamento anônimo eficiente em sistemas peer-to-peer estruturados e um serviço de nomes para facilitar a publicação de serviços anonimizados. As principais contribuições deste trabalho são: (i) estudo de definições, métricas e técnicas relacionadas a anonimato computacional; (ii) estudo do paradigma de Criptografia de Chave Pública Sem Certificados; (iii) projeto de uma rede de anonimização completa, adequada tanto para comunicação genérica como para funcionalidade específica; (iv) estudo e projeto de esquemas de roteamento em ambientes anônimos; (v) projeto de um serviço de nomes que aplica técnicas criptográficas avançadas para fornecer suporte a serviços anonimizados; (vi) implementação em software dos conceitos apresentados Abstract: In several scenarios, it¿s desirable to protect not only the content of a communication, but the identities of its participants. To satisfy this property, different techniques from those used to support confidentiality and authentication are commonly required. In this work, the problem of anonymous communication on the Internet is explored through the design and implementation of specific components with this function. In particular, a name service and a routing component for anonymous environments are presented. The main contributions of this work are: (i) the study of definitions, metrics and techniques related to computational anonymity; (ii) the study of Certificateless Public Key Cryptography, a new model of public key cryptography; (iii) the design of a complete anonymization network, suitable for both generic communication and dedicated functionality; (iv) the study and design of routing schemes for anonymous communication; (v) the design of a name service to support location-hidden services in the anonymous network; (vi) the implementation of the concepts presented. Mestrado Criptografia e Segurança Computacional Mestre em Ciência da Computação

Orientador: Ricardo Dahab Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Computação Resumo: A escolha dos parâmetros sobre os quais uma dada implementação de Criptografia sobre Curvas Elípticas baseia-se tem influência direta sobre o desempenho das operações associadas bem como sobre seu grau de segurança. Este trabalho visa analisar a forma como os padrões mais usados na atulalidade lidam com este processo de seleção, mostrando as implicações que tais escolhas acarretam Abstract: The choice of parameters associated with a given implementation of ECC (Elliptic Curve Cryptography) has direct impact on its performance and security leveI. This dissertation aims to compare the most common standards used now-a-days, taking into account their selection criteria and their implications on performance and security Mestrado Engenharia de Software Mestre em Ciência da Computação

Orientador: Paulo Licio de Geus Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Os mecanismos de segurança empregados em ambientes de redes atuais têm complexidade crescente e o gerenciamento de suas configurações adquire um papel fundamental para proteção desses ambientes. Particularmente em redes de computadores de larga escala, os administradores de segurança se vêem confrontados com o desafio de projetar, implementar, manter e monitorar um elevado número de mecanismos, os quais possuem sintaxes de configuração heterogêneas e complicadas. Uma conseqüência dessa situação é que erros de configuração são causas freqüentes de vulnerabilidades de segurança. O presente trabalho oferece uma sistemática para o gerenciamento da configuração de sistemas de segurança de redes que corresponde especialmente às necessidades dos ambientes complexos encontrados em organizações atuais. A abordagem, construída segundo o paradigma de Gerenciamento Baseado em Modelos, inclui uma técnica de modelagem que trata uniformemente diferentes tipos de mecanismos e permite que o projeto de suas configurações seja executado de forma modular, mediante um modelo orientado a objetos. Esse modelo é segmentado em Subsistemas Abstratos, os quais encerram um grupo de mecanismos de segurança e outras entidades relevantes do sistema ¿ incluindo seus diferentes tipos de mecanismo e as inter-relações recíprocas entre eles. Uma ferramenta de software apóia a abordagem, oferecendo um diagrama para edição de modelos que inclui técnicas de visualização de foco e contexto. Essas técnicas são particularmente adaptadas para cenários de larga escala, possibilitando ao usuário a especificação de certa parte do sistema sem perder de vista o contexto maior no qual essa parte se encaixa. Após a conclusão da modelagem, a ferramenta deriva automaticamente parâmetros de configuração para cada mecanismo de segurança do sistema, em um processo denominado refinamento de políticas. Os principais resultados deste trabalho podem ser sumarizados nos seguintes pontos: (i) uma técnica de modelagem uniforme e escalável para o gerenciamento de sistemas de segurança em ambientes complexos e de larga escala; (ii) um processo para o projeto de configurações apoiado por uma ferramenta que inclui técnicas de foco e contexto para melhor visualização e manipulação de grandes modelos; (iii) uma abordagem formal para a validação do processo de refinamento de políticas Abstract: The security mechanisms employed in current networked environments are increasingly complex, and their configuration management has an important role for the protection of these environments. Especially in large scale networks, security administrators are faced with the challenge of designing, deploying, maintaining and monitoring a huge number of mechanisms, most of which have complicated and heterogeneous configuration syntaxes. Consequently, configuration errors are nowadays a frequent cause of security vulnerabilities. This work offers an approach to the configuration management of network security systems specially suited to the needs of the complex environments of today¿s organizations. The approach relies upon the Model-Based Management (MBM) paradigm and includes a modelling framework that allows the design of security systems to be performed in a modular fashion, by means of an object-oriented model. This model is segmented into logical units (so-called Abstract Subsystems) that enclose a group of security mechanisms and other relevant system entities, offering a more abstract representation of them. In this manner, the administrator is able to design a security system¿including its different mechanism types and their mutual relations¿by means of an abstract and uniform modelling technique. A software tool supports the approach, offering a diagram editor for models, which includes focus and context visualization techniques. These techniques are particularly suitable to large scale scenarios, enabling a designer to precisely specify a given part of the system without losing the picture of the context to which this part belongs. After the model is complete, the tool automatically derives configuration parameters for each security mechanism in the system, in a process called policy refinement. The major results of this work can be summarised as follows: (i) definition of a uniform and scalable object-oriented modelling framework for the configuration management of large, complex network security systems; (ii) development of a configuration design process assistes by a tool that implements focus and context techniques to improve visualization and manipulation of large models; (iii) a formal validation approach of the policy refinement process Doutorado Doutor em Ciência da Computação

Orientador: Guido Costa Souza de Araujo Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: O aumento na comunicação utilizando-se sistemas eletrônicos tem demandado a troca de informações cifradas, permitindo a comunicação entre dois sistemas desconhecidos através de um canal inseguro (como a Internet). Criptografia baseada em curvas elípticas (ECC) é um mecanismo de chave pública que requer apenas que as entidades, que desejam se comunicar, troquem material de chave que é autêntico e possuem a propriedade de ser computacionalmente infactível descobrir a chave privada somente com informações da chave pública. A principal operação de sistemas ECC é a multiplicação de ponto (kP) que gasta 90% de seu tempo de execução na multiplicação em corpos finitos. Assim, a velocidade de um sistema ECC é altamente dependente do desempenho das operações aritméticas em corpos finitos. Nesse trabalho, estudamos a especialização de um processador NIOS2 para aplicações criptográficas em curvas elípticas. Mais precisamente,implementamos operações em corpos finitos e a multiplicação de pontos sobre F2163 como instruções especializadas e periféricos do NIOS2, e as analisamos em termos de área e speedup. Determinamos também, quais implementações s¿ao mais apropriadas para sistemas voltados a desempenho e para ambientes restritos. Nossa melhor implementação em hardware da multiplicação de pontos é capaz de acelerar o cálculo de kP em 2900 vezes, quando comparado com a melhor implementação em software executando no NIOS2. De acordo com a literatura especializada, obtivemos a mais rápida implementação da multiplicação de pontos sobre F2163 , comprovando que bases normais Gaussianas s¿ao bastante apropriadas para implementações em hardware Abstract: The increase in electronic communication has lead to a high demand for encrypted information exchange between unfamiliar hosts over insecure channels (such as the Internet). Elliptic curve cryptography (ECC) is a public-key mechanism that requires the communicating entities exchange key material that is authentic and has the property of being computationally infeasible to determine the private key from the knowledge of the public key. The fundamental ECC operation is the point multiplication (kP), which spends around 90% of its running time in the finite field multiplication. Therefore, the speed of an ECC scheme is highly dependent on the performance of its underlying finite field arithmetic. In this work, we studied the specialization of the NIOS2 processor for ECC applications. More precisely, we implemented the finite field operations and the point multiplication over F2163 as NIOS2 custom instructions and peripherals, and thus, we analyzed them in terms of area and speedup. We also determined which implementations are best suited for performance-driven and area-constrained environments. Our best hardware implementation of the point multiplication is capable of accelerating the kP computation in 2900 times, when compared to the best software implementation running in the NIOS2. According to the literature, we obtained the fastest point multiplier in hardware over F2163 , proving that Gaussian normal bases are quite appropriate for hardware implementations Mestrado Arquitetura e Sistemas de Computação Mestre em Ciência da Computação

Orientador: Ricardo Dahab Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: A indústria desenvolvedora de software vem promovendo a Arquitetura Orientada a Serviços (SOA) como sendo um novo marco no processo evolutivo de desenvolvimento de software. Segundo o Gartner Group, estima-se que a arquitetura SOA estará presente em grande parte dos novos desenvolvimentos de software ate o ano de 2008. Portanto, nesse processo evolutivo o estilo de arquitetar, desenvolver e implementar novos processos de negócios e aplicações serão fortemente influenciados pela arquitetura SOA. Arquiteturas tradicionais se tornaram mais complexas, caras, difíceis de gerenciar e desafiadoras nos aspectos de integração, interoperabilidade e segurança. Como alternativa, surge a arquitetura SOA que promete reduzir custos integrando plataformas heterogêneas e reutilizando linhas de códigos já existentes, proporcionando assim agilidade na melhoria e ou geração de novos negócios. A arquitetura SOA também tem seus desafios, talvez o maior deles seja disponibilizar mecanismos de seguranças adequados para cada tipo de negócio proporcionado por ela. Por exemplo, os processos de negócios baseados na arquitetura SOA tendem a ser diferentes dos processos de negócios baseados em arquitetura tradicionais, em conseqüência disso novos requisitos de segurança surgem e as vezes demandam mecanismos de segurança alternativos aos já existentes. A arquitetura SOA esta de certa forma refém da capacidade de prover mecanismos de segurança adequados e principalmente interoperabilidade entre esses mecanismos. Esses são pelo menos os desafios mais relevantes que a arquitetura SOA tem pela frente antes de se tornar de fato uma arquitetura completa. Alias, o sucesso da Arquitetura Orientada a Serviço (principalmente serviços baseados em Web Services) esta totalmente dependente do sucesso na utilização dos mecanismos de segurança disponíveis. Essa dissertação tem o propósito de discutir e avaliar as características básicas da Arquitetura Orientada a Serviços e os novos requisitos de seguranças gerados pelos processos de negócios. A capacidade de interoperabilidade entre os mecanismos de segurança atuais e os novos mecanismos desenvolvidos para arquitetura SOA também fazem parte dessa dissertação Abstract: The software industry is promoting Service Oriented Architecture (SOA) as a new starting point of the evolutionary process of software development. Based on estimations from the Gartner Group, by 2008, most of the software development initiatives will be SOA-based. Hence, in this evolutionary process, SOA will be a strong influence in the design, development and implementation of new business processes and applications. Traditional architectures became more complex, expensive, difficult to manage and challenging, with respect to the aspects of integration, interoperability and security. As an alternative, SOA architecture offers easy and cost-effective integration of heterogeneous platforms and the reuse of existing source code, with direct consequences in the dynamism of business. SOA architecture also has its challenges: perhaps making available an adequate security mechanism for each type of business could be considered one of them. For instance, business processes based on SOA architecture usually are different from traditional business processes; therefore, new security requirements need to be addressed by security mechanisms, usually different from traditional ones. SOA architecture is heavily tied with security mechanisms; providing interoperability between systems implies in finding a good coupling of different security mechanism, without losing the advantages provided by the architecture. Thus, these challenges have to be met before SOA becomes a complete architecture. In fact, the success of Services Oriented Architecture (mainly Web Services) is totally dependent on the success of its security mechanisms. The objective of this dissertation is to discuss and evaluate the basic characteristics of the SOA architecture and the security requirements of business processes. The interoperability between traditional security mechanisms and the new security mechanisms of the SOA architecture are also covered by this dissertation Mestrado Engenharia de Computação Mestre em Computação

Orientador: Paulo Licio de Geus Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Os sistemas de arquivos distribuídos são um componente importante em praticamente todas as redes coorporativas, acadêmicas e até mesmo domésticas. Neste cenário, o NFS (Network File System) é um dos sistemas de maior importância, não só pela importância histórica em ter sido um dos pioneiros, mas por ser largamente utilizado em todo o mundo. Porém, o NFS foi projetado com recursos insuficientes de segurança. A versão 3 do NFS, que é a versão utilizada atualmente em ambientes de produção, apresenta um nível de segurança praticamente nulo. Mais recentemente, foi elaborada a especificação da versão 4 do protocolo que corrige adequadamente os problemas de segurança. Contudo, o protocolo apresenta um grau de complexidade extremamente elevado e, devido a isso, poucos estão dispostos a enfrentar sua implementação. Atualmente, existem apenas algumas implementações preliminares deste protocolo e as mesmas não se encontram completas e estáveis. Logo, a migração para o NFSv4 a curto prazo é inviável. Neste trabalho foi realizado um amplo estudo dos diversos aspectos envolvidos com a segurança de sistemas de arquivos distribuídos, em especial o NFS. Foram levantadas as deficiências do NFS e foram analisados diversos trabalhos envolvendo segurança no compartilhamento de arquivos. Este trabalho resultou no projeto e implementação do NFS Guard, uma ferramenta para agregar segurança ao NFS versão 3 de forma simples e totalmente compatível com as redes NFS já instaladas. O NFS Guard utiliza clientes e servidores NFS padrão e não requer recompilação de nenhum software já instalado, podendo ser utilizado inclusive em sistemas de código fechado. Para isso foi desenvolvida uma técnica de Kerberização utilizando interceptação de pacotes, que também pode ser utilizada para agregar segurança a outros serviços além do NFS Abstract: Distributed File Systems are an important component in practicalIy every corporate, academic or even home network. In this scenario, NFS (Network File System) is one of the most important of these systems, not only due to its historical importance for being one of the pioneers, but also for being largely used alI over the world. However, NFS was designed with insufficient security features. NFS version 3, which is the version currently being used in production environments, presents an almost nulI security leveI. More recently, the version 4 of the protocol was designed,among other thigs, to tackle the security issues. Nevertheless, this protocol presents an extremely high leveI of complexity, and consequently, a few want to face its implementation. At the moment, a few preliminary implementations are available, but usualIy incomplete and unstable. Hence, the migration to NFSv4 in a short term is not feasible. In this work we accomplished a wide study of many aspects involved with distributed file system security, specialIy with regards to NFS. NFS's shortcoming were identified e many works involving security in file sharing were analyzed. This work resulted in the design and implementation of NFS Guard, a tool to add security do NFS version 3 in a simple way and totalIy compatible with instalIed NFS networks. NFS Guard uses standard NFS client and server and does not require recompilation of any installed software, so it can be used with closed source systems. To accomplish that, a Kerberization technique was developed using packet interception, which can also be used to add security to other services besides NFS Mestrado Ciência da Computação Mestre em Ciência da Computação

Orientador: Ricardo Dahab Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Com a proliferação dos sistemas de informação geográfica (GIS) e a disponibilidade crescente de dados espaciais, empresas de vários segmentos têm tido a oportunidade de criar bases de dados geográficas para uso próprio ou fornecimento de serviços. A representação de informações nessas bases de dados se dá através de mapas em formato vetorial, produzidos geralmente a um alto custo, mas de fácil reprodução. Este trabalho tem como objetivo a apresentação de um novo método para inserção de marcas d'água visuais em mapas vetoriais digitais, para combater a cópia e a distribuição ilegais desse tipo de mídia. Neste novo método, a marca d'água, formada pelos pixels de uma imagem, é inserida em um mapa através de deslocamentos controlados de suas coordenadas. A detecção da marca d'água em um mapa é feita com a extração da imagem inserida e sua comparação com a original. Vários experimentos práticos mostram que o método é bastante resistente a diversos tipos de ataque, como cropping, adição de coordenadas, alteração da ordem das entidades, inserção de ruído, transformações locais e globais e combinações desses ataques Abstract: The proliferation of geographic information systems (GIS) and the increasing availability of spatial data makes it possible to create geographic databases for a large variety of ends and services. The information in these databases is represented by digital vector maps which are expensive to produce, but easy to copy. In this work we present a new method for embedding visual watermarks into digital vector maps to counter illegal copying and distribution of these digital contents. In this new method, the watermark, formed by pixels of an image, is embedded within a map by controlled displacements of its coordinates. The detection of the watermark within a map is accomplished by extracting the embedded image and comparing it with the original one. Many experiments show that the method has good resiliency against attacks such as cropping, coordinate addition, entity order scrambling, random noise insertion, global and local transformations and some combinations of these attacks Mestrado Engenharia de Computação Mestre Profissional em Computação

Orientador: Flavio Keidi Miyazawa Dissertação (mestrado profissional) - Universidade Estadual de Campinas. Instituto de Computação Resumo: Neste trabalho, investigamos abordagens para problemas de roteamento, que têm como finalidade encontrar um melhor conjunto de rotas para que veículos possam transportar mercadorias a clientes geograficamente dispersos, respeitando certas restrições, como por exemplo, a de capacidade de carga dos veículos. Para isto, além de pesquisas em diversas fontes de informações, desenvolvemos um aplicativo para auxiliar no entendimento dos algoritmos, na ilustração do texto e na realização de experimentos. A partir de observações feitas durante as execuções do aplicativo, experimentamos combinações de critérios de seleção de localidades, utilizando tais combinações durante a realização dos movimentos de intercâmbio de vértices entre rotas de uma conhecida estratégia, a Metaheurística Busca Tabu. Foram combinados critérios baseados em distâncias com critérios baseados em ângulos, para compor algoritmos que foram testados com instâncias clássicas utilizadas por diversos pesquisadores. Os resultados obtidos foram apresentados juntamente com os de outras estratégias, fornecendo valores iguais ao melhor valor conhecido para duas instâncias, e valores intermediários para as outras cinco instâncias utilizadas nos testes In this work, we examine some approaches for vehicle routing problems, to find a best set of routes to enable companies for delivery goods or commodities to customers, respecting some constraints, such as vehicles loading capacity. To this purpose, besides researching available information sources, we have developed a software to help us to understand the algorithms issues, for enriching the text with illustrations, and for effectiving some experiments concerning to previously selected approaches. From the analysis made during running software process, we decided to arrange chosen vertices criterias, using these arrangements in the vertices interchanging movements between routes of an already know method, the Tabu Search Metaheuristic. More precisely, we have combined distances and angles criteria, to implement algorithms on which it were tested using some classical instances considered by several researchers. The obtained results are presented with those selected approaches, and it provided us two equals values to the best known solution, and five intermediate values amoung to the others used on these experiments Mestrado Engenharia de Software Mestre Profissional em Computação

Orientador : Paulo Licio de Geus Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: As Redes Privadas Virtuais (Virtual Private Network { VPN) são um componente importante dentro de um ambiente cooperativo, principalmente em seu aspecto econômico, ao permitirem que conexões dedicadas e estruturas de acesso remoto, que possuem custos bastante elevados, sejam substituídas por conexões publicas. Contudo, a conseqüente utilização de uma rede publica para o trafego de informações privadas e a extensão do perímetro de segurança das organizações, trazem consigo serias implicações de segurança. O acesso remoto VPN, onde o usuário remoto acessa diretamente os recursos da organização, possui implicações de segurança especas ainda mais serias que precisam ser consideradas. Neste contexto, a escolha de um conjunto de mecanismos de segurança capazes de prover uma solução adequada para os diversos possíveis cenários de acesso remoto constitui uma decisão fundamental para a segurança do ambiente cooperativo. Neste trabalho foi realizado um amplo estudo dos diversos aspectos envolvidos na elaboração de uma solução segura e viável de acesso remoto VPN. Através desta analise foi possível identificar os principais requisitos e avaliar algumas das soluções existentes que compõem esse complexo cenário. Como resultado da avaliação desses fatores foi possível desenvolver uma solução de acesso remoto VPN utilizando o software FreeS/WAN, uma implementação Open Source do protocolo IPSec baseada em Linux. Devido _a expressiva parcela de mercado ocupada por produtos Microsoft, também foram abordadas algumas soluções de clientes VPN baseados em Windows Abstract: A Virtual Private Network (VPN) is an important component in a cooperative computing environment, since it allows expensive dedicated connections and remote access infrastructures to be substituted by cheaper public connections. However, the use of a public network for transporting private information, and the consequent extension of an organization's security perimeter, brings serious implications for information security. Remote access VPN, in which a remote user has direct access to an organization's resources, has even more serious, speci_c, security implications that must be addressed. In this context, the choice of the most appropriate security mechanisms for enabling remote access whilst ensuring the security of the cooperative environment, in a diverse range of possible scenarios, is a fundamental decision. This work presents the results of a detailed study of the diverse aspects involved in the elaboration of a secure and viable remote access VPN solution. From this study, it has been possible to identify the principal requirements for remote access VPN and review some of the existing solutions available for this complex scenario. Using these results, a remote access VPN solution has been developed using the FreeS/WAN software, an opensource implementation of the IPSec protocol for Linux. Due to the signi_cant market share occupied by Microsoft products, some Windows based client VPN solutions are also discussed. Mestrado Ciência da Computação Mestre em Ciência da Computação

Orientador: Ricardo Dahab Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Computação Resumo: A integração de aplicações é um item dentro do universo da tecnologia da informação com demanda em forte crescimento. A descentralização do processamento das aplicações, a transposição dos limites físicos das corporações sustentada pelo avanço tecnológico, bem como as constantes mudanças do ponto de vista dos negócios estimulam esse crescimento. A discussão de um Modelo Conceitual para EAI (Enterprise Application Integration) explorada nesse trabalho tem por objetivo o estudo do problema da integração de aplicações, a partir do levantamento e esclarecimento dos seus requisitos e é concluída com a proposição conceitual de uma solução. Fazem parte do estudo os tipos de integrações conforme a camada onde estão os dados a serem integrados, são discutidos os métodos e a abrangência a serem considerados para realização do levantamento do projeto de integração, as várias estratégias e dispositivos utilizados para integração propriamente dita e finalmente é proposto um modelo conceitual que visa atender ao conjunto de requisitos de integração discutidos Abstract: There has been a strong increase of the need for integration within the universe of Information Technology, spurred mainly by the decentralization of application processing, the transposition of physical limits of enterprises and the constant changes on business models. This work discusses and proposes a conceptual model for EAI ¿ Enterprise Application Integration, having as starting point the study and clarification of its requirements, and concluding with the proposal of a conceptual solution. As part of this study different requirements are considered such as the types of layer-dependent data integration, the methods and scope of the integration project, and the several strategies and devices to be utilized in the integration itself. The resulting conceptual model aims at satisfying these requirements Mestrado Engenharia de Computação Mestre em Computação

Orientadores: Nelson Luis Saldanha da Fonseca, Omar Carvalho Branquinho Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Computação Resumo: As redes locais sem fio (WLANs) têm crescido muito ultimamente com a popularidade do padrão 802.11. Diferentemente das redes cabeadas, as WLANs têm algumas características específicas da tecnologia sem fio e utilizam configurações de parâmetros que afetam o desempenho e a interoperabilidade. Este trabalho avalia as redes locais em fio 802.11b, com arquiteturas Fat e arquiteturas Thin. Apresentam-se resultados de medidas de desempenho, nos quais os Pontos de Acesso (APs) testados foram submetidos a tráfego UDP, tendo sido testado o tráfego no sentido AP para estação sem fio. Foram avaliadas situações de taxa máxima fornecida, comportamento com saturação de tráfego e comportamento com estação em condição desfavorável. Mostra-se a superioridade de desempenho na arquitetura Thin em relação às arquiteturas Fat. Justifica-se o desempenho considerando uma priorização de tráfego em função da relação sinal-ruído Abstract: Wireless Local Area Networks (WLANs) have grown a lot with the popularity of the 802.11 standard. WLAN is different than network wired, it has some specific features from wireless technology and use parameters to configure that affect performance and interoperability. This assignrnent evaluate WLANs 802.11b, with Fat architectures and Thin architecture. It presents results of performance measures, tested Access Point (APs) were submitted to UDP traffic. The traffic flowed from AP to wireless station. The assignrnent evaluated situations to supplied maximum rate, behavior with traftic saturation and behavior with station in degraded rate. It show the good performance with Thin architecture regarding Fat architectures. It justify the performance result considering a traffic priorization for signal-noise ratio Mestrado Engenharia de Computação Mestre Profissional em Computação

Orientador : Guido Costa Souza de Araujo Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Segurança da Informação é fator chave para o desenvolvimento da sociedade. Diariamente quantidades massivas de dados são transportadas em redes de alta velocidade sem o suporte adequado de segurança criptográfica. Criptografia é infra-estrutura computacional e como tal está migrando para o hardware. Neste contexto a criação de um cripto-processador parametrizado utilizando tecnologia reconfigurável é de importância estratégica para o país. Esta dissertação apresenta estudos acerca da construção de tal cripto-processador, com os estudos e as implementações de vários mecanismos relacionados com dispositivos criptográficoso Foram implementados e testados em VHDe os algoritmos AES3 - FIPS4197 e ECC5 IEEE61363, rendendo aceleradores criptográficos de alto desempenho. Além disso, análises sobre a eficiência em hardware reconfigurável do algoritmo SHA -17 foram realizadas e seus resultados foram estendidos para toda família FIPS 180-2. O interfaceamento lógico e eletrônico do sistema também recebeu atenção nesta dissertação. No primeiro caso, um estudo de interfaces padrão para dispositivos criptográficos, ou tokens, baseados no PKCS8#11 foi realizado, rendendo uma implementação simplificada, mas compatível com este padrão. No caso do interfaceamento elétrico, diversas alternativas foram estudadas, resultando na escolha do sistema PCI PCI-SIG r.2.1 Abstract: Information Security is a key factor for de development ofmodern society. Every day, massive amounts of data flow through high speed networks without proper cryptographic security support. Cryptography services belong to the computational infTastructure and as such they are migrating into computer' s hardware. In this context, the design of a parameterized crypto-processor that uses reconfigurable technology contributes to the development of such technology in the country. This dissertation presents cases studies on the construction of such crypto-processor, along with de analysis of many mechanisms for cryptographic devices. By using VHDL for both implementation and testing, the AES - FIPS 197 and the ECC - IEEE 1363 algorithms were implemented yielding high performance cryptographic accelerators. In addition, efficiency analysis of hash functions as SHA-! and others from its family were conducted for the resulting reconfigurable hardware. The logical and electrical interfaces received some attention too. In the first case, a brief study of cryptographic token interfaces, based on PKCS# 11, was done and a simplified compatible implementation was constructed. For the electrical interface many alternatives were analyzed and the PCI PCI-SIG r.2.! was chosen Mestrado Mestre em Ciência da Computação

Orientador : Paulo Licio de Geus Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: o sistema imunológico humano, por ser capaz de garantir a sobrevivência de um indivíduo durante cerca de 70 anos, mesmo que ele se depare, a cada dia, com bactérias e vírus potencialmente mortais, provê uma rica fonte de inspiração para a segurança de redes de computadores. Além de representar um modelo bastante próximo das condições em que a maioria das redes de computadores se encontra, o sistema imunológico humano engloba uma série de características desejáveis a um sistema de segurança. Baseado nisso, este trabalho apresenta um mecanismo automático de resposta a intruções que integra um sistema de segurança projetado para detectar e responder a potenciais ameaças, mesmo que previamente não conhecidas. Com as respostas providas pelo mecanismo almeja-se conter o poder de uma possível intrusão, evitando que atividades ilícitas possam aumentar o comprometimento da confidencialidade, integridade e disponibilidade de um sistema. É fato que estratégias inadequadas de resposta ou respostas disparadas sob a detecção de falsos positivos podem prejudicar usuários e processos legítimos. Considerando essa possibilidade, o mecanismo dispõe de funcionalidades que procuram suavizar os efeitos de tal reação imprópria Abstract: The human immune system, since it is able to guarantee the survival of an individual for almost 70 years, even though he/she encounters potentially deadly parasites, bacteria and viruses on a daily basis, provides a rich source of inspiration for computer network security. Besides the fact that the human immune system presents a closely-related model of the real network conditions in the present day, it has many features that are desirable for a security system. Given these facts, this work presents an automatic intrusion response mechanism as part of a security system developed to detect and respond to harmful activities, including those not previously encountered. It is expected, with the response provided by the mechanism, to limit the harmful effects of a intrusion, thus avoiding illict activities to futher compromise confidenciality, integrity and availability of the system. It is well known that inadequate response strategies or responses triggered by false positive detection can harm legitimate user and process activities. Given this, the mechanism has features that seek to minimize the effects of inadequate reaction Mestrado Computação Mestre em Computação

Orientador: Flavio Keidi Miyazawa Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Computação Mestrado Engenharia de Computação Mestre Profissional em Computação

Orientador : Ricardo Dahab Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Um agente móvel é um programa que realiza uma tarefa de forma autônoma em nome de um usuário e que pode migrar para os servidores que forneçam os recursos necessários para a realização da tarefa delegada. Servidores de agentes fornecem um ambiente de execução para agentes e oferecem diversos serviços para migração, comunicação e acesso a recursos como bancos de dados, por exemplo. O conjunto de agentes, servidores de agentes e componentes auxiliares como diretório de nomes e uma terceira parte confiável forma uma infra-estrutura que suporta o paradigma de agentes móveis e é chamada de sistema de agentes móveis. A mobilidade de código presente nestes sistemas introduz novos problemas de segurança que devem ser considerados. Esta dissertação apresenta um estudo detalhado dos aspectos de segurança de sistemas de agentes móveis, compreendendo as classes de ameaças existentes, os requisitos de segurança e os mecanismos propostos para solucionar ou amenizar tais ameaças. Uma vez que a linguagem Java é comumente utilizada para desenvolver tais sistemas, a arquitetura de segurança da plataforma Java é analisada com o objetivo de se entender como os mecanismos utilizados podem ser úteis para a segurança destes sistemas. Diversos sistemas de agentes móveis, acadêmicos e comerciais, são analisados neste trabalho, com ênfase nas arquiteturas de segurança providas por cada um deles. As fraquezas encontradas são relatadas e melhorias, propostas. Para o sistema de agentes móveis Aglets, são adicionados novos mecanismos de segurança Abstract: A mobile agent is a program which executes tasks on behalf of a user and can autonomously migrate from server to server, searching for the necessary resources to complete the delegated tasks. Agent servers provide an execution environment and resources to agents, as well as several services for supporting migration and communication, among others activities. Agents, agent servers and auxiliary components such as a trusted third party form an infrastructure called mobile agent system. The code mobility in these systems raises new security issues that should be addressed. This dissertation presents a detailed account of the security aspects of mobile agent systems, encompassing existing threats, security requirements and the corresponding mechanisms proposed in the literature to counter these threats. Since Java is one of the languages of choice for the development of such systems, the security architecture of the Java platform is analyzed, in order to understand its impact on the security of mobile agent systems. As for specific systems, security mechanisms present in several proposals, academic and comercial, are detailed, pointing weaknesses and proposing strengthenings. For one system, Aglets, new, additional security features are presented and implemented. Mestrado Mestre em Ciência da Computação

Orientador: Arnaldo Vieira Moura Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Problemas de otimização combinatória são classificados na grande maioria das vezes como NP-difíceis. Para estes problemas, não são conhecidos algoritmos polinomiais capazes de resolvê-los. Logo, é necessário o desenvolvimento de estratégias eficientes para tratá-los. O desenvolvimento de técnicas híbridas para a resolução destes problemas tem por objetivo valorizar os pontos fortes dos métodos que estão sendo empregados, para, desta forma, compensar os pontos mais fracos, criando um procedimento de qualidade superior. Este trabalho propõe um método híbrido que integra técnicas de Programação por Restrições com metaheurísticas de Busca Tabu para atacar o problema de escalonamento de atividades na produção de um campo petrolífero. Como não há resultados anteriores para serem comparados com os resultados obtidos para as instâncias consideradas neste trabalho, modelos de programação matemática foram utilizados para a obtenção de limitantes duais para a solução do problema. Além disso, para determinar quão robusta é a técnica proposta, uma análise de sensibilidade foi realizada sobre as instâncias consideradas Abstract: Combinatorial optimization problems are generally NP-hard. As it is not known polinomial time algorithms to solve them, it is necessary to develop efficient strategies to treat them. The aim in developing hybrid techniques to solve combinatorial optimization problems is to strength the good features of the methods that are being combined to compensate for their weakness. In this paper, we propose a hybrid method that combines Constraint Programming techniques and Tabu Search metaheuristics to schedule the activities involved in the production process of an oil field. As there are no previous results to estabilish a comparision with the results obtained with the instances considered in this work, bounds were determined using mathematical programming models. Finally, to estabilish the robusteness of proposed method, a sensibility analysis was performed over the considered instances Mestrado Mestre em Ciência da Computação

Orientador: Ricardo Dahab Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Os smart cards são dispositivos com tamanho e formato semelhantes ao de um cartão de crédito comum, com o diferencial de serem equipados com um chip com poder de processamento e uma quantidade de memória muito superior a dos cartões de tarja magnética, cerca de 8K bytes. Estas características permitem o armazenamento de informações sigilosas, além de possibilitar o cálculo de sofisticadas funções criptográficas. Esses fatores fazem dos smart cards dispositivos móveis ideais para identificação de usuários e, portanto, extremamente úteis em aplicações voltadas a prestação de serviços como cartões de saúde, de crédito e outros. Uma das várias plataformas de smart cards que tem obtido destaque é o Java Card, uma versão reduzida da arquitetura Java para sua adequação à ambientes restritos. No entanto, a especificação dos recursos criptográficos disponibilizados no Java Card definiu o uso do algoritmo de chave pública RSA, que atualmente necessita de chaves com tamanho grande demais para dispositivos com pouca memória. Além disso, a aritmética modular necessária para o RSA requer o uso de um co-processador, o que introduz um custo adicional nos cartões. Uma alternativa ao RSA é a utilização de sistemas criptográficos baseados em curvas elípticas, que têm se mostrado os mais adequados para dispositivos com recursos limitados, como é o caso dos smart cards. Assim, o objetivo deste estudo foi verificar a viabilidade da implementação de algoritmos criptográficos baseados em curvas elípticas no Java Card utilizando a linguagem Java disponível no cartão. Um dos resultados do nosso trabalho foi a construção de uma biblioteca portável para a aritmética de curvas elípticas. No entanto, o desempenho dessa aritmética mostrou que ainda há muito o que melhorar antes que tais sistemas sejam úteis na arquitetura Java Cardo Mestrado Mestre em Ciência da Computação

Orientador : João Meidanis Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Hoje em dia, estão disponíveis, publicamente, uma imensa quantidade de informações genéticas. O desafio atual da Genômica é processar estes dados de forma a obter conclusões biológicas relevantes. Uma das maneiras de estruturar estas informações é através de comparação de genomas, que busca semelhanças e diferenças entre os genomas de dois ou mais organismos. Neste contexto, a área de Rearranjo de Genomas vem recebendo bastante atenção ultimamente. Uma forma de comparar genomas é através da distância de rearranjo, determinada pelo número mínimo de eventos de rearranjo que podem explicar as diferenças entre dois genomas. Os principais estudos em distância de rearranjo envolvem eventos de reversões e transposições. A presente coletânea é composta de oito artigos, contendo vários resultados importantes sobre Rearranjo de Genomas. Estes trabalhos foram apresentados em seis conferências, sendo uma nacional e cinco internacionais. Dois destes trabalhos serão publicados em importantes revistas internacionais e outro foi incluído como um capítulo de um livro. Nossas principais contribuições podem ser divididas em dois grupos: um novo formalismo algébrico e uma série de resultados envolvendo o evento de transposição. A nova teoria algébrica relaciona a teoria de Rearranjo de Genomas com a de grupos de permutações. Nossa intenção foi estabelecer um formalismo algébrico que simplificasse a obtenção de novos resultados, até hoje, muito baseados na construção de diagramas. Estudamos o evento de transposição de várias formas. Além de apresentarmos resultados sobre a distância de transposição entre uma permutação e sua inversa, também estudamos o problema de rearranjo envolvendo transposições e reversões simultaneamente, construindo algoritmos de aproximação e estabelecendo uma conjectura sobre o diâmetro. Usamos o formalismo algébrico para mostrar que é possível determinar a distância de fusão, fissão e transposição em tempo polinomial. Este é o primeiro resultado polinomial conhecido para um problema de rearranjo envolvendo o evento de transposição. Por último, introduzimos dois novos problemas de rearranjo: o problema de distância sintênica envolvendo fusões e fissões, e o problema de transposição de prefixos. Para ambos apresentamos resultados significativos, que avançam o conhecimento na área Abstract: Nowadays, a huge amount of genetic information is public1y available. Genomic's current challenge is to process this information in order to obtain relevant biological conc1usions. One possible way of structuring this information is through genome comparison, where we seek similarities and differences among the genomes of two or more organisms. In this context, the area of Genome Rearrangements has received considerable attention lately. One way of comparing genomes is given by the rearrangement distance, which is determined by the minimum number of rearrangement events that explain the differences between two genomes. The main studies in rearrangement distance involve reversal and transposition events. The present collection is composed of eight artic1es, containing several important results on Genome Rearrangements. These papers were presented in six conferences, one with Brazilian scope and five with international scope. Two of these works will be published in important international journals, and one other work appeared as a book chapter. Our main contributions can be divided into two groups: a new algebraic formalism and a series of results involving the transposition event. The new algebraic theory relates the genome rearrangement theory to the theory of permutation groups. Our intention was to establish an algebraic formalism that simplifies the creation of new results, up to now excessively based on the construction of diagrams. We studied the transposition event in several ways. Besides presenting results on the transpositions distance between a permutation and its inverse, we also studied the rearrangement problem involving transpositions and reversals simultaneously, constructing approximation algorithms and proposing a conjecture on the diameter. We used the algebraic formalism to show that it is possible to determine the distance of fusion, fission, and transposition in polynomial time. This is the first polynomial time result for a rearrangement problem involving the transposition event. Finally, we introduced two now rearrangement problems: the syntenic distance problem involving fission and fusion, and the prefix transposition problem. For each one of these problems we present significant results, widening the knowledge in this area Doutorado Doutor em Ciência da Computação

Orientador: Celio Cardoso Guimarães Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Esta dissertação de mestrado visa analisar a segurança dos protocolos de comunicação do sistema operacional Windows NT da Microsoft, especialmente quando usados em ambientes corporativos, onde é importante determinar se informações sigilosas estão adequadamente protegidas. Várias falhas importantes, de difícil correção, encontradas dispersas na bibliografia, foram apontadas e agrupadas. Novas e importantes vulnerabilidades foram descobertas, mostrando que mesmo o Windows 2000, a última versão deste sistema operacional, está sujeita a ataques eficientes que permitem sobrepujar esses protocolos de comunicação para obter informações sigilosas. Abstract: This master thesis aims to assess Microsoft Windows NT operating system communication protocols security, mainly when used in corporation environments, where it is important to ascertain if sensitive information is adequately secured. Several important security faults, which are difficult to correct and are dispersed in bibliography, were pointed and grouped. Important new vulnerabilities were discovered, showing that even Windows 2000, the last version of this operating system, is subject to efficient attacks that allow supplanting those communication protocols in order to obtain sensitive information. Mestrado Mestre em Ciência da Computação

Orientador : Ricardo Dahab Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Mestrado

Orientador : Paulo Licio de Geus Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: A principal característica de um ambiente cooperativo é a complexidade das conexões lógicas. Isso traz como conseqüência uma série de implicações de segurança. Diferentes níveis de acesso são agora utilizados para recursos, antes disponíveis apenas internamente, a partir de múltiplas e heterogêneas conexões. Isso faz com que a abordagem clássica dos firewalls, de criar uma separação entre a rede da organização e a rede pública, já não baste. Diversos conceitos e tecnologias têm que ser utilizados para que a segurança seja provida em ambientes cooperativos. Mais do que isso, um modelo de segurança também é necessário. Assim, este trabalho tem como objetivo apresentar tais conceitos e tecnologias de segurança, e propor um modelo para que eles possam proteger de fato um ambiente cooperativo. Política de segurança,firewalls, sistemas de detecção de intrusões, redes privadas virtuais, infra-estrutura de chaves públicas e autenticação são os tópicos abordados neste trabalho. O modelo de segurança proposto é formado por três elementos: i) o firewall cooperativo, que sugere uma arquitetura de segurança para a integração das diferentes tecnologias e conceitos; ii) um modo de minimizar os problemas resultantes da complexidade das regras de filtragem e iii) um modelo de cinco níveis hierárquicos de defesa, que visa facilitar a compreensão dos problemas de segurança existentes, e assim minimizar as possibilidades de erros na definição da estratégia de defesa da organização Abstract: The main charaeteristic of a cooperative environment is the complexity of logical connections. This brings about a series of security implications. Different access levels are now used for resources, previously available only internally, from multiple and heterogeneous connections. This makes the classical approach to firewalls, that of creating a division between the organization's and the public networks, no longer enough for the task. Diverse conecpts and technologies need to be employed to provide security to cooperative environments. More than that, a security model is also needed. As such, this work has as its main goal to present such security concepts and teehnologies and to propose a framework 50 that they may in fact protect a cooperative environment. Security poliey, firewalls, intrusion detection systems, virtual private networks, public key infrastructure and authentication are the topies discussed in this work. The security model proposed is made of three e!ements: í) the cooperative firewall, which suggests a security architecture for the integration of different concepts and technologies; ii) a way of minimizing the problems resulting from the complexity of filtering rules and iii) a 5-leveI hierarchical defense model, which intends to case the understanding of existing security problems, so that the process of defining the organization's defense strategy is made less error-prone Mestrado Mestre em Ciência da Computação

Orientador: Ricardo Dahab Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: A criptografia de chave-pública é, reconhecidamente, uma ferramenta muito útil para prover requisitos de segurança tais como confidencialidade, integridade, autenticidade e não-repudio, parte integrante das comunicações. A principal vantagem dos criptossistemas de curvas elípticas (CCE) em relação a outras tecnologias de chave-pública concorrentes tais como RSA e DSA, é que parâmetros significativamente menores podem ser usados nos CCE com o mesmo nível de segurança. Essa vantagem é especialmente importante em aplicações em ambientes computacionais limitados como cartões inteligentes, telefones celulares, computadores de bolso e pagers. De um ponto de vista prático, a implementação dos CCE apresenta vários desafios. Uma aplicação baseada nos CCE precisa que várias escolhas sejam feitas tais como o nível de segurança, algoritmos para implementar a aritmética no corpo finito subjacente, algoritmos para implementar a aritmética na curva elíptica, protocolos de curvas elípticas e a plataforma computacional. Essas escolhas podem ter um grande impacto no desempenho da aplicação resultante. Esta dissertação trata do desenvolvimento de algoritmos eficientes para implementação em software de criptossistemas de curvas elípticas sobre o corpo finito F2m. Neste contexto, foram desenvolvidos métodos eficientes para implementar a aritmética no corpo finito F2m, e para calcular múltiplos de um ponto elíptico, a operação fundamental da criptografia pública baseada em curvas elípticas. Nesta dissertação também foi abordado o problema da implementação eficiente em software dos algoritmos propostos, em diferentes plataformas computacionais tais como PCs, estações de trabalho, e em dispositivos limitados como o pager da RIM. Abstract: It is widely recognized that public-key cryptography is an important tool for providing security services such as confidentiality, data integrity, authentication and non-repudiation, which are requirements present in almost all communications. The main advantage of elliptic curve cryptography (ECC) over competing public-key technologies such as RSA and DSA is that significantly smaller parameters can be used in ECC, but with equivalent levels of security. This advantage is especially important for applications on constrained environments such as smart cards, cell phones, personal device assistants, and pagers. From a practical point of view, the implementation of ECC presents various challenges. An ECC-based application requires that several choices be made including the security level, algorithms for implementing the finite field arithmetic, algorithms for implementing the elliptic group operation, elliptic curve protocols, and the computer platform. These choices may have a significant impact on the performance of the resulting application. This dissertation focuses on developing efficient algorithms for software implementation of ECC over F2m. In this framework, we study different ways of efficiently implementing arithmetic in F2¿, and computing an elliptic scalar multiplication, the central operation of public-key cryptography based on elliptic curves. We also concentrate on the software implementation of these algorithms for different platforms including PCs, workstations, and constrained devices such as the RIM interactive pager. This dissertation is a collection of five papers written in English, with an introduction and conclusions written in Portuguese. Doutorado Doutor em Ciência da Computação

Orientadores: Ricardo Dahab, Cecilia M. F. Rubira Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: No limiar da sociedade da informação, cada computador pessoal, aparelho de televisão ou telefone celular contém, ou conterá muito em breve, software para comunicação em rede. Esse software deve garantir as propriedades de segurança (integridade, autenticação, sigilo e não repúdio) de uma grande variedade de atividades, tais como comércio eletrônico, correio eletrônico, acesso a bases de dados distribuídas, teleconferência, etc. A segurança de informações baseada em criptografia, antes conhecida apenas por um grupo pequeno de especialistas, hoje preocupa uma boa parcela da comunidade de software, quer na indústria, quer na academia. Por outro lado, software não é mais desenvolvido como há quatro décadas. Soluções monolíticas programadas artesanalmente para problemas específicos não são econômicas. A composição de componentes e a reutilização em larga escala são duas características que devem estar presentes nos softwares de segurança modernos. Esta dissertação combina técnicas de engenharia de software e segurança de informações. O resultado é um arcabouço de software que não somente oferece reutilização em larga escala de mecanismos da criptografia, mas (principalmente) captura o conjunto de cenários fundamentais de utilização das técnicas criptográficas. Atividades interdisciplinares às vezes exigem traduções de conceitos de urna disciplina para outra. Esta dissertação oferece uma abordagem inovadora para o tratamento dos mecanismos da criptografia: uma redefinição ou reescrita destes mecanismos como um conjunto fortemente coeso de padrões de projeto. Este conjunto de padrões auxiliará engenheiros de software inexperientes em segurança a identificar os serviços mais adequados às suas necessidades Abstract: Not informed Mestrado Mestre em Ciência da Computação

Orientador: Ricardo Dahab Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: A cada dia que passa o computador tem uma participação maior na vida das pessoas. Formas tradicionais de interação estão sendo substituídas por suas equivalentes digitais, virtuais ou eletrônicas. Correio eletrônico, lojas virtuais, dinheiro digitai, entre outros, já fazem parte do cotidiano das pessoas. Estas novas formas de interação não podem conviver com as formas tradicionais de garantir segurança. Uma assinatura em uma carta, uma impressão digital em um documento, um lacre de cera em um envelope, um cofre de aço cheio de cédulas também terão que ser substituídos por seus equivalentes eletrônicos. A criptografia moderna tem resposta para a maioria destes desafios.As funções criptográficas tradicionais de ciframento foram projetadas com o objetivo de garantir privacidade dos dados, mas nem sempre são suficientes para garantir outros requisitos de segurança. Devido ao fato de serem simples, rápidas e facilmente implementadas, tanto em hardware como em software, as funções criptográficas de hashing são utilizadas para gerar representações compactas de cadeias de bits (chamadas de impressão digital, message digest, valor hash ou simplesmente hash) que serão tratadas como seus identificadores únicos pelos protocolos criptográficos. Os principais usos das funções de hashing estão nos protocolos que visam garantir integridade, autenticidade e não repúdio. Este texto tem como objetivo estudar as funções de hashing criptográficas apresentando conceitos teóricos, implementações, usos e questões relevantes quanto à sua segurança. Abstract: Not informed. Mestrado Mestre em Ciência da Computação

Orientador: Celia Picinin de Mello Dissertação (mestrado) - Universidade Estadual de Campinas , Instituto de Computação Resumo: Esta dissertação aborda o assunto Coloração de Arestas (Problema da Classificação) restrita aos cografos, onde o problema está em aberto. Após uma breve compilação de resultados de pesquisas tanto em coloração de arestas como em cografos, encontram-se os resultados obtidos para uma subclasse obtida ao limitarmos o número de níveis da cotree para 3: Ser subgrafo overfull é equivalente a ser overfull ou vizinhança overfull e Algoritmos que colocam na Classe 1 subconjuntos desta subclasse obtidos ao limitarmos o número de ramos da cotree para 2. Abstract: This dissertation is on the subject of Edge Coloring (Classification Problem) restricted to cographs, for which the problem is open. After a brief compilation of research results on edge coloring and cographs, the results found for a subclass obtained when the number of levels of the cotree is limited to three: Being subgraph overfull is equivalent to being overfull or neighborhood overfull and Algorithms that place into Class 1 some subsets of this subclass obtained when the number of the branches of the cotree is limited to two. Mestrado Mestre em Ciência da Computação

Orientador: Ricardo Dahab Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Esta dissertação trata de sistemas projetados para permitir a transferência de valor através de comunicação eletrônica, ou, simplesmente, sistemas de pagamento eletrônico. Estes sistemas terão fundamental importância no desenvolvimento do comércio na Internet e fora dela. Três aspectos desses sistemas são abordados: classificação, análise formal e implementação. A classificação consiste de um esquema que descreve um sistema de pagamento através da sua tipificação, dos requisitos desejáveis, seu funcionamento e fatores de implementação. Este esquema permite analisar, comparar e melhor compreender os sistemas de pagamento. Durante o processo de análise, pudemos encontrar similaridades em diversas classes de tais sistemas. A análise formal é feita pela aplicação de dois métodos adequados à análise de sistemas criptográficos. Em conjunto com a aplicação destes métodos formais, é apresentado um modelo que generaliza o funcionamento dos sistemas de pagamento baseados em cartões de crédito, e que facilita a compreensão deste tipo de sistema. Utilizando o esquema de classificação proposto, implementamos um protótipo capaz de automatizar parte do processo de construção de sistemas de pagamento Abstract: Not informed Mestrado Mestre em Ciência da Computação

Orientador: Cid Carvalho de Souza Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Esta dissertação dá ênfase à abordagem poliedral para a resolução exata do Problema da Clique .Máxima com Peso nas Arestas. Dado um grafo completo não-dirigido Kn = (Vn, En), onde |Vn|= n, com um peso Cij associado a cada aresta (i,j) ? En, e um inteiro b, onde b = n; procuramos uma clique C em Kn cuja sorna dos pesos das arestas em C seja máxima e |C| = b. São apresentadas e discutidas diferentes formulações de programação linear inteira para o problema. Investigamos ainda a estrutura facial do poliedro associado ao problema realizando urna revisão bibliográfica das desigualdades conhecidas e introduzindo novas famílias de facetas. Por último, descrevemos os experimentos computacionais realizados com um algoritmo branch-and-cut e com urna metaheurística, ambos propostos neste trabalho. As maiores instâncias resolvidas de forma exata para este problema na literatura referem-se a grafos completos com no máximo 30 vértices. Neste trabalho, resolvemos exatamente instâncias para grafos com até 48 vértices e mostramos a força computacional para as novas desigualdades que introduzimos. Abstract: Given a complete non-directed graph Kn = (Vn, En) on n nodes with weights on the edges and an integer b = n, we look for a clique C in Kn whose sum of the weights of the edges in e is maximum and such that |C| = b. We discuss on different integer programming formulations and investigate the facial structure of the polyhedron associated to the problem. New families of facet defining inequalities are introduced. Finally we describe our computational experiments with a branch-and-cut algorithm and a metaheuristic that we have proposed. The largest instances that are solved exactly in the literature refer to complete graphs with at most 30 nodes. In this work we solve to optimality instances for graphs with up to 48 nodes and we show the computational strength of the new inequalities we have introduced. Mestrado Mestre em Ciência da Computação

Orientador: João Carlos Setubal Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação Resumo: Abordamos os principais algoritmos para o problema de emparelhamento máximo em grafos genéricos e desenvolvemos uma implementação paralela eficiente na prática, baseada no algoritmo seqüencial de Edmonds. Por prática entendemos uma implementação eficiente num multiprocessador de memória com partilhada. A implementação consiste em permitir que cada processador procure caminhos aumentantes no grafo de forma assíncrona e independente dos demais. Embora a busca ocorra de forma paralela, o aumento do emparelhamento é feito por somente 1 processador por vez, o que garante a corretude do algoritmo sem incorrrer em atraso significativo no tempo de execução. O desenvolvimento da implementação teve como antecedente uma experiência negativa de paralelização baseada no algoritmo de Micali e Vazirani. Abstract: In this work we present the most important matching algorithms for general graphs and develop an efficient parallel implementation in practice based on Edmonds'matching algorithm. By practice we mean an efficient implementation on a shared memory multiprocessor. The implementation allows each processor to find augmenting paths assinchronously and independently of each other. Each matching augmentation is done by only one processor, and this makes the algorithm correct without causing significant delay in the execution time, in practice. The development of this implementation was made after a nega tive experience of paralelization based on the sequential algorithm of Micali and Vazirani. Mestrado Mestre em Ciência da Computação

Orientador: Claudio L. Lucchesi Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação Resumo: Esta dissertação tem como objetivo apresentar igualdades minimax em grafos que envolvem cortes orientados; cortes ímpares e suas coberturas. A primeira metade da dissertação trata das igualdades que relacionam famílias disjuntas máximas de cortes com as coberturas mínimas dos cortes do grafo. Na segunda parte, os papéis destes problemas são inveI:tidos, isto é, as igualdades relacionam cortes mínimos com famílias disjuntas máximas de coberturas dos cortes. Mostramos ao longo do trabalho que em muitos casos é possível estabelecer analogias entre resultados para cortes orientados e para cortes ímpares. Estas analogias apresentam-se de duas maneiras: através de enunciados semelhantes e através de demonstrações semelhantes. Entre os teoremas apresentados na primeria parte do trabalho, destacam-se os Teoremas de ~ucchesi- Younger e de Edmonds-Giles para cortes orientados e os de Lovász e de Seymour para cortes ímpares. Também são apresentados teoremas que tratam de circuitos orientados e ímpares em grafos planares, mostrando que a analogia também se estende para outros tipos de problemas. Na segunda parte estabelecemos relações entre a igualdade minimax dual ao Teorema de Lovász com a generalização de uma famosa conjectura de Fulkerson. . Provamos um caso particular desta igualdade. Apresentamos também um resultado para um caso particular da igualdade dual ao Teorema de Lucchesi- Younger que foi provado por Schrijver e independentemente por Feofiloff e Younger. Abstract: The goal of this dissertation is to unify some results of Graph Theory related to directed cuts, odd cuts and their coverings. In the first half of this work we show equalities that relate maximum disjoint families of cuts with the minimum coverings of the cuts of the graph. In the second half, we present the duals of those equalities, i. e., they relate minimum cuts with disjoint families of coverings. Qur main purpose. is to provi de examples that show analogies between results on directed cuts and odd cuts. The analogies are of two types: in the statements of the results and in their proofs. Among the results presented in the first half, the most important are Lucchesi- Younger and Edmonds-Giles' theorems on directed cuts and Lovász and Seymour's theorems for odd cuts. In the last part of this work we extend a result by Seymour that relates the dual of Lovász's theorem with a generalizatión of a famous conjecture due to Fulkerson. We prove a particular case of that equality. We also show an equality for a particular case of the dual of LucchesiYounger's theorem which had been proved by Schrijver and independent1y by Fe,ofiloff and Younger. Mestrado Mestre em Ciência da Computação