Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T09:16:09Z (GMT). No. of bitstreams: 1 Sambinelli_Maycon_M.pdf: 1793287 bytes, checksum: 11aee090fa90d75328e5caf25578f7da (MD5) Previous issue date: 2014 / Resumo: Problemas de emparelhamentos estáveis consistem em dividir um ou mais grupos de agentes em pares, onde cada agente possui uma lista de preferências ordenada, e deseja-se encontrar uma emparelhamento entre eles que respeite um critério de estabilidade que é baseado nas suas preferências. Estes problemas são importantes pois possuem muitas aplicações práticas, tais como associação de residentes de medicina à hospitais, alocação de recursos em comunicação sem fio e doação de rins. Devido à importância do tema, esta dissertação apresenta um survey descrevendo os problemas mais importantes junto com seus principais resultados / Abstract: Stable matching problems consist of dividing one or more groups of agents in pairs, where each agent has an ordered preference list, and one wish to find a matching between them which respects a stability criterion that is based on their preferences. These problems are important because they have many practical applications, such as association of medical residents to hospitals, resource allocation in wireless communication and kidney donation. Due to the importance of the topic, this dissertation presents a survey describing the most important problems along with its main results / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Marco Aurélio Amaral Henriques / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-26T04:02:15Z (GMT). No. of bitstreams: 1 Sangalli_LeandroAparecido1988-_M.pdf: 2889538 bytes, checksum: 474d1ae695fc20d0f0b214ac8ba4716f (MD5) Previous issue date: 2014 / Resumo: Emparelhamentos bilineares sobre curvas elípticas são funções matemáticas que podem viabilizar protocolos criptográficos promissores. Porém, um fato que enfraquece o desenvolvimento destes protocolos é o alto custo computacional para calcular estes emparelhamentos. Diversas técnicas de otimização foram propostas nos últimos anos para realizar este cálculo de forma mais eficiente. Dentre estas técnicas existem as que mudam o tipo de emparelhamentos, o tipo de curvas elípticas ou a forma de cálculo dos emparelhamentos. As curvas Barreto-Naehrig são conhecidas como curvas amigáveis para emparelhamentos, pois se destacam para aplicações que buscam eficiência no cálculo dos mesmos. Este trabalho avalia em detalhes o custo das operações presentes no cálculo de alguns dos emparelhamentos mais utilizados atualmente definidos sobre curvas Barreto-Naehrig. Por meio desta análise, foi possível realizar uma comparação destes emparelhamentos no nível de operações de adição, multiplicação, quadrado, inversão e redução modular sobre um corpo finito primo e sobre um processador genérico. Os resultados mostram que de acordo com os parâmetros adotados, um dos emparelhamentos mais utilizados (Optimal Ate) pode não apresentar o melhor desempenho entre os analisados. Além disso, foi possível avaliar como o cálculo dos emparelhamentos é afetado pela adoção de diferentes processadores, desde aqueles com palavras curtas até aqueles que no futuro poderão ter palavras muito longas / Abstract: Bilinear pairings over elliptic curves are functions that support promising cryptographic protocols. However, a fact that hinders the development of these protocols is their high computational cost. Many techniques seeking more efficiency in the calculation of pairings have been proposed in the last years. Among these techniques are those that change the pairing type, the curve type and/or the pairing calculation method. Barreto-Naehrig curves are known as pairing-friendly curves, because they perform well in applications that require more efficiency in the pairing calculation. This work evaluates the cost of operations present in the most used pairings that are based on Barreto-Naehrig curves. With this evaluation, it was possible to compare these pairings at the level of basic operations as addition, multiplication, square, inversion and modular reduction over a prime finite field in a generic processor. The results show that, for the security parameters adopted in this work, one of the most used pairing algorithms (Optimal Ate) is not the fastest among those evaluated. Moreover, this work estimates the impact caused in the pairing calculation by different processors, ranging from the current short-medium word processors to the future very long word ones / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2018-06-05T13:32:44Z No. of bitstreams: 1 texto completo.pdf: 3038671 bytes, checksum: 989b48613d3d2c169a2fc7e19dc661aa (MD5) / Made available in DSpace on 2018-06-05T13:32:44Z (GMT). No. of bitstreams: 1 texto completo.pdf: 3038671 bytes, checksum: 989b48613d3d2c169a2fc7e19dc661aa (MD5) Previous issue date: 2018-02-28 / Pesquisa desenvolvida a partir das noções sobre grafos, grafos eulerianos, árvores, emparelhamentos em grafos, grafos planares e coloração. Foram abordados alguns dos principais teoremas e lemas, bem como imagens e exemplos para facilitar a leitura. Conclusão da pesquisa com o relato das aulas práticas sobre grafos. / The research was developed based on the notion about graphs, eulerian graphs, trees, matchings in graphs, planar graphs and coloring. Some of the main theorems and lemmas were discussed, as well as images and examples to facilitate reading. The conclusion of the research with the report of the practical classes about graphs. / Sem lattes e agência de fomento.

