Decision oracles are equivalent to matching oracles

被引:0
|
作者
Handschuh, H [1 ]
Tsiounis, Y
Yung, M
机构
[1] ENST, Gemplus Grp, Paris, France
[2] GTE Labs Inc, Waltham, MA USA
[3] CertCo Inc, New York, NY USA
来源
PUBLIC KEY CRYPTOGRAPHY | 1999年 / 1560卷
关键词
Diffie-Hellman variants; randomized reductions; uniform reductions; public-key encryption; homomorphic encryption functions (ElGamal; Goldwasser-Micali; Okamoto-Uchiyama; Naccache-Stern); random self-reducibility; decision problems; matching problems; universal malleability;
D O I
暂无
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
One of the key directions in complexity theory which has also filtered through to cryptographic research, is the effort to classify related but seemingly distinct notions. Separation or reduction arguments are the basic means for this classification. Continuing this direction we identify a class of problems, called "matching problems," which are related to the class of "decision problems." In many cases, these classes are neither trivially equivalent nor distinct. Briefly, a "decision" problem consists of one instance and a supposedly related image of this instance; the problem is to decide whether the instance and the image indeed satisfy the given predicate. In a "matching" problem two such pairs of instances-images are given, and the problem is to "match" or "distinguish" which image corresponds to which instance. Clearly the decision problem is more difficult, since given a "decision" oracle one can simply test each of the two images to be matched against an instance and solve the matching problem. Here we show that the opposite direction also holds, presuming that randomization of the input is possible, and that the matching oracle is successful in all but a negligible part of its input set. We first apply our techniques to show equivalence between the matching Diffie-Hellman and the decision Diffie-Hellman problems which were both applied recently quite extensively. This is a constructive step towards examining the strength of the Diffie-Hellman related problems. Then we show that in cryptosystems which can be uniformly randomized, non-semantic security implies that there is an oracle that decides whether a given plaintext corresponds to a given ciphertext. In the process we provide a new characteristic of encryption functions, which we call "universal malleability."
引用
收藏
页码:276 / 289
页数:14
相关论文
共 18 条
  • [1] Hidden Credential Retrieval without Random Oracles
    Miyaji, Atsuko
    Rahman, Mohammad Shahriar
    Soshi, Masakazu
    INFORMATION SECURITY APPLICATIONS, 2011, 6513 : 160 - +
  • [2] Toward RSA-OAEP Without Random Oracles
    Cao, Nairen
    O'Neill, Adam
    Zaheri, Mohammad
    PUBLIC-KEY CRYPTOGRAPHY - PKC 2020, PT I, 2020, 12110 : 279 - 308
  • [3] Compact public key encryption without full random oracles
    Yoneyama, Kazuki
    Hanaoka, Goichiro
    PERVASIVE AND MOBILE COMPUTING, 2017, 41 : 286 - 299
  • [4] New Constructions of Equality Test Scheme Without Random Oracles
    Zhu, Huijun
    Ahmad, Haseeb
    Xue, Qingji
    Li, Tianfeng
    Liu, Ziyu
    Liu, Ao
    IEEE ACCESS, 2023, 11 (49519-49529) : 49519 - 49529
  • [5] Quantum Security Proofs Using Semi-classical Oracles
    Ambainis, Andris
    Hamburg, Mike
    Unruh, Dominique
    ADVANCES IN CRYPTOLOGY - CRYPTO 2019, PT II, 2019, 11693 : 269 - 295
  • [6] Efficient Selective Identity-Based Encryption Without Random Oracles
    Boneh, Dan
    Boyen, Xavier
    JOURNAL OF CRYPTOLOGY, 2011, 24 (04) : 659 - 693
  • [7] An Efficient Certificate-Based Encryption Scheme Without Random Oracles
    Guo, Lan
    Lu, Yang
    Miao, Qing
    Zu, Guangao
    Wang, Zhongqi
    ARTIFICIAL INTELLIGENCE AND SECURITY, ICAIS 2022, PT III, 2022, 13340 : 97 - 107
  • [8] Secure public-key encryption scheme without random oracles
    Tan, Chik How
    INFORMATION SCIENCES, 2008, 178 (17) : 3435 - 3442
  • [9] Identity-Based Encryption Resilient to Continual Leakage Without Random Oracles
    Guo, Yuyan
    Jiang, Mingming
    Wei, Shimin
    Xie, Ming
    Sun, Mei
    FRONTIERS IN CYBER SECURITY, FCS 2019, 2019, 1105 : 53 - 64
  • [10] Attribute-Based Equality Test Over Encrypted Data Without Random Oracles
    Wang, Yuanhao
    Cui, Yuzhao
    Huang, Qiong
    Li, Hongbo
    Huang, Jianye
    Yang, Guomin
    IEEE ACCESS, 2020, 8 : 32891 - 32903