How to encrypt a graph. Issue 6 (1st November 2020)

• Record Type: Journal Article
• Authors: Akl, Selim G.
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 35:Issue 6(2020)
• Page Start: 668
• Page End: 681
• Publication Date: 2020-11-01
• Subjects: Cryptography -- cryptanalysis -- cryptology -- encryption -- decryption -- secret key -- one-way function -- trapdoor one-way function -- graph -- multigraph -- plaintext -- ciphertext -- one-time key -- encryption algorithm -- encryption scheme -- public-key cryptosystem -- malleability -- confusion -- diffusion -- graph database -- homomorphic encryption -- social networks -- unconventional cryptographic function -- quantum cryptography protocol -- molecular encoding; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2018.1550771
• Languages: English
• ISSNs: 1744-5760

Abstract

ABSTRACT: An algorithm is described for encrypting a graph to be transmitted securely from a sender to a receiver. In communications terminology, "the graph is the message": its vertices, its edges, and its edge weights are the information to be concealed. The encryption algorithm is based on an unconventional mapping, conjectured to be a trapdoor one-way function, designed for graphs. This function requires the sender and the receiver to use a secret one-time encryption/decryption key. It is claimed that a malicious eavesdropper with no knowledge of the key will be faced with a computational task requiring exponential time in the size of the input graph in order to extract the original plaintext from the ciphertext carried by the encrypted graph. A number of variants to the main algorithm are also proposed.