Orientador: Claudio Leonardo Lucchesi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-07T04:48:23Z (GMT). No. of bitstreams: 1 Miranda_AlbertoAlexandreAssis_M.pdf: 924668 bytes, checksum: 5707312a9e0513f890e4affc3858fbb6 (MD5) Previous issue date: 2006 / Resumo: Um grafo G que tem emparelhamento perfeito é o Pfaffiano se existe uma orientação D das arestas de G, tal que todo circuito conforme de G tem orientação ímpar em D. Um subgrafo H de G é conforme se G- V (H) tem emparelhamento perfeito. Uma orientação de um circuito par é ímpar se numa dada direção de percurso do circuito o número de arestas que concorda com a direção é ímpar. Calcular o número de emparelhamentos perfeitos de um grafo, no caso geral, _e NP-difícil [11, pág. 307]. No entanto, para grafos Pfaffiano, seu cálculo torna-se polinomial [11, pág. 319]. A caracterização de grafos bipartidos Pfaffiano, feita por Little, tem quase trinta anos [9]. No entanto, somente nos últimos anos apareceram algoritmos polinomiais para reconhecimento de tais grafos, por McCuaig [13] e independentemente por Robertson, Seymour e Thomas [14]. A solução para este problema resolve também uma série de problemas, muitos deles clássicos, em teoria dos grafos, economia e química, como descrito no artigo de McCuaig [13, págs. 16 a 35]. Nesta dissertação, apresentamos uma prova de corretude do algoritmo distinta das duas provas anteriormente conhecidas / Abstract: A graph G that contains a perfect matching is Pfaffiano if there is an orientation D of the edges of G, such that every conformal circuit of G is oddly oriented in D. A subgraph H of G is conformal if G - V (H) has a perfect matching. A circuit with an even number of edges is oddly oriented if the number of edges whose orientation in D agrees with any sense of traversal of the circuit is odd. Counting the number of perfect matchings of a graph is known to be NP-hard [11, page 307]. However, when restricted to Pfaffiano graphs, this problem is solvable in polynomial time [11, page 319]. The characterisation of Pfaffiano bipartite graphs, achieved by Charles Little, is almost thirty years old [9]. However, only recently, polynomial time algorithms for determining whether a bipartite graph is Pfaffiano were discovered, by McCuaig [13] and independently by Robertson, Seymour and Thomas [14]. This problem's solution solves a lot of problems, some of them are quite famous, in graph theory, economy and chemistry, as described in McCuaig's article [13, pages 16 to 35]. On this dissertation, we present a new proof of the correctness of this algorithm distinct from the two previously known proofs / Mestrado / Mestre em Ciência da Computação

