IACR News item: 22 October 2014
Sandro Coretti, Yevgeniy Dodis, Bj\\\"orn Tackmann, Daniele Venturi
ePrint ReportDomain Extension: For any $K > 1$, there is a black-box construction of a $K$-bit NM-SDA PKE scheme from a single-bit NM-SDA PKE scheme. Moreover, this can be done using only $O(\\lambda)$ calls to the underlying single-bit NM-SDA scheme, where $\\lambda$ is the security parameter. To achieve our goal, we define and construct a novel type of continuous non-malleable code (NMC), called secret-state NMC, as we show that standard continuous NMCs are not enough for the natural ``expand-then-encrypt-bit-by-bit\'\' approach to work.
Black-Box Construction from IND-CPA: Prior work showed that NM-CPA secure PKE can be constructed from any IND-CPA secure PKE in a black-box way. Here we show that the same construction actually achieves our strictly stronger notion of NM-SDA security. (This requires a non-trivial extension of the original security proof to handle multiple parallel decryption queries.) Hence, the notions of IND-CPA, NM-CPA, IND-SDA and NM-SDA security are all equivalent, lying (plausibly, strictly?) below IND-CCA security. We also show how to improve the rate of the resulting NM-SDA scheme from quadratic to linear.
Additional news items may be found on the IACR news page.