Abstrakt. I detta dokument beaktas den beräkningsmässiga komplexiteten hos den diskreta logaritmen och relaterade problem i samband med \generiska algoritmer" d.v.s. algoritmer som inte utnyttjar några speciella egenskaper hos kodningen av gruppelement, förutom egenskapen att varje gruppelement kodas som en unik binär sträng. Nedre gränser på komplexiteten av dessa problem bevisas som matchar de kända övre gränserna: alla generiska algoritmer måste utföra (p 1=2 ) gruppoperationer, där p är den största prime dividerar ordningen i gruppen. Dessutom presenteras en ny metod för att korrigera en felaktig Di-E-Hellman oracle.
I REF visas DH-problemets hårdhet (och därmed DL-problemet) i den generiska modellen, dvs. för algoritmer för allmänna ändamål som inte utnyttjar någon särskild egenskap hos representationen av gruppelementen.
Lower Bounds for Discrete Logarithms and Related Problems
{'venue': 'EUROCRYPT', 'journal': None, 'mag_field_of_study': ['Computer Science']}