Mathematik
Refine
Year of publication
Document Type
- Article (110)
- Doctoral Thesis (76)
- Preprint (46)
- diplomthesis (39)
- Book (25)
- Report (22)
- Conference Proceeding (18)
- Bachelor Thesis (8)
- Contribution to a Periodical (8)
- Diploma Thesis (8)
Has Fulltext
- yes (372) (remove)
Is part of the Bibliography
- no (372)
Keywords
- Kongress (6)
- Kryptologie (5)
- Mathematik (5)
- Stochastik (5)
- Doku Mittelstufe (4)
- Doku Oberstufe (4)
- Online-Publikation (4)
- Statistik (4)
- Finanzmathematik (3)
- LLL-reduction (3)
- Moran model (3)
- coalescent (3)
- computational complexity (3)
- contraction method (3)
- point process (3)
- spike train (3)
- Algebraische Geometrie (2)
- Arithmetische Gruppe (2)
- Biographie (2)
- Brownian motion (2)
- Commitment Scheme (2)
- Frankfurt <Main> / Universität (2)
- Fuchsian groups (2)
- Fächerübergreifender Unterricht (2)
- Geometrie (2)
- Heat kernel (2)
- Hinterlegungsverfahren <Kryptologie> (2)
- Integral Geometry (2)
- Knapsack problem (2)
- Kombinatorische Optimierung (2)
- Krein space (2)
- Laplace operator on graphs (2)
- Lattice basis reduction (2)
- Martingal (2)
- Mathematiker (2)
- Musik (2)
- Oblivious Transfer (2)
- Perception (2)
- Quantum Zeno dynamics (2)
- San Jose (2)
- Semidefinite Programming (2)
- Shortest lattice vector problem (2)
- Stochastischer Prozess (2)
- Subset sum problem (2)
- Tropical geometry (2)
- Tropische Geometrie (2)
- Valuation Theory (2)
- Verzweigungsprozess (2)
- Vision (2)
- W*-dynamical system (2)
- X-Y model (2)
- Yule-Prozess (2)
- ancestral selection graph (2)
- binary search tree (2)
- collective intelligence (2)
- combinatorial optimization (2)
- complexity (2)
- duality (2)
- firing patterns (2)
- fixation probability (2)
- genealogy (2)
- level of difficulty (2)
- quantum spin systems (2)
- return to equilibrium (2)
- segments (2)
- task space (2)
- thought structure (2)
- Λ−coalescent (2)
- A-Discriminant (1)
- ADM1 (1)
- Abelian (1)
- Action potential (1)
- Actions in mathematical learning (1)
- Activity (1)
- Adaptive dynamics (1)
- Algebra (1)
- Algorithmus (1)
- Amoeba (1)
- Anaerobe Fermentation (1)
- Analyse von Algorithmen (1)
- Ancestral selection graph (1)
- Anisotropic Norm (1)
- Approximation (1)
- Approximation algorithm (1)
- Approximationsalgorithmus (1)
- Arbitrage (1)
- Assignment Problem (1)
- Asymptotically Even Nonlinearity (1)
- Ausreißer <Statistik> (1)
- Automorphismengruppe (1)
- Axon (1)
- Banach spaces (1)
- Bayesian Inference (1)
- Berkovich spaces (1)
- Binomialmodell (1)
- Binärsuchbaum (1)
- Black and Scholes Option Price theory (1)
- Black-Scholes (1)
- Blind Signature (1)
- Block Korkin—Zolotarev reduction (1)
- Blockplay (1)
- Bolthausen-Sznitman (1)
- Boolean Lattice (1)
- Bootstrap-Statistik (1)
- Boundary (1)
- Boundary Value Problems (1)
- Branch and Bound (1)
- Branching particle systems (1)
- Branching process approximation (1)
- Breaking knapsack cryptosystems (1)
- Bruhat-Tits-Gebäude (1)
- Burst (1)
- CAT(0)-Räume (1)
- CAT(0)-spaces (1)
- CIR-1 (1)
- Calderón problem (1)
- Cannings model (1)
- Catalan number (1)
- Cauchy-Anfangswertproblem (1)
- Cayley-Graph (1)
- China-Restaurant-Prozess (1)
- Chinese Remainder Theorem (1)
- Chinese restaurant process (1)
- Chinese-restaurant-process (1)
- Circuit (1)
- Closest Vector Problem (1)
- Coamoeba (1)
- Cognitive psychology (1)
- Commitment (1)
- Commitment schemes (1)
- Computational complexity (1)
- Concentration Inequality (1)
- Condensing (1)
- Containment (1)
- Contraction method (1)
- Datenbank (1)
- Datenstruktur (1)
- Degenerate Linear Part (1)
- Dehn (1)
- Derivate (1)
- Dessins d'enfants (1)
- Diagrams and mathematical learning (1)
- Dichte <Stochastik> (1)
- Digital and analogue materials (1)
- Digital trees (1)
- Dimension 2 (1)
- Directional selection (1)
- Dirichlet bound (1)
- Dirichlet random measure (1)
- Dirichletsche L-Reihe; Nullstelle (1)
- Discrete Logarithm (1)
- Diskrete Geometrie (1)
- Diskrete Mathematik (1)
- Diskreter Markov-Prozess (1)
- Diversity in trait space (1)
- Donkers theorem (1)
- Dopamine (1)
- Doplicher-Haag-Roberts Axiomatik; Algebraische Quantenfeldtheorie; Superauswahlregeln und -sektoren; Quantenstatistik; Zopfgruppenstatistik (1)
- Dormancy (1)
- Dosis-Wirkungs-Modellierung (1)
- Dreiecksgruppe (1)
- Dreiecksgruppen (1)
- Duality (1)
- Early Childhood (1)
- Einbettung <Mathematik> (1)
- Elektronische Unterschrift (1)
- Elementar- und Primarbereich (1)
- Endliche Präsentation (1)
- Endlichkeitseigenschaften (1)
- Energie-Modell (1)
- Error Bound (1)
- Erwartungswert (1)
- Evolutionary branching (1)
- Evolving Yield Curves in the Real-World Measures (1)
- Ewens sampling formula (1)
- Examples (1)
- Extended RMJBN Modell (1)
- FEM-BEM-coupling (1)
- FID model (1)
- FIND algorithm (1)
- Face (1)
- Face recognition (1)
- Factoring (1)
- Familie (1)
- Family (1)
- Feller branching with logistic growth (1)
- Finite element methods (1)
- Finitely many measurements (1)
- Fixation probability (1)
- Fixpunkt (1)
- Fractional Brownian Motion (1)
- Fractional Laplacian (1)
- Frühe Bildung (1)
- Fuchs-Gruppe (1)
- Fuchssche Gruppe ; Modulare Einbettung (1)
- Fuchssche Gruppen (1)
- Functions (1)
- Funktionenkegel (1)
- Funktionenkörper ; Arithmetische Gruppe ; Auflösbare Gruppe ; Endlichkeit (1)
- Galerkin Approximation (1)
- Galois group (1)
- Galois-Gruppe (1)
- Game Tree (1)
- Gaussian Random Field (1)
- Gaussian process (1)
- Gelfand-Shilov space (1)
- Gemischte Volumen (1)
- Genealogical construction (1)
- Genealogische Konstruktion (1)
- Genetischer Fingerabdruck (1)
- Genus One (1)
- Geometrische Gruppentheorie (1)
- Geometry (1)
- Gespräch (1)
- Gestaenge (1)
- Girsanov transform (1)
- Gitter <Mathematik> ; Basis <Mathematik> ; Reduktion ; Algorithmus ; Laufzeit ; L-unendlich-Norm ; Rucksackproblem ; Kryptosystem (1)
- Gitter <Mathematik> ; Basis <Mathematik> ; Reduktion ; Gauß-Algorithmus (1)
- Gram-Hadamard inequalities (1)
- Graphen (1)
- Grenzwertsatz (1)
- Griffiths–Engen–McCloskey distribution (1)
- Group dynamics (1)
- Große Abweichung (1)
- Großinvestor (1)
- Gruppendynamiken (1)
- Gruppentheorie (1)
- Hadamard's Three-Lines Theorem (1)
- Halbeinfache algebraische Gruppe (1)
- Handelman (1)
- Handlung (1)
- Harmoniebox (1)
- Heisenberg algebra (1)
- Hidden Markov models (1)
- Hintertür <Informatik> (1)
- Hodge bundle (1)
- Holzklötzchen (1)
- Hopf algebroids (1)
- Householder reflection (1)
- Hyperfunktion ; Asymptotische Entwicklung (1)
- Hypotrochoid (1)
- Identification (1)
- Immigration (1)
- Index at Infinity (1)
- Infrared singularity (1)
- Integer relations (1)
- Integraldarstellung (1)
- Interaction (1)
- Internet (1)
- Invariante (1)
- Inverse problems (1)
- Iteration (1)
- Jahr der Mathematik (1)
- Kettenbruchentwicklung ; Dimension n ; Diophantische Approximation (1)
- Kieferorthopädie (1)
- Klassifizierender Raum (1)
- Klebsiella pneumoniae (1)
- Knotenabstand (1)
- Knotentiefe (1)
- Koaleszent (1)
- Kochen-Specker theorem (1)
- Kollektivintelligenz (1)
- Kombinatorische Gruppen (1)
- Konforme Feldtheorie (1)
- Konstruktiver Beweis (1)
- Kontaktprozess (1)
- Kontraktionsmethode (1)
- Konzentrationsungleichung (1)
- Korkin—Zolotarev reduction (1)
- Kreuzkorrelation (1)
- Kryptosystem (1)
- Kullback-Leibler Informational Divergence (1)
- L^p bounds (1)
- L^p means (1)
- Label cover (1)
- Lanzeitverhalten (1)
- Laplace-Differentialgleichung (1)
- Large Deviation (1)
- Lattice Reduction (1)
- Leerverkauf (1)
- Lernen (1)
- Linear Filtering (1)
- Linear Preferential Attachment Trees (1)
- Linear-Implicit Scheme (1)
- Linkages (1)
- Loewner monotonicity and convexity (1)
- Logarithmic Laplacian (1)
- Long- Range Dependence (1)
- Long-Range Dependence (1)
- Long-time behaviour (1)
- Longitudinal Study (1)
- Lotka-Volterra system (1)
- Lovász Local Lemma (1)
- Low density subset sum algorithm (1)
- MINT-Bildung (1)
- Machine Learning (1)
- Malliavin calculus (1)
- Mallows model (1)
- Markov chain Monte Carlo Method (1)
- Markov chain imbedding technique (1)
- Markov model (1)
- Markov-Kette (1)
- Mathematical Giftedness (1)
- Mathematical Reasoning (1)
- Mathematical modelling (1)
- Mathematics Learning (1)
- Mathematische Bildung (1)
- Mathematische Modellierung (1)
- Max (1)
- McEliece (1)
- Mean Anisotropy (1)
- Message authentication (1)
- Methanogenese (1)
- Mixed Volumes (1)
- Modellierung (1)
- Modular Multiplication (1)
- Mooney faces (1)
- Morava K-theory (1)
- Mouse (1)
- Multi-Harmonie-Ansatz (1)
- Multiple lineare Regression (1)
- Multityp-Verzweigungsprozess mit Immigration (1)
- Multitype Branching with Immigration (1)
- NP-complete problems (1)
- NP-hard (1)
- NP-hardness (1)
- Nash-Gleichgewicht (1)
- Nelson-Siegel (1)
- Neural encoding (1)
- Neurophysiology (1)
- Neuroscience (1)
- Neurowissenschaft (1)
- Newton–Okounkov bodies (1)
- Non-Malleability (1)
- Noticeable Probability (1)
- Optimal Mean-Square Filter (1)
- Oracle Query (1)
- Parabolic SPDE (1)
- Parisi conjecture (1)
- Participation (1)
- Partizipation (1)
- Patientenbewertung (1)
- Pause (1)
- Permutation (1)
- Permutationsgruppen (1)
- Pfadeigenschaften (1)
- Phragmén-Lindelöf principle (1)
- Piecewise-constant coefficient (1)
- Poisson Process (1)
- Poisson boundary (1)
- Poisson-Prozess (1)
- Polyedrische Kombinatorik (1)
- Polymorphic evolution sequence (1)
- Polynomial Optimization (1)
- Pontrjagin space (1)
- Populationsdynamiken (1)
- Portfolios (1)
- Positivstellensatz (1)
- Potenzialtheorie (1)
- Prag <1999> (1)
- Preferential Attachment-Modelle (1)
- Private Information Retrieval (1)
- Probabilistic analysis of algorithms (1)
- Probabilistically checkable proofs (1)
- Probabilistische Analyse von Algorithmen (1)
- Probability distribution (1)
- Probability of fixation (1)
- Professionalisierung (1)
- Profil Likelihood (1)
- Projektionen (1)
- Public Key Cryptosystem (1)
- Public Parameter (1)
- Punktprozess (1)
- Pólya urn (1)
- Quadratic Residue (1)
- Quantenfeldtheorie ; Konforme Feldtheorie ; Algebraische Methode (1)
- Quantum Zeno Effect (1)
- Quantum Zeno effect (1)
- Quasi-Automorphismen (1)
- Quaternionenalgebra (1)
- Quickselect (1)
- RSA-Verschlüsselung (1)
- Radix sort (1)
- Random Oracle (1)
- Random Split Trees (1)
- Random String (1)
- Random environment (1)
- Random variables (1)
- Randomisieren (1)
- Ray-Knight representation (1)
- Reaction time (1)
- Reale vs. risikoneutrale Welt in der Finanzmathematik (1)
- Rechenzentrum (1)
- Rekursiver Algorithmus (1)
- Relaxation (1)
- Representation Problem (1)
- Research article (1)
- Riemann surfaces (1)
- Riemannsche Fläche (1)
- Riemannsche Flächen (1)
- Ringtheorie (1)
- Risikobewertung (1)
- Risikomanagement (1)
- Robustheit (1)
- Rückkopplungseffekt (1)
- S-arithmetic groups (1)
- SLLL-reduction (1)
- Sackgassen (1)
- San Francisco (1)
- Santa Barbara (1)
- Schizophrenia (1)
- Schwarz triangel functions (1)
- Schwinger model (1)
- Security (1)
- Security Parameter (1)
- Semidefinite Optimierung (1)
- Semidefinite Optimization (1)
- Semiotics according to C. S. Peirce (1)
- Sensory perception (1)
- Sensory processing (1)
- Sigma-Invariante (1)
- Sigma-invariant (1)
- Signalverarbeitung (1)
- Signature (1)
- Small Worlds (1)
- Small order expansion (1)
- Spectrahedra (1)
- Spiel (1)
- Spielbaum (1)
- Spielbaum-Suchverfahren (1)
- Stable reduction algorithm (1)
- State dependent branching rate (1)
- Stationarity (1)
- Stochastic Analysis of Square Zero Variation Processes (1)
- Stonesches Spektrum (1)
- Striatum (1)
- Strong Taylor Scheme (1)
- Stummel, Friedrich (1)
- Suchbaum (1)
- Suchoperation (1)
- Sudoku (1)
- Sum of Squares (1)
- Support (1)
- Symmetrie (1)
- Symmetrischer Raum (1)
- Symmetry (1)
- Sympatric speciation (1)
- Tail Bound (1)
- Tailschranke (1)
- Talk (1)
- Thorne Kishino Felsenstein model (1)
- Topic Model (1)
- Trapdoor (1)
- Trinomial (1)
- Tropical Geometry (1)
- Tropical Grassmannians (1)
- Tropical bases (1)
- Tropical varieties (1)
- Tropische Basen (1)
- Trotter's product formula (1)
- Turkish immigrants (1)
- Typ-In-Algebra (1)
- Typology (1)
- Türkisch (1)
- Uniform regularity (1)
- Uniform resource locators (1)
- Unterstützung (1)
- Valuation on functions (1)
- Varianz (1)
- Vertexoperator (1)
- Verzweigende Teilchensysteme (1)
- Virasoro-Algebra (1)
- Wahrscheinlichkeit (1)
- Wahrscheinlichkeitsverteilung (1)
- Wiener Index (1)
- Wiener index (1)
- Wiener-Index (1)
- Yule process (1)
- Yule-process (1)
- Zinsstrukturmodelle (1)
- Zinsänderungsrisiko (1)
- Zolotarev metric (1)
- Zolotarev-Metrik (1)
- Zopfgruppe ; Lineare Darstellung ; Kettengruppe ; Homologiegruppe ; Automorphismengruppe ; Kettenkomplex (1)
- Zufall (1)
- Zufallsgraph (1)
- Zufällige Umgebung (1)
- Zustandsabhängige Verzweigungsrate (1)
- Zweiphasen-Biogasreaktor (1)
- Zweistufen-Biogasreaktor (1)
- abelian differentials (1)
- abstract potential theory (1)
- algebraic curves (1)
- algebraic values (1)
- alpha-stable branching (1)
- ampleness (1)
- analysis of algorithms (1)
- anti-Zeno effect (1)
- argumentation (1)
- arithmetic ball quotients (1)
- arithmetic group (1)
- assignment problem (1)
- augmented and restricted base loci (1)
- autocorrelograms (1)
- bid-ask spread (1)
- bordism theory (1)
- branching processes (1)
- branching random walk in random medium (1)
- buildings (1)
- cancer cell dormancy (1)
- canonical divisors (1)
- catastrophe modeling (1)
- central limit theorem (1)
- chosen ciphertext attack (1)
- clique problem (1)
- colorabdity (1)
- colored graphs (1)
- compact Riemann surfaces (1)
- complex multiplication (1)
- composition (1)
- computational geometry (1)
- concurrent composition (1)
- condensing (1)
- confirmatory factory analysis (1)
- consensus (1)
- contact process (1)
- continued fraction algorithm (1)
- controlled homotopy (1)
- convexity (1)
- convolution quadrature (1)
- cooperative systems (1)
- cross correlation (1)
- cryptography (1)
- cycle structure of permutations (1)
- dead ends (1)
- degenerate semigroup (1)
- delay equation (1)
- depth of a nod (1)
- dessins d’enfants (1)
- difference sets (1)
- digital search tree (1)
- digital tools (1)
- discrete dynamical system (1)
- discrete logarithm (1)
- discrete logarithm (DL) (1)
- diskrete Mathematik (1)
- dose-resoponse modelling (1)
- doubly stochastic point process (1)
- eigenvalue (1)
- elastodynamic wave equation (1)
- emergence (1)
- endliche metrische Räume (1)
- error bounds (1)
- exponentiation (1)
- external branch (1)
- face inversion (1)
- face perception (1)
- fake projective planes (1)
- families of hash functions (1)
- feedback effect (1)
- finite resolution (1)
- finiteness-properties (1)
- flat surfaces (1)
- floating norms (1)
- floating point arithmetic (1)
- floating point errors (1)
- foliated Schwarz symmetry (1)
- forming a group (1)
- fractional Brownian motion (1)
- fractions of exponentiation (1)
- frühkindliche Erziehung (1)
- fuchsian group (1)
- functional limit theorem (1)
- functional limit theorems (1)
- fächerübergreifendes Lernen (1)
- generic algorithm (1)
- generic algorithms (1)
- generic complexity (1)
- generic group model (1)
- geometry (1)
- graph coloring (1)
- graph isomorphism (1)
- h-transform (1)
- hard bit (1)
- hardcore subsets (1)
- harmonic function (1)
- heavy tails (1)
- hidden Markov model (1)
- hierarchical mean-field limit (1)
- highly regular nearby points (1)
- hyperbolische Geometrie (1)
- hypergeometric functions (1)
- hypervariable region (1)
- höhere Momente (1)
- incremental schemes (1)
- indefinite inner product space (1)
- individual-based models (1)
- inner product (1)
- integer relation (1)
- integer vector (1)
- interacting particle Systems (1)
- interdisziplinäre Lehre (1)
- internal diffusion limited aggregation (1)
- internal path length (1)
- inverse coefficient problem, (1)
- iterated subsegments (1)
- key comparisons (1)
- kinetic fingerprint (1)
- knapsack cryptosystems (1)
- kontrollierte Homotopie (1)
- large deviations (1)
- large trader (1)
- latent variance (1)
- lattice basis reduction (1)
- lattices (1)
- leapfrog (1)
- length defect (1)
- limit order markets (1)
- local LLL-reduction (1)
- local LLLreduction (1)
- local coordinates (1)
- local randomness (1)
- local time (1)
- local time drift (1)
- logarithmic geometry (1)
- logical networks (1)
- lookdown construction (1)
- lower bounds (1)
- manifold and geodesic (1)
- market making (1)
- mathematical modeling (1)
- mathematical modelling (1)
- mathematics (1)
- measurement (1)
- mehrdimensionale Ausreißererkennung (1)
- message-passing algorithm (1)
- modelling (1)
- modular automorphism group (1)
- modular group (1)
- moduli spaces (1)
- multi-agents system (1)
- multi-drug treatment (1)
- multiharmony (1)
- multilevel branching (1)
- music (1)
- mutation parameter estimation (1)
- neuronal code (1)
- neuronaler Kode (1)
- nichtlineare stochastische Integration (1)
- non-archimedean geometry (1)
- non-autonomous dynamical systems (1)
- non-malleability (1)
- noncommutative ring spectra (1)
- nondetermmistlc Turing machines (1)
- nonlinear stochastic integration (1)
- numerical experiments (1)
- observable Funktion (1)
- one-more decryption attack (1)
- one-way function (1)
- one-way functions (1)
- operator algebra (1)
- optimal transport (1)
- pair HMM (1)
- parameter dependent semimartingales (1)
- parameterabhängige Semimartingale (1)
- partial match queries (1)
- path properties (1)
- perceptual closure (1)
- permutation groups (1)
- phage (1)
- phage therapy (1)
- phase coding (1)
- phase transitions (1)
- platonischer Körper (1)
- poisson process (1)
- polynomial random number generator (1)
- population dynamics (1)
- portfolio optimization (1)
- positivity of line bundles (1)
- preferential attachment (1)
- preferential attachment models (1)
- probabilistic analysis of algorithms (1)
- probability (1)
- probability metric (1)
- professional development (1)
- profile likelihood (1)
- projections (1)
- projective planes (1)
- q-binomial theorem (1)
- quantum field theory (1)
- quasi-automorphisms (1)
- quaternion algebra (1)
- quincunx (1)
- random assignment problem (1)
- random environment (1)
- random function generator (1)
- random graphs (1)
- random measures (1)
- random media (1)
- random metric (1)
- random move (1)
- random number generator (1)
- random oracle model (1)
- random partition (1)
- random recursive tree (1)
- random rekursiv tree (1)
- random trees (1)
- random walks (1)
- raum-zeitliche Muster (1)
- reactant-catalyst systems (1)
- recursive distributional equation (1)
- reguläre Parkettierung (1)
- resistance (1)
- resistance mutation (1)
- reversibility (1)
- riemann surfaces (1)
- risk assessment (1)
- risk theory (1)
- rotating plane method (1)
- rough paths theory (1)
- satlsfiablhty (1)
- scaling (1)
- search operation (1)
- searchtrees (1)
- secure bit (1)
- security analysis of protocols (1)
- security of data (1)
- self-organizing groups (1)
- self-organizing groups; population dynamics; collective intelligence; forming groups; metric on finite sets (1)
- semidefinite optimization (1)
- sequence alignment (1)
- set-valued pullback attractors (1)
- shadow price (1)
- short integer relation (1)
- shortest lattice vector (1)
- signature size (1)
- signed ElGamal encryption (1)
- simultaneous diophantine approximations (1)
- simultaneous security of bits (1)
- single block replacement (1)
- small worlds (1)
- spatio-temporal patterns (1)
- split tree (1)
- statistic analysis (1)
- statistical alignment (1)
- statistische Analyse (1)
- statistischer Test (1)
- stoch. Analyse von Algorithmen (1)
- stochastic filtering (1)
- stochastic modeling (1)
- stochastic population dynamics (1)
- stochastische Prozesse (1)
- strong transience (1)
- subgroup growth (1)
- subset sum problems (1)
- substitution attacks (1)
- sum of squared factor loadings (1)
- switching systems (1)
- synergistic interaction (1)
- therapy evasion (1)
- topological entropy (1)
- trading strategies (1)
- transcendence (1)
- transversal learning (1)
- treatment protocol design (1)
- treatment success (1)
- triangle group (1)
- triangle groups (1)
- tropical geometry (1)
- tropical universal Jacobian (1)
- tropicalization (1)
- universal compactified Jacobian (1)
- urn model (1)
- von Neumann algebra (1)
- von Neumann algebras (1)
- von Neumann-Algebra (1)
- weak convergence (1)
- zufälliger Algorithmus (1)
- zufälliger rekursiver Baum (1)
- zufälliges Assignment Problem (1)
- Λ-coalescent (1)
- σ-field (1)
Institute
- Mathematik (372) (remove)
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 study the following problem: given x element Rn either find a short integer relation m element Zn, so that =0 holds for the inner product <.,.>, or prove that no short integer relation exists for x. Hastad, Just Lagarias and Schnorr (1989) give a polynomial time algorithm for the problem. We present a stable variation of the HJLS--algorithm that preserves lower bounds on lambda(x) for infinitesimal changes of x. Given x \in {\RR}^n and \alpha \in \NN this algorithm finds a nearby point x' and a short integer relation m for x'. The nearby point x' is 'good' in the sense that no very short relation exists for points \bar{x} within half the x'--distance from x. On the other hand if x'=x then m is, up to a factor 2^{n/2}, a shortest integer relation for \mbox{x.} Our algorithm uses, for arbitrary real input x, at most \mbox{O(n^4(n+\log \alpha))} many arithmetical operations on real numbers. If x is rational the algorithm operates on integers having at most \mbox{O(n^5+n^3 (\log \alpha)^2 + \log (\|q x\|^2))} many bits where q is the common denominator for x.
Black box cryptanalysis applies to hash algorithms consisting of many small boxes, connected by a known graph structure, so that the boxes can be evaluated forward and backwards by given oracles. We study attacks that work for any choice of the black boxes, i.e. we scrutinize the given graph structure. For example we analyze the graph of the fast Fourier transform (FFT). We present optimal black box inversions of FFT-compression functions and black box constructions of collisions. This determines the minimal depth of FFT-compression networks for collision-resistant hashing. We propose the concept of multipermutation, which is a pair of orthogonal latin squares, as a new cryptographic primitive that generalizes the boxes of the FFT. Our examples of multipermutations are based on the operations circular rotation, bitwise xor, addition and multiplication.
Parallel FFT-hashing
(1994)
We propose two families of scalable hash functions for collision resistant hashing that are highly parallel and based on the generalized fast Fourier transform (FFT). FFT hashing is based on multipermutations. This is a basic cryptographic primitive for perfect generation of diffusion and confusion which generalizes the boxes of the classic FFT. The slower FFT hash functions iterate a compression function. For the faster FFT hash functions all rounds are alike with the same number of message words entering each round.
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.
We introduce novel security proofs that use combinatorial counting arguments rather than reductions to the discrete logarithm or to the Diffie-Hellman problem. Our security results are sharp and clean with no polynomial reduction times involved. We consider a combination of the random oracle model and the generic model. This corresponds to assuming an ideal hash function H given by an oracle and an ideal group of prime order q, where the binary encoding of the group elements is useless for cryptographic attacks In this model, we first show that Schnorr signatures are secure against the one-more signature forgery : A generic adversary performing t generic steps including l sequential interactions with the signer cannot produce l+1 signatures with a better probability than (t 2)/q. We also characterize the different power of sequential and of parallel attacks. Secondly, we prove signed ElGamal encryption is secure against the adaptive chosen ciphertext attack, in which an attacker can arbitrarily use a decryption oracle except for the challenge ciphertext. Moreover, signed ElGamal encryption is secure against the one-more decryption attack: A generic adversary performing t generic steps including l interactions with the decryption oracle cannot distinguish the plaintexts of l + 1 ciphertexts from random strings with a probability exceeding (t 2)/q.