Key-Recovery Attack on a Public-Key Encryption Related to Planted Clique

Caicai Chen; Chris Jones

Paper 2024/359

Key-Recovery Attack on a Public-Key Encryption Related to Planted Clique

Caicai Chen, Bocconi University

Chris Jones

, Bocconi University

Abstract

Hudoba proposed a public key encryption (PKE) scheme and conjectured its security to be based on the Planted Clique problem. In this note, we show that this scheme is not secure. We do so by devising an efficient algorithm for the even neighbor independent set problem proposed by Hudoba. This leaves open the possibility of building PKE based on Planted Clique.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: planted clique public key encryption average-case complexity
Contact author(s): caicai chen @ unibocconi it
chris jones @ unibocconi it
History: 2024-03-01: approved; 2024-02-28: received; See all versions
Short URL: https://ia.cr/2024/359
License: CC BY

BibTeX

@misc{cryptoeprint:2024/359,
      author = {Caicai Chen and Chris Jones},
      title = {Key-Recovery Attack on a Public-Key Encryption Related to Planted Clique},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/359},
      year = {2024},
      url = {https://eprint.iacr.org/2024/359}
}