Resumo: Este trabalho propõe algoritmos determinísticos que, dado um conjunto com n chaves, constroem em tempo esperado O(n) uma função hash com tempo de busca no pior caso O(1), a qual mapeia sem colisão as chaves para o conjunto {0, . . . , n-1}. Esses esquemas de hashing perfeitos e mínimos são meras variantes dos esquemas aleatorizados de Botelho, Kohayakawa e Ziviani (2005) e Botelho, Pagh e Ziviani (2007) e mostraram resultados empíricos equivalentes aos dos algoritmos originais. As variantes determinísticas foram implementadas a partir dos códigos dos esquemas originais desenvolvidos na biblioteca CMPH pelos próprios autores, a qual é mantida no SourceForge.net. Todos os esquemas foram alimentados com os mesmos conjuntos de chaves, para que pudessem ser comparados com justiça. Foram executados testes para conjuntos com até 25 000 000 de chaves. Ademais, os esquemas propostos contam evidentemente com a vantagem de sempre produzirem a mesma hash para um mesmo conjunto de chaves. Esse comportamento determinístico pode ser útil para o desenvolvimento dum esquema dinâmico de hashing, em que figuram operações como inserção e deleção de chaves, inspirado num dos excelentes esquemas estáticos abordados. Um dos esquemas de Botelho, Pagh e Ziviani (2007), por exemplo de excelência, constrói hashes representáveis por apenas aproximadamente 2,62 bits por chave. Tal resultado é muito próximo da cota inferior justa conhecida, de aproximadamente 1,44 bits por chave. Tanto as versões determinísticas propostas quanto as originais mostram-se práticas para aplicações reais de Hashing. No entanto, na fundamentação teórica do trabalho de Botelho, Kohayakawa e Ziviani (2005) ainda restava uma conjectura. A presente dissertação também propõe uma demonstração para a conjectura e encerra a corretude do esquema.

Orientador: Ricardo Dahab / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-25T01:13:52Z (GMT). No. of bitstreams: 1 Sendin_IvandaSilva_M.pdf: 2088136 bytes, checksum: 1ca40560c5f99ce66467f8a173457084 (MD5) Previous issue date: 1999 / 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: Ricardo Dahab / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-09T00:39:10Z (GMT). No. of bitstreams: 1 Tavares_PauloHenrique_M.pdf: 612792 bytes, checksum: 34039a441661bcdbc5f686566d558fae (MD5) Previous issue date: 2006 / Resumo: Nos últimos anos, a quantidade de dispositivos móveis tem crescido dramaticamente assim como a complexidade das aplicações que os usuários desejam executar neles. Ao mesmo tempo, a preocupação com a segurança do grande público também tem aumentado, criando uma demanda maior por aplicações criptográficas, como assinaturas digitais, que dependem de funções de resumo (hash) criptográfico. Neste contexto tornou-se importante estudar o desempenho de funções de resumo nesta nova geração de processadores, desenvolvidos para estes dispositivos. Neste trabalho estudamos a família de funções de resumo SHA (Secure Hash Algorithm) e Whirlpool, algumas de suas implementações, as características dos processadores Intel XScale que podem ser usadas para melhorar o desempenho de tais funções, com atenção especial para as novas extensões Wireless MMX. Também aplicamos algumas dessas técnicas e apresentamos os resultados dos testes de desempenho executados / Abstract: In recent years, the number of mobile devices has grown dramatically and so has the complexity of applications their users wish to run. At the same time, security concerns of the general public have also increased, creating a greater demand for cryptographic applications such as digital signatures, which use hash functions. In this context it has become very important to study the performance of hash functions on the new generation of processors developed for these devices. In this work we study the SHA (Secure Hash Algorithm) family of hash functions and some of their implementations, the Intel XScale processors characteristics that can be used to improve the performance of those functions, with special attention to the new Wireless MMX extensions. We also applied some of these techniques and report the results of the performance tests executed. / Mestrado / Engenharia de Computação / Mestre Profissional em Computação

