LSV Seminar

The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Laurent Doyen and Stefan Göller.

The seminar is open to public and does not require any form of registration.

Next Seminar

Fully Homomorphic Encryption: Implementation Progresses and Challenges

Visit website for this news | Export event in iCalendar format

 Caroline Fontaine
Date
Thursday, July 19 2018 at 11:00AM
Place
Pavillon des Jardins
Speaker
Caroline Fontaine (STICC/CID and IMT-Atlantique/ITI)

Since the introduction of the notion of privacy homomorphism by Rivest et al. in the late 1970s, the design of efficient and secure encryption schemes allowing the performance of general computations in the encrypted domain has been one of the holy grails of the cryptographic community. Despite numerous partial answers, the problem of designing such a powerful primitive has remained open until the theoretical breakthrough of the Fully Homomorphic Encryption scheme published by Gentry in the late 2000s. Since then, progress has been fast-paced, and it can now be reasonably said that practical homomorphic encryption-based computing will become a reality in the near future. Nevertheless, a lot of effort remains necessary to drive Fully Homomorphic Encryption schemes beyond theoretical interest, to ensure confidentiality of outsourced data in practical use cases. In this talk, we will first start with a brief history and state-of-the-art, and discuss different challenges that have to be handled: complexity, expansion, security,... Then, we will mention several approaches and results concerning their implementation, complexity and expansion reduction, and security analysis. We will in particular focus on the design of a dedicated stream cipher that helps to manage the expansion issue.


Upcoming Seminars

Querying regular languages over sliding-windows

Visit website for this news | Export event in iCalendar format

 Markus Lohrey
Date
Tuesday, July 24 2018 at 11:00AM
Place
Salle de Conférence (Pavillon des Jardins)
Speaker
Markus Lohrey (University of Siegen)

Sliding-window streaming algorithms get as input a stream of data values and have to answer queries about the last n values for a certain window size n. In the talk we consider queries that are given by regular languages. More precisely, we consider the so-called sliding window word problem for a language L: Given a data stream of symbols a_1 a_2 a_3 ..., answer at every time instant t, whether a_{t-n+1} ... a_t belongs to L. We are mainly interested in the space complexity of this problem measured in the window length n. For regular languages, we prove that the space complexity of the sliding window word problem is either constant, logarithmic, or linear. Moreover, for the constant and logarithmic space classes we provide very natural characterizations: For every regular language L the sliding window word problem can be solved in (i) constant space if and only if L is a boolean combination of regular length languages and suffix-testable languages and in (ii) logarithmic space if and only if L is a boolean combination of regular length languages and regular left ideals. If we allow randomized streaming algorithms with a two-sided error, then the above space trichotomy becomes a space quatrochotomy: for every regular languages, the space complexity of the sliding window word problem is either constant, doubly logarithmic, logarithmic, or linear.


About LSV

Agenda

Export agenda in iCalendar format | Past seminars

Today (Thu, Jul 19)
Tue, Jul 24

Past seminars