Achtung:

Sie haben Javascript deaktiviert!
Sie haben versucht eine Funktion zu nutzen, die nur mit Javascript möglich ist. Um sämtliche Funktionalitäten unserer Internetseite zu nutzen, aktivieren Sie bitte Javascript in Ihrem Browser.

AG Codes and Kryptographie Bildinformationen anzeigen

AG Codes and Kryptographie

Publikationen


Liste im Research Information System öffnen

2018

Cloud Architectures for Searchable Encryption

J. Blömer, N. Löken, in: Proceedings of the 13th International Conference on Availability, Reliability and Security - ARES '18, ACM Press, 2018


Complexity of single-swap heuristics for metric facility location and related problems

S. Brauer, Theoretical Computer Science (2018)

DOI

Delegatable Attribute-based Anonymous Credentials from Dynamically Malleable Signatures

J. Blömer, J. Bobolz, in: ACNS 2018 Applied Cryptography & Network security, 2018

Download
Abstract

In this paper, we introduce the notion of delegatable attribute-based anonymous credentials (DAAC). Such systems offer fine-grained anonymous access control and they give the credential holder the ability to issue more restricted credentials to other users. In our model, credentials are parameterized with attributes that (1) express what the credential holder himself has been certified and (2) define which attributes he may issue to others. Furthermore, we present a practical construction of DAAC. For this construction, we deviate from the usual approach of embedding a certificate chain in the credential. Instead, we introduce a novel approach for which we identify a new primitive we call dynamically malleable signatures (DMS) as the main ingredient. This primitive may be of independent interest. We also give a first instantiation of DMS with efficient protocols.


Enhanced Security of Attribute-Based Signatures

J. Blömer, F. Eidens, J. Juhnke, in: The International Conference on Cryptology And Network Security (CANS), 2018


Fully-Featured Anonymous Credentials with Reputation System

K. Bemmann, J. Blömer, J. Bobolz, H. Bröcher, D. Diemert, F. Eidens, L. Eilers, J. Haltermann, J. Juhnke, B. Otour, L. Porzenheim, S. Pukrop, E. Schilling, M. Schlichtig, M. Stienemeier, in: Proceedings of the 13th International Conference on Availability, Reliability and Security - ARES '18, ACM Press, 2018


Practical, Anonymous, and Publicly Linkable Universally-Composable Reputation Systems

J. Blömer, F. Eidens, J. Juhnke, in: Topics in Cryptology - {CT-RSA} 2018 - The Cryptographers' Track at the {RSA} Conference 2018, Proceedings, Springer International Publishing, 2018, pp. 470-490


Voronoi Cells of Lattices with Respect to Arbitrary Norms

J. Blömer, K. Kohn, SIAM Journal on Applied Algebra and Geometry. (2018), pp. 314-338

DOI

2017

Attribute-Based Encryption as a Service for Access Control in Large-Scale Organizations

J. Blömer, P. Günther, V. Krummel, N. Löken, in: Foundations and Practice of Security, Springer International Publishing, 2017, pp. 3-17

DOI

CCA-Security for Predicate Encryption Schemes

G. Liske, Universität Paderborn, 2017


Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems

S. Brauer, in: Lecture Notes in Computer Science, Springer International Publishing, 2017, pp. 116-127

DOI
Abstract

Metric facility location and K-means are well-known problems of combinatorial optimization. Both admit a fairly simple heuristic called single-swap, which adds, drops or swaps open facilities until it reaches a local optimum. For both problems, it is known that this algorithm produces a solution that is at most a constant factor worse than the respective global optimum. In this paper, we show that single-swap applied to the weighted metric uncapacitated facility location and weighted discrete K-means problem is tightly PLS-complete and hence has exponential worst-case running time.


Searchable Encryption with Access Control

N. Löken, in: Proceedings of the 12th International Conference on Availability, Reliability and Security - ARES '17, ACM Press, 2017



Subtleties in Security Definitions for Predicate Encryption with Public Index

J. Blömer, G. Liske, in: Proceedings of the International Conference of Mathematical Aspects of Computer and Information Sciences (MACIS), Springer International Publishing, 2017, pp. 438-453


2016

