- Markus Hinkelmann, Andreas Jakoby:
Preserving Privacy versus Data Retention.
Technischer Bericht SIIM-TR-A-08-04,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
2008.
PDF anzeigen | Zusammenfassung anzeigen
The retention of communication data has recently attracted much public interest, mostly because of the possibility of its misuse.
In this paper, we present protocols that address the privacy concerns of the communication partners.
Our data retention protocols store streams of encrypted data items,
some of which may be flagged as
critical (representing misbehavior). The frequent occurrence of critical data items justifies the self-decryption of all recently stored data items, critical or not.
Our first protocol allows the party gathering the retained data to decrypt
all data items collected within, say, the last half year
whenever the number of critical data items reaches some threshold within, say, the last month.
The protocol ensures that the senders of data remain anonymous but may reveal that different critical data items came from the same sender. We call this the affiliation of critical data. Our second, computationally more complex scheme obscures the affiliation of critical data with high probability.
- Markus Hinkelmann, Andreas Jakoby, Peer Stechert:
t-Private and t-Secure Auctions.
Technischer Bericht SIIM-TR-A-08-01,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
2008.
PDF anzeigen | Zusammenfassung anzeigen
In most of the used auction systems the values of bids are known to the auctioneer. This allows him to manipulate the outcome of the auction. Hence, one is
interested in hiding these values. Some cryptographically secure protocols for electronic auctions have been presented in the last decade.
Our work extends these protocols in several ways. Based on garbled circuits, i.e., encrypted circuits, we present protocols for sealed-bid auctions that fulfill the following requirements:
1. Protocols are information-theoretically t-private for honest but curious parties.
2. The number of bits that can be learned by malicious adversaries is bounded by the output length of the auction.
3. The computational requirements for participating parties are very low: only random bit choices and bitwise computation of the XOR-function are necessary.
Note that one can distinguish between the protocol
that generates a garbled circuit for an auction and the protocol to evaluate the auction. In this paper we address both problems. We will present a t-private protocol
for the construction of a garbled circuit that reaches the lower bound of 2t+1 parties, and a more randomness efficient protocol for (t+1)^2 parties.
Finally, we address the problem of bid changes in an auction.
- Markus Hinkelmann, Andreas Jakoby, Peer Stechert:
t-Private and t-Secure Auctions.
Journal of Computer Science and Technology, 23(5):694-710, 2008.
Zusammenfassung anzeigen
In most of the auction systems the values of bids are known to the auctioneer. This allows him to manipulate the outcome of the auction. Hence, one might be interested in hiding these values. Some cryptographically secure protocols for electronic auctions have been presented in the last decade. Our work extends these protocols in several ways. On the basis of garbled circuits, i.e., encrypted circuits, we present protocols for sealed-bid auctions that fulfill the following requirements: 1) protocols are information-theoretically t-private for {\em honest but curious parties; 2) the number of bits that can be learned by {\em malicious adversaries is bounded by the output length of the auction; 3) the computational requirements for participating parties are very low: only random bit choices and bitwise computation of the {\tt XOR-function are necessary. Note that one can distinguish between the protocol that generates a garbled circuit for an auction and the protocol to evaluate the auction. In this paper we address both problems. We will present a t-private protocol for the construction of a garbled circuit that reaches the lower bound of 2t+1 parties, and a more randomness efficient protocol for (t+1)^2 parties. Finally, we address the problem of bid changes in an auction.
- Andreas Jakoby, Rüdiger Reischuk:
Average Complexity of Unbounded Fanin Circuits.
In 11. IEEE Conference on Computational Complexity COMPLEXITY'2000, S. 170-185.
IEEE Computer Society,
2000.
Website anzeigen - Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
Space Efficient Algorithms for Series-Parallel Graphs.
Technischer Bericht SIIM-TR-A-00-17,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
2000.
Postscript anzeigen | Zusammenfassung anzeigen
The subclass of directed series-parallel graphs plays an important role in
computer science. To determine whether a graph is series-parallel is a
well studied problem in algorithmic graph theory. Fast sequential and
parallel algorithms for this problem have been developed in a sequence
of papers. For series-parallel graphs methods are also known to solve
the reachability and the decomposition problem time efficiently.
However, no dedicated results have been obtained for the space complexity
of these problems -- the topic of this paper.
For this special class of graphs, we develop deterministic algorithms
for the recognition, reachability, decomposition and the path counting
problem that use only logarithmic space. Since for arbitrary directed
graphs reachability and path counting are believed not to be solvable
in log-space the main contribution of this work are novel deterministic
path finding routines that work correctly in series-parallel graphs,
and a new characterization of series-parallel graphs by forbidden subgraphs.
We then sketch how these results can be generalised to extension of
the series-parallel graph family: to graphs with multiple sources or multiple
sinks and to the class of minimal vertex series-parallel graphs.
It it also shown that the space bounds are best possible,
i.e. the decision problems are L-complete with respect to AC-reductions.
Finally, we discuss implications of theses small space bounds for
the parallel time complexity of series-parallel graphs.
- Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
The Expressive Power and Complexity of Dynamic Process Graphs.
In 26. Int. Workshop on Graph-Theoretical Concepts in Computer Science WG'2000, Band 1928 von Lecture Notes in Computer Science, S. 230-242.
Springer,
2000.
Website anzeigen - Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
The Expressive Power and Complexity of Dynamic Process Graphs.
Technischer Bericht SIIM-TR-A-00-07,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
2000.
Postscript anzeigen | Zusammenfassung anzeigen
A model for parallel and distributed programs, the dynamic process graph,
is investigated under graph-theoretic and complexity aspects. Such graphs
are capable of representing all possible executions of a parallel or
distributed program in a very compact way. The size of this representation
is small -- in many cases only logarithmic with respect to the size of any
execution of the program. An important feature of this model is that
the encoded executions are directed acyclic graphs with a regular structure,
which is typical of parallel programs, and that it embeds constructors for
parallel programs, synchronization mechanisms as well as conditional branches.
In a previous paper we have analysed the expressive power of the general
model and various restrictions. Furthermore, from an algorithmic point
of view it is important to decide whether a given dynamic process graph can
be executed correctly and to estimate the minimal deadline given enough
parallelism. Our model takes into account communication delays between
processors when exchanging data.
In this paper we study a variant with output restriction. It is appropriate
in many situations, but its expressive power has not been known exactly.
First, we investigate structural properties of the executions of such dynamic
process graphs G. A natural graph-theoretic conjecture that executions must
always split into components isomorphic to subgraphs of G turns out to be
wrong. We are able to establish a weaker property. This implies a quadratic
bound on the maximal deadline in contrast to the general case, where
the execution time may be exponential. However, we show that the problem
to determine the minimal deadline is still intractable, namely this problem
is NEXPTIME-complete as is the general case. The lower bound is obtained by
showing that this kind of dynamic process graphs can represent certain
Boolean formulas in a highly succinct way.
This is an extended abstract to be presented at 26th International Workshop
on Graph-Theoretic Concepts in Computer Science, Konstanz, Germany, 2000.
- Andreas Jakoby, Rüdiger Reischuk:
Average Case Complexity of Unbounded Fanin Circuits.
Technischer Bericht SIIM-TR-A-98-17,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
1998.
Postscript anzeigen | Zusammenfassung anzeigen
Several authors have shown that the PARITY-function cannot be computed by
unbounded fanin circuits of small depth and polynomial size.
Even more, constant depth k circuits of size exp n^Theta(1/k) give
wrong results for PARITY for almost half of all inputs.
We generalize these results in two directions.
First, we obtain similar tight lower bounds for the average
case complexity of circuits, measuring the computational delay
instead of the static circuit depth.
Secondly, with respect to average delay of unbounded fanin circuits
we completely classify all parallel prefix functions,
for which PARITY is just one promiment example.
It is shown that only two cases can occur: a parallel prefix functions f either
has the same average complexity as PARITY, that is the average delay has to be
of order Theta(log n / loglog s) for circuits of size s,
or f can be computed with constant average delay and almost linear size --
there is no complexity level in between.
This classification is achieved by analyzing the algebraic structure of
semigroups that correspond to parallel prefix functions.
It extends methods developed for bounded fanin circuits
by the first author in his Ph.D. Thesis.
- Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
Scheduling Dynamic Graphs.
Technischer Bericht SIIM-TR-A-98-07,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
1998.
Postscript anzeigen | Zusammenfassung anzeigen
In parallel and distributed computing scheduling low level tasks on the
available hardware is a fundamental problem. Traditionally, one has assumed
that the set of tasks to be executed is known beforehand. Then the scheduling
constraints are given by a precedence graph. Nodes represent the elementary
tasks and edges the dependencies among tasks. This static approach is not
appropriate in situations where the set of tasks is not known exactly in
advance, for example, when different options how to continue a program may
be granted.
In this paper a new model for parallel and distributed programs, the dynamic
process graph will be introduced, which represents all possible executions of
a program in a compact way. The size of this representation is small -- in
many cases only logarithmically with respect to the size of any execution.
An important feature of our model is that unlike precedence graphs, the
encoded executions are directed acyclic graphs having a "regular" structure
that is typical of parallel programs. Dynamic process graphs embed
constructors for parallel programs, synchronization mechanisms as well as
conditional branches. With respect to such a compact representation we
investigate the complexity of different aspects of the scheduling problem:
the question whether a legal schedule exists at all and how to find an
optimal schedule. Our analysis takes into account communication delays
between processors exchanging data.
Precise characterization of the computational complexity of various variants
of this compact scheduling problem will be given in this paper. The results
range from easy, that is NL-complete, to very hard, namely NEXPTIME-complete.
- Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer:
The Complexity of Broadcasting in Planar and Decomposable Graphs.
Discrete Applied Mathematics, 1-3(83):179-206, 1998.
Website anzeigen | Zusammenfassung anzeigen
[URL=http://www.elsevier.com/wps/find/journaldescription.cws_home/505609/description#description]also included in special issue "Discrete Applied Mathematics - Editors' Choice 1988[/URL]
- Andreas Jakoby:
Die Komplexität von Präfixfunktionen bezüglich ihres mittleren Zeitverhaltens.
Universität zu Lübeck, Institut für Theoretische Informatik,
1998.
Gutachter: Rüdiger Reischuk, Walter Dosch, Wolfgang Thomas.
- Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer:
Circuit Complexity: from the Worst Case to the Average Case.
Technischer Bericht SIIM-TR-A-95-02,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
1995.
Postscript anzeigen | Zusammenfassung anzeigen
In contrast to machine models like Turing machines or random access
machines, circuits are a rigid computational model. The internal
information flow of a computation is fixed in advance, independent
of the actual input. Therefore, in complexity theory only worst case
complexity measures have been used to analyse this model. Concerning
the circuit size this seems to be the best one can do.
The delay between feeding the input bits into a circuit and being
able to read off the output bits at the output gates is usually
measured by the depth of the circuit. One might try to take advantage
of favourable cases in which the output values are obtained much
earlier. This will be the case when critical paths, e.g. paths
between input and output gates of maximal length, have no influence
on the final output.
Inspired by recent successful attempts to develop a meaningful
average case analysis for TM computations [L86,G91,BCGL92,RS93a], we
follow the same goal for the circuit model. For this purpose, a new
comlexity measure for the internal delay is defined, called time.
This may be given implicitely or explicitely, where in the latter case
a gate has to signal that it is ``ready'', e.g. has computed the desired
result. Using a simple coding both models are shown to be equivalent.
By doubling the number of gates any circuit with implicit timing can
easily be transformed to an equivalent circuit with explicit time
signals.
Based on the notion of time, two average case measures for the circuit
delay are defined. The analysis is not restricted to uniform distributions
over the input space, instead a large class of distributions will be
considered. For this purpose, a complexity notion is needed for
distributions. We define a measure based on the circuit model by considering
the complexity of circuits with uniform distributed random input bits
that generate such distributions.
Finally, this new approach is applied to concrete examples. We derive
matching lower and upper bounds for the average circuit delay for basic
functions like the OR, ADDITION, THRESHOLD and PARITY. It will be shown
that for PARITY the average delay remains logarithmic. In many cases,
however, an exponential speedup compared to the worst case can be achieved.
For example, the average delay for n-Bit-ADDITION is of order loglog n.
The circuit designs to achieve these bounds turn out to be very different
from the standard ones for optimal worst case results.
A preliminary version was presented at 26th STOC'94
- Andreas Jakoby, Rüdiger Reischuk:
Data Transmission in Processor Networks.
In 9. International Workshop on Distributed Algorithms WDAG'95, Band 972 von Lecture Notes in Computer Science, S. 145-159.
Springer,
1995.
Website anzeigen - Andreas Jakoby, Rüdiger Reischuk:
Data Transmission in Processor Networks.
Technischer Bericht SIIM-TR-A-95-18,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
1995.
Postscript anzeigen | Zusammenfassung anzeigen
We investigate the communication capacity and optimal data
transmission schedules for processor networks connected by
communication links, for example Transputer clusters. Each
link allows the two processors at its endpoints to exchange
data with a given fixed transmission rate tau_d. The commu-
nication itself is done in a blocking mode, that means the
two processors have to synchronize before starting to exchange
data and at any time each processor cannot communicate with
more than one other processor.
Our efficiency analysis will be more realistic by also taking
into account the setup time for a communication, which will be
assumed to be a fixed constant tau_s > 0. Thus, a large amount
of data can be sent from one processor to a neighbour faster by
a single long communication step than by a bunch of small data
exchange steps: sending p data units in one step takes time
tau_s + p * tau_d. However, there is a tradeoff since the receiver
has to wait until it has received the complete set of data before
it can forward pieces to other processors.
The following prototype task called scattering will be considered:
At the beginning one processor called the source possesses a set of
unit size data packets, one for each processor in the network. The
goal is to distribute the packets in minimal time to all recipients.
- Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer:
Malign Distributions for Average Case Circuit Complexity.
In 12. GI-AFCET Symposium on Theoretical Aspects of Computer Science STACS'95, Band 900 von Lecture Notes in Computer Science, S. 628-639.
Springer,
1995.
Website anzeigen - Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer:
Malign Distributions for Average Case Circuit Complexity.
Technischer Bericht SIIM-TR-A-95-06,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
1995.
Postscript anzeigen | Zusammenfassung anzeigen
In contrast to machine models like Turing machines or random access
machines, circuits are a rigid computational model. The internal
information flow of a computation is fixed in advance, independent of
the actual input. Therefore, in complexity theory only worst case
complexity measures have been used to analyse this model. In [JRS94] we
have defined an average case measure for the time complexity of circuits.
Using this notion tight upper and lower bounds could be obtained for
the average case complexity of several basic Boolean functions.
In this paper we will examine the asymptotic average case complexity of
the set of n-input Boolean functions. In contrast to the worst case a
simple counting argument does not work. We prove that almost all Boolean
function require at least n-log n-llog n expected time even for the uniform
probability distribution. On the other hand, we show that there are
significant subsets of functions that can be computed with a constant
average delay.
Finally, the worst case and average case complexity of a Boolean function
will be compared. We show that for each function that requires circuit
depth d, the expected time complexity will be at least d-log n-log d
with respect to an explicitely defined probability distribution. A nontrivial
bound on the complexity of such a distribution is obtained.
- Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer, Stephan Weis:
The Average Case Complexity of the Parallel Prefix Problem.
Technischer Bericht SIIM-TR-A-95-03,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
1995.
Postscript anzeigen | Zusammenfassung anzeigen
We analyse the average case complexity of evaluating all prefixes of
an input vector over a given semigroup. As computational model
circuits over the semigroup are used and a complexity measure for the
average delay of such circuits, called time, is introduced. Based on
this notion, we then define the average case complexity of a
computational problem for arbitrary input distributions.
For highly nonuniform distributions the average case complexity turns
out to be as large as the worst case complexity. Thus, in order to
make the average case analysis meaningful we also develop a complexity
measure for distributions.
Using this framework we show that two n-bit numbers can be added with
an average delay of order loglog n for a large class of distributions.
We then give a complete characterization of the average case
complexity of the parallel prefix problem with respect to the
underlying semigroup. By considering a related reachability problem
for finite automata it is shown that the complexity only depends on a
property of the semigroup we will call a confluence.
Our analysis yields that only two different cases can arise for the
reachability question. We show that the parallel prefix problem
either can be solved with an average delay of order loglog n, that
means with an exponential speedup compared to the worst case, or in
case of nonconfluent semigroups that no speedup is possible. Circuit
designs are presented that for confluent semigroups achieve the
optimal double logarithmic delay while keeping the circuit size
linear.
The analysis and results are illustrated at some concrete functions.
For the n-ary Boolean OR, THRESHOLD and PARITY, for example, the
average case circuit delay is determined exactly up to small constant
factors for arbitrary distributions.
Finally, we determine the complexity of the reachability problem
itself and show that it is at most quadratic in the size of the
semigroup.
- Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer:
The Complexity of Broadcasting in Planar and Decomposable Graphs.
Technischer Bericht SIIM-TR-A-95-08,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
1995.
Postscript anzeigen | Zusammenfassung anzeigen
Broadcasting in processor networks means disseminating a single piece
of information, which is originally known only at some nodes, to all
members of the network. The goal is to inform everybody using as few
rounds as possible, that is minimize the broadcasting time.
Given a graph and a subset of nodes, the sources, the problem to determine
its specific broadcast time, or more general to find a broadcast schedule
of minimal length has shown to be NP-complete. In contrast to other
optimization problems for graphs, like vertex cover or traveling salesman,
little was known about restricted graph classes for which polynomial time
algorithms exist, for example for graphs of bounded treewidth. The
broadcasting problem is harder in this respect because it does not have the
finite state property. Here, we will investigate this problem in detail and
prove that it remains hard even if one restricts to planar graphs of bounded
degree or constant broadcasting time. A simple consequence is that the
minimal broadcasting time cannot even be approximated with an error less than
1/8, unless P = NP.
On the other hand, we will investigate for which classes of graphs this
problem can be solved efficiently and show that broadcasting and even a more
general version of this problem becomes easy for graphs with good
decomposition properties. The solution strategy can efficiently be
parallelized, too. Combining the negative and the positive results reveals
the parameters that make broadcasting difficult. Depending on simple graph
properties the complexity jumps from NC or P to NP.
Classification: algorithms and data structures, computational complexity.