Bevisbar säkerhet och svåra predikat

Abstrakt:

Seminariet kommer handla om svåra predikat. Givet en funktion f och ett predikat P så är P svårt om det inte finns en algoritm som kan gissa värdet P(x), givet värdet av f(x), bättre än en slumpgissning. Vi kommer att gå igenom en känd konstruktion av ett svårt predikat som baseras på en godtycklig enkelriktad funktion (Goldreich och Levin, STOC '89).

Konceptet svåra predikat kommer bland annat till användning när man ska bevisa säkerheten hos en pseudoslumptalsgeneratorer (PSG), ett viktigt kryptografiskt primitiv. Utdata från en PSG ska inte kunna skiljas från slump av motståndare som är begränsade av en viss tidsåtgång. Bevisgången är att reducera problemet att förutsäga värdet av ett svårt predikat till problemet att "knäcka" PSG:n. Här är effektiviteten hos reduktionen viktig eftersom den relaterar direkt till hur kraftfulla motståndare beviset fungerar på. Vi kommer även att ta upp en effektivare reduktion för specifika, men vanligt förekommande, användningsområden för PSG:er (Hast, EUROCRYPT 2003).