Paper 2016/880

Naor-Yung Paradigm with Shared Randomness and Applications

Silvio Biagioni, Daniel Masny, and Daniele Venturi

Abstract

The Naor-Yung paradigm (Naor and Yung, STOC '90) allows to generically boost security under chosen-plaintext attacks (CPA) to security against chosen-ciphertext attacks (CCA) for public-key encryption (PKE) schemes. The main idea is to encrypt the plaintext twice (under independent public keys), and to append a non-interactive zero-knowledge (NIZK) proof that the two ciphertexts indeed encrypt the same message. Later work by Camenisch, Chandran, and Shoup (Eurocrypt '09) and Naor and Segev (Crypto '09 and SIAM J. Comput. '12) established that the very same techniques can also be used in the settings of key-dependent message (KDM) and key-leakage attacks (respectively). In this paper we study the conditions under which the two ciphertexts in the Naor-Yung construction can share the same random coins. We find that this is possible, provided that the underlying PKE scheme meets an additional simple property. The motivation for re-using the same random coins is that this allows to design much more efficient NIZK proofs. We showcase such an improvement in the random oracle model, under standard complexity assumptions including Decisional Diffie-Hellman, Quadratic Residuosity, and Subset Sum. The length of the resulting ciphertexts is reduced by 50\%, yielding truly efficient PKE schemes achieving CCA security under KDM and key-leakage attacks. As an additional contribution, we design the first PKE scheme whose CPA security under KDM attacks can be directly reduced to (low-density instances of) the Subset Sum assumption. The scheme supports key-dependent messages computed via any affine function of the secret key.

Note: Minor revision. Full version published in Theoretical Computer Science.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. SCN 2016
Keywords
Naor-Yung paradigmKDM securityleakageSubset Sum
Contact author(s)
daniele venturi @ unitn it
History
2017-06-25: revised
2016-09-14: received
See all versions
Short URL
https://ia.cr/2016/880
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/880,
      author = {Silvio Biagioni and Daniel Masny and Daniele Venturi},
      title = {Naor-Yung Paradigm with Shared Randomness and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2016/880},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/880}},
      url = {https://eprint.iacr.org/2016/880}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.