Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Matthias Krause:

TR01-078 | 6th November 2001
Matthias Krause

BDD-based Cryptanalysis of Keystream Generators

Many of the keystream generators which are used in practice are LFSR-based in the sense
that they produce the keystream according to a rule $y=C(L(x))$,
where $L(x)$ denotes an internal linear bitstream, produced by a small number of parallel
linear feedback shift registers (LFSRs),
and $C$ denotes ... more >>>

TR00-014 | 16th February 2000
Matthias Krause, Stefan Lucks

On Learning versus Distinguishing and the Minimal Hardware Complexity of Pseudorandom Function Generators

A set $F$ of $n$-ary Boolean functions is called a pseudorandom function generator
(PRFG) if communicating
with a randomly chosen secret function from $F$ cannot be
efficiently distinguished from communicating with a truly random function.
We ask for the minimal hardware complexity of a PRFG. This question ... more >>>

TR00-003 | 26th November 1999
Matthias Krause, Hans Ulrich Simon

Determining the Optimal Contrast for Secret Sharing Schemes in Visual Cryptography

This paper shows that the largest possible contrast C(k,n)
in a k-out-of-n secret sharing scheme is approximately
4^(-(k-1)). More precisely, we show that
4^(-(k-1)) <= C_{k,n} <= 4^(-(k-1))}n^k/(n(n-1)...(n-(k-1))).
This implies that the largest possible contrast equals
4^(-(k-1)) in the limit when n approaches ... more >>>

TR99-011 | 14th April 1999
Matthias Krause, Petr Savicky, Ingo Wegener

Approximations by OBDDs and the variable ordering problem

Ordered binary decision diagrams (OBDDs) and their variants
are motivated by the need to represent Boolean functions
in applications. Research concerning these applications leads
also to problems and results interesting from theoretical
point of view. In this paper, methods from communication
complexity and ... more >>>

TR95-009 | 2nd February 1995
Matthias Krause

A note on realizing iterated multiplication by small depth threshold circuits

It is shown that decomposition via Chinise Remainder does not
yield polynomial size depth 3 threshold circuits for iterated
multiplication of n-bit numbers. This result is achieved by
proving that, in contrast to multiplication of two n-bit
numbers, powering, division, and other related problems, the
... more >>>

TR94-023 | 12th December 1994
Matthias Krause, Pavel Pudlak

On the Computational Power of Depth 2 Circuits with Threshold and Modulo Gates

We investigate the computational power of depth two circuits
consisting of $MOD^r$--gates at the bottom and a threshold gate at
the top (for short, threshold--$MOD^r$ circuits) and circuits with
two levels of $MOD$ gates ($MOD^{p}$-$MOD^q$ circuits.) In particular, we
will show the following results

(i) For all prime numbers ... more >>>

ISSN 1433-8092 | Imprint