Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Matemática, 2017. / Submitted by Raquel Almeida (raquel.df13@gmail.com) on 2017-06-20T21:15:09Z
No. of bitstreams: 1
2017_BrunodeAssisDelboni.pdf: 1000608 bytes, checksum: 0c7c86de2221eca903edd2ffda11ee2c (MD5) / Approved for entry into archive by Raquel Viana (raquelviana@bce.unb.br) on 2017-08-17T15:39:39Z (GMT) No. of bitstreams: 1
2017_BrunodeAssisDelboni.pdf: 1000608 bytes, checksum: 0c7c86de2221eca903edd2ffda11ee2c (MD5) / Made available in DSpace on 2017-08-17T15:39:39Z (GMT). No. of bitstreams: 1
2017_BrunodeAssisDelboni.pdf: 1000608 bytes, checksum: 0c7c86de2221eca903edd2ffda11ee2c (MD5)
Previous issue date: 2017-08-17 / Esta dissertação tem como foco o estudo do problema de unificação módulo uma teoria equacional cuja assinatura contém um operador binário que satisfaz as identidades Associatividade, Comutatividade, Unidade e Nilpotência (ACUN), e que pode ou não conter um operador unário que satisfaz a identidade de homomorfismo (ACUNh), que é a teoria equacional do operador , amplamente utilizado em diversas ferramentas criptográficas, como MAUDE-NPA[10] que utiliza uma encriptação de grupos abelianos, incluindo ( ou exclusivo ), exponenciação e encriptação homomórfica. Primeiro apresentaremos alguns critérios para existência de soluções para problemas de ACUN(h)-unificação elementar com constantes que consiste em associar o problema de unificação à um sistema de equações lineares cujos coeficientes são elementos de ou , dependendo se o homomorfismo é ou não considerado. Segundo, apresentaremos um algoritmo para resolver problemas de ACUN(h)- unificação geral que retorna sempre um conjunto completo de unificadores. Finalmente, apresentaremos o estudo de um novo paradigma de unificação, a dizer, \emph{unificação assimétrica}, que consiste de obter unificadores de um problema de unificação com a propriedade de preservar formas normais do lado direito de cada equação de com relação a um sistema de reescrita convergente e coerente módulo uma teoria equacional . No caso particular da teoria equacional ACUN construiremos um algoritmo de conversão de ACUN-unificadores para ACUN-unificadores assimétricos. / This dissertation focuses on the study of unification problems modulo an equational theory whose signature contains a binary operator , which satisfies the identities of Associativity, Commutativity, Unity and Nilpotence (ACUN), and which may or not contain a unary operator satisfying the homomorphism identity (ACUNh), which is the equational theory for the operator XOR, Widely used on many cryptographic tools, like MAUDE[10], which uses group encryption, including XOR ( exclusive or ), exponentiation and homomorphic encryption. First we will present some criteria to the existence of solutions for elementary with constants ACUN(h)-unification problems which consist of associating a unification problem to a linear equation system whose coefficients are elements of or , depending one we are considering homomorphism or not. Second, we will present an algorithm to solve general ACUNh-unification problems which always returns a complete set of most general unifiers. Finally, we will present the study of a new unification paradigm, to say so, asymmetric unification, which consist of obtaining unifiers from the unification problem , with the property of preserving the normal form from of the right hand side of each equation in , considering a convergent and coherent rewriting system. In the particular case of the equational theory ACUN, we will also present an algorithm which takes as input ACUN-unifiers and outputs ACUN-asymmetric unifiers.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unb.br:10482/24161 |
| Date | 06 March 2017 |
| Creators | Delboni, Bruno de Assis |
| Contributors | Sobrinho, Daniele Nantes |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UnB, instname:Universidade de Brasília, instacron:UNB |
| Rights | A concessão da licença deste item refere-se ao termo de autorização impresso assinado pelo autor com as seguintes condições: Na qualidade de titular dos direitos de autor da publicação, autorizo a Universidade de Brasília e o IBICT a disponibilizar por meio dos sites www.bce.unb.br, www.ibict.br, http://hercules.vtls.com/cgi-bin/ndltd/chameleon?lng=pt&skin=ndltd sem ressarcimento dos direitos autorais, de acordo com a Lei nº 9610/98, o texto integral da obra disponibilizada, conforme permissões assinaladas, para fins de leitura, impressão e/ou download, a título de divulgação da produção científica brasileira, a partir desta data., info:eu-repo/semantics/openAccess |
Page generated in 0.002 seconds