Orientador: Ricardo DahabDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: A validação de certicados digitais é um processo naturalmente custoso, pois envolve opera ções de criptograa assimétrica, que por sua vez envolvem operações aritméticas cujo tamanho dos operandos é da ordem de milhares de bits. Em alguns casos, dependendo da topologia da infraestrutura de chaves pública (ICP) e dos usuários envolvidos, validar um certicado implica validar uma cadeia de certicados, denominada caminho de certica- ção, aumentando ainda mais o custo de validação do certicado em questão. No sentido de tornar o processo de validação de certicados digitais mais eciente, vários mecanismos foram propostos nos últimos anos. Os mais importantes são: NOVOMODO [26], CRT [17], 23CRT [28], ICPA [20], EFFECT [14] e certicados efêmeros [31]. Neste trabalho, as vantagens e desvantagens desses mecanismos são discutidas assim como seus custos, especialmente sobre a ótica de validar um caminho de certicação. Dá-se destaque à ICPA, que permite otimizar a validação dos caminhos de certicação através da supressão parcial da necessidade de se vericar informações de revogação e da substitui- ção de operações assimétricas por operações de hash. Também é levantada a questão do custo de emissão de certicados aninhados na ICPA, o que pode torná-la inadequada para ambientes em que o número de usuários é muito grande. Finalmente, introduz-se uma modicação à ICPA, ICPAm, cujo objetivo principal é reduzir o custo de emissão de certicados aninhados, sem aumentar signicativamente o custo de validação do caminho de certicação. Na ICPAm, diferentemente do que ocorre na IPCA, as ACs superiores não emitem certicados aninhados quando suas filhas emitem certicados para usuários finais. Consequentemente, o custo de emissão dos certicados aninhados é reduzidoAbstract: The digital certicate validation process is very costly because it involves asymmetric cryp-tographic operations which involve arithmetic operations whose operands have more than a hundred bits. In some cases, depending on the public-key infrastructure (PKI) topology and its number of users, validating a certicate means validation of a chain of certicates, known as a certication path, further increasing the cost of validating the target certi- cate. To make this process less costly, a lot of mechanisms have been proposed in recent years. The most important are: NOVOMODO [26], CRT [17], 23CRT [28], ICPA [20], EFFECT [14] and short lived certicates [31]. In this thesis, the advantages and disad- vantages of these mechanisms are discussed as well as their costs, emphasizing the cost of validating a certication path. We give special attention to NPKI, which permits the optimization of certication path validation, partially suppressing the necessity of verify- ing certicate revocation information and replacing asymmetric cryptographic operations with cryptographic hash operations. We also discuss the nested certicate emission costs in a NPKI, which can make NPKIs not practical for environments where there are a great number of users. Finally, we introduce a modication to NPKIs, the ICPAm, whose ob- jective is to reduce nested certicate emission costs without increasing signicantly the certication path validation costs. On the ICPAm, dierently from ICPA, the superiors CAs do not emit nested certicate when its daughters CAs emit certicates to end users. Consequently, the nested certicate emission costs are reducedMestradoCiência da ComputaçãoMestre em Ciência da Computação131810/2005-7CNPQCAPES