A Theoretical Analysis of the Fuzzy K-Means Problem

J. Blömer, S. Brauer, K. Bujna, in: 2016 IEEE 16th International Conference on Data Mining (ICDM), IEEE, 2016, pp. 805-810

DOI
Abstract

One of the most popular fuzzy clustering techniques is the fuzzy K-means algorithm (also known as fuzzy-c-means or FCM algorithm). In contrast to the K-means and K-median problem, the underlying fuzzy K-means problem has not been studied from a theoretical point of view. In particular, there are no algorithms with approximation guarantees similar to the famous K-means++ algorithm known for the fuzzy K-means problem. This work initiates the study of the fuzzy K-means problem from an algorithmic and complexity theoretic perspective. We show that optimal solutions for the fuzzy K-means problem cannot, in general, be expressed by radicals over the input points. Surprisingly, this already holds for simple inputs in one-dimensional space. Hence, one cannot expect to compute optimal solutions exactly. We give the first (1+eps)-approximation algorithms for the fuzzy K-means problem. First, we present a deterministic approximation algorithm whose runtime is polynomial in N and linear in the dimension D of the input set, given that K is constant, i.e. a polynomial time approximation scheme (PTAS) for fixed K. We achieve this result by showing that for each soft clustering there exists a hard clustering with similar properties. Second, by using techniques known from coreset constructions for the K-means problem, we develop a deterministic approximation algorithm that runs in time almost linear in N but exponential in the dimension D. We complement these results with a randomized algorithm which imposes some natural restrictions on the sought solution and whose runtime is comparable to some of the most efficient approximation algorithms for K-means, i.e. linear in the number of points and the dimension, but exponential in the number of clusters.


Adaptive Seeding for Gaussian Mixture Models

J. Blömer, K. Bujna, in: Advances in Knowledge Discovery and Data Mining, Springer International Publishing, 2016, pp. 296-308

DOI

Construction of Fully CCA-Secure Predicate Encryptions from Pair Encoding Schemes

J. Blömer, G. Liske, in: Proceedings of the CT-RSA 2016, 2016, pp. 431-447

DOI
Abstract

This paper presents a new framework for constructing fully CCA-secure predicate encryption schemes from pair encoding schemes. Our construction is the first in the context of predicate encryption which uses the technique of well-formedness proofs known from public key encryption. The resulting constructions are simpler and more efficient compared to the schemes achieved using known generic transformations from CPA-secure to CCA-secure schemes. The reduction costs of our framework are comparable to the reduction costs of the underlying CPA-secure framework. We achieve this last result by applying the dual system encryption methodology in a novel way.


Effizienz und Sicherheit paarungsbasierter Kryptographie

J. Blömer, P. Günther, Tagungsband des 26. Fraunhofer SIT Smartcard-Workshops, 2016


Hard-Clustering with Gaussian Mixture Models

J. Blömer, S. Brauer, K. Bujna, 2016


Implementing Cryptographic Pairings on Accumulator Based Smart Card Architectures

P. Günther, V. Krummel, in: Mathematical Aspects of Computer and Information Sciences, Springer International Publishing, 2016, pp. 151-165

DOI

Physical attacks on pairing-based cryptography

P. Günther, Universität Paderborn, 2016


Singular Curve Point Decompression Attack

J. Blömer, P. Günther, in: 2015 Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC), IEEE, 2016

DOI

Theoretical Analysis of the k-Means Algorithm – A Survey

J. Blömer, C. Lammersen, M. Schmidt, C. Sohler, in: Algorithm Engineering, Springer International Publishing, 2016, pp. 81-116

DOI

2015

Anonymous and Publicly Linkable Reputation Systems

J. Blömer, J. Juhnke, C. Kolb, in: Proceedings of the 18th International Conference on Financial Cryptography and Data Security (FC), 2015, pp. 478--488

DOI Download
Abstract

Reputation systems are used to compute and publish reputation scores for services or products. We consider reputation systems where users are allowed to rate products that they purchased previously. To obtain trustworthy reputations, they are allowed to rate these products only once. As long as users rate products once, they stay anonymous. Everybody is able to detect users deviating from the rate-products-only-once policy and the anonymity of such dishonest users can be revoked by a system manager. In this paper we present formal models for such reputation systems and their security. Based on group signatures presented by Boneh, Boyen, and Shacham we design an efficient reputation system that meets all our requirements.


