What is an encryption? Most people would think of encryption as a locked box which you can open only if you have a correct key. However, this analogy is not entirely correct. For a locked box, we don’t expect to open it with two different keys. But one can actually come up with a ciphertext that can be opened properly by two keys (probably to different messages). This gap seems harmless at first, but it has led to several attacks on important applications, such as the Abuse Report mechanism of Facebook Messenger, or password-based encryption. The situation is serious enough that the National Institute of Science and Technology (NIST) has been considering to include a novel security goal, known as committing security, to future encryption standard to resist such attacks.
There have been several proposals on how to build a committing encryption, but all suffer from the same shortcoming: a ciphertext now must be at least 16B larger than before. The 16B overhead seems minor, but it creates a big trouble if you have legacy software that expects smaller ciphertext length, or if you are in an energy-constrained environment (such as IoT) where shaving this extra 16B is worth making the cryptography 10x more expensive. Unfortunately, the 16B overhead seems impossible to avoid due to a generic attack.
In this work, Dr. Hoang and his co-author find a way to circumvent the impossibility. They provide an general approach to transform a standard encryption scheme to a committing one (without enlarging the ciphertext), with essentially optimal overhead.
It’s still too early to tell how the results of the paper will affect future encryption (an encryption standardization process often takes years to finish), but so far the results haven been well received by standard agencies, such as NIST and the UK National Cyber Security Center.