Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
10 Cards in this Set
- Front
- Back
- 3rd side (hint)
Application of boolean operators |
Cryptography: Encoding and decoding messages
|
|
|
Base 2 digital computing uses |
I/O logic in hardware Boolean values of operators in higher programming languages e.g. true/false |
|
|
Propositional logic |
The theory of boolean expressions |
|
|
Application of satisfiability |
Security of cryptographic host: Recap: Hash function h() Input: arbitrary string s, with length n Output: a binary hashcode with k bits (fixed length) Usually expected: runtime faster than O(n^2) Cryptographic hash function: In addition to above: Hard to do the birthday attack Find s1, s2 with h (s1) = h (s2) (hash collision)
Similarly it is hard for given x to find s with h(s) = x (Hash inversion) |
|
|
Hardness of cryptographic hash h() |
We have no proof for any h() that attacking h() is hard We would like at least relative proof of hardness e.g. if SAT is hard, so is attacking h() h() is often too specialised to solve general SAT For many h() used in practice, hardness is debated |
|
|
Proof of hardness test of satisfisbility |
hash with polynomial O(n^m) number of calls to a SAT subroutine (and polynomial runtime for processing the results) Give algorithm that attacks cryptographic hash with polynomial O(n^m) number of calls to a SAT subroutine (and polynomial runtime for processing the results) If SAT can be solved in O(n^k) time then h() can be attacked in O(n^(k+m)) |
|
|
Implementation of hash function |
Cryptographic hash function on input of length 2k with output of length k and runtime O(k^2) can be implemented in a feedback free NAND circuit of size O(k^4) |
|
|
Circuit SAT |
Given a circuit, and a known output, find the input that gives the output |
|
|
Proof of work protocol |
E.g. Used in bitcoin mining Uses Partial hash inversion Find s so that h(s) = x starts with n zeros |
|
|
Summary |
|
|