Short Group Signatures with Distributed Traceability

J. Blömer, J. Juhnke, N. Löken, in: Proceedings of the Sixth International Conference on Mathematical Aspects of Computer and Information Sciences (MACIS), 2015, pp. 166-180

DOI
Abstract

Group signatures, introduced by Chaum and van Heyst [15], are an important primitive in cryptography. In group signature schemes every group member can anonymously sign messages on behalf of the group. In case of disputes a dedicated opening manager is able to trace signatures - he can extract the identity of the producer of a given signature. A formal model for static group signatures schemes and their security is defined by Bellare, Micciancio, and Warinschi [4], the case of dynamic groups is considered by Bellare, Shi, and Zhang [5]. Both models define group signature schemes with a single opening manager. The main difference between these models is that the number of group members in static schemes is fixed, while in dynamic schemes group members can join the group over time.


Voronoi Cells of Lattices with Respect to Arbitrary Norms

J. Blömer, K. Kohn, Universität Paderborn, 2015

Download
Abstract

Motivated by the deterministic single exponential time algorithm of Micciancio and Voulgaris for solving the shortest and closest vector problem for the Euclidean norm, we study the geometry and complexity of Voronoi cells of lattices with respect to arbitrary norms.On the positive side, we show that for strictly convex and smooth norms the geometry of Voronoi cells of lattices in any dimension is similar to the Euclidean case, i.e., the Voronoi cells are defined by the so-called Voronoi-relevant vectors and the facets of a Voronoi cell are in one-to-one correspondence with these vectors. On the negative side, we show that combinatorially Voronoi cells for arbitrary strictly convex and smooth norms are much more complicated than in the Euclidean case.In particular, we construct a family of three-dimensional lattices whose number of Voronoi-relevant vectors with respect to the l_3-norm is unbounded.Since the algorithm of Micciancio and Voulgaris and its run time analysis crucially dependonthefactthatfortheEuclidean normthenumber of Voronoi-relevant vectors is single exponential in the lattice dimension, this indicates that the techniques of Micciancio and Voulgaris cannot be extended to achieve deterministic single exponential time algorithms for lattice problems with respect to arbitrary l_p-norms.


2014

A Practical Second-Order Fault Attack against a Real-World Pairing Implementation

J. Blömer, R. Gomes da Silva, P. Günther, J. Krämer, J. Seifert, in: Proceedings of Fault Tolerance and Diagnosis in Cryptography(FDTC), 2014, pp. 123--136

DOI
Abstract

Several fault attacks against pairing-based cryptography have been described theoretically in recent years. Interestingly, none of these have been practically evaluated. We accomplished this task and prove that fault attacks against pairing-based cryptography are indeed possible and are even practical — thus posing a serious threat. Moreover, we successfully conducted a second-order fault attack against an open source implementation of the eta pairing on an AVR XMEGA A1. We injected the first fault into the computation of the Miller Algorithm and applied the second fault to skip the final exponentiation completely. We introduce a low-cost setup that allowed us to generate multiple independent faults in one computation. The setup implements these faults by clock glitches which induce instruction skips. With this setup we conducted the first practical fault attack against a complete pairing computation.


A Theoretical and Experimental Comparison of the EM and SEM Algorithm

J. Blömer, K. Bujna, D. Kuntze, in: 2014 22nd International Conference on Pattern Recognition, IEEE, 2014

DOI

Analysis of Agglomerative Clustering

M.R. Ackermann, J. Blömer, D. Kuntze, C. Sohler, Algorithmica (2014)

DOI

Constructing CCA-secure predicate encapsulation schemes from CPA-secure schemes and universal one-way hash functions

J. Blömer, G. Liske, 2014

Abstract

We present a new transformation of chosen-plaintext secure predicate encryption schemes with public index into chosen-ciphertext secure schemes. Our construction requires only a universal one-way hash function and is selectively secure in the standard model. The transformation is not generic but can be applied to various existing schemes constructed from bilinear groups. Using common structural properties of these schemes we provide an efficient and simple transformation without overhead in form of one-time signatures or message authentication codes as required in the known generic transformations.

