Project acronym CNTM
Project Cryptography on Non-Trusted Machines
Researcher (PI) Stefan Dziembowski
Host Institution (HI) UNIWERSYTET WARSZAWSKI
Call Details Starting Grant (StG), PE5, ERC-2007-StG
Summary This project is about the design of cryptographic schemes that are secure even if implemented on not-secure devices. The motivation for this problem comes from an observation that most of the real-life attacks on cryptographic devices do not break their mathematical foundations, but exploit vulnerabilities of their implementations. This concerns both the cryptographic software executed on PCs (that can be attacked by viruses), and the implementations on hardware (that can be subject to the side-channel attacks). Traditionally fixing this problem was left to the practitioners, since it was a common belief that theory cannot be of any help here. However, new exciting results in cryptography suggest that this view was too pessimistic: there exist methods to design cryptographic protocols in such a way that they are secure even if the hardware on which they are executed cannot be fully trusted. The goal of this project is to investigate these methods further, unify them in a solid mathematical theory (many of them were developed independently), and propose new ideas in this area. The project will be mostly theoretical (although some practical experiments may be performed). Our main interest lies within the theory of private circuits, bounded-retrieval model, physically-observable cryptography, and human-assisted cryptography. We view these theories just as the departing points, since the area is very fresh and we expect to soon witness completely new ideas in this field.
Summary
This project is about the design of cryptographic schemes that are secure even if implemented on not-secure devices. The motivation for this problem comes from an observation that most of the real-life attacks on cryptographic devices do not break their mathematical foundations, but exploit vulnerabilities of their implementations. This concerns both the cryptographic software executed on PCs (that can be attacked by viruses), and the implementations on hardware (that can be subject to the side-channel attacks). Traditionally fixing this problem was left to the practitioners, since it was a common belief that theory cannot be of any help here. However, new exciting results in cryptography suggest that this view was too pessimistic: there exist methods to design cryptographic protocols in such a way that they are secure even if the hardware on which they are executed cannot be fully trusted. The goal of this project is to investigate these methods further, unify them in a solid mathematical theory (many of them were developed independently), and propose new ideas in this area. The project will be mostly theoretical (although some practical experiments may be performed). Our main interest lies within the theory of private circuits, bounded-retrieval model, physically-observable cryptography, and human-assisted cryptography. We view these theories just as the departing points, since the area is very fresh and we expect to soon witness completely new ideas in this field.
Max ERC Funding
872 550 €
Duration
Start date: 2008-11-01, End date: 2013-10-31
Project acronym SOSNA
Project Expressive Power of Tree Logics
Researcher (PI) Mikolaj Bojanczyk
Host Institution (HI) UNIWERSYTET WARSZAWSKI
Call Details Starting Grant (StG), PE6, ERC-2009-StG
Summary Logics for expressing properties of labeled trees and forests figure importantly in several different areas of Computer Science, including verification (branching temporal logics) and database theory (many XML query languages). The goal of this project is to investigate the expressive power of tree logics, mainly those logics that can be captured by tree automata. A similar study, but for word languages, is one of the main lines of research in formal language theory. The study of the expressive power of word logics has lead to many beautiful and fundamental results, including Schutzenberger's characterization of star-free languages, and the Krohn-Rhodes decomposition theorem. We intend to extend this research for trees. The type of questions we want to answer is: what is the expressive power of first-order logic in trees? is there a Krohn-Rhodes decomposition theory for trees? what is a tree group? We expect that our study of tree logics will use algebraic techniques, possibly the setting of forest algebra (as introduced by the principal investigator and Igor Walukiewicz). We would also like to extend the algebraic setting beyond regular languages of finite trees, to e.g. infinite trees, or nonregular languages.
Summary
Logics for expressing properties of labeled trees and forests figure importantly in several different areas of Computer Science, including verification (branching temporal logics) and database theory (many XML query languages). The goal of this project is to investigate the expressive power of tree logics, mainly those logics that can be captured by tree automata. A similar study, but for word languages, is one of the main lines of research in formal language theory. The study of the expressive power of word logics has lead to many beautiful and fundamental results, including Schutzenberger's characterization of star-free languages, and the Krohn-Rhodes decomposition theorem. We intend to extend this research for trees. The type of questions we want to answer is: what is the expressive power of first-order logic in trees? is there a Krohn-Rhodes decomposition theory for trees? what is a tree group? We expect that our study of tree logics will use algebraic techniques, possibly the setting of forest algebra (as introduced by the principal investigator and Igor Walukiewicz). We would also like to extend the algebraic setting beyond regular languages of finite trees, to e.g. infinite trees, or nonregular languages.
Max ERC Funding
799 920 €
Duration
Start date: 2009-11-01, End date: 2014-10-31
