Skip to content
DSML.KZ
Publications

Talk · AIP conference proceedings · January 1, 2018

Computing quantum hashing in the model of quantum branching programs

Farid Mansurovich Ablayev, Marat Ablayev, Alexander Vasiliev

Marat Ablayev
Open via DOIPDF

Abstract

We investigate the branching program complexity of quantum hashing. We consider a quantum hash function that maps elements of a finite field into quantum states. We require that this function is preimage-resistant and collision-resistant.We consider two complexity measures for Quantum Branching Programs (QBP): a number of qubits and a number of compu-tational steps. We show that the quantum hash function can be computed efficiently. Moreover, we prove that such QBP construction is optimal. That is, we prove lower bounds that match the constructed quantum hash function computation.

Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyCoding theory and cryptographypreimage resistancecollision resistancefinite fields

More by Marat Ablayev