Download
Abstract

We present a new transformation of chosen-plaintext secure predicate encryption schemes with public index into chosen-ciphertext secure schemes. Our construction requires only a universal one-way hash function and is selectively secure in the standard model. The transformation is not generic but can be applied to various existing schemes constructed from bilinear groups. Using common structural properties of these schemes we provide an efficient and simple transformation without overhead in form of one-time signatures or message authentication codes as required in the known generic transformations.


Tampering attacks in pairing-based cryptography

J. Blömer, P. Günther, G. Liske, in: Proceedings of Fault Tolerance and Diagnosis in Cryptography(FDTC), 2014, pp. 1--7

DOI
Abstract

In the last decade pairings have become an important, and often indispensable, ingredient in the construction of identity-based and attribute-based cryptosystems, as well as group signatures and credential systems. Consequently, the applicability of timing, power, or fault attacks to implementations of pairings is an important research topic. We will review some of the known results in this area.


2013

An Approach for Determining Optimal Contrast in Visual Cryptography

J. Juhnke, H. Lefmann, V. Strehl, Fortschritt-Berichte VDI, 2013


Coresets and Approximate Clustering for Bregman Divergences

M.R. Ackermann, J. Blömer, in: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2013, pp. 1088-1097

DOI

Direct Chosen-Ciphertext Secure Attribute-Based Key Encapsulations without Random Oracles

J. Blömer, G. Liske, 2013

Abstract

We present a new technique to realize attribute-based encryption (ABE) schemes secure in the standard model against chosen-ciphertext attacks (CCA-secure). Our approach is to extend certain concrete chosen-plaintext secure (CPA-secure) ABE schemes to achieve more efficient constructions than the known generic constructions of CCA-secure ABE schemes. We restrict ourselves to the construction of attribute-based key encapsulation mechanisms (KEMs) and present two concrete CCA-secure schemes: a key-policy attribute-based KEM that is based on Goyal's key-policy ABE and a ciphertext-policy attribute-based KEM that is based on Waters' ciphertext-policy ABE. To achieve our goals, we use an appropriate hash function and need to extend the public parameters and the ciphertexts of the underlying CPA-secure encryption schemes only by a single group element. Moreover, we use the same hardness assumptions as the underlying CPA-secure encryption schemes.

Download
Abstract

We present a new technique to realize attribute-based encryption (ABE) schemes secure in the standard model against chosen-ciphertext attacks (CCA-secure). Our approach is to extend certain concrete chosen-plaintext secure (CPA-secure) ABE schemes to achieve more efficient constructions than the known generic constructions of CCA-secure ABE schemes. We restrict ourselves to the construction of attribute-based key encapsulation mechanisms (KEMs) and present two concrete CCA-secure schemes: a key-policy attribute-based KEM that is based on Goyal's key-policy ABE and a ciphertext-policy attribute-based KEM that is based on Waters' ciphertext-policy ABE. To achieve our goals, we use an appropriate hash function and need to extend the public parameters and the ciphertexts of the underlying CPA-secure encryption schemes only by a single group element. Moreover, we use the same hardness assumptions as the underlying CPA-secure encryption schemes.


Improved Side Channel Attacks on Pairing Based Cryptography

J. Blömer, P. Günther, G. Liske, in: Constructive Side-Channel Analysis and Secure Design, Springer Berlin Heidelberg, 2013, pp. 154-168

DOI


Securing Critical Unattended Systems with Identity Based Cryptography - A Case Study

J. Blömer, P. Günther, V. Krummel, in: Proceedings of the 5th International Conference on Mathematical Aspects of Computer and Information Sciences (MACIS), 2013, pp. 98-105

Abstract

Unattended systems are key ingredients of various critical infrastruc-tures like networks of self service terminals or automated teller machines.For cost and efficiency reasons they should mostly run autonomously.Unattended systems are attractive and lucrative targets for various kindsof attacks, including attacks on the integrity of their components and thecommunication between components. In this paper, we propose a gen-eral cryptographic framework to protect unattended systems. We alsodemonstrate that instantiating the framework with techniques from iden-tity based cryptography is particularly well-suited to efficiently secureunattended systems.


