New ENcryption Primitives for Uncertain TImes

Encryption is one of the few things that you can rely on.

But existing encryption primitives aren't always helping:
DPI can block protocols (like Tor) --> encrytpion tools are easy to detection ---> format transforming encryption
Dropbox has access to your data --> encryption doesn't allow de-duplication to save space --> message-locked encryption
Passord-based encryption often get bad passwords ---> de-encrpty yield garbage for wrong key, but meaningful things for correct key, thus good for brute force attacking--> Honey encryption

1. Encryption doesn't try to hide its persence
    Stegonagraphy: emmed bits into HTTP messages; but too slow
    Obsfproxy: encrypt all bits sent over network, but DPI will flag traffic as "????"
    Want:  Trick DPI to think its HTTP tranffic
     Can we build encryption which could fool regular expression matching?  ---> Format-transforming encryption: take clear text and a regular expression R, and the encrypted text is guaranteed to match R.
      Mechanism: Ranking for DFAs, but now for regexes (exponential complexity, but it's OK here)
      Can DPI adapt to detect FTE?
       1. Use R1, R2 against FTE --> flse positives
       2. FInd R that matches against FTE, but not legimate --> fast to change FTE formats
       3. Find non-regular checks ---> speed?
       4. Costum fight back? ----> ???

     FTE beats China's blocking of Tor, but Tor guys are skeptical about deploying an "academic" product (like they weren't an academic product. themselves....)

2. De-duplication doesn't work with conventional client-side encryption
    Prior work (in distributed system literature, surprisingly): convergent encryption (CE)
     Their solution:
        M --> KeyGen(M) ---> K (being used for encryption Enc(K,m)--> ?????
     Big idea: message is "shared  encrypted"
      But it has brute-force attaching problem.
       DupLESS is built to overcome the brute-force attaching issue of MLE

   Q: If we store the same data, then I know that you know (that I know...?)
   A: Yes, but this an orthogonal (side channel) issue with what we are looking at. 


3. Password-based encryption -> people don't pick good passward, you need to assume it is drawn from a small set
  
message + secrate key K ---> Cipher text C. Brute force attach possible by iterating K ( only one decrptyed text is not garbage)
Prior solution: PKCS5 standard, which do decryption b lots of hashing, thus attacker has to guess the right key each single time, but slow, and it onl slows down previous attack by constant factor.
Idea: increase the complexity of choosing the right key by producing plausible output if you use the wrong key to decrypt
Honey Encryption: same API as password-based encryption schemes, but use special encodings to ensure that decrypting ciphertext with *wrong*  key yield fresh sample from some target distribution (like an uniformation distribution in natural language).
Honey encryption for prime numbers: P (prime number) + K ---> C. Attacker can just try decrypt with each key and look for the prime numbers. Now you want an encoding so that every decrption of C yield a prime number.
           P --> (distribution transforming encoder) --->> Uniform bit-string ----> COnventional Encryption with K --> C
           Attacker: C --> decrypt with K' ---> Fresh Uniform bit string ---> Distribution transforming unencoder  ---> P'
      No attacker A can recover message with probability bettern than 1/q (the size of set where you draw password from)  no matter how long you runs 

Hopefully Next year we will have a general encryption scheme which covers all three above (because they are based on similar ideas anyway).

Q: Have you looked at other security real-world problems that you think could use an interesting encryption scheme, but you don't know what that encryption sheme yet?
A: Yes, all the time. LIke Gmail encryption, you lose spam detection, and we don't know how to solve it. In general, if you want data to be safe, but you also want third-party to do something about your data (de-duplication, spam detection), you have a problem.