International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Possibility and Impossibility Results for Receiver Selective Opening Secure PKE in the Multi-Challenge Setting

Authors:
Rupeng Yang
Junzuo Lai
Zhengan Huang
Man Ho Au
Qiuliang Xu
Willy Susilo
Download:
DOI: 10.1007/978-3-030-64837-4_7
Search ePrint
Search Google
Abstract: Public key encryption (PKE) schemes are usually deployed in an open system with numerous users. In practice, it is common that some users are corrupted. A PKE scheme is said to be receiver selective opening (RSO) secure if it can still protect messages transmitted to uncorrupted receivers after the adversary corrupts some receivers and learns their secret keys. This is usually defined by requiring the existence of a simulator that can simulate the view of the adversary given only the opened messages. Existing works construct RSO secure PKE schemes in a single-challenge setting, where the adversary can only obtain one challenge ciphertext for each public key. However, in practice, it is preferable to have a PKE scheme with RSO security in the multi-challenge setting, where public keys can be used to encrypt multiple messages. In this work, we explore the possibility for achieving PKE schemes with receiver selective opening security in the multi-challenge setting. Our contributions are threefold. First, we demonstrate that PKE schemes with RSO security in the single-challenge setting are not necessarily RSO secure in the multi-challenge setting. Then, we show that it is impossible to achieve RSO security for PKE schemes if the number of challenge ciphertexts under each public key is a priori unbounded. In particular, we prove that no PKE scheme can be RSO secure in the $k$-challenge setting (i.e., the adversary can obtain $k$ challenge ciphertexts for each public key) if its secret key contains less than $k$ bits. On the positive side, we give a concrete construction of PKE scheme with RSO security in the $k$-challenge setting, where the ratio of the secret key length to $k$ approaches the lower bound 1.
Video from ASIACRYPT 2020
BibTeX
@article{asiacrypt-2020-30674,
  title={Possibility and Impossibility Results for Receiver Selective Opening Secure PKE in the Multi-Challenge Setting},
  booktitle={Advances in Cryptology - ASIACRYPT 2020},
  publisher={Springer},
  doi={10.1007/978-3-030-64837-4_7},
  author={Rupeng Yang and Junzuo Lai and Zhengan Huang and Man Ho Au and Qiuliang Xu and Willy Susilo},
  year=2020
}