Orientador: Julio César López Hernández / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-18T13:36:05Z (GMT). No. of bitstreams: 1 Oliveira_ThomazEduardodeFigueiredo_M.pdf: 4175073 bytes, checksum: 14d147ca37955c85736d05e60182a583 (MD5) Previous issue date: 2011 / 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: Maurício Ferreira Magalhães / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-18T18:55:11Z (GMT). No. of bitstreams: 1 Paula_LucianoBernardesde_D.pdf: 1395906 bytes, checksum: 9d9a3c99b7292a6482f33e12db95abd6 (MD5) Previous issue date: 2011 / Resumo: O volume de dados disponíveis na WWW aumenta a cada dia. Com o surgimento da Web Semântica, os dados passaram a ter uma representação do seu significado, ou seja, serem classificados em um conceito de um domínio de conhecimento, tal domínio geralmente definido por uma ontologia. Essa representação, apoiada em todo o ferramental criado para a Web Semântica, propicia a busca conceitual. Nesse tipo de busca, o objetivo não é a recuperação de um dado específico, mas dados, de diversos tipos, classificados em um conceito de um domínio de conhecimento. Utilizando um índice de similaridade, é possível a recuperação de dados referentes a outros conceitos do mesmo domínio, aumentando a abrangência da busca. A indexação distribuída desses dados pode fazer com que uma busca conceitual por similaridade se torne muito custosa. Existem várias estruturas de indexação distribuída, como as redes P2P, que são empregadas na distribuição e compartilhamento de grandes volumes de dados. Esta tese propõe a utilização de funções LSH na indexação de conceitos de um domínio, definido por uma ontologia, mantendo a similaridade entre eles. Dessa forma, conceitos similares são armazenados próximos um dos outros, tal conceito de proximidade medida em alguma métrica, facilitando a busca conceitual por similaridade / Abstract: The volume of data available in the WWW increases every day. The Semantic Web emerged, giving a representation of the meaning of data, being classified in a concept of a knowledge domain, which is generally defined using an ontology. This representation, based in all the tools created for the Semantic Web, possibilitates the conceptual search. In this type of search, the goal is not to retrieve a specific piece of data, but several data, of several types, classified in a concept of an ontology. Using a similarity level, the retrieval of data that refer to other concepts of the domain is also possible, making the search broader. The distributed indexing of all these data may turn the conceptual search costly. The Internet holds several structures of distributed indexing, such as P2P networks, which are used in the distribution and sharing of huge volumes of data. This thesis presents how it is possible to use LSH functions to generate identifiers to concepts of a domain, defined using an ontology, keeping their similarity. This way, similar concepts are stored near each other, such distance measured in some metric, turning the conceptual search by similarity easier / Doutorado / Engenharia de Computação / Doutor em Engenharia Elétrica

Orientador: Eduardo Alves do Valle Junior / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-26T08:10:33Z (GMT). No. of bitstreams: 1 Silva_EliezerdeSouzada_M.pdf: 2350845 bytes, checksum: dd31928bd19312563101a08caea74d63 (MD5) Previous issue date: 2014 / Resumo: A crescente disponibilidade de conteúdo multimídia é um desafio para a pesquisa em Recuperação de Informação. Usuários querem não apenas ter acesso aos documentos multimídia, mas também obter semântica destes documentos, de modo que a capacidade de encontrar um conteúdo específico em grandes coleções de documentos textuais e não textuais é fundamental. Nessas grandes escalas, sistemas de informação multimídia de recuperação devem contar com a capacidade de executar a busca por semelhança de forma eficiente. No entanto, documentos multimídia são muitas vezes representados por descritores multimídia representados por vetores de alta dimensionalidade, ou por outras representações complexas em espaços métricos. Fornecer a possibilidade de uma busca por similaridade eficiente para esse tipo de dados é extremamente desafiador. Neste projeto, vamos explorar uma das famílias mais citado de soluções para a busca de similaridade, o Hashing Sensível à Localidade (LSH - Locality-sensitive Hashing em inglês), que se baseia na criação de funções de hash que atribuem, com maior probabilidade, a mesma chave para os dados que são semelhantes. O LSH está disponível apenas para um punhado funções de distância, mas, quando disponíveis, verificou-se ser extremamente eficiente para arquiteturas com custo de acesso uniforme aos dados. A maioria das funções LSH existentes são restritas a espaços vetoriais. Propomos dois métodos novos para o LSH, generalizando-o para espaços métricos quaisquer utilizando particionamento métrico (centróides aleatórios e k-medoids). Apresentamos uma comparação com os métodos LSH bem estabelecidos em espaços vetoriais e com os últimos concorrentes novos métodos para espaços métricos. Desenvolvemos uma modelagem teórica do comportamento probalístico dos algoritmos propostos e demonstramos algumas relações e limitantes para a probabilidade de colisão de hash. Dentre os algoritmos propostos para generelizar LSH para espaços métricos, esse desenvolvimento teórico é novo. Embora o problema seja muito desafiador, nossos resultados demonstram que ela pode ser atacado com sucesso. Esta dissertação apresentará os desenvolvimentos do método, a formulação teórica e a discussão experimental dos métodos propostos / Abstract: The increasing availability of multimedia content poses a challenge for information retrieval researchers. Users want not only have access to multimedia documents, but also make sense of them --- the ability of finding specific content in extremely large collections of textual and non-textual documents is paramount. At such large scales, Multimedia Information Retrieval systems must rely on the ability to perform search by similarity efficiently. However, Multimedia Documents are often represented by high-dimensional feature vectors, or by other complex representations in metric spaces. Providing efficient similarity search for that kind of data is extremely challenging. In this project, we explore one of the most cited family of solutions for similarity search, the Locality-Sensitive Hashing (LSH), which is based upon the creation of hashing functions which assign, with higher probability, the same key for data that are similar. LSH is available only for a handful distance functions, but, where available, it has been found to be extremely efficient for architectures with uniform access cost to the data. Most existing LSH functions are restricted to vector spaces. We propose two novel LSH methods (VoronoiLSH and VoronoiPlex LSH) for generic metric spaces based on metric hyperplane partitioning (random centroids and K-medoids). We present a comparison with well-established LSH methods in vector spaces and with recent competing new methods for metric spaces. We develop a theoretical probabilistic modeling of the behavior of the proposed algorithms and show some relations and bounds for the probability of hash collision. Among the algorithms proposed for generalizing LSH for metric spaces, this theoretical development is new. Although the problem is very challenging, our results demonstrate that it can be successfully tackled. This dissertation will present the developments of the method, theoretical and experimental discussion and reasoning of the methods performance / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica