Concept

Hidden subgroup problem

Related publications (14)

Approximate CVPp in time 2(0.802n)

Friedrich Eisenbrand, Moritz Andreas Venzin

We show that a constant factor approximation of the shortest and closest lattice vector problem in any l(p)-norm can be computed in time 2((0.802 + epsilon)n). This matches the currently fastest constant factor approximation algorithm for the shortest vect ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2022

New Results in Integer and Lattice Programming

Christoph Hunkenschröder

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

b \in \Z^m

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem o ...

EPFL2020

Programming Quantum Computers Using Design Automation

Mathias Soeken

Recent developments in quantum hardware indicate that systems featuring more than 50 physical qubits are within reach. At this scale, classical simulation will no longer be feasible and there is a possibility that such quantum devices may outperform even c ...

IEEE2018

Arithmetic and geometric structures in cryptography

Benjamin Pierre Charles Wesolowski

We explore a few algebraic and geometric structures, through certain questions posed by modern cryptography. We focus on the cases of discrete logarithms in finite fields of small characteristic, the structure of isogeny graphs of ordinary abelian varietie ...

EPFL2018

LPN in Cryptography

Sonia Mihaela Bogos

The security of public-key cryptography relies on well-studied hard problems, problems for which we do not have efficient algorithms. Factorization and discrete logarithm are the two most known and used hard problems. Unfortunately, they can be easily solv ...

EPFL2017

ON THE DISCRETE LOGARITHM PROBLEM IN FINITE FIELDS OF FIXED CHARACTERISTIC

Robert Granger, Thorsten Kleinjung, Jens Markus Zumbrägel

For~

q

a prime power, the discrete logarithm problem (DLP) in~

\F_{q}

consists in finding, for any

g \in \mathbb{F}_{q}^{\times}

and

h \in \langle g \rangle

, an integer~

x

such that

g^x = h

. We present an algorithm for computing discrete logarithm ...

2016

A Tale of Two Quasi-Polynomial Algorithms

Robert Granger

In 2013 the Discrete Logarithm Problem in finite fields of small characteristic enjoyed a rapid series of developments, starting with the heuristic polynomial-time relation generation method due to Gologlu, Granger, McGuire and Zumbragel, and culminating w ...

2015

Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling

Divesh Aggarwal

We give a randomized 2^{n+o(n)}-time and space algorithm for solving the Shortest Vector Problem (SVP) on n-dimensional Euclidean lattices. This improves on the previous fastest algorithm: the deterministic O(4^n)-time and O(2^n)-space algorithm of Miccian ...

ACM2015

On the discrete logarithm problem in finite fields of fixed characteristic

Robert Granger, Thorsten Kleinjung, Jens Markus Zumbrägel

For

q

a prime power, the discrete logarithm problem (DLP) in

\mathbb{F}_q

consists in finding, for any

g \in \mathbb{F}_{q}^{\times}

and

h \in \langle g \rangle

, an integer

x

such that

g^x = h

. We present an algorithm for computing discrete log ...

2015

A sieve algorithm based on overlattices

Anja Annemone Becker

In this paper, we present a heuristic algorithm for solving exact, as well as approximate, shortest vector and closest vector problems on lattices. The algorithm can be seen as a modified sieving algorithm for which the vectors of the intermediate sets lie ...

Cambridge Univ Press2014

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

On the discrete logarithm problem in finite fields of fixed characteristic

Robert Granger, Thorsten Kleinjung, Jens Markus Zumbrägel

For

q

a prime power, the discrete logarithm problem (DLP) in

\mathbb{F}_q

consists in finding, for any

g \in \mathbb{F}_{q}^{\times}

and

h \in \langle g \rangle

, an integer

x

such that

g^x = h

. We present an algorithm for computing discrete log ...

2015