51 search hits
-
Promotionsordnung der Mathematisch-Naturwissenschaftlichen Fachbereiche der Johann Wolfgang Goethe-Universität in Frankfurt am Main vom 26. Mai 1993 (ABL.1/94, S. 21) zuletzt geändert am 05.09.2007 (Uni-Report 13.11.2008) : genehmigt durch Beschluss des Präsidiums der Johann Wolfgang Goethe-Universität Frankfurt am Main am 27. Januar 2009 ; hier: Änderung
(2009)
-
Habilitationsordnung der Mathematisch–Naturwissenschaftlichen Fachbereiche der Johann Wolfgang Goethe-Universität Frankfurt am Main vom 04.02.1992 (ABl. 1992, S.816 ff.), zuletzt geändert am 28. April 2002 (StAnz. 41/2003, S. 4024 – 4025) : genehmigt durch Beschluss des Präsidiums der Johann Wolfgang Goethe-Universität Frankfurt am Main am 27. Januar 2009 ; hier: Änderung bzw. Ergänzung
(2009)
-
Satisfiability is quasilinear complete in NQL
(1978)
-
Claus Peter Schnorr
- Considered are the classes QL (quasilinear) and NQL (nondet quasllmear) of all those problems that can be solved by deterministic (nondetermlnlsttc, respectively) Turmg machines in time O(n(log n) ~) for some k Effloent algorithms have time bounds of th~s type, it is argued. Many of the "exhausUve search" type problems such as satlsflablhty and colorabdlty are complete in NQL with respect to reductions that take O(n(log n) k) steps This lmphes that QL = NQL iff satisfiabdlty is m QL CR CATEGORIES: 5.25
-
The process complexity and effective random tests
(1972)
-
Claus Peter Schnorr
- We propose a variant of the Kolmogorov concept of complexity which yields a common theory of finite and infinite random sequences. The process complexity does not oscillate. We establish some concepts of effective tests which are proved to be equivalent.
-
The Complexity of Approximate Optima for Greatest Common Divisor Computations
(1996)
-
Carsten Rössner
Jean-Pierre Seifert
- We study the approximability of the following NP-complete (in their feasibility recognition forms) number theoretic optimization problems: 1. Given n numbers a1 ; : : : ; an 2 Z, find a minimum gcd set for a1 ; : : : ; an , i.e., a subset S fa1 ; : : : ; ang with minimum cardinality satisfying gcd(S) = gcd(a1 ; : : : ; an ). 2. Given n numbers a1 ; : : : ; an 2 Z, find a 1-minimum gcd multiplier for a1 ; : : : ; an , i.e., a vector x 2 Z n with minimum max 1in jx i j satisfying P n...
-
Primale / duale Segment-Reduktion von Gitterbasen
(2004)
-
Henrik Koy
-
Incremental cryptography and memory checkers
(1997)
-
Marc Fischlin
- We introduce the relationship between incremental cryptography and memory checkers. We present an incremental message authentication scheme based on the XOR MACs which supports insertion, deletion and other single block operations. Our scheme takes only a constant number of pseudorandom function evaluations for each update step and produces smaller authentication codes than the tree scheme presented in [BGG95]. Furthermore, it is secure against message substitution attacks, where the adversary is allowed to tamper messages before update steps, making it applicable to virus protection. From this scheme we derive memory checkers for data structures based on lists. Conversely, we use a lower bound for memory checkers to show that so-called message substitution detecting schemes produce signatures or authentication codes with size proportional to the message length.
-
Pseudorandom function tribe ensembles based on one-way permutations: improvements and applications
(1999)
-
Marc Fischlin
- Pseudorandom function tribe ensembles are pseudorandom function ensembles that have an additional collision resistance property: almost all functions have disjoint ranges. We present an alternative to the construction of pseudorandom function tribe ensembles based on oneway permutations given by Canetti, Micciancio and Reingold [CMR98]. Our approach yields two different but related solutions: One construction is somewhat theoretic, but conceptually simple and therefore gives an easier proof that one-way permutations suffice to construct pseudorandom function tribe ensembles. The other, slightly more complicated solution provides a practical construction; it starts with an arbitrary pseudorandom function ensemble and assimilates the one-way permutation to this ensemble. Therefore, the second solution inherits important characteristics of the underlying pseudorandom function ensemble: it is almost as effcient and if the starting pseudorandom function ensemble is efficiently invertible (given the secret key) then so is the derived tribe ensemble. We also show that the latter solution yields so-called committing private-key encryption schemes. i.e., where each ciphertext corresponds to exactly one plaintext independently of the choice of the secret key or the random bits used in the encryption process.
-
Practical memory checkers for stacks, queues and deques
(1997)
-
Marc Fischlin
- A memory checker for a data structure provides a method to check that the output of the data structure operations is consistent with the input even if the data is stored on some insecure medium. In [8] we present a general solution for all data structures that are based on insert(i,v) and delete(j) commands. In particular this includes stacks, queues, deques (double-ended queues) and lists. Here, we describe more time and space efficient solutions for stacks, queues and deques. Each algorithm takes only a single function evaluation of a pseudorandomlike function like DES or a collision-free hash function like MD5 or SHA for each push/pop resp. enqueue/dequeue command making our methods applicable to smart cards.
-
Efficient non-malleable commitment schemes
(2000)
-
Marc Fischlin
Roger Fischlin
- We present efficient non-malleable commitment schemes based on standard assumptions such as RSA and Discrete-Log, and under the condition that the network provides publicly available RSA or Discrete-Log parameters generated by a trusted party. Our protocols require only three rounds and a few modular exponentiations. We also discuss the difference between the notion of non-malleable commitment schemes used by Dolev, Dwork and Naor [DDN00] and the one given by Di Crescenzo, Ishai and Ostrovsky [DIO98].