Orientador: Claudio Leonardo Lucchesi / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T06:54:51Z (GMT). No. of bitstreams: 1 Miranda_AlbertoAlexandreAssis_D.pdf: 571362 bytes, checksum: bd3600cbf8fe0c2875d8e5c60b6abfd3 (MD5) Previous issue date: 2009 / Resumo: A área de grafos Pfaffianos apresenta muitos problemas em aberto. Nesta tese resolvemos dois problemas sobre grafos Pfaffianos. O primeiro problema resolvido é a obtenção de um algoritmo polinomial para reconhecimento de grafos quase-bipartidos Pfaffianos. Além disso, estendemos tanto o algoritmo como a caracterização de grafos quase-bipartidos Pfaffianos para a classe dos grafos meio-bipartidos. O segundo resultado é a obtencão de vários resultados estruturais básicos sobre grafos k-Pfaffianos. Utilizando esses resultados, obtivemos um contra-exemplo para a conjectura de Norine, que afirma que o número Pfaffiano de todo grafo é uma potência de quatro: apresentamos um grafo cujo numero Pfaffiano é 6 / Abstract: The area of Pfaffian graphs contains many open problems. In this thesis, we solve two problems related to Pfaffian graphs. The first result is a polynomial time algorithm to recognize near-bipartite Pfaffian graphs. Moreover, we extend this algorithm and the characterization of near-bipartite Pfaffian graphs to the class of half-bipartite graphs. The second result is obtaining several basic structural results concerning k-Pfaffian graphs. Using these results, we obtained a counter-example to Norine's conjecture, which states that the Pfaffian number of a graph is always a power of four: we present a graph whose Pfaffian number is 6 / Doutorado / Matematica Discreta e Combinatoria / Doutor em Ciência da Computação

Orientador: Julio César López Hernández / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:18:34Z (GMT). No. of bitstreams: 1 Gouvea_ConradoPortoLopes_D.pdf: 3342900 bytes, checksum: b3a072bdbc369f1a1fffd95e1c1f4365 (MD5) Previous issue date: 2013 / Resumo: A implementação eficiente e segura de esquemas criptográficos é um aspecto importante da criptografia aplicada. Neste trabalho, foca-se na implementação em software de algoritmos relevantes da criptografia de curvas elípticas (CCE), criptografia baseada em emparelhamentos (CBE), e de cifração autenticada (CA). Duas plataformas computacionais modernas foram utilizadas: o microcontrolador MSP430, bastante utilizado em redes de sensores sem fio, e o processador ARM, amplamente empregado por dispositivos móveis como smartphones e tablets que estão se tornando cada vez mais populares. Técnicas para a melhoria de desempenho em software utilizando conjuntos de instruções, periféricos e melhorias algorítmicas são descritas. A implementação segura, cujo objetivo é prevenir certos ataques de canais secundários, também é estudada e novas técnicas são providas para reduzir seu impacto na velocidade em processadores ARM. Tais resultados contribuem para a construção eficiente e segura de sistemas criptográficos em sensores sem fio e processadores móveis / Abstract: The efficient and secure implementation of cryptographic schemes is an important aspect of practical cryptography. In this work, we focus on the software implementation of relevant algorithms in elliptic curve cryptography (ECC), pairing-based cryptography (PBC) and in authenticated encryption (AE). Two modern computational platforms were targeted: the MSP430 microcontroller often used in wireless sensor networks, and the ARM processor, widely employed in mobile devices such as smartphones and tablets which are increasingly becoming ubiquitous. Techniques for improving the software performance by taking advantage of instruction sets, peripherals and algorithmic enhancements are described. The secure implementation, which aims at thwarting common side-channel attacks, is also studied and new techniques are provided for improving its efficiency on ARM processors. These results contribute to the building of efficient and secure cryptographic systems on wireless sensors and mobile processors / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Voz sobre IP (ou VoIP) vem sendo adotada progressivamente não apenas por um grande número de empresas mas também por um número expressivo de pessoas, no Brasil e em outros países. Entretanto, essa crescente adoção de VoIP no mundo traz consigo algumas preocupações tais como ameaças e riscos de segurança, sobretudo no que diz respeito à autenticidade, privacidade e integridade da comunicação. Para proteger a sessão de mídia existem protocolos muito eficientes, como o Secure Real-time Transport Protocol (SRTP). Mas ele depende de uma chave secreta para tornar a comunicação segura de fato. Assim, uma boa estratégia é aproveitar o processo de sinalização que estabelece a sessão de mídia e negociar uma chave secreta de sessão que seja comum às partes comunicantes. Esse processo de sinalização é realizado por tipos específicos de protocolo tais como o Session Initiation Protocol (SIP), um protocolo de sinalização muito importante e que vem sendo usado cada vez mais por softphones para comunicação na Internet. Todavia, os riscos e ameaças mencionados já existem no próprio processo de sinalização e, dentre eles, o ataque do tipo man-in-the-middle é o mais perigoso, devido aos prejuízos que ele pode causar. Depois de fazer uma revisão bibliográfica dos riscos e ameaças inerentes ao SIP, bem como de seus mecanismos de segurança (analisando os pontos fortes e de atenção deles), foi possível originar um novo mecanismo de segurança, o qual é apresentado neste trabalho. O mecanismo proposto usa um protocolo para troca segura de informações o protocolo Massey-Omura o qual, quando combinado com emparelhamentos bilineares, provê ao SIP um melhor nível de segurança em todos os aspectos (autenticidade, privacidade e integridade). Além disso, o novo mecanismo é avaliado através de uma prova de conceito, na qual utilizou-se um softphone SIP funcional. A análise de segurança realizada e os resultados obtidos da prova de conceito fazem do mecanismo de segurança proposto uma alternativa viável para o SIP. / Voice over IP (or VoIP) has been progressively adopted not only by a great number of companies but also by an expressive number of people, in Brazil and in other countries. However, this increasing adoption of VoIP in the world brings some concerns such as security risks and threats, mainly on the authenticity, privacy and integrity of the communication. In order to protect the media session, efficient protocols like the Secure Real-time Transport Protocol (SRTP) have been used. However, it depends on a secret key to make the communication secure. Thus, a good strategy is to take advantage of the signaling process to establish the media session, and agree on a common secret session key between the communicating parties. This signaling process is performed by specific types of protocols such as the Session Initiation Protocol (SIP), a very important signaling protocol, which has been used more and more by softphones in the Internet communication. Nevertheless, those risks and threats already exist in the own signaling process and, among them, the man-in-the-middle attack is the worst of all due to its high danger degree. After doing a bibliographical revision of the SIP security risks and threats, as well as its security mechanisms (analyzing their advantages and drawbacks), it was possible to generate a new security mechanism, which is presented in this work. The proposed mechanism uses a protocol for secure information exchange the Massey-Omura protocol which, when combined with bilinear pairings, provides a better security level for SIP in all its aspects (authenticity, privacy and integrity). Besides this, the new mechanism is evaluated by a proof of concept, in the which a functional SIP softphone was used. The security analysis and the results obtained from the proof of concept, make the proposed security mechanism a viable alternative for SIP.

