<div dir="ltr">There is a copy of the paper in the github repo if anyone else is looking for it.<div><br></div><div><div>This isn't a ratchet, it's an encryption scheme you can use to replace 3DH/forward secure key exchange. Why would you want this ? Because it works without interaction and has a constant size public key (unlike signed ephemerals which, even if not distributed by a server, require linear storage). </div><div>You can and should use it to bootstrap a ratchet just like 3DH.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span style="font-size:12.8px">the application can pay extra CPU cost to allow for longer-delayed messages / worse-synchronised clocks",</span></blockquote><div> </div><div>The entire point of the combined scheme is that allowing for decrypting late messages costs nothing: we simply keep interval keys around because forward security doesn't depend on us deleting them. When I said we combine puncturable encryption with the time interval based approach, I didn't mean we kept the deletion part. The entire point is we can avoid that.</div><div><br></div><div>The only time you pay the cost is if you get another message that was sent in the same interval (late or otherwise) because then you have to decrypt with a punctured key (and if you get n messages in the interval, with a key punctured n times ). Minimizing the probability of this happening is why we make intervals small. </div><div><br></div><div>If your traffic follows a Poisson distribution (i.e. it has an average rate of arrival of x), you are unlikely to get many messages in a given interval if you pick the interval appropriately(e.g. if you get 10 messages an hour on average, make your interval 10 minute). So occasionally your pay the cost of decrypting with a key with once puncture, less frequently you decrypt using a 2 puncture key, even less for 3, etc because the odds of getting n messages in an interval decrease very quickly as n increases. So costs stay manageable. Real messaging traffic is probably more bursty than a poisson process because of replies and such, but ratcheting smoothes that over since we use it for subsequent messages.</div><div><br></div><div><br></div><div>Ian</div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Sep 5, 2015 at 9:08 AM, Ximin Luo <span dir="ltr"><<a href="mailto:infinity0@pwned.gg" target="_blank">infinity0@pwned.gg</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On 05/09/15 12:27, Ximin Luo wrote:<br> > Do you have a paper that describes this in more detail?<br> ><br> <br> </span>I just found the paper and skimmed through it. To answer my own questions, the differences between this and e.g. a typical ratchet is that:<br> <br> - the encrypted messages are not ordered, within an interval; ratchets encode an implicit order to the messages, in when they must be decrypted. This is probably a good thing; you can always add ordering on the layer above if needed.<br> - don't need to generate a new random ephemeral key for each session, which is very good<br> <br> So I can see the benefits of using this to seed Axolotl sessions (or a non-lossy ratchet as I suggested previously).<br> <br> However, I don't think you suggest a good performance tradeoff for users of your library:<br> <br> - In a solely interval-based scheme, after a delay/unsync of T the message become undecryptable. Messages sent within <T of each other, are not forward-secret with respect to each other. If we want them to be so, we must reduce T.<br> <br> - Your scheme allows one to set a greater T, and still retain forward secrecy for individual messages within this time interval, at the cost of decryption performance. But then you suggest that users should set T to expect "1 message per interval", which roughly neutralises this benefit - messages delayed for longer than time T will again become undecryptable, just like in a naive interval-based scheme. Then the benefit is very small (i.e. those rare messages that are sent <T are still FS wrt each other), which probably doesn't justify the complexity of using this scheme.<br> <br> In other words, the tradeoff can be expressed as "the application can pay extra CPU cost to allow for longer-delayed messages / worse-synchronised clocks", and this (I guess) is something that users of your library will need to understand, judge for themselves, and set when using your library. The topic could be studied further too, to figure out what the best way of actually making this trade-off is.<br> <br> On another note, do you think it would be feasible to come up with a Puncture scheme that has a lower decryption cost? Or, alternatively, is this expected to be mathematically impossible?<br> <div class="HOEnZb"><div class="h5"><br> X<br> <br> --<br> GPG: 4096R/1318EFAC5FBBDBCE<br> git://<a href="http://github.com/infinity0/pubkeys.git" rel="noreferrer" target="_blank">github.com/infinity0/pubkeys.git</a><br> <br> </div></div><br>_______________________________________________<br> Messaging mailing list<br> <a href="mailto:Messaging@moderncrypto.org">Messaging@moderncrypto.org</a><br> <a href="https://moderncrypto.org/mailman/listinfo/messaging" rel="noreferrer" target="_blank">https://moderncrypto.org/mailman/listinfo/messaging</a><br> <br></blockquote></div><br></div>