Candidate trapdoor claw-free functions from group actions with applications to quantum protocols

N Alamati, G Malavolta, A Rahimi - Theory of Cryptography Conference, 2022 - Springer
N Alamati, G Malavolta, A Rahimi
Theory of Cryptography Conference, 2022Springer
Abstract Trapdoor Claw-free Functions (TCFs) are two-to-one trapdoor functions where it is
computationally hard to find a claw, ie, a colliding pair of inputs. TCFs have recently seen a
surge of renewed interest due to new applications to quantum cryptography: as an example,
TCFs enable a classical machine to verify that some quantum computation has been
performed correctly. In this work, we propose a new family of (almost two-to-one) TCFs
based on conjectured hard problems on isogeny-based group actions. This is the first …
Abstract
Trapdoor Claw-free Functions (TCFs) are two-to-one trapdoor functions where it is computationally hard to find a claw, i.e., a colliding pair of inputs. TCFs have recently seen a surge of renewed interest due to new applications to quantum cryptography: as an example, TCFs enable a classical machine to verify that some quantum computation has been performed correctly. In this work, we propose a new family of (almost two-to-one) TCFs based on conjectured hard problems on isogeny-based group actions. This is the first candidate construction that is not based on lattice-related problems and the first scheme (from any plausible post-quantum assumption) with a deterministic evaluation algorithm. To demonstrate the usefulness of our construction, we show that our TCF family can be used to devise a computational test of a qubit, which is the basic building block used in the general verification of quantum computations.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果