Search Results

Documents authored by Krause, Matthias

Document
DOI: 10.4230/DagSemProc.09031.3
Algebraic Attacks against Linear RFID Authentication Protocols

Authors: Matthias Krause and Dirk Stegemann

Published in: Dagstuhl Seminar Proceedings, Volume 9031, Symmetric Cryptography (2009)

Abstract
The limited computational resources available on RFID tags imply a need for specially designed authentication protocols. The light weight authentication protocol $extsf{HB}^+$ proposed by Juels and Weis seems currently secure for several RFID applications, but is too slow for many practical settings. As a possible alternative, authentication protocols based on choosing random elements from $L$ secret linear $n$-dimensional subspaces of $GF(2)^{n+k}$ (so called linear $(n,k,L)$-protocols), have been considered. We show that to a certain extent, these protocols are vulnerable to algebraic attacks. Particularly, our approach allows to break Cicho'{n}, Klonowski and Kutyl owski's $ extsf{CKK}^2$-protocol, a special linear $(n,k,2)$-protocol, for practically recommended parameters in less than a second on a standard PC. Moreover, we show that even unrestricted $(n,k,L)$-protocols can be efficiently broken if $L$ is too small.
Cite as

Matthias Krause and Dirk Stegemann. Algebraic Attacks against Linear RFID Authentication Protocols. In Symmetric Cryptography. Dagstuhl Seminar Proceedings, Volume 9031, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{krause_et_al:DagSemProc.09031.3,
  author =	{Krause, Matthias and Stegemann, Dirk},
  title =	{{Algebraic Attacks against Linear RFID Authentication Protocols}},
  booktitle =	{Symmetric Cryptography},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9031},
  editor =	{Helena Handschuh and Stefan Lucks and Bart Preneel and Phillip Rogaway},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09031.3},
  URN =		{urn:nbn:de:0030-drops-19576},
  doi =		{10.4230/DagSemProc.09031.3},
  annote =	{Keywords: RFID Authentication, HB+, CKK, CKK2}
}
Document
DOI: 10.4230/DagSemProc.06111.2
06111 Executive Summary – Complexity of Boolean Functions

Authors: Matthias Krause, Dieter van Melkebeek, Pavel Pudlák, and Rüdiger Reischuk

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
We briefly describe the state of the art concerning the complexity of discrete functions. Computational models and analytical techniques are summarized. After describing the formal organization of the Dagstuhl seminar "Complexity of Boolean Functions" held in March 2006, we introduce the different topics that have been discussed there and mention some of the major achievements. The summary closes with an outlook on the development of discrete computational complexity in the future.
Cite as

Matthias Krause, Dieter van Melkebeek, Pavel Pudlák, and Rüdiger Reischuk. 06111 Executive Summary – Complexity of Boolean Functions. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{krause_et_al:DagSemProc.06111.2,
  author =	{Krause, Matthias and van Melkebeek, Dieter and Pudl\'{a}k, Pavel and Reischuk, R\"{u}diger},
  title =	{{06111 Executive Summary – Complexity of Boolean Functions}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.2},
  URN =		{urn:nbn:de:0030-drops-8409},
  doi =		{10.4230/DagSemProc.06111.2},
  annote =	{Keywords: Boolean and quantum circuits, discrete problems, computational complexity, lower bounds, communication complexity, proof and query complexity, randomization, pseudo-randomness, derandomization, approximation, cryptography, computational learning}
}
Document
DOI: 10.4230/DagSemProc.06111.1
06111 Abstracts Collection – Complexity of Boolean Functions

Authors: Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, and Dieter van Melkebeek

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
From 12.03.06 to 17.03.06, the Dagstuhl Seminar 06111 ``Complexity of Boolean Functions'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, and Dieter van Melkebeek. 06111 Abstracts Collection – Complexity of Boolean Functions. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{krause_et_al:DagSemProc.06111.1,
  author =	{Krause, Matthias and Pudl\'{a}k, Pavel and Reischuk, R\"{u}diger and van Melkebeek, Dieter},
  title =	{{06111 Abstracts Collection – Complexity of Boolean Functions}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.1},
  URN =		{urn:nbn:de:0030-drops-7593},
  doi =		{10.4230/DagSemProc.06111.1},
  annote =	{Keywords: Complexity of Boolean functions, Boolean circuits, binary decision diagrams, lower bound proof techniques, combinatorics of Boolean functions, communi algorithmic learning, cryptography, derandomization}
}
Document
DOI: 10.4230/DagSemRep.338
Complexity of Boolean Functions (Dagstuhl Seminar 02121)

Authors: Johan Hastad, Matthias Krause, David A. M. Barrington, and Rüdiger Reischuk

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Johan Hastad, Matthias Krause, David A. M. Barrington, and Rüdiger Reischuk. Complexity of Boolean Functions (Dagstuhl Seminar 02121). Dagstuhl Seminar Report 338, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{hastad_et_al:DagSemRep.338,
  author =	{Hastad, Johan and Krause, Matthias and Barrington, David A. M. and Reischuk, R\"{u}diger},
  title =	{{Complexity of Boolean Functions (Dagstuhl Seminar 02121)}},
  pages =	{1--25},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{338},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.338},
  URN =		{urn:nbn:de:0030-drops-152207},
  doi =		{10.4230/DagSemRep.338},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact