510 Mathematik
Refine
Year of publication
Document Type
- Preprint (52) (remove)
Language
- English (52)
Has Fulltext
- yes (52)
Is part of the Bibliography
- no (52)
Keywords
- Kongress (5)
- Kryptologie (5)
- Online-Publikation (4)
- Commitment Scheme (2)
- Degree Sequence (2)
- Moran model (2)
- Oblivious Transfer (2)
- Random Graph (2)
- San Jose (2)
- Switching Algorithm (2)
- Temporal Graph (2)
- Uniform Sampling (2)
- ancestral selection graph (2)
- duality (2)
- fixation probability (2)
- Λ−coalescent (2)
- Blind Signature (1)
- Block Korkin—Zolotarev reduction (1)
- Calderón problem (1)
- Chinese Remainder Theorem (1)
- Closest Vector Problem (1)
- Commitment (1)
- Commitment schemes (1)
- Dessins d'enfants (1)
- Discrete Logarithm (1)
- FID model (1)
- Factoring (1)
- Identification (1)
- Knapsack problem (1)
- Kochen-Specker theorem (1)
- Korkin—Zolotarev reduction (1)
- LLL-reduction (1)
- Lattice Reduction (1)
- Lattice basis reduction (1)
- Loewner monotonicity and convexity (1)
- Low density subset sum algorithm (1)
- Markov chain Monte Carlo Method (1)
- McEliece (1)
- Modular Multiplication (1)
- Non-Malleability (1)
- Noticeable Probability (1)
- Oracle Query (1)
- Prag <1999> (1)
- Private Information Retrieval (1)
- Public Key Cryptosystem (1)
- Public Parameter (1)
- Quadratic Residue (1)
- Random Oracle (1)
- Random String (1)
- Representation Problem (1)
- San Francisco (1)
- Santa Barbara (1)
- Security Parameter (1)
- Shortest lattice vector problem (1)
- Signature (1)
- Stable reduction algorithm (1)
- Subset sum problem (1)
- Thorne Kishino Felsenstein model (1)
- Trapdoor (1)
- cancer cell dormancy (1)
- compact Riemann surfaces (1)
- computational complexity (1)
- computational geometry (1)
- concurrent composition (1)
- cooperation (1)
- families of hash functions (1)
- finite resolution (1)
- hidden Markov model (1)
- highly regular nearby points (1)
- host-parasite population dynamics (1)
- hypervariable region (1)
- individual-based models (1)
- inner product (1)
- integer vector (1)
- invasion probability (1)
- invasion time (1)
- inverse coefficient problem, (1)
- local randomness (1)
- logarithmic geometry (1)
- multi-drug treatment (1)
- mutation parameter estimation (1)
- non-archimedean geometry (1)
- non-malleability (1)
- one-way functions (1)
- optimal transport (1)
- pair HMM (1)
- polynomial random number generator (1)
- random function generator (1)
- random geometric graph (1)
- random number generator (1)
- resistance mutation (1)
- security analysis of protocols (1)
- semidefinite optimization (1)
- sequence alignment (1)
- short integer relation (1)
- spatial host population structure (1)
- statistical alignment (1)
- stochastic population dynamics (1)
- subgroup growth (1)
- therapy evasion (1)
- treatment protocol design (1)
- treatment success (1)
- tropical geometry (1)
- tropical universal Jacobian (1)
- tropicalization (1)
- universal compactified Jacobian (1)
- von Neumann algebras (1)
Institute
Uniform sampling from the set G(d) of graphs with a given degree-sequence d=(d1,…,dn)∈Nn is a classical problem in the study of random graphs. We consider an analogue for temporal graphs in which the edges are labeled with integer timestamps. The input to this generation problem is a tuple D=(d,T)∈Nn×N>0 and the task is to output a uniform random sample from the set G(D) of temporal graphs with degree-sequence d and timestamps in the interval [1,T]. By allowing repeated edges with distinct timestamps, G(D) can be non-empty even if G(d) is, and as a consequence, existing algorithms are difficult to apply.
We describe an algorithm for this generation problem which runs in expected time O(M) if Δ2+ϵ=O(M) for some constant ϵ>0 and T−Δ=Ω(T) where M=∑idi and Δ=maxidi. Our algorithm applies the switching method of McKay and Wormald [1] to temporal graphs: we first generate a random temporal multigraph and then remove self-loops and duplicated edges with switching operations which rewire the edges in a degree-preserving manner.
Uniform sampling from the set G(d) of graphs with a given degree-sequence d=(d1,…,dn)∈Nn is a classical problem in the study of random graphs. We consider an analogue for temporal graphs in which the edges are labeled with integer timestamps. The input to this generation problem is a tuple D=(d,T)∈Nn×N>0 and the task is to output a uniform random sample from the set G(D) of temporal graphs with degree-sequence d and timestamps in the interval [1,T]. By allowing repeated edges with distinct timestamps, G(D) can be non-empty even if G(d) is, and as a consequence, existing algorithms are difficult to apply.
We describe an algorithm for this generation problem which runs in expected time O(M) if Δ2+ϵ=O(M) for some constant ϵ>0 and T−Δ=Ω(T) where M=∑idi and Δ=maxidi. Our algorithm applies the switching method of McKay and Wormald [1] to temporal graphs: we first generate a random temporal multigraph and then remove self-loops and duplicated edges with switching operations which rewire the edges in a degree-preserving manner.
n this paper we study invasion probabilities and invasion times of cooperative parasites spreading in spatially structured host populations. The spatial structure of the host population is given by a random geometric graph on [0,1]n, n∈N, with a Poisson(N)-distributed number of vertices and in which vertices are connected over an edge when they have a distance of at most rN∈Θ(Nβ−1n) for some 0<β<1 and N→∞. At a host infection many parasites are generated and parasites move along edges to neighbouring hosts. We assume that parasites have to cooperate to infect hosts, in the sense that at least two parasites need to attack a host simultaneously. We find lower and upper bounds on the invasion probability of the parasites in terms of survival probabilities of branching processes with cooperation. Furthermore, we characterize the asymptotic invasion time.
An important ingredient of the proofs is a comparison with infection dynamics of cooperative parasites in host populations structured according to a complete graph, i.e. in well-mixed host populations. For these infection processes we can show that invasion probabilities are asymptotically equal to survival probabilities of branching processes with cooperation.
Furthermore, we build in the proofs on techniques developed in [BP22], where an analogous invasion process has been studied for host populations structured according to a configuration model.
We substantiate our results with simulations.
Muller's ratchet, in its prototype version, models a haploid, asexual population whose size~N is constant over the generations. Slightly deleterious mutations are acquired along the lineages at a constant rate, and individuals carrying less mutations have a selective advantage. The classical variant considers {\it fitness proportional} selection, but other fitness schemes are conceivable as well. Inspired by the work of Etheridge et al. ([EPW09]) we propose a parameter scaling which fits well to the ``near-critical'' regime that was in the focus of [EPW09] (and in which the mutation-selection ratio diverges logarithmically as N→∞). Using a Moran model, we investigate the``rule of thumb'' given in [EPW09] for the click rate of the ``classical ratchet'' by putting it into the context of new results on the long-time evolution of the size of the best class of the ratchet with (binary) tournament selection, which (other than that of the classical ratchet) follows an autonomous dynamics up to the time of its extinction. In [GSW23] it was discovered that the tournament ratchet has a hierarchy of dual processes which can be constructed on top of an Ancestral Selection graph with a Poisson decoration. For a regime in which the mutation/selection-ratio remains bounded away from 1, this was used in [GSW23] to reveal the asymptotics of the click rates as well as that of the type frequency profile between clicks. We will describe how these ideas can be extended to the near-critical regime in which the mutation-selection ratio of the tournament ratchet converges to 1 as N→∞.
Using limit linear series on chains of curves, we show that closures of certain Brill-Noether loci contain a product of pointed Brill-Noether loci of small codimension. As a result, we obtain new non-containments of Brill-Noether loci, in particular that dimensionally expected non-containments hold for expected maximal Brill-Noether loci. Using these degenerations, we also give a new proof that Brill-Noether loci with expected codimension −ρ≤⌈g/2⌉ have a component of the expected dimension. Additionally, we obtain new non-containments of Brill-Noether loci by considering the locus of the source curves of unramified double covers.
We prove that the projectivized strata of differentials are not contained in pointed Brill-Noether divisors, with only a few exceptions. For a generic element in a stratum of differentials, we show that many of the associated pointed Brill-Noether loci are of expected dimension. We use our results to study the Auel-Haburcak Conjecture: We obtain new non-containments between maximal Brill-Noether loci in Mg. Our results regarding quadratic differentials imply that the quadratic strata in genus 6 are uniruled.
The free energy of TAP-solutions for the SK-model of mean field spin glasses can be expressed as a nonlinear functional of local terms: we exploit this feature in order to contrive abstract REM-like models which we then solve by a classical large deviations treatment. This allows to identify the origin of the physically unsettling quadratic (in the inverse of temperature) correction to the Parisi free energy for the SK-model, and formalizes the true cavity dynamics which acts on TAP-space, i.e. on the space of TAP-solutions. From a non-spin glass point of view, this work is the first in a series of refinements which addresses the stability of hierarchical structures in models of evolving populations.
Muller's ratchet, in its prototype version, models a haploid, asexual population whose size~N is constant over the generations. Slightly deleterious mutations are acquired along the lineages at a constant rate, and individuals carrying less mutations have a selective advantage. The classical variant considers {\it fitness proportional} selection, but other fitness schemes are conceivable as well. Inspired by the work of Etheridge et al. ([EPW09]) we propose a parameter scaling which fits well to the ``near-critical'' regime that was in the focus of [EPW09] (and in which the mutation-selection ratio diverges logarithmically as N→∞). Using a Moran model, we investigate the``rule of thumb'' given in [EPW09] for the click rate of the ``classical ratchet'' by putting it into the context of new results on the long-time evolution of the size of the best class of the ratchet with (binary) tournament selection, which (other than that of the classical ratchet) follows an autonomous dynamics up to the time of its extinction. In [GSW23] it was discovered that the tournament ratchet has a hierarchy of dual processes which can be constructed on top of an Ancestral Selection graph with a Poisson decoration. For a regime in which the mutation/selection-ratio remains bounded away from 1, this was used in [GSW23] to reveal the asymptotics of the click rates as well as that of the type frequency profile between clicks. We will describe how these ideas can be extended to the near-critical regime in which the mutation-selection ratio of the tournament ratchet converges to 1 as N→∞.
Motivated by the question of the impact of selective advantage in populations with skewed reproduction mechanims, we study a Moran model with selection. We assume that there are two types of individuals, where the reproductive success of one type is larger than the other. The higher reproductive success may stem from either more frequent reproduction, or from larger numbers of offspring, and is encoded in a measure Λ for each of the two types. Our approach consists of constructing a Λ-asymmetric Moran model in which individuals of the two populations compete, rather than considering a Moran model for each population. Under certain conditions, that we call the "partial order of adaptation", we can couple these measures. This allows us to construct the central object of this paper, the Λ−asymmetric ancestral selection graph, leading to a pathwise duality of the forward in time Λ-asymmetric Moran model with its ancestral process. Interestingly, the construction also provides a connection to the theory of optimal transport. We apply the ancestral selection graph in order to obtain scaling limits of the forward and backward processes, and note that the frequency process converges to the solution of an SDE with discontinous paths. Finally, we derive a Griffiths representation for the generator of the SDE and use it to find a semi-explicit formula for the probability of fixation of the less beneficial of the two types.
Motivated by the question of the impact of selective advantage in populations with skewed reproduction mechanims, we study a Moran model with selection. We assume that there are two types of individuals, where the reproductive success of one type is larger than the other. The higher reproductive success may stem from either more frequent reproduction, or from larger numbers of offspring, and is encoded in a measure Λ for each of the two types. Our approach consists of constructing a Λ-asymmetric Moran model in which individuals of the two populations compete, rather than considering a Moran model for each population. Under certain conditions, that we call the ``partial order of adaptation'', we can couple these measures. This allows us to construct the central object of this paper, the Λ−asymmetric ancestral selection graph, leading to a pathwise duality of the forward in time Λ-asymmetric Moran model with its ancestral process. Interestingly, the construction also provides a connection to the theory of optimal transport. We apply the ancestral selection graph in order to obtain scaling limits of the forward and backward processes, and note that the frequency process converges to the solution of an SDE with discontinous paths. Finally, we derive a Griffiths representation for the generator of the SDE and use it to find a semi-explicit formula for the probability of fixation of the less beneficial of the two types.
Therapy evasion – and subsequent disease progression – is a major challenge in current oncology. An important role in this context seems to be played by various forms of cancer cell dormancy. For example, therapy-induced dormancy, over short timescales, can create serious obstacles to aggressive treatment approaches such as chemotherapy, and long-term dormancy may lead to relapses and metastases even many years after an initially successful treatment. The underlying dormancy-related mechanisms are complex and highly diverse, so that the analysis even of basic patterns of the population-level consequences of dormancy requires abstraction and idealization, as well as the identification of the relevant specific scenarios.
In this paper, we focus on a situation in which individual cancer cells may switch into and out of a dormant state both spontaneously as well as in response to treatment, and over relatively short time-spans. We introduce a mathematical ‘toy model’, based on stochastic agent-based interactions, for the dynamics of cancer cell populations involving individual short-term dormancy, and allow for a range of (multi-drug) therapy protocols. Our analysis shows that in our idealized model, even a small initial population of dormant cells can lead to therapy failure under classical (and in the absence of dormancy successful) single-drug treatments. We further investigate the effectiveness of several multidrug regimes (manipulating dormant cancer cells in specific ways) and provide some basic rules for the design of (multi-)drug treatment protocols depending on the types and parameters of dormancy mechanisms present in the population.
For genus g=r(r+1)2+1, we prove that via the forgetful map, the universal Prym-Brill-Noether locus Rrg has a unique irreducible component dominating the moduli space Rg of Prym curves.
For genus g=2i≥4 and the length g−1 partition μ=(4,2,…,2,−2,…,−2) of 0, we compute the first coefficients of the class of D¯¯¯¯(μ) in PicQ(R¯¯¯¯g), where D(μ) is the divisor consisting of pairs [C,η]∈Rg with η≅OC(2x1+x2+⋯+xi−1−xi−⋯−x2i−1) for some points x1,…,x2i−1 on C. We further provide several enumerative results that will be used for this computation.
Between his arrival in Frankfurt in 1922 and and his proof of his famous finiteness theorem for integral points in 1929, Siegel had no publications. He did, however, write a letter to Mordell in 1926 in which he explained a proof of the finiteness of integral points on hyperelliptic curves. Recognizing the importance of this argument (and Siegel's views on publication), Mordell sent the relevant extract to be published under the pseudonym "X".
The purpose of this note is to explain how to optimize Siegel's 1926 technique to obtain the following bound. Let K be a number field, S a finite set of places of K, and f∈oK,S[t] monic of degree d≥5 with discriminant Δf∈o×K,S. Then: #|{(x,y):x,y∈oK,S,y2=f(x)}|≤2rankJac(Cf)(K)⋅O(1)d3⋅([K:Q]+#|S|).
This improves bounds of Evertse-Silverman and Bombieri-Gubler from 1986 and 2006, respectively.
The main point underlying our improvement is that, informally speaking, we insist on "executing the descents in the presence of only one root (and not three) until the last possible moment".
For genus g=2i≥4 and the length g−1 partition μ=(4,2,…,2,−2,…,−2) of 0, we compute the first coefficients of the class of D¯¯¯¯(μ) in PicQ(R¯¯¯¯g), where D(μ) is the divisor consisting of pairs [C,η]∈Rg with η≅OC(2x1+x2+⋯+xi−1−xi−⋯−x2i−1) for some points x1,…,x2i−1 on C. We further provide several enumerative results that will be used for this computation.
We prove that the projectivized strata of differentials are not contained in pointed Brill-Noether divisors, with only a few exceptions. For a generic element in a stratum of differentials, we show that many of the associated pointed Brill-Noether loci are of expected dimension. We use our results to study the Auel-Haburcak Conjecture: We obtain new non-containments between maximal Brill-Noether loci in Mg. Our results regarding quadratic differentials imply that the quadratic strata in genus 6 are uniruled.
Using the notion of a root datum of a reductive group G we propose a tropical analogue of a principal G-bundle on a metric graph. We focus on the case G=GLn, i.e. the case of vector bundles. Here we give a characterization of vector bundles in terms of multidivisors and use this description to prove analogues of the Weil--Riemann--Roch theorem and the Narasimhan--Seshadri correspondence. We proceed by studying the process of tropicalization. In particular, we show that the non-Archimedean skeleton of the moduli space of semistable vector bundles on a Tate curve is isomorphic to a certain component of the moduli space of semistable tropical vector bundles on its dual metric graph.
In this article we provide a stack-theoretic framework to study the universal tropical Jacobian over the moduli space of tropical curves. We develop two approaches to the process of tropicalization of the universal compactified Jacobian over the moduli space of curves -- one from a logarithmic and the other from a non-Archimedean analytic point of view. The central result from both points of view is that the tropicalization of the universal compactified Jacobian is the universal tropical Jacobian and that the tropicalization maps in each of the two contexts are compatible with the tautological morphisms. In a sequel we will use the techniques developed here to provide explicit polyhedral models for the logarithmic Picard variety.
Foundations of geometry
(2020)
In an earlier paper we proposed a recursive model for epidemics; in the present paper we generalize this model to include the asymptomatic or unrecorded symptomatic people, which we call dark people (dark sector). We call this the SEPARd-model. A delay differential equation version of the model is added; it allows a better comparison to other models. We carry this out by a comparison with the classical SIR model and indicate why we believe that the SEPARd model may work better for Covid-19 than other approaches.
In the second part of the paper we explain how to deal with the data provided by the JHU, in particular we explain how to derive central model parameters from the data. Other parameters, like the size of the dark sector, are less accessible and have to be estimated more roughly, at best by results of representative serological studies which are accessible, however, only for a few countries. We start our country studies with Switzerland where such data are available. Then we apply the model to a collection of other countries, three European ones (Germany, France, Sweden), the three most stricken countries from three other continents (USA, Brazil, India). Finally we show that even the aggregated world data can be well represented by our approach.
At the end of the paper we discuss the use of the model. Perhaps the most striking application is that it allows a quantitative analysis of the influence of the time until people are sent to quarantine or hospital. This suggests that imposing means to shorten this time is a powerful tool to flatten the curves.
Changes in the efficacies of synapses are thought to be the neurobiological basis of learning and memory. The efficacy of a synapse depends on its current number of neurotransmitter receptors. Recent experiments have shown that these receptors are highly dynamic, moving back and forth between synapses on time scales of seconds and minutes. This suggests spontaneous fluctuations in synaptic efficacies and a competition of nearby synapses for available receptors. Here we propose a mathematical model of this competition of synapses for neurotransmitter receptors from a local dendritic pool. Using minimal assumptions, the model produces a fast multiplicative scaling behavior of synapses. Furthermore, the model explains a transient form of heterosynaptic plasticity and predicts that its amount is inversely related to the size of the local receptor pool. Overall, our model reveals logistical tradeoffs during the induction of synaptic plasticity due to the rapid exchange of neurotransmitter receptors between synapses.
Antimicrobial resistance is a major threat to global health and food security today. Scheduling cycling therapies by targeting phenotypic states associated to specific mutations can help us to eradicate pathogenic variants in chronic infections. In this paper, we introduce a logistic switching model in order to abstract mutation networks of collateral resistance. We found particular conditions for which unstable zero-equilibrium of the logistic maps can be stabilized through a switching signal. That is, persistent populations can be eradicated through tailored switching regimens.
Starting from an optimal-control formulation, the switching policies show their potential in the stabilization of the zero-equilibrium for dynamics governed by logistic maps. However, employing such switching strategies, deserve a specific characterization in terms of limit behaviour. Ultimately, we use evolutionary and control algorithms to find either optimal and sub-optimal switching policies. Simulations results show the applicability of Parrondo’s Paradox to design cycling therapies against drug resistance.
We propose a generalized modeling framework for the kinetic mechanisms of transcriptional riboswitches. The formalism accommodates time-dependent transcription rates and changes of metabolite concentration and permits incorporation of variations in transcription rate depending on transcript length. We derive explicit analytical expressions for the fraction of transcripts that determine repression or activation of gene expression, pause site location and its slowing down of transcription for the case of the (2’dG)-sensing riboswitch from Mesoplasma florum. Our modeling challenges the current view on the exclusive importance of metabolite binding to transcripts containing only the aptamer domain. Numerical simulations of transcription proceeding in a continuous manner under time-dependent changes of metabolite concentration further suggest that rapid modulations in concentration result in a reduced dynamic range for riboswitch function regardless of transcription rate, while a combination of slow modulations and small transcription rates ensures a wide range of finely tuneable regulatory outcomes.
COVID-19 pandemic has underlined the impact of emergent pathogens as a major threat for human health. The development of quantitative approaches to advance comprehension of the current outbreak is urgently needed to tackle this severe disease. In this work, several mathematical models are proposed to represent SARS-CoV-2 dynamics in infected patients. Considering different starting times of infection, parameters sets that represent infectivity of SARS-CoV-2 are computed and compared with other viral infections that can also cause pandemics.
Based on the target cell model, SARS-CoV-2 infecting time between susceptible cells (mean of 30 days approximately) is much slower than those reported for Ebola (about 3 times slower) and influenza (60 times slower). The within-host reproductive number for SARS-CoV-2 is consistent to the values of influenza infection (1.7-5.35). The best model to fit the data was including immune responses, which suggest a slow cell response peaking between 5 to 10 days post onset of symptoms. The model with eclipse phase, time in a latent phase before becoming productively infected cells, was not supported. Interestingly, both, the target cell model and the model with immune responses, predict that virus may replicate very slowly in the first days after infection, and it could be below detection levels during the first 4 days post infection. A quantitative comprehension of SARS-CoV-2 dynamics and the estimation of standard parameters of viral infections is the key contribution of this pioneering work.
We deal with the reconstruction of inclusions in elastic bodies based on monotonicity methods and construct conditions under which a resolution for a given partition can be achieved. These conditions take into account the background error as well as the measurement noise. As a main result, this shows us that the resolution guarantees depend heavily on the Lamé parameter μ and only marginally on λ.
The Calderón problem with finitely many unknowns is equivalent to convex semidefinite optimization
(2023)
We consider the inverse boundary value problem of determining a coefficient function in an elliptic partial differential equation from knowledge of the associated Neumann-Dirichlet-operator. The unknown coefficient function is assumed to be piecewise constant with respect to a given pixel partition, and upper and lower bounds are assumed to be known a-priori.
We will show that this Calderón problem with finitely many unknowns can be equivalently formulated as a minimization problem for a linear cost functional with a convex non-linear semidefinite constraint. We also prove error estimates for noisy data, and extend the result to the practically relevant case of finitely many measurements, where the coefficient is to be reconstructed from a finite-dimensional Galerkin projection of the Neumann-Dirichlet-operator.
Our result is based on previous works on Loewner monotonicity and convexity of the Neumann-Dirichlet-operator, and the technique of localized potentials. It connects the emerging fields of inverse coefficient problems and semidefinite optimization.
The purpose of the paper is to initiate the development of the theory of Newton Okounkov bodies of curve classes. Our denition is based on making a fundamental property of NewtonOkounkov bodies hold also in the curve case: the volume of the NewtonOkounkov body of a curve is a volume-type function of the original curve. This construction allows us to conjecture a new relation between NewtonOkounkov bodies, we prove it in certain cases.
Motivation: The topic of this paper is the estimation of alignments and mutation rates based on stochastic sequence-evolution models that allow insertions and deletions of subsequences ("fragments") and not just single bases. The model we propose is a variant of a model introduced by Thorne, Kishino, and Felsenstein (1992). The computational tractability of the model depends on certain restrictions in the insertion/deletion process; possible effects we discuss.
Results: The process of fragment insertion and deletion in the sequence-evolution model induces a hidden Markov structure at the level of alignments and thus makes possible efficient statistical alignment algorithms. As an example we apply a sampling procedure to assess the variability in alignment and mutation parameter estimates for HVR1 sequences of human and orangutan, improving results of previous work. Simulation studies give evidence that estimation methods based on the proposed model also give satisfactory results when applied to data for which the restrictions in the insertion/deletion process do not hold.
Availability: The source code of the software for sampling alignments and mutation rates for a pair of DNA sequences according to the fragment insertion and deletion model is freely available from www.math.uni-frankfurt.de/~stoch/software/mcmcsalut under the terms of the GNU public license (GPL, 2000).
Pseudorandom function tribe ensembles based on one-way permutations: improvements and applications
(1999)
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.
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.
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].
Based on the quadratic residuosity assumption we present a non-interactive crypto-computing protocol for the greater-than function, i.e., a non-interactive procedure between two parties such that only the relation of the parties' inputs is revealed. In comparison to previous solutions our protocol reduces the number of modular multiplications significantly. We also discuss applications to conditional oblivious transfer, private bidding and the millionaires' problem.
We propose a new security measure for commitment protocols, called Universally Composable (UC) Commitment. The measure guarantees that commitment protocols behave like an \ideal commitment service," even when concurrently composed with an arbitrary set of protocols. This is a strong guarantee: it implies that security is maintained even when an unbounded number of copies of the scheme are running concurrently, it implies non-malleability (not only with respect to other copies of the same protocol but even with respect to other protocols), it provides resilience to selective decommitment, and more. Unfortunately two-party uc commitment protocols do not exist in the plain model. However, we construct two-party uc commitment protocols, based on general complexity assumptions, in the common reference string model where all parties have access to a common string taken from a predetermined distribution. The protocols are non-interactive, in the sense that both the commitment and the opening phases consist of a single message from the committer to the receiver.
We review the representation problem based on factoring and show that this problem gives rise to alternative solutions to a lot of cryptographic protocols in the literature. And, while the solutions so far usually either rely on the RSA problem or the intractability of factoring integers of a special form (e.g., Blum integers), the solutions here work with the most general factoring assumption. Protocols we discuss include identification schemes secure against parallel attacks, secure signatures, blind signatures and (non-malleable) commitments.
We show that non-interactive statistically-secret bit commitment cannot be constructed from arbitrary black-box one-to-one trapdoor functions and thus from general public-key cryptosystems. Reducing the problems of non-interactive crypto-computing, rerandomizable encryption, and non-interactive statistically-sender-private oblivious transfer and low-communication private information retrieval to such commitment schemes, it follows that these primitives are neither constructible from one-to-one trapdoor functions and public-key encryption in general. Furthermore, our separation sheds some light on statistical zeroknowledge proofs. There is an oracle relative to which one-to-one trapdoor functions and one-way permutations exist, while the class of promise problems with statistical zero-knowledge proofs collapses in P. This indicates that nontrivial problems with statistical zero-knowledge proofs require more than (trapdoor) one-wayness.
We propose a fast variant of the Gaussian algorithm for the reduction of two dimensional lattices for the l1-, l2- and l-infinite- norm. The algorithm runs in at most O(nM(B) logB) bit operations for the l-infinite- norm and in O(n log n M(B) logB) bit operations for the l1 and l2 norm on input vectors a, b 2 ZZn with norm at most 2B where M(B) is a time bound for B-bit integer multiplication. This generalizes Schönhages monotone Algorithm [Sch91] to the centered case and to various norms.
We introduce algorithms for lattice basis reduction that are improvements of the famous L3-algorithm. If a random L3-reduced lattice basis b1,b2,...,bn is given such that the vector of reduced Gram-Schmidt coefficients ({µi,j} 1<= j< i<= n) is uniformly distributed in [0,1)n(n-1)/2, then the pruned enumeration finds with positive probability a shortest lattice vector. We demonstrate the power of these algorithms by solving random subset sum problems of arbitrary density with 74 and 82 many weights, by breaking the Chor-Rivest cryptoscheme in dimensions 103 and 151 and by breaking Damgard's hash function.
We call a vector x/spl isin/R/sup n/ highly regular if it satisfies =0 for some short, non-zero integer vector m where <...> is the inner product. We present an algorithm which given x/spl isin/R/sup n/ and /spl alpha//spl isin/N finds a highly regular nearby point x' and a short integer relation m for x'. The nearby point x' is 'good' in the sense that no short relation m~ of length less than /spl alpha//2 exists for points x~ within half the x'-distance from x. The integer relation m for x' is for random x up to an average factor 2/sup /spl alpha//2/ a shortest integer relation for x'. Our algorithm uses, for arbitrary real input x, at most O(n/sup 4/(n+log A)) many arithmetical operations on real numbers. If a is rational the algorithm operates on integers having at most O(n/sup 5/+n/sup 3/(log /spl alpha/)/sup 2/+log(/spl par/qx/spl par//sup 2/)) many bits where q is the common denominator for x.
We report on improved practical algorithms for lattice basis reduction. We propose a practical floating point version of theL3-algorithm of Lenstra, Lenstra, Lovász (1982). We present a variant of theL3-algorithm with "deep insertions" and a practical algorithm for block Korkin—Zolotarev reduction, a concept introduced by Schnorr (1987). Empirical tests show that the strongest of these algorithms solves almost all subset sum problems with up to 66 random weights of arbitrary bit length within at most a few hours on a UNISYS 6000/70 or within a couple of minutes on a SPARC1 + computer.
We call a distribution on n bit strings (", e) locally random, if for every choice of e · n positions the induced distribution on e bit strings is in the L1 norm at most " away from the uniform distribution on e bit strings. We establish local randomness in polynomial random number generators (RNG) that are candidate one way functions. Let N be a squarefree integer and let f1, . . . , f be polynomials with coe±- cients in ZZN = ZZ/NZZ. We study the RNG that stretches a random x 2 ZZN into the sequence of least significant bits of f1(x), . . . , f(x). We show that this RNG provides local randomness if for every prime divisor p of N the polynomials f1, . . . , f are linearly independent modulo the subspace of polynomials of degree · 1 in ZZp[x]. We also establish local randomness in polynomial random function generators. This yields candidates for cryptographic hash functions. The concept of local randomness in families of functions extends the concept of universal families of hash functions by Carter and Wegman (1979). The proofs of our results rely on upper bounds for exponential sums.
We propose two improvements to the Fiat Shamir authentication and signature scheme. We reduce the communication of the Fiat Shamir authentication scheme to a single round while preserving the e±ciency of the scheme. This also reduces the length of Fiat Shamir signatures. Using secret keys consisting of small integers we reduce the time for signature generation by a factor 3 to 4. We propose a variation of our scheme using class groups that may be secure even if factoring large integers becomes easy.
Assuming a cryptographically strong cyclic group G of prime order q and a random hash function H, we show that ElGamal encryption with an added Schnorr signature is secure against the adaptive chosen ciphertext attack, in which an attacker can freely use a decryption oracle except for the target ciphertext. We also prove security against the novel one-more-decyption attack. Our security proofs are in a new model, corresponding to a combination of two previously introduced models, the Random Oracle model and the Generic model. The security extends to the distributed threshold version of the scheme. Moreover, we propose a very practical scheme for private information retrieval that is based on blind decryption of ElGamal ciphertexts.
We enhance the security of Schnorr blind signatures against the novel one-more-forgery of Schnorr [Sc01] andWagner [W02] which is possible even if the discrete logarithm is hard to compute. We show two limitations of this attack. Firstly, replacing the group G by the s-fold direct product G exp(×s) increases the work of the attack, for a given number of signer interactions, to the s-power while increasing the work of the blind signature protocol merely by a factor s. Secondly, we bound the number of additional signatures per signer interaction that can be forged effectively. That fraction of the additional forged signatures can be made arbitrarily small.
Let G be a Fuchsian group containing two torsion free subgroups defining isomorphic Riemann surfaces. Then these surface subgroups K and alpha-Kalpha exp(-1) are conjugate in PSl(2,R), but in general the conjugating element alpha cannot be taken in G or a finite index Fuchsian extension of G. We will show that in the case of a normal inclusion in a triangle group G these alpha can be chosen in some triangle group extending G. It turns out that the method leading to this result allows also to answer the question how many different regular dessins of the same type can exist on a given quasiplatonic Riemann surface.