Language, Complexity and Cryptography

Researchers

Luís Antunes,  Armando Matos, Nelma Moreira, Rogério Reis, Marco Almeida, Alexandre Pinto, André Souto, Andreia Sofia Teixeira

Topics

• Descriptional complexity of regular languages

  Due to novel applications in Computer Science - from bio-informatics to computer networks and Web technologies - automata theory has faced renewed theoretical developments. One of the areas that has had special attention is the descriptional complexity of formal languages representations with the same expressive power. Several aspects of the descriptional complexity of regular languages, are unknown or not well understood. The main objectives of this line of research are: study of the non injective and non complexity preserving conversions between combinatorial representations with the same expressive power and the descriptional complexity of generic languages operations; enumerative and random generation of languages representations with applications in characterization studies and average case analysis; development of high-performance tools for assisting research on formal and computational models, such as: an open source extensible high-performance software library for the symbolic manipulation of automata, tools for automatic drawing of automata diagrams and a modular graphical user interface for the manipulation of automata and other models of computation.[More info]

• Individual analysis of cryptographic protocols

  The classical analysis of cryptographic protocols assumes that certain probability distributions are well defined and known in practice; but that is often not the case. A completely different approach is the so called "individual analysis". Only very recently has this kind of analysis been attempted. The continuation of the research (which began a few years ago in LIACC and elsewhere) is the main topic of this project. The individual analysis is based on variants of the Kolmogorov complexity; however, security measures based on resourced unbounded Kolmogorov complexity are usually uncomputable and defined "apart from a constant"; this is a serious drawback for practical applications, so that the research will include the search for appropriate computable alternatives to Kolmogorov complexity. [More info]

• Formal models for reversible computation: measuring the degree of reversibility

  The Landauer principle is the ultimate lower bound for non reversible computations. Only reversible forms of computation can in theory be almost dissipationless. The objectives can be divided in 4 main subareas: characterization and study of very simple reversible languages (this is the continuation of some previous work in this area); use of Kolmogorov complexity (or related concepts) to measure the degree of irreversibility of a computation; compare several theoretical models for reversible computation such that reversible automata, reversible languages, some forms of rewrite rules and the unitary transformations of quantum mechanics; search for efficient methods for restoring previous states, such as the previous configurations of a machine or the previous states of a database system. [More info]

• Cryptology and Security of Protocols

  Areas of interest and research in classical symmetric ciphers includes: algebraic analysis of processes and classical algorithms both considering them as cryptographical devices and as combinatorial objects; study of the applicability of modern attacks to this algorithms and their respective complexity. In particular we consider the digital reconstruction of classical cryptanalysis methods developed in middle 20th century; transformation of classical cryptographic ciphers to the digital block ciphers; study of possible application of differential and linear cryptanalysis to these ciphers. Another area of research consists in the formal analysis of the security features of cryptographic protocols. [More info]

• Enumerative Combinatorics

  The aim of this line of research is to study some combinatorial games and graph problems. In particular we studied a new combinatorial number h(n) that can be seen as the longest set [n] with a sum free partition. [ More info]