2012

StreamKM++: A clustering algorithm for data streams

M.R. Ackermann, M. Märtens, C. Raupach, K. Swierkot, C. Lammersen, C. Sohler, ACM, 2012

DOI

Turing und Kryptografie

J. Blömer, Informatik-Spektrum (2012)

DOI
Abstract

Ich beschreibe die deutsche Enigma-Verschlüsselungsmaschine und skizziere, wie sie von den Codebrechern von Bletchely Park um Alan Turing gebrochen wurde. Besonderes Augenmerk lege ich auf die Beiträge Alan Turings und die Bedeutung seiner Leistung für die Entwicklung moderner Kryptografie.


2011


Hardness and Non-Approximability of Bregman Clustering Problems.

M.R. Ackermann, J. Blömer, C. Scholz, 2011


How to Share a Secret

J. Blömer, in: Algorithms Unplugged, Springer Berlin Heidelberg, 2011, pp. 159-168

DOI

Solving the Closest Vector Problem with respect to Lp Norms

J. Blömer, S. Naewe, in: arXiv:1104.3720, 2011

Abstract

In this paper, we present a deterministic algorithm for the closest vector problem for all l_p-norms, 1 < p < \infty, and all polyhedral norms, especially for the l_1-norm and the l_{\infty}-norm. We achieve our results by introducing a new lattice problem, the lattice membership problem. We describe a deterministic algorithm for the lattice membership problem, which is a generalization of Lenstra's algorithm for integer programming. We also describe a polynomial time reduction from the closest vector problem to the lattice membership problem. This approach leads to a deterministic algorithm that solves the closest vector problem for all l_p-norms, 1 < p < \infty, in time p log_2 (r)^{O (1)} n^{(5/2+o(1))n} and for all polyhedral norms in time (s log_2 (r))^{O (1)} n^{(2+o(1))n}, where s is the number of constraints defining the polytope and r is an upper bound on the coefficients used to describe the convex body.

Abstract

In this paper, we present a deterministic algorithm for the closest vector problem for all l_p-norms, 1 < p < \infty, and all polyhedral norms, especially for the l_1-norm and the l_{\infty}-norm. We achieve our results by introducing a new lattice problem, the lattice membership problem. We describe a deterministic algorithm for the lattice membership problem, which is a generalization of Lenstra's algorithm for integer programming. We also describe a polynomial time reduction from the closest vector problem to the lattice membership problem. This approach leads to a deterministic algorithm that solves the closest vector problem for all l_p-norms, 1 < p < \infty, in time p log_2 (r)^{O (1)} n^{(5/2+o(1))n} and for all polyhedral norms in time (s log_2 (r))^{O (1)} n^{(2+o(1))n}, where s is the number of constraints defining the polytope and r is an upper bound on the coefficients used to describe the convex body.


2010

Bregman Clustering for Separable Instances

M.R. Ackermann, J. Blömer, in: SWAT 2010, Springer Berlin Heidelberg, 2010, pp. 212-223

DOI

Clustering for Metric and Nonmetric Distance Measures

M.R. Ackermann, J. Blömer, C. Sohler, ACM Trans. Algorithms (2010), pp. 59:1--59:26

DOI


Engineering self-coordinating software intensive systems

W. Schäfer, A. Trächtler, M. Birattari, J. Blömer, M. Dorigo, G. Engels, R. O'Grady, M. Platzner, F. Rammig, W. Reif, in: Proceedings of the FSE/SDP workshop on Future of software engineering research - FoSER '10, ACM Press, 2010

DOI

On the initialization of dynamic models for speech features

A. Krueger, V. Leutnant, R. Haeb-Umbach, M. Ackermann, J. Blömer, Proc. of ITG Fachtagung Sprachkommunikation. ITG, Bochum, Germany (2010)


2009

Algorithms for the Bregman k-Median Problem

M.R. Ackermann, Universität Paderborn, 2009


Sampling methods for shortest vectors, closest vectors and successive minima

