Pseudo-Secret Random Qubit Generator (PSQRG): Difference between revisions

*''One-Way'' A family of functions {fk : D → R}k∈K is one-way if there exists a QPT algorithm that can compute fk(x) for any k, any input x ∈ D, and any QPT algorithm can invert fk with at most negligible probability over the choice of k.

*''Second preimage Resistant'' A family of functions {fk : D → R}k∈K is second preimage resistant if there exists a QPT algorithm that can compute fk(x) for any index function k, any input x ∈ D, and given an input x, it can find a different input x0 such that fk(x) = fk(x0) with at most negligible probability over the choice of k.

*''Collision Resistant'' A family of functions {fk : D → R}k∈K is collision resistant if there exists a QPT algorithm that can compute fk(x) for any index function k, any input x ∈ D, any QPT algorithm can find two inputs x 6= x0 such that fk(x) = fk(x0) with at most negligible probability over the choice of k.

*''Two-regular'' A deterministic function f : D → R is two-regular if ∀y ∈ =(f), we have |f−1(y)| = 2

*''Trapdoor Function'' A family of functions {fk : D → R} is a trapdoor function if there exists a QPT algorithm Gen which on input 1n outputs (k,tk), where k represents the index of a function, {fk : D → R}k∈K, where fk is a one-way function, then there exists a QPT algorithm Inv, which on inputs tk (which is called the trapdoor information) which was output by Gen(1n), and y = fk(x) can invert y (by returning all preimages of y with non-negligible probability over the choice of (k,tk) and uniform choice of x.