BEGIN:VCALENDAR
CALSCALE:GREGORIAN
VERSION:2.0
X-WR-TIMEZONE:Europe/Paris
METHOD:PUBLISH
PRODID:-//LIP6//www.lip6.fr//FR
X-WR-CALNAME;VALUE=TEXT:Séminaire LIP6
X-LIC-LOCATION:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
DTSTART:19810329T020000
TZNAME:GMT+02:00
TZOFFSETTO:+0200
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
DTSTART:19961027T030000
TZNAME:GMT+01:00
TZOFFSETTO:+0100
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
SUMMARY:Attacks on Pseudo-Random Number Generators Hiding a Linear Structu
re
ORGANIZER;CN=Damien Vergnaud:MAILTO:damien.vergnaud@lip6.fr
ATTENDEE;CN=Florette Martinez;CUTYPE=INDIVIDUAL;PARTSTAT=ACCEPTED
DESCRIPTION:We introduce lattice-based practical seed-recovery attacks aga
inst two efficient number-theoretic pseudo-random number generators: the f
ast knapsack generator and a family of combined multiple recursive generat
ors. The fast knapsack generator was introduced in 2009 by Von Zur Gathen
and Shparlinski. It generates pseudo-random numbers very efficiently with
strong mathematical guarantees on their statistical properties but its res
istance to cryptanalysis was left open since 2009. The given attacks are s
urprisingly efficient when the truncated bits do not represent a too large
proportion of the internal states. Their complexities do not strongly inc
rease with the size of parameters\, only with the proportion of discarded
bits. A multiple recursive generator is a pseudo-random number generator b
ased on a constant-recursive sequence. A combined multiple recursive gener
ator is a pseudo-random number generator based on combining two or more mu
ltiple recursive generators. L’Écuyer presented the general constructio
n in 1996 and a popular instantiation deemed MRG32k3a in 1999. We use alge
braic relations of both pseudo-random generators with underlying algebraic
generators to show that they are cryptographically insecure. We provide a
theoretical analysis as well as efficient implementations.
https://epri
nt.iacr.org/2021/1204
DTSTAMP:20211019T230808Z
DTSTART;TZID=Europe/Paris:20211014T140000
DURATION:PT2H
URL;VALUE=URI:https://www.lip6.fr/liens/organise-fiche.php?ident=O1078
UID:LIP6/SEM/O1078
LOCATION:Salle 309\, couloir 24-25\, 4 place Jussieu - 75005 Paris
GEO:48.846954;2.354357
END:VEVENT
END:VCALENDAR