nach oben

2008 | Buch

Kapitel lesen Erstes Kapitel lesen

Mathematical Methods in Computer Science

Essays in Memory of Thomas Beth

herausgegeben von: Jacques Calmet, Willi Geiselmann, Jörn Müller-Quade

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Inhaltsverzeichnis

Frontmatter

Cryptography I

On the Security of Beth’s Identification Schemes against Active and Concurrent Adversaries

Abstract

One of the earliest identification schemes was proposed by Beth in [6]. Since its introduction, variations and generalizations of this scheme have been considered, and, recently, the property of security against passive impersonation was shown, under a weak unforgeability assumption on the hashed El Gamal signature scheme, for two such variants: one in the standard (i.e., not identity-based) and one in the identity-based model. However, the security of both protocols under active and concurrent impersonation attacks was left open.

In this paper we prove that very minor modifications to these schemes result in schemes that satisfy security under active and concurrent impersonation attacks, assuming a one-more-dlog assumption. The resulting protocols are just as efficient as the original variants, which are, in turn, somewhat more efficient (but less general) of the original one proposed by Beth.

Giovanni Di Crescenzo

Designs

Steiner t-Designs for Large t

Abstract

One of the most central and long-standing open questions in combinatorial design theory concerns the existence of Steiner t-designs for large values of t. Although in his classical 1987 paper, L. Teirlinck has shown that non-trivial t-designs exist for all values of t, no non-trivial Steiner t-design with t > 5 has been constructed until now. Understandingly, the case t = 6 has received considerable attention. There has been recent progress concerning the existence of highly symmetric Steiner 6-designs: It is shown in [M. Huber, J. Algebr. Comb. 26 (2007), pp. 453–476] that no non-trivial flag-transitive Steiner 6-design can exist. In this paper, we announce that essentially also no block-transitive Steiner 6-design can exist.

Michael Huber

New Spatial Configurations

Abstract

This second paper on constructions of spatial configurations follows the author’s paper of 1994 [2]. For the first time again new spatial configurations are constructed, in particular a configuration (33₈)₂, the smallest known configuration (v ₈)₂, and several configurations (v ₉)₂, in particular for v = 40 and for v ≥ 43.

Harald Gropp

Construction of Large Constant Dimension Codes with a Prescribed Minimum Distance

Abstract

In this paper we construct constant dimension codes with prescribed minimum distance. There is an increased interest in subspace codes in general since a paper [13] by Kötter and Kschischang where they gave an application in network coding. There is also a connection to the theory of designs over finite fields. We will modify a method of Braun, Kerber and Laue [7] which they used for the construction of designs over finite fields to construct constant dimension codes. Using this approach we found many new constant dimension codes with a larger number of codewords than previously known codes. We finally give a table of the best constant dimension codes we found.

Axel Kohnert, Sascha Kurz

Quantum Computing

Invited Talk: Embedding Classical into Quantum Computation

Abstract

We describe a simple formalism for generating classes of quantum circuits that are classically efficiently simulatable and show that the efficient simulation of Clifford circuits (Gottesman-Knill theorem) and of matchgate circuits (Valiant’s theorem) appear as two special cases. Viewing these simulatable classes as subsets of the space of all quantum computations, we may consider minimal extensions that suffice to regain full quantum computational power, which provides an approach to exploring the efficacy of quantum over classical computation.

Richard Jozsa

A Criterion for Attaining the Welch Bounds with Applications for Mutually Unbiased Bases

Abstract

The paper gives a short introduction to mutually unbiased bases and the Welch bounds and demonstrates that the latter is a good technical tool to explore the former. In particular, a criterion for a system of vectors to satisfy the Welch bounds with equality is given and applied for the case of MUBs. This yields a necessary and sufficient condition on a set of orthonormal bases to form a complete system of MUBs.

This condition takes an especially elegant form in the case of homogeneous systems of MUBs. We express some known constructions of MUBs in this form. Also it is shown how recently obtained results binding MUBs and some combinatorial structures (such as perfect nonlinear functions and relative difference sets) naturally follow from this criterion.

Some directions for proving non-existence results are sketched as well.

Aleksandrs Belovs, Juris Smotrovs

An Efficient Quantum Algorithm for the Hidden Subgroup Problem over Weyl-Heisenberg Groups

Abstract

