Ettekanded / Talks

Mayuresh Anand: Post-quantum security of the CBC, CFB, OFB, CTR, and XTS modes of operation

Slides from the talk [pdf]

Abstract: We examine the IND-qCPA security of the wide-spread block cipher modes of operation CBC, CFB, OFB, CTR, and XTS (i.e., security against quantum adversaries doing queries in superposition). We show that OFB and CTR are secure assuming that the underlying block cipher is a standard secure PRF (a pseudorandom function secure under classical queries). We give counterexamples that show that CBC, CFB, and XTS are not secure under the same assumption. And we give proofs that CBC and CFB mode are secure if we assume a quantum secure PRF (secure under queries in superposition).

This is joint work with Ehsan Ebrahimi, Gelo Tabia and Dominique Unruh.

Gholamreza Anbarjafari: Facial multi-emotional expression recognition using C-support vector classification

Slides from the talk [pdf]

Abstract: Human-computer interaction performs more realistic if the computer is capable of recognising more detailed expression of the human who is interacting with it. For this purpose we are proposing a new facial multi-emotional expression recognition which introduces 49 detailed facial emotional expression recognisable by a computer any artificial intelligence which is interacting with human. In iCV one of the research work that we have recently focused on is recognising a facial emotion by using upper and lower part of face including eyes-eyebrow and noise-mouth pairs respectively. In this current work, it is shown that the lower part of face is recognising facial emotional expression more correctly than the upper part. Also we have introduce two categories for the expressions, namely, dominant expressions and complementary expressions. A dominant expression has been recognised by using C-support vector classification of all facial landmark and the complimentary emotion is recognised by the lower part of the facial landmarks. We have done some experimental results on various databases which are very interesting, as emotions such as surprisingly sad, which sadness is dominant expression and surprise is complimentary expression.

Kalmer Apinis: Enhancing top-down solving with widening and narrowing

Slides from the talk [pdf]

Abstract: We present an enhancement of the generic fixpoint algorithm TD which can deal with widening and narrowing even for non-monotonic systems of equations. In constrast to corresponding enhancements proposed for other standard fixpoint algorithms, no extra priorities on variables are required. Still, a mechanism can be devised so that occurrences of the widening/narrowing operator are inserted as well as removed dynamically.

This is joint work with Helmut Seidl and Vesal Vojdani, appeared in the Nielsons Festschrift.

Silvio Capobianco: Sofic groups and cellular automata

Slides from the talk [pdf]

Abstract: Cellular automata (briefly, CA) are parallel synchronous systems on regular grids where the next state of a point depends on the current state of a finite neighborhood. The grid is determined by a finitely generated group and can be visualized as the Cayley graph of the group according to a suitable set of generators. In addition to being a useful tool for simulations, CA also raise important and interesting questions, such as how properties of the global transition function (obtained by synchronous application of the local update rule at each point) are linked to each other, and to properties of the underlying group.

It is well known that injective d-dimensional CA are also surjective. A conjecture by Walter Gottschalk asks if this is true for CA on arbitrary groups: this is true for, among others, the amenable groups and the residually finite groups. The largest class of groups for which Gottschalk's conjecture is known to be true is the class of sofic groups, introduced by Mikhail Gromov with a geometrical definition, later adapted by Benjamin Weiss into a combinatorial one for finitely generated groups.

We discuss sofic groups and Weiss' proof of surjunctivity. We then link soficness to another property of cellular automata, a strengthening of surjectivity of the global function which we call post-surjectivity. Our contribution consists in an improvement of our work from last year, and a suggestion for a "dual" to Gottschalk's conjecture.

This is joint work with Jarkko Kari and Siamak Taati, to be submitted to Automata 2016.

Morteza Daneshmand: 3D modeling and visualization

Slides from the talk [pdf]

Abstract: Nowadays, research and development communities try to replace real, physical materials and processes by virtual alternatives, aiming at exploiting both practical and economic benefits and ease brought about upon doing so. In other words, simulation and visualization of real-world objects and processes lead to alternative representations and understandings of the associated actual phenomena, while they do not demand going through costly processes required for creating, trying out, manipulating and maintaining the actual assets. Although it may initially seem to be expensive and challenging to realize, producing 3D models of materials and simulating the interactions taking place between them, in the most cases, prove to be able to pay off fruitfully in not a very long term, and overall, should be appropriate substitutes, given a fundamental condition, namely, that their results have to be close enough to the reality, so that they could be relied upon for analyzing or predicting the notions sought from the outset, having been based on empirical experiences. This project is intended to investigate the existing literature on 3D modeling and visualization methodologies, and attempts to enhance them for the sake of coming up with new ones, such that the foregoing terms would be satisfied to the greatest extent possible.

