BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Urs Wagner

Urs Wagner contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Cryptography and Securitymath.COmath.CAmath.GM

Trust snapshot

Quick read

Trust 19 - UnverifiedVerification L1Unclaimed author
5works
0followers
4topics
3close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

5 published item(s)

preprint2013arXiv

PotLLL: A Polynomial Time Version of LLL With Deep Insertions

Lattice reduction algorithms have numerous applications in number theory, algebra, as well as in cryptanalysis. The most famous algorithm for lattice reduction is the LLL algorithm. In polynomial time it computes a reduced basis with provable output quality. One early improvement of the LLL algorithm was LLL with deep insertions (DeepLLL). The output of this version of LLL has higher quality in practice but the running time seems to explode. Weaker variants of DeepLLL, where the insertions are restricted to blocks, behave nicely in practice concerning the running time. However no proof of polynomial running time is known. In this paper PotLLL, a new variant of DeepLLL with provably polynomial running time, is presented. We compare the practical behavior of the new algorithm to classical LLL, BKZ as well as blockwise variants of DeepLLL regarding both the output quality and running time.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Polynomial Time Version of LLL With Deep Insertions

Lattice reduction algorithms have numerous applications in number theory, algebra, as well as in cryptanalysis. The most famous algorithm for lattice reduction is the LLL algorithm. In polynomial time it computes a reduced basis with provable output quality. One early improvement of the LLL algorithm was LLL with deep insertions (DeepLLL). The output of this version of LLL has higher quality in practice but the running time seems to explode. Weaker variants of DeepLLL, where the insertions are restricted to blocks, behave nicely in practice concerning the running time. However no proof of polynomial running time is known. In this paper a new variant of DeepLLL with provably polynomial running time is presented. We compare the practical behavior of the new algorithm to classical LLL, BKZ as well as blockwise variants of DeepLLL regarding both the output quality and running time.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Improvements in closest point search based on dual HKZ-bases

In this paper we review the technique to solve the CVP based on dual HKZ-bases by J. Bloemer. The technique is based on the transference theorems given by Banaszczyk which imply some necessary conditions on the coefficients of the closest vectors with respect to a basis whose dual is HKZ reduced. Recursively, starting with the last coefficient, intervals of length i can be derived for the i-th coefficient of any closest vector. This leads to n! candidates for closest vectors. In this paper we refine the necessary conditions derived from the transference theorems, giving an exponential reduction of the number of candidates. The improvement is due to the fact that the lengths of the intervals are not independent. In the original algorithm the candidates for a coefficient pair (a_i,a_{i+1}) correspond to the integer points in a rectangle of volume i(i+1). In our analysis we show that the candidates for (a_i,a_{i+1}) in fact lie in an ellipse with transverse and conjugate diameter i+1, respectively i. This reduces the overall number of points to be enumerated by an exponential factor of about 0.886^n. We further show how a choice of the coefficients (a_n,...,a_{i+1}) influences the interval from which a_i can be chosen. Numerical computations show that these considerations allow to bound the number of points to be enumerated by n^{0.75 n} for 10 <= n <= 2000. Under the assumption that the Gaussian heuristic for the length of the shortest nonzero vector in a lattice is tight, this number can even be bounded by 2^{-2n} n^{n/2}.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Solving the LPN problem in cube-root time

In this paper it is shown that given a sufficient number of (noisy) random binary linear equations, the Learning from Parity with Noise (LPN) problem can be solved in essentially cube root time in the number of unknowns. The techniques used to recover the solution are known from fast correlation attacks on stream ciphers. As in fast correlation attacks, the performance of the algorithm depends on the number of equations given. It is shown that if this number exceeds a certain bound, and the bias of the noisy equations is polynomial in number of unknowns, the running time of the algorithm is reduced to almost cube root time compared to the brute force checking of all possible solutions. The mentioned bound is explicitly given and it is further shown that when this bound is exceeded, the complexity of the approach can even be further reduced.

0 citations0 reviewsNo code linkedOpen access