J. Blömer, S. Naewe, Theoretical Computer Science (2009), pp. 1648 - 1665

DOI

Three-Valued Spotlight Abstractions

J. Schrieb, H. Wehrheim, D. Wonisch, in: FM 2009: Formal Methods, Springer Berlin Heidelberg, 2009, pp. 106-122

DOI

2008

Reliable Evidence of Data Integrity from an Untrusted Storage Service

C. Stern, P. Adelt, V. Krummel, M.R. Ackermann, in: Fourth International Conference on Networking and Services (icns 2008), IEEE, 2008

DOI

2007

A Probabilistic Zero-Test for Expressions Involving Roots of Rational Numbers

J. Blömer, in: Algorithms — ESA’ 98, Springer Berlin Heidelberg, 2007, pp. 151-162

DOI

Analysis of Countermeasures Against Access Driven Cache Attacks on AES

J. Blömer, V. Krummel, in: Selected Areas in Cryptography, Springer Berlin Heidelberg, 2007, pp. 96-109


Cryptanalysis of Unbalanced RSA with Small CRT-Exponent

A. May, in: Advances in Cryptology — CRYPTO 2002, Springer Berlin Heidelberg, 2007, pp. 242-256

DOI

Dimension Reduction Methods for Convolution Modular Lattices

A. May, J.H. Silverman, in: Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2007, pp. 110-125

DOI

Key Revocation with Interval Cover Families

J. Blömer, A. May, in: Selected Areas in Cryptography, Springer Berlin Heidelberg, 2007, pp. 325-341

DOI

Low Secret Exponent RSA Revisited

J. Blömer, A. May, in: Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2007, pp. 4-19

DOI


2006

Fault Based Collision Attacks on AES

J. Blömer, V. Krummel, in: Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2006, pp. 106-120

DOI

Randomness and Secrecy - A Brief Introduction

J. Blömer, Journal of Universal Computer Science (J.UCS) (2006), pp. 654--671

DOI
Abstract

We give a brief introduction to probabilistic encryptions. This serves as an example how randomness plays a pivotal role in cryptographic systems that satisfy advanced security concepts.


Sign Change Fault Attacks on Elliptic Curve Cryptosystems

J. Blömer, M. Otto, J. Seifert, in: Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2006, pp. 36-52

DOI

Wagner’s Attack on a Secure CRT-RSA Algorithm Reconsidered

J. Blömer, M. Otto, in: Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2006, pp. 13-23

DOI

2005

A Tool Kit for Finding Small Roots of Bivariate Polynomials over the Integers

J. Blömer, A. May, in: EUROCRYPT 2005, Springer Berlin Heidelberg, 2005, pp. 251-267

DOI

Fault Attacks and Countermeasures

M. Otto, Universität Paderborn, 2005


Partial Key Exposure Attacks on RSA up to Full Size Exponents

M. Ernst, E. Jochemsz, A. May, B. de Weger, in: EUROCRYPT 2005, Springer Berlin Heidelberg, 2005, pp. 371-386

DOI

2004

A Generalized Wiener Attack on RSA

J. Blömer, A. May, in: Public Key Cryptography – PKC 2004, Springer Berlin Heidelberg, 2004, pp. 1-13

DOI

A new CRT-RSA algorithm secure against bellcore attacks

J. Blömer, M. Otto, J. Seifert, in: Proceedings of the 10th ACM conference on Computer and communication security - CCS '03, ACM Press, 2004

DOI

Computing the RSA Secret Key Is Deterministic Polynomial Time Equivalent to Factoring

A. May, in: Advances in Cryptology – CRYPTO 2004, Springer Berlin Heidelberg, 2004, pp. 213-219

DOI

Provably Secure Masking of AES

J. Blömer, J. Guajardo, V. Krummel, in: Selected Areas in Cryptography, Springer Berlin Heidelberg, 2004, pp. 69-83

DOI

Secret Exponent Attacks on RSA-type Schemes with Moduli N=p^{r}q

A. May, in: Public Key Cryptography – PKC 2004, Springer Berlin Heidelberg, 2004, pp. 218-230

DOI

2003

Fault Based Cryptanalysis of the Advanced Encryption Standard (AES)

