The foundations of cryptography Cryptography is based on digital tasks that are easy to do forward,but hard to do backwards We are not 100%sure such tasks exist at all,but there are several viable candidates 953081 0 0 ×603749 575421700669 0
• Cryptography is based on digital tasks that are easy to do forward, but hard to do backwards • We are not 100% sure such tasks exist at all, but there are several viable candidates The foundations of cryptography 953081 × 603749 575421700669 0 1 1 1 0 0 0 1 1 0
Goldreich's function 0 1 0 input bits 0 output bits output=majority (input,inputz,inputs) Input and output are typically large,e.g.500 bits input, 10,000 bits output
Goldreich ’s function 1 0 1 1 1 0 0 1 0 1 1 0 input bits output bits Input and output are typically large, e.g. 500 bits input, 10,000 bits output very easy ? output = majority(input1 , input2 , input3 )