Many exponential speedups that have been achieved in quantum computing are obtained via hidden subgroup problems (HSPs). We show that the HSP over Weyl-Heisenberg groups can be solved efficiently on a quantum computer. These groups are well-known in physics and play an important role in the theory of quantum error-correcting codes. Our algorithm is based on non-commutative Fourier analysis of coset states which are quantum states that arise from a given black-box function. We use Clebsch-Gordan decompositions to combine and reduce tensor products of irreducible representations. Furthermore, we use a new technique of changing labels of irreducible representations to obtain low-dimensional irreducible representations in the decomposition process. A feature of the presented algorithm is that in each iteration of the algorithm the quantum computer operates on two coset states simultaneously. This is an improvement over the previously best known quantum algorithm for these groups which required four coset states.

Hari Krovi, Martin Rötteler

Algorithms

Computing Equiangular Lines in Complex Space

Abstract

We consider the problem of finding equiangular lines in complex space, i. e., sets of unit vectors such that the modulus of the inner product between any two vectors is constant. We focus on the case of d ² such vectors in a space of dimension d which corresponds to so-called SIC-POVMs. We discuss how symmetries can be used to simplify the problem and how the corresponding system of polynomial equations can be solved using techniques of modular computation.

Markus Grassl

Complexity of Comparing Monomials and Two Improvements of the Buchberger-Möller Algorithm

Abstract

We give a new algorithm for merging sorted lists of monomials. Together with a projection technique we obtain a new complexity bound for the Buchberger-Möller algorithm.

Samuel Lundqvist

Coding Theory

Invited Talk: Decoding Cyclic Codes: The Cooper Philosophy

(Extended Abstract)

Abstract

In 1990, Cooper [9, 10] suggested to use Gröbner basis [3, 4] computation in order to deduce error locator polynomials of cyclic codes.

Teo Mora, Emmanuela Orsini

Kernel Dimension for Some Families of Quaternary Reed-Muller Codes

Abstract

Recently, new families of quaternary linear Reed-Muller codes such that, after the Gray map, the corresponding ℤ₄-linear codes have the same parameters and properties as the codes in the usual binary linear Reed-Muller family have been introduced. A structural invariant, the kernel dimension, for binary codes can be used to classify these ℤ₄-linear codes. The kernel dimension for these ℤ₄-linear codes is established generalizing the known results about the kernel dimension for ℤ₄-linear Hadamard and ℤ₄-linear extended 1-perfect codes.

J. Pernas, J. Pujol, M. Villanueva

Cryptography II

Coding-Based Oblivious Transfer

Abstract

We present protocols for two flavors of oblivious transfer (OT): the Rabin and 1-out-of-2 OT based on the assumptions related to security of the McEliece cryptosystem and two zero-knowledge identification (ZKID) schemes, Stern’s from Crypto ’93 and Shamir’s from Crypto ’89, which are based on syndrome decoding and permuted kernels, respectively. This is a step towards diversifying computational assumptions on which OT – cryptographic primitive of central importance – can be based.

As a by-product, we expose new interesting applications for both ZKID schemes: Stern’s can be used for proving correctness of McEliece encryption, while Shamir’s – for proving that some matrix represents a permuted subcode of a given code.

Unfortunately, it turned out to be difficult to reduce the sender’s security of both schemes to a hard problem, although the intuition suggests a successful attack may allow to solve some long-standing problems in coding theory.

Kazukuni Kobara, Kirill Morozov, Raphael Overbeck

Protection of Sensitive Security Parameters in Integrated Circuits

Abstract

To protect sensitive security parameters in the non-volatile memory of integrated circuits, a device is designed that generates a special secret key (called IC-Eigenkey) to symmetrically encrypt this data. The IC-Eigenkey is generated by the integrated circuit itself and therefore unknown to anybody else. The desired properties of such an IC-Eigenkey are postulated and a theoretical limit on the distribution of IC-Eigenkeys over an IC-production series is derived. The design of the IC-Eigenkey generator is based on silicon physical uncloneable functions. It exploits the marginal random variations of the propagation delays of gates and wires in an integrated circuit. A method is introduced that uses codewords of error control codes to configure the IC-Eigenkey generator in a way that the generated bits are as statistically independent of each other as possible.

Dejan E. Lazich, Micaela Wuensche

On Reconstruction of RC4 Keys from Internal States

Abstract

In this work key recovery algorithms from the known internal states of RC4 are investigated. In particular, we propose a bit-by-bit approach to recover the key by starting from LSB’s of the key bytes and ending with their MSB’s.

Shahram Khazaei, Willi Meier

Backmatter

Titel: Mathematical Methods in Computer Science
herausgegeben von: Jacques Calmet
Willi Geiselmann
Jörn Müller-Quade
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-89994-5
Print ISBN: 978-3-540-89993-8
DOI: https://doi.org/10.1007/978-3-540-89994-5