• Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle Off
Reading...
Front

Card Range To Study

through

image

Play button

image

Play button

image

Progress

1/10

Click to flip

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