<div dir="ltr"><div style="font-size:12.8px"><font color="#000000"><span style="font-size:13px">Matthew Green and I developed a scheme <span>for</span> <span>forward</span> secure encryption without interaction that, unlike early schemes, works with badly synchronized clocks and late messages. It was published at IEEE S&P (aka Oakland) this year and has a formal argument <span>for</span> security.  More importantly, we wrote a C++ library implementing it, available at </span><a href="https://github.com/imichaelmiers/libforwardsec/" style="font-size:13px" target="_blank">https://github.com/imichaelmiers/<span>libforwardsec</span>/</a><span style="font-size:13px"> </span><span style="font-size:13px">and we think it is actually useful in the real world.</span></font></div><div><font color="#000000" style="font-size:12.8px"><br></font><div style="font-size:13px"><font color="#000000">TLDR :</font></div><div><ul><li style="font-size:13px;margin-left:15px"><font color="#000000">Performance: depends on message distribution. Assuming a poisson process <span>for</span> initial messages (you only need this <span>for</span> initial messages, after that use Axolotl or another ratchet):  <br></font></li><ul style="font-size:13px"><li style="margin-left:15px"><font color="#000000"><span>For</span> desktops: decryption takes 20ms expected and with 99.99% less than 200 ms.</font></li><span><li style="margin-left:15px"><font color="#000000">Mobile is 3 to 4x worse but I haven't experimented with compiler optimization flags, so there's room for improvement.</font></li></span><li style="margin-left:15px"><font color="#000000">Ciphertexts are less than 0.5kb.</font></li><span><li style="margin-left:15px"><font color="#000000">A public key is 1.6kb and lasts <span>for</span> 68 years if we expect one message a second.</font></li></span><li style="margin-left:15px"><font color="#000000">Secret key material should be less than 1mb.</font></li></ul><li style="font-size:13px;margin-left:15px"><font color="#000000">Crypto:  </font></li><ul><li style="font-size:13px;margin-left:15px"><font color="#000000">Pairings over BN256 curves</font></li><li style="margin-left:15px"><font color="#000000" style="font-size:13px">Assumes Bilinear Diffie Hellman Inversion Assumption and</font><font color="#000000"> Decisional Bilinear Diffie-Hellman</font></li><span style="font-size:13px"><li style="margin-left:15px"><font color="#000000">Random oracle <span>for</span> CCA security via Fiat Shamir </font></li></span></ul></ul></div><div style="font-size:13px"><font color="#000000">This code is in far better shape than most academic software and was written to be released. If people are interested in using it Matt and I need to review it more carefully and others may need to do so as well. We'd love to see it used. So please contact us if you are interested.</font></div><span style="font-size:12.8px"><font color="#000000"><div style="font-size:13px"><br></div><div style="font-size:13px">Because you can always use this to wrap a message encrypted with a vetted library, the worst case given a cryptographic failure of our library is you end up not having <span>forward </span>security <span>for</span> messages that, absent this, wouldn't have it anyway. The larger concern is buffer overflows and the like in our library , the underlying pairing library (RELIC), or GMP. </div><div style="font-size:13px"><br>A BRIEF EXPLANATION  OF THE SCHEME </div></font></span><div><div style="font-size:13px"><font color="#000000"><span>Forward</span> Secure Encryption (in contrast to key exchange protocols) typically works by mapping time intervals (e.g. one an hour) to portions of a secret key. (You can think of this as having one public/private key pair per time interval but with some advanced crypto that compresses the public key down to constant size and gets logarithmic sized private keys.) Messages <span>for</span> a given time interval can only be decrypted with the corresponding portion of the secret key.  After the time interval expires, that part of the secret key is deleted.</font></div><div style="font-size:13px"><font color="#000000"><br></font></div><div style="font-size:13px"><font color="#000000">While this ensures <span>forward</span> security, it means late arriving messages (either due to delays or badly set clocks) can't be decrypted. This means we face a choice: either have fine grained <span>forward</span> security with short intervals and risk losing messages or have long intervals and leave more exposed.</font></div><div style="font-size:13px"><font color="#000000"><br></font></div><div style="font-size:13px"><font color="#000000">Our scheme, Puncturable <span>Forward</span> Secure Encryption, avoids this. Instead of deleting keys, we update ("puncture" them) every time we receive a ciphertext. Once punctured on a ciphertext, a key cannot decrypt that message but can decrypt new ciphertexts (e.g. late arrivals). Obviously, keys can be deleted at some point to avoid an attacker dropping messages and then breaking into your computer later.</font></div><div style="font-size:13px"><font color="#000000"><br></font></div><div><font color="#000000">Unfortunately, decryption is linear in the number of punctures. However, punctures are per time interval and don't cary over, so if we make our time intervals short, we only expect to see one message per interval and never need to decrypt with a punctured key. This ends up being very efficient. It does mean performance depends on your message distribution. When you only get one message in an interval it works very well.<br><br>If you get many messages in an interval, performance only in that interval linearly worse but is still manageable for a while. (For those of you wondering about DOS, the system can always fall back to the time based approach. If too many messages arrive in an interval we can stop puncturing and lock in whatever performance we have <span style="font-size:13px">for</span> that interval.... you probably should delete that key soon after the interval expires). If you have high variance in your message distribution, you're going to need to use shorter intervals to ensure you usually get one message per interval. Past a certain point, this will also get expensive and the entire scheme might not be well suited to your needs.   I don't think this is close to the common case at all. For most applications, I think you can reasonably ensure you get one message per interval on average.<br><br></font></div><div style="font-size:13px"><font color="#000000">Ian Miers <br>Ph.D. student,  JHU Computer Science </font></div></div></div></div>