Ehsan Ebrahimi: Quantum collision-resistance of non-uniformly distributed functions

Slides from the talk [pdf]

Abstract: We study the quantum query complexity of finding a collision for a function f whose outputs are chosen according to a distribution with min-entropy k. We prove that Ω(2k/9) quantum queries are necessary to find a collision for function f. This is needed in some security proofs in the quantum random oracle model (e.g., the Fujisaki-Okamoto transform).

This is joint work with Gelo Tabia and Dominique Unruh.

Juhan Ernits: Model programs in F#: model-based testing reloaded

Abstract: tba

Denis Firsov: Variations on Noetherianness

Slides from the talk [pdf]

Abstract: In type theory several inequivalent notions of finiteness exist. In this paper we continue the study of Noetherian sets. A set is Noetherian if whenever we are shown elements from it one after another, sooner or later we will have seen some element twice. In a dependently typed setting this idea can be encoded in different ways. We explore properties and connections among various representations. In particular, we show that certain implementations imply decidable equality while others do not, and we construct counterexamples in the latter case. Additionally we explore the relation between Noetherianness and other notions of finiteness.

This is joint work with Tarmo Uustalu and Niccol˛ Veltri.

Nalin Jayakody: Transceiver hardware impairments in cognitive networks

Slides from the talk [pdf]

Abstract: This paper demonstrates the impact of transceiver impairments on channel capacity and bit-error-rate performance of a dual-hop half-duplex cognitive relay networks over AWGN channel. We consider the soft-information-relaying (SIR) protocol where the relay node computes the reliabilities (soft) of the received signal from source and then forwards to the destination. The hardware impairment model of the received signal via AWGN channel is first introduced. The analysis on capacity and bit-error-rate (BER) performance are then presented for the network with binary phase shift keying (BPSK) modulation. Furthermore, the impacts of hardware impairments on BER are quantified for the network with SIR and hard decode and-forward (DF) protocol. The simulation results on channel capacity of the network with SIR protocol acknowledge the ceiling channel capacity of the realistic transceivers with hardware impairments are presented. We found that the BER performance of SIR network with the worst hardware impairment level in 3GPP LTE requirements is on par with that of hard DF. This concludes that the SIR outperforms hard DF and limits the impact of hardware impairments on BER performance.

This is joint work with Khao D. Nguyen, appeared in ICICS 2016.

Liisi Kerik, Jaak Randmets: Optimizing SMC for robust and scalable integer and floating-point arithmetic

Slides from the talk [pdf]

Abstract: Secure multiparty computation (SMC) is a rapidly maturing field, but its number of practical applications so far has been small. Most existing applications have been run on small data volumes with the exception of a recent study processing tens of millions of education and tax records. For practical usability, SMC frameworks must be able to work with large collections of data and perform reliably under such conditions. In this work we demonstrate that with the help of our recently developed tools and some optimizations, the Sharemind secure computation framework is capable of executing tens of millions integer operations or hundreds of thousands floating-point operations per second. We also demonstrate robustness in handling a billion integer inputs and a million floating-point inputs in parallel. Such capabilities are absolutely necessary for real world deployments.

This is joint work with Peeter Laud.

Pejman Rasti: Facial image super resolution using sparse representation for improving face recognition in surveillance monitoring

Slides from the talk [pdf]

Abstract: Due to importance of security in the society, monitoring activities and recognizing specific people through surveillance video camera is playing an important role. One of the main issues in such activity rises from the fact that cameras do not meet the resolution requirement for many face recognition algorithm. In order to solve this issue, in this paper we are proposing a new system which super resolve the image using sparse representation with the specific dictionary involving only facial images followed by Hidden Markov Model and Support vector machine based face recognition. The proposed system has been tested on many well-known face databases such as HeadPose, and Essex University databases as well as our recently introduced iCV Face Recognition database (iFR). The experimental results shows that the recognition rate is increasing considerably after apply the super resolution by using facial image dictionary.

This is joint work with T§nis Uiboupin and Gholamreza Anbarjafari.

Ando Saabas: Interpreting machine learning models

Slides from the talk [pdf]

Abstract: In data analysis or applied machine learning related tasks, it is often crucial to understand how a machine learning model that is being used is making a particular decision. In general, this is tackled by using simple models that are easily interpretable by humans, so that each output of the model can be manually checked. More powerful methods such as random forests (which can have millions of internal nodes) are in general considered to be "black boxes", where the complexity of the model means that there is no real insight into how the model is making decisions.

