Anais do XI Workshop de Teses, Dissertações e Trabalhos de Iniciação Científica do IC-Unicamp.
Profa. Ariadne Maria Brito Rizzoni, Profa. Esther Luna Colombini, Profa. Juliana Freitag Borin, Allan da Silva Pinto, Amanda Cristina Davi Resende, Carlos Alberto Petry, Eliana Alves Moreira, Emanuel Felipe Duarte, Ícaro Cavalcante Dourado, José Valderlei da Silva, Luís Augusto Martins Pereira, Lucas Augusto Carvalho, Samuel Botter Martins, Sueny Messias, and Vanessa R. M. L. Maike.
August 2016. Partly in English, partly in Portuguese, 147 pages.

Resumo: Este relatório técnico contém os resumos de 26 trabalhos autorizados a serem publicados de um total de 46 trabalhos apresentados no XI Workshop de Teses, Dissertações e Trabalhos de Iniciação Científica (WTD), do Instituto de Computação (IC) da Universidade Estadual de Campinas (Unicamp) do ano de 2016. O Workshop ocorreu nos dias 3 e 4 de Agosto de 2016 e contou com cerca de 160 participantes, entre ouvintes, apresentadores de trabalhos e organizadores. Na ocasião houve 30 apresentações orais e 16 pôsteres. Aos alunos foi dada a possibilidade de escolher a forma de apresentação (oral, pôster), bem como escolher se desejasse publicar o seu trabalho nos anais do evento. A publicação dos resumos, sob forma de relatório técnico, tem por objetivo divulgar os trabalhos em andamento e registrar, de forma sucinta, o estado da arte da pesquisa do Instituto de Computação no ano de 2016.

Test suite completeness and black box testing.
Adilson Luiz Bonifacio and Arnaldo Vieira Moura.
August 2016. In English, 28 pages.

Abstract: Model-based testing has been widely studied and successfully applied to generate and verify completeness of test suites. Roughly, completeness guarantees that a non-equivalent implementation under test will always be identified regarding complete deterministic Finite State Machines. Several approaches showed sufficient, and sometimes also necessary, conditions on specification models and test suites in order to guarantee completeness. In these studies, usually, test cases are required to be non-blocking -- that is, they are required to run to completion -- on both the specification and the implementation models. However, often it is desirable to have blocking test cases, and in some situations the presence of blocking test cases cannot be circumvented. In the present work we allow test cases to block, both in the specification as well as in the implementation models, and we study a natural variant of completeness, here called perfectness. Perfectness guarantees that non-compliance between a specification and an implementation will be detected, even in the presence of blocking test cases when an input action of the test case is not defined. We characterize perfectness in terms of isomorphisms, and establish a relationship between the classical notion of completeness and perfectness. We also give an upper bound on the number of states in implementations, beyond which no test suite can be complete, both in a conventional sense and in the presence of blocking test cases.

On Linial's conjecture for spine digraphs.
Maycon Sambinelli, Cândida Nunes da Silva, and Orlando Lee.
June 2016. In English, 6 pages.

Abstract: In this paper we introduce a superclass of split digraphs, which we call spine digraphs. Those are the digraphs whose vertex set can be partitioned into two sets and such that the subdigraph induced by is traceable and is a stable set. We also show that Linial's Conjecture holds for spine digraphs.

Homomorphic encryption.
Eduardo Morais and Ricardo Dahab.
April 2016. In English, 49 pages.

Resumo: Em 2009, Gentry propôs a primeira construção de encriptação completamente homomórfica, resolvendo um problema que permaneceu em aberto desde 1978 quando o problema foi proposto por Dertouzos et al. Essa construção criptográfica é importante porque ela permite a computação de algoritmos arbitrários sobre dados encriptados. Ela é baseada em problemas difíceis sobre reticulados e portanto é parte da chamada criptografia pós-quântica. Neste documento nós descrevemos a construção feita sob a suposição de que o problema do MDC aproximado é difícil, seguindo a mesma estratégia originalmente proposta por Gentry. Nós consideramos que esta construção possibilita uma compreensão mais fácil dos conceitos envolvidos neste tipo de primitiva. Mesmo embora nenhum esquema completamente homomórfico seja prático, nós mostraremos como construir encriptação parcialmente homomórfica com base no problem LWE, que é usado para avaliar uma classe restrita de algoritmos sobre dados encriptados. Nós também discutimos ataques sobre esquemas de encriptação homomórfica e como a escolha de parâmetros é determinada considerando uma estmativa de tempo de execução do melhor ataque. Nós comparamos construções e mostramos vantagens e desvantagens de cada esquema, dependendo na aplicação desajada e do cenário em que o criptossistema é implementado.

Abstract: In 2009, Gentry [] constructed the first fully homomorphic encryption (FHE) scheme, solving a conjecture that remained open since 1978 when it was proposed by Dertouzos et al []. The cryptographic construction is important because it allows to compute arbitrary algorithms over encrypted data. It is based on hard problems over ideal lattices and hence is part of the post-quantum cryptography. In this document we describe the construction under the assumption that the approximate GCD problem is hard, following the same blueprint originally described in Gentry's work. We think the AGCD-based scheme allows an easier understanding of the concepts involved in the construction of FHE cryptosystems. Even though no FHE proposal till now turned out to be a practical scheme, we are going to show how to build somewhat homomorphic encryption (SHE) based on the learning with errors (LWE) problem, which can be used to evaluate a restricted class of algorithms over encrypted data. We also discuss lattice attacks to homomorphic encryption schemes and how the choice of parameters is determined based on the best-attack effort estimation. We compare variants of the main construction and show that each one has advantages and disadvantages depending on the application and on the concrete scenario under which the cryptosystem is implemented.

Lattice-based cryptography.
Eduardo Morais and Ricardo Dahab.
April 2016. In English, 49 pages.

Resumo: Neste documento nós vamos introduzir o leitor à criptografia baseada em reticulados. O fundamento matemático será apresentado e os principais conceitos serão dados. Nós vamos mostrar comoconstruir criptografia sob a suposição de que determinados problemas em reticulados são computacionalmente difíceis e veremos que é possível adicionar estrutura algébrica para o reticulado subjacente para obter esquemas mais eficientes. Recentemente, novas primitivas foram propostas, mostrando que a criptografia baseada em reticulados pode oferecer flexibilidade e maleabilidade, enquanto melhorias na performance têm mostrado que ela é uma possibilidade prática em certos cenários.

Abstract: In this document we will give an introduction to lattice-based cryptography. Some mathematical apparatus will be presented to the reader and the main concepts are going to be pointed out. We will show how cryptography can be constructed under the assumption that a determined lattice problem is hard and we will see that it is possible to add algebraic structure to the subjacent lattice in order to obtain more efficient cryptosystems. Recently, new primitives have emerged, showing that lattice-based cryptography can achieve flexibility and malleability, while improvements in the performance have shown that it is becoming a practical possibility for some scenarios.