Building public key system One-way function: fo is one way if For any x, y=f(x) is easy to compute For any (or almost all)y, it is hard to find an x such that f(x)=y Trapdoor one-way function fO given s and y, it is easy to compute an x such that f(x)=yBuilding Public Key System • One-way function: f() is one way if – For any x, y = f(x) is easy to compute – For any (or almost all) y, it is hard to find an x such that f(x) = y • Trapdoor one-way function fs () – given s and y, it is easy to compute an x such that fs (x) = y