Improved Quantum Algorithms for the k-XOR Problem

Lorenzo Grassi, María Naya‐Plasencia, André Schrottenloher

Yufei Yuan, Wenling Wu, Tairong Shi +2 more

This paper presents a novel approach to optimizing the linear layer of block ciphers using the matrix decomposition framework. It is observed that the reduction properties proposed by Xiang et al. (in FSE 2020) need to be improved. To address these limitations, we propose a new reduction framework with a complete reduction algorithm and swapping algorithm. Our approach formulates matrix decomposition as a new framework with an adaptive objective function and converts the problem to a Graph Isomorphism problem (GI problem). Using the new reduction algorithm, we were able to achieve lower XOR counts and depths of quantum implementations under the s-XOR metric. Our results outperform previous works for many linear layers of block ciphers and hash functions; some of them are better than the current g-XOR implementation. For the AES MixColumn operation, we get two implementations with 91 XOR counts and depth 13 of in-place quantum implementation, respectively.

Peter W. Shor

María Naya‐Plasencia, André Schrottenloher

The k-xor or Generalized Birthday Problem aims at finding, given k lists of bit-strings, a k-tuple among them XORing to 0. If the lists are unbounded, the best classical (exponential) time complexity has withstood since Wagner’s CRYPTO 2002 paper. If the lists are bounded (of the same size) and such that there is a single solution, the dissection algorithms of Dinur et al. (CRYPTO 2012) improve the memory usage over a simple meet-in-the-middle.

María Naya‐Plasencia, André Schrottenloher

Praveen Kumar, Areeba Fatima, Naveen Kumar Nishchal

Abstract Exclusive-OR (XOR) operation is a popular technique in optical cryptography. The linear and inverse properties of XOR operation provide a simple way of encryption but in some cases fail to provide strong security. In XOR-based image encryption, each pixel is individually encrypted, therefore secret information can be traced with partial knowledge of the key. In this paper, we describe a simple and practical method to improve the strength and effectiveness of XOR-based encryption. A higher level of security is achieved by implementing a phase retrieval algorithm with XOR operation. Another advantage of the proposed scheme is that the optical XOR operation is demonstrated using incoherent light sources, which make the system compact, speckle free, and cost effective. Also, to overcome the problem of quality degradation while decrypting, quick response code-based ciphertext has been implemented. Both simulation and experimental results are demonstrated as a proof-of-concept.