Proceedings of the XI IC-Unicamp Thesis, Dissertation and Scientific Initiation Workshop.
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 RM L. Maike.
August 2016. Partly in English, partly in Portuguese, 147 pages.

Summary: This technical report contains summaries of 26 papers authorized to be published out of a total of 46 papers presented at XI Workshop of Theses, Dissertations and Scientific Initiation Works (WTD), from the Computing Institute (IC) of the State University of Campinas (Unicamp) in 2016. The Workshop it took place on the 3rd and 4th of August 2016 and had about 160 participants, including listeners, presenters of work and organizers. On the occasion there were 30 oral presentations and 16 posters. Students were given the possibility to choose the form of presentation (oral, poster), as well as to choose if they wished to publish their work in the proceedings of the event. The publication of abstracts, in the form of a technical report, aims to disseminate the work in progress and record, in a succinct way, the state of the art of the research of the Institute of Computing in 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.

Summary: In 2009, Gentry proposed the first construction of completely homomorphic encryption, solving a problem that remained open since 1978 when the problem was proposed by Dertouzos et al. This cryptographic construction is important because it allows the computation of arbitrary algorithms over encrypted data. It is based on difficult lattice problems and is therefore part of the so-called post-quantum cryptography. In this document we describe the construction made under the assumption that the approximate LCD problem it is difficult, following the same strategy originally proposed by Gentry. We consider that this construction allows an easier understanding of the concepts involved in this type of primitive. Even though no completely homomorphic scheme is practical, we will show you how to build partially homomorphic encryption based on the LWE problem, which is used to evaluate a restricted class of algorithms over encrypted data. We also discussed attacks on homomorphic encryption schemes and how the choice of parameters is determined considering a runtime estimate of the best attack. We compare constructions and show advantages and disadvantages of each scheme, depending on the desired application and the scenario in which the cryptosystem is implemented.

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 in the 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.

Summary: In this document we will introduce the reader to lattice-based encryption. The mathematical foundation will be presented and the main concepts will be given. We will show how to build cryptography under the assumption that certain lattice problems are computationally difficult and we will see that it is possible to add algebraic structure to the underlying lattice for more efficient schemes. Recently, new primitives have been proposed, showing that lattice-based cryptography can offer flexibility and malleability, while performance improvements have shown that it is a practical possibility in certain scenarios.

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.