In this talk, I argue that instead of trying to understand the full model itself, we can make models "explain" the reasoning behind individual decisions. Furthermore, I will demonstrate how random forest decisions can be explained by breaking down each output in terms of contributions from each feature in the input vector.

Vitaly Skachek: New bound for batch codes with restricted query size

Slides from the talk [pdf]

Abstract: Batch codes were proposed for load balancing in the distributed server systems. They are also of potential use in private information retrieval. Batch codes have a lot of similarities with so-called locally-repairable codes (or codes with locality) in the area of distributed storage systems.

In this work, we present new upper bounds on the parameters of batch codes with restricted query size. These bounds are an improvement on the Singleton bound. The techniques for derivations of these bounds are based on the ideas in the literature for codes with locality. By employing additional ideas, we obtain further improvement on the bounds obtained for the batch codes.

This is joint work with Hui Zhang.

Gelo Tabia: A geometric approach to quantum probabilities

Slides from the talk [pdf]

Abstract: Why are quantum states most conveniently described in terms of vectors in Hilbert spaces? Since the only truly observable quantities in quantum theory are the outcome probabilities of measurements, it must be possible to understand the properties of quantum state space in terms of such probabilities.

In this talk, I will describe a particular representation of quantum states in terms of a canonical measurement known as a SIC-POVM. I will highlight some of the interesting geometric features of the set of quantum states that can be observed in this framework.

Hellis Tamm: Lower bound methods for the size of nondeterministic finite automata revisited

Slides temporarily withheld. Check back later.

Abstract: We revisit the following lower bound methods for the size of nondeterministic finite automata: the fooling set technique, the extended fooling set technique, and the biclique edge cover technique, presenting these methods in terms of quotients and atoms of regular languages. We show that the Kameda-Weiner method for finding a minimal NFA of a language is related to finding a corresponding biclique edge cover of the dependency graph of the language.

This is joint work in progress with Brink van der Merwe.

Ahto Truu: Efficient implementation of hash-sequence signatures

Slides from the talk [pdf]

Abstract: We present a new digital signature scheme that is based solely on cryptographic hash functions and does not use trapdoor functions. The scheme combines hash-tree based time-stamping with hash sequence authentication and is resistant to known quantum attacks. The report builds on a previous one given at the same venue by Risto Laanoja and after summarizing the basics will focus on efficient implementation of the scheme in personal signing devices such as smart cards.

This is joint work with Ahto Buldas and Risto Laanoja.

Dominique Unruh: Verification of quantum cryptography

Slides from the talk [pptx]

Abstract: In recent years, the verification of cryptographic schemes on the computational level (i.e., without symbolic abstractions) has seen great progress. For example, various state-of-the-art cryptographic schemes were analyzed using the EasyCrypt tool using a probabilistic relational Hoare logic (pRHL). However, existing tools and logics are unsuited for analysis of quantumcryptographic protocol - be it protocols using quantum mechanics, or protocols secure against quantum adversaries. In this talk, we explain why pRHL is not sound for quantum cryptography, and show how to lift the ideas from pRHL to the quantum setting. (With the long-term goal of getting a quantum version of EasyCrypt.)

Tarmo Uustalu: Coalgebraic bar recursion

Slides from the talk [pdf]

Abstract: We reformulate the bar recursion and induction principles in terms of recursive and wellfounded coalgebras. Bar induction was originally proposed by Brouwer as an axiom to recover certain classically valid theorems in a constructive setting. It is a form of induction on non-wellfounded trees satisfying certain properties. Bar recursion, introduced later by Spector, is the corresponding function definition principle.

We give a generalization of these principles, by introducing the notion of barred coalgebra: a process with a branching behaviour given by a functor, such that all possible computations terminate.

Coalgebraic bar recursion is the statement that every barred coalgebra is recursive; a recursive coalgebra is one that allows definition of functions by a coalgebra-to-algebra morphism. It is a framework to characterize valid forms of recursion for terminating functional programs. One application of the principle is the tabulation of continuous functions: Ghani, Hancock and Pattinson defined a type of wellfounded trees that represent continuous functions on streams. Bar recursion allows us to prove that every stably continuous function can be tabulated to such a tree where by stability we mean that the modulus of continuity is also continuous.

Coalgebraic bar induction states that every barred coalgebra is wellfounded; a wellfounded coalgebra is one that admits proof by induction.

This is joint work with Venanzio Capretta, to appear in FoSSaCS 2016.

Peeter Laud
Helger Lipmaa
Vitaly Skachek
Tarmo Uustalu
Viimane uuendus 6.6.2016