J. Blömer, J. Seifert, in: Financial Cryptography, Springer Berlin Heidelberg, 2003, pp. 162-181

DOI

New Partial Key Exposure Attacks on RSA

J. Blömer, A. May, in: Advances in Cryptology - CRYPTO 2003, Springer Berlin Heidelberg, 2003, pp. 27-43

DOI


2002

Priority encoding transmission

A. Albanese, J. Blömer, J. Edmonds, M. Luby, M. Sudan, in: Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press, 2002

DOI

Priority encoding transmission

A. Albanese, J. Blömer, J. Edmonds, M. Luby, M. Sudan, IEEE Transactions on Information Theory (2002), pp. 1737-1744

DOI

2000

Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices

J. Blömer, in: Automata, Languages and Programming, Springer Berlin Heidelberg, 2000, pp. 248-259

DOI

1999

On the complexity of computing short linearly independent vectors and short bases in a lattice

J. Blömer, J. Seifert, in: Proceedings of the thirty-first annual ACM symposium on Theory of computing - STOC '99, ACM Press, 1999

DOI

1998

A lower bound for a class of graph based loss resilient codes

J. Blömer, B. Trachsler, Technical report/Departement of Computer Science, ETH Zürich (1998)


1997

Denesting by bounded degree radicals

J. Blömer, in: Algorithms — ESA '97, Springer Berlin Heidelberg, 1997, pp. 53-63

DOI

The rank of sparse random matrices over finite fields

J. Blömer, R. Karp, E. Welzl, Random Structures \& Algorithms (1997), pp. 407-419

DOI

1995

An XOR-based erasure-resilient coding scheme

J. Blömer, M. Kalfane, R. Karp, M. Karpinski, M. Luby, D. Zuckerman, 1995


Approximate matching of polygonal shapes

H. Alt, B. Behrends, J. Blömer, Annals of Mathematics and Artificial Intelligence (1995)

Abstract

For two given simple polygonsP, Q, the problem is to determine a rigid motionI ofQ giving the best possible match betweenP andQ, i.e. minimizing the Hausdorff distance betweenP andI(Q). Faster algorithms as the one for the general problem are obtained for special cases, namely thatI is restricted to translations or even to translations only in one specified direction. It turns out that determining pseudo-optimal solutions, i.e. ones that differ from the optimum by just a constant factor, can be done much more efficiently than determining optimal solutions. In the most general case, the algorithm for the pseudo-optimal solution is based on the surprising fact that for the optimal possible match betweenP and an imageI(Q) ofQ, the distance between the centroids of the edges of the convex hulls ofP andI(Q) is a constant multiple of the Hausdorff distance betweenP andI(Q). It is also shown that the Hausdorff distance between two polygons can be determined in timeO(n logn), wheren is the total number of vertices.


1993

On Kummer theory and the number of roots of unity in radical extensions of Q

J. Blömer, Technical Report, Freie Universität Berlin, Fachbereich Mathematik und Informatik, 1993


1992

How to denest Ramanujan's nested radicals

J. Blömer, in: Proceedings., 33rd Annual Symposium on Foundations of Computer Science, IEEE, 1992

DOI

Resemblance and symmetries of geometric patterns

H. Alt, J. Blömer, in: Data structures and efficient algorithms, Springer Berlin Heidelberg, 1992, pp. 1-24

DOI

Simplifying Expressions Involving Radicals

J. Blömer, PhD thesis, Freie Universität Berlin, Fachbereich Mathematik und Informatik, 1992


1991

Approximate matching of polygonal shapes (extended abstract)

H. Alt, B. Behrends, J. Blömer, in: Proceedings of the seventh annual symposium on Computational geometry - SCG '91, ACM Press, 1991

DOI

Computing sums of radicals in polynomial time

J. Blömer, in: Proceedings 32nd Annual Symposium of Foundations of Computer Science, IEEE Comput. Soc. Press, 1991

DOI

1990

Approximation of convex polygons

H. Alt, J. Blömer, H. Wagener, in: Automata, Languages and Programming, Springer-Verlag, 1990, pp. 703-716

DOI

Liste im Research Information System öffnen

Die Universität der Informationsgesellschaft