How to encrypt a graph

作     者：Akl, Selim G. 

作者机构：Queens Univ Sch Comp Kingston ON K7L 3N6 Canada 

出 版 物：《INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS》 (并行、紧急、分布式系统国际杂志)

年 卷 期：2020年第35卷第6期

页      面：668-681页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：I am grateful to Pat Martin  Marius Nagy  Naya Nagy  and Kai Salomaa for their helpful comments 

主　　题：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 

摘      要：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.