A tendência para o futuro da tecnologia é a produção de dispositivos eletrônicos e de computação cada vez menores. Em curto e médio prazos, ainda há poucos recursos de memória e processamento neste ambiente. A longo prazo, conforme a Física, a Química e a Microeletrônica se desenvolvem, constata-se significativo aumento na capacidade de tais dispositivos. No intervalo de curto e médio prazos, entre 20 e 50 anos, até que a tecnologia tenha avanços, soluções leves de software se vêem necessárias. No Brasil, o protocolo de assinatura digital RSA é o mais amplamente adotado, sendo obsolescente como padrão. O problema é que os avanços tecnológicos impõem um aumento considerável no tamanho das chaves criptográficas para que se mantenha um nível de segurança adequado, resultando efeitos indesejáveis em tempo de processamento, largura de banda e armazenamento. Como solução imediata, temos a criptografia de curvas elípticas sendo mais adequada para utilização por órgãos públicos e empresas. Dentro do estudo de curvas elípticas, este trabalho contribui especificamente com a introdução de uma nova subfamília das curvas amigáveis a emparelhamento Barreto-Naehrig (BN). A subfamília proposta tem uma descrição computacionalmente simples, tornando-a capaz de oferecer oportunidades de implementação eficiente. A escolha das curvas BN também se baseia no fato de possibilitarem uma larga faixa de níveis práticos de segurança. A partir da subfamília introduzida foram feitas algumas implementações práticas começando com algoritmos mais básicos de operações em corpos de extensão, passando por algoritmos de aritmética elíptica e concluindo com o cálculo da função de emparelhamento. A combinação da nova subfamília BN com a adoção de técnicas de otimização, cuidadosamente escolhidas, permitiu a mais eficiente implementação do emparelhamento Ate ótimo, operação bastante útil em aplicações criptográficas práticas. / The trend for the future consists of steadfast shrinking of electrical and computing devices. In the short to medium term, one will still find constrained storage and processing resources in that environment. In the long run, as Physics, Chemistry and Microelectronics progress, the capabilities of such devices are likely to increase. In 20 to 50 years from now, until technology has firm advances, lightweight software solutions will be needed. In Brazil, the most widely adopted signature protocol, the RSA scheme, is obsolescent as a standard. The problem is that technological advances impose a considerable increase in cryptographic key sizes in order to maintain a suitable security level, bringing about undesirable effects in processing time, bandwidth occupation and storage requirements. As an immediate solution, we have the Elliptic Curve Cryptography which is more suitable for utilization in public agencies and industry. In the field of elliptic curves, this work contributes specifically with the introduction of a new subfamily of the pairing-friendly Barreto-Naehrig (BN) curves. The proposed subfamily has a computationally simple description, and makes it able to offer opportunities for efficient implementation. The choice of the BN curves is also based on the fact that they allow a range of practical security levels. Furthermore, there were made practical implementations from the introduced subfamily, like the most basic extension fields algorithms, elliptic curve arithmetic and pairing computation. The adoption of the new BN subfamily with carefully chosen optimization techniques allowed the most efficient implementation of the optimal Ate pairing, which is a very useful operation in many practical cryptographic applications.

A tendência para o futuro da tecnologia é a produção de dispositivos eletrônicos e de computação cada vez menores. Em curto e médio prazos, ainda há poucos recursos de memória e processamento neste ambiente. A longo prazo, conforme a Física, a Química e a Microeletrônica se desenvolvem, constata-se significativo aumento na capacidade de tais dispositivos. No intervalo de curto e médio prazos, entre 20 e 50 anos, até que a tecnologia tenha avanços, soluções leves de software se vêem necessárias. No Brasil, o protocolo de assinatura digital RSA é o mais amplamente adotado, sendo obsolescente como padrão. O problema é que os avanços tecnológicos impõem um aumento considerável no tamanho das chaves criptográficas para que se mantenha um nível de segurança adequado, resultando efeitos indesejáveis em tempo de processamento, largura de banda e armazenamento. Como solução imediata, temos a criptografia de curvas elípticas sendo mais adequada para utilização por órgãos públicos e empresas. Dentro do estudo de curvas elípticas, este trabalho contribui especificamente com a introdução de uma nova subfamília das curvas amigáveis a emparelhamento Barreto-Naehrig (BN). A subfamília proposta tem uma descrição computacionalmente simples, tornando-a capaz de oferecer oportunidades de implementação eficiente. A escolha das curvas BN também se baseia no fato de possibilitarem uma larga faixa de níveis práticos de segurança. A partir da subfamília introduzida foram feitas algumas implementações práticas começando com algoritmos mais básicos de operações em corpos de extensão, passando por algoritmos de aritmética elíptica e concluindo com o cálculo da função de emparelhamento. A combinação da nova subfamília BN com a adoção de técnicas de otimização, cuidadosamente escolhidas, permitiu a mais eficiente implementação do emparelhamento Ate ótimo, operação bastante útil em aplicações criptográficas práticas. / The trend for the future consists of steadfast shrinking of electrical and computing devices. In the short to medium term, one will still find constrained storage and processing resources in that environment. In the long run, as Physics, Chemistry and Microelectronics progress, the capabilities of such devices are likely to increase. In 20 to 50 years from now, until technology has firm advances, lightweight software solutions will be needed. In Brazil, the most widely adopted signature protocol, the RSA scheme, is obsolescent as a standard. The problem is that technological advances impose a considerable increase in cryptographic key sizes in order to maintain a suitable security level, bringing about undesirable effects in processing time, bandwidth occupation and storage requirements. As an immediate solution, we have the Elliptic Curve Cryptography which is more suitable for utilization in public agencies and industry. In the field of elliptic curves, this work contributes specifically with the introduction of a new subfamily of the pairing-friendly Barreto-Naehrig (BN) curves. The proposed subfamily has a computationally simple description, and makes it able to offer opportunities for efficient implementation. The choice of the BN curves is also based on the fact that they allow a range of practical security levels. Furthermore, there were made practical implementations from the introduced subfamily, like the most basic extension fields algorithms, elliptic curve arithmetic and pairing computation. The adoption of the new BN subfamily with carefully chosen optimization techniques allowed the most efficient implementation of the optimal Ate pairing, which is a very useful operation in many practical cryptographic applications.

Voz sobre IP (ou VoIP) vem sendo adotada progressivamente não apenas por um grande número de empresas mas também por um número expressivo de pessoas, no Brasil e em outros países. Entretanto, essa crescente adoção de VoIP no mundo traz consigo algumas preocupações tais como ameaças e riscos de segurança, sobretudo no que diz respeito à autenticidade, privacidade e integridade da comunicação. Para proteger a sessão de mídia existem protocolos muito eficientes, como o Secure Real-time Transport Protocol (SRTP). Mas ele depende de uma chave secreta para tornar a comunicação segura de fato. Assim, uma boa estratégia é aproveitar o processo de sinalização que estabelece a sessão de mídia e negociar uma chave secreta de sessão que seja comum às partes comunicantes. Esse processo de sinalização é realizado por tipos específicos de protocolo tais como o Session Initiation Protocol (SIP), um protocolo de sinalização muito importante e que vem sendo usado cada vez mais por softphones para comunicação na Internet. Todavia, os riscos e ameaças mencionados já existem no próprio processo de sinalização e, dentre eles, o ataque do tipo man-in-the-middle é o mais perigoso, devido aos prejuízos que ele pode causar. Depois de fazer uma revisão bibliográfica dos riscos e ameaças inerentes ao SIP, bem como de seus mecanismos de segurança (analisando os pontos fortes e de atenção deles), foi possível originar um novo mecanismo de segurança, o qual é apresentado neste trabalho. O mecanismo proposto usa um protocolo para troca segura de informações o protocolo Massey-Omura o qual, quando combinado com emparelhamentos bilineares, provê ao SIP um melhor nível de segurança em todos os aspectos (autenticidade, privacidade e integridade). Além disso, o novo mecanismo é avaliado através de uma prova de conceito, na qual utilizou-se um softphone SIP funcional. A análise de segurança realizada e os resultados obtidos da prova de conceito fazem do mecanismo de segurança proposto uma alternativa viável para o SIP. / Voice over IP (or VoIP) has been progressively adopted not only by a great number of companies but also by an expressive number of people, in Brazil and in other countries. However, this increasing adoption of VoIP in the world brings some concerns such as security risks and threats, mainly on the authenticity, privacy and integrity of the communication. In order to protect the media session, efficient protocols like the Secure Real-time Transport Protocol (SRTP) have been used. However, it depends on a secret key to make the communication secure. Thus, a good strategy is to take advantage of the signaling process to establish the media session, and agree on a common secret session key between the communicating parties. This signaling process is performed by specific types of protocols such as the Session Initiation Protocol (SIP), a very important signaling protocol, which has been used more and more by softphones in the Internet communication. Nevertheless, those risks and threats already exist in the own signaling process and, among them, the man-in-the-middle attack is the worst of all due to its high danger degree. After doing a bibliographical revision of the SIP security risks and threats, as well as its security mechanisms (analyzing their advantages and drawbacks), it was possible to generate a new security mechanism, which is presented in this work. The proposed mechanism uses a protocol for secure information exchange the Massey-Omura protocol which, when combined with bilinear pairings, provides a better security level for SIP in all its aspects (authenticity, privacy and integrity). Besides this, the new mechanism is evaluated by a proof of concept, in the which a functional SIP softphone was used. The security analysis and the results obtained from the proof of concept, make the proposed security mechanism a viable alternative for SIP.