TY - CONF
AB - We propose a new authentication protocol that is provably secure based on a ring variant of the learning parity with noise (LPN) problem. The protocol follows the design principle of the LPN-based protocol from Eurocrypt’11 (Kiltz et al.), and like it, is a two round protocol secure against active attacks. Moreover, our protocol has small communication complexity and a very small footprint which makes it applicable in scenarios that involve low-cost, resource-constrained devices.
Performance-wise, our protocol is more efficient than previous LPN-based schemes, such as the many variants of the Hopper-Blum (HB) protocol and the aforementioned protocol from Eurocrypt’11. Our implementation results show that it is even comparable to the standard challenge-and-response protocols based on the AES block-cipher. Our basic protocol is roughly 20 times slower than AES, but with the advantage of having 10 times smaller code size. Furthermore, if a few hundred bytes of non-volatile memory are available to allow the storage of some off-line pre-computations, then the online phase of our protocols is only twice as slow as AES.
AU - Heyse, Stefan
AU - Kiltz, Eike
AU - Lyubashevsky, Vadim
AU - Paar, Christof
AU - Pietrzak, Krzysztof Z
ID - 2049
T2 - Conference proceedings FSE 2012
TI - Lapin: An efficient authentication protocol based on ring-LPN
VL - 7549
ER -
TY - JOUR
AB - The BCI competition IV stands in the tradition of prior BCI competitions that aim to provide high quality neuroscientific data for open access to the scientific community. As experienced already in prior competitions not only scientists from the narrow field of BCI compete, but scholars with a broad variety of backgrounds and nationalities. They include high specialists as well as students.The goals of all BCI competitions have always been to challenge with respect to novel paradigms and complex data. We report on the following challenges: (1) asynchronous data, (2) synthetic, (3) multi-class continuous data, (4) sessionto-session transfer, (5) directionally modulated MEG, (6) finger movements recorded by ECoG. As after past competitions, our hope is that winning entries may enhance the analysis methods of future BCIs.
AU - Tangermann, Michael
AU - Müller, Klaus
AU - Aertsen, Ad
AU - Birbaumer, Niels
AU - Braun, Christoph
AU - Brunner, Clemens
AU - Leeb, Robert
AU - Mehring, Carsten
AU - Miller, Kai
AU - Müller Putz, Gernot
AU - Nolte, Guido
AU - Pfurtscheller, Gert
AU - Preissl, Hubert
AU - Schalk, Gerwin
AU - Schlögl, Alois
AU - Vidaurre, Carmen
AU - Waldert, Stephan
AU - Blankertz, Benjamin
ID - 493
JF - Frontiers in Neuroscience
TI - Review of the BCI competition IV
VL - 6
ER -
TY - JOUR
AB - We solve the longstanding open problems of the blow-up involved in the translations, when possible, of a nondeterministic Büchi word automaton (NBW) to a nondeterministic co-Büchi word automaton (NCW) and to a deterministic co-Büchi word automaton (DCW). For the NBW to NCW translation, the currently known upper bound is 2o(nlog n) and the lower bound is 1.5n. We improve the upper bound to n2n and describe a matching lower bound of 2ω(n). For the NBW to DCW translation, the currently known upper bound is 2o(nlog n). We improve it to 2 o(n), which is asymptotically tight. Both of our upper-bound constructions are based on a simple subset construction, do not involve intermediate automata with richer acceptance conditions, and can be implemented symbolically. We continue and solve the open problems of translating nondeterministic Streett, Rabin, Muller, and parity word automata to NCW and to DCW. Going via an intermediate NBW is not optimal and we describe direct, simple, and asymptotically tight constructions, involving a 2o(n) blow-up. The constructions are variants of the subset construction, providing a unified approach for translating all common classes of automata to NCW and DCW. Beyond the theoretical importance of the results, we point to numerous applications of the new constructions. In particular, they imply a simple subset-construction based translation, when possible, of LTL to deterministic Büchi word automata.
AU - Boker, Udi
AU - Kupferman, Orna
ID - 494
IS - 4
JF - ACM Transactions on Computational Logic (TOCL)
TI - Translating to Co-Büchi made tight, unified, and useful
VL - 13
ER -
TY - CONF
AB - An automaton with advice is a finite state automaton which has access to an additional fixed infinite string called an advice tape. We refine the Myhill-Nerode theorem to characterize the languages of finite strings that are accepted by automata with advice. We do the same for tree automata with advice.
AU - Kruckman, Alex
AU - Rubin, Sasha
AU - Sheridan, John
AU - Zax, Ben
ID - 495
T2 - Proceedings GandALF 2012
TI - A Myhill Nerode theorem for automata with advice
VL - 96
ER -
TY - CONF
AB - We study the expressive power of logical interpretations on the class of scattered trees, namely those with countably many infinite branches. Scattered trees can be thought of as the tree analogue of scattered linear orders. Every scattered tree has an ordinal rank that reflects the structure of its infinite branches. We prove, roughly, that trees and orders of large rank cannot be interpreted in scattered trees of small rank. We consider a quite general notion of interpretation: each element of the interpreted structure is represented by a set of tuples of subsets of the interpreting tree. Our trees are countable, not necessarily finitely branching, and may have finitely many unary predicates as labellings. We also show how to replace injective set-interpretations in (not necessarily scattered) trees by 'finitary' set-interpretations.
AU - Rabinovich, Alexander
AU - Rubin, Sasha
ID - 496
TI - Interpretations in trees with countably many branches
ER -