crypto primitives

It’s been a while since I studied cryptography. I think it’d be nice to try to remember all the primitives and the ideas proofs that relate them.

todo

Here’s the primitives that’d be on my list to remember

• Pseudorandom Generator (PRG):

  • input
  • output
    • although we can do length extension to get arbitrary polynomial larger output
  • must satisfy
    • computationally indistinguishable from uniform distribution
  • N has a post on how to get PRGs from OWFs. His summary:

    • Next-Bit Unpredictability Lemma (for a string to look random, its enough that you can’t predict any bit from the preceding substring)
    • Goldreich-Levin Theorem (hashing one-way functions with random matrices lets you pull out computationally unpredictable bits)
    • Leftover Hash Lemma (hashing with random matrices makes high-entropy distributions look uniform)

  • I think maybe if you assume OWP instead of OWF you just need the theorem that for a OWF, the dot product of the input with a random vector is a hardcore predicate
    • i.e., given can’t guess with good pr.

• Pseudorandom Function (PRF):

  • Input key .
  • Output: function
  • should be computationally indistinguishable from a truly random function.

• how to do this:

  • tree of PRGs
  • the key indexes into the tree

• Message Authentication Code (MAC):
  A MAC is a symmetric key algorithm used to verify the integrity and authenticity of a message. It takes as input a secret key and a message and outputs a tag. The receiver, with the same key, can verify that the message was not tampered with and was generated by someone knowing the key.

• Digital Signature Scheme:
  A digital signature scheme provides a method for signing a message such that the signature is verifiable by others. It uses a pair of cryptographic keys: a private signing key and a public verification key. The signer uses the private key to generate a signature, and anyone with the public key can verify the validity of the signature.

• Collision Resistant Hash Function:
  A hash function is collision resistant if it is computationally infeasible to find two distinct inputs that hash to the same output. Even though hash functions map inputs to fixed-size outputs, finding two inputs that collide should be very difficult.

• Indistinguishability Obfuscation (iO):
  An indistinguishability obfuscator transforms a program into an obfuscated version that is computationally indistinguishable from the obfuscation of any other equivalent program (i.e., a program that has the same functionality). The obfuscated program should not reveal any more information than what can be inferred from the input-output behavior of the program itself.

• Public Key Encryption (PKE):
  Public key encryption is an asymmetric encryption method where a user has two keys: a public key for encryption and a private key for decryption. Anyone can use the public key to encrypt a message, but only the holder of the corresponding private key can decrypt it. This allows secure communication between parties without the need for shared secret keys.

• FHE