Write, autoreview, editor, reviewer
3,129
edits
Pseudo-Secret Random Qubit Generator (PSQRG): Difference between revisions
Pseudo-Secret Random Qubit Generator (PSQRG) (edit)
Revision as of 09:52, 11 October 2018
, 11 October 2018→Definitions (informal)
| Line 26: | Line 26: | ||
==Definitions (informal)== | ==Definitions (informal)== | ||
*''Quantum-Safe'' A protocol/function is quantum-safe (also known as post-quantum secure), if all its properties remain valid when the adversaries are quantum polynomial-time (QPT). | *''Quantum-Safe'' A protocol/function is quantum-safe (also known as post-quantum secure), if all its properties remain valid when the adversaries are quantum polynomial-time (QPT). | ||
*''One-Way'' A family of functions <math>\{f_k : D \rightarrow R\}k\epsilon {0,1}</math> is one-way if there exists a QPT algorithm that can compute <math>f_k(x)</math> for any k, any input x ∈ D, and any QPT algorithm can invert <math>f_k</math> with at most negligible probability over the choice of k. | *''One-Way'' A family of functions <math>\{f_k : D \rightarrow R\}_{k\epsilon {0,1}}</math> is one-way if there exists a QPT algorithm that can compute <math>f_k(x)</math> for any k, any input x ∈ D, and any QPT algorithm can invert <math>f_k</math> with at most negligible probability over the choice of k. | ||
*''Second pre-image Resistant'' A family of functions <math>\{f_k : D \rightarrow R\}k\epsilon {0,1}</math> is second pre-image resistant if there exists a QPT algorithm that can compute <math>f_k(x)</math> for any index function k, any input x ∈ D, and given an input x, it can find a different input <math>x_0</math> such that <math>f_k(x) = f_k(x')</math> with at most negligible probability over the choice of k. | *''Second pre-image Resistant'' A family of functions <math>\{f_k : D \rightarrow R\}_{k\epsilon {0,1}}</math> is second pre-image resistant if there exists a QPT algorithm that can compute <math>f_k(x)</math> for any index function k, any input x ∈ D, and given an input x, it can find a different input <math>x_0</math> such that <math>f_k(x) = f_k(x')</math> with at most negligible probability over the choice of k. | ||
*''Collision Resistant'' A family of functions <math>\{f_k : D \rightarrow R\}k\epsilon {0,1}</math> is collision resistant if there exists a QPT algorithm that can compute <math>f_k(x)</math> for any index function k, any input <math>x \epsilon D</math>, any QPT algorithm can find two inputs <math>x \neq x'</math> such that <math>f_k(x) = f_k(x')</math> with at most negligible probability over the choice of k. | *''Collision Resistant'' A family of functions <math>\{f_k : D \rightarrow R\}_{k\epsilon {0,1}}</math> is collision resistant if there exists a QPT algorithm that can compute <math>f_k(x)</math> for any index function k, any input <math>x \epsilon D</math>, any QPT algorithm can find two inputs <math>x \neq x'</math> such that <math>f_k(x) = f_k(x')</math> with at most negligible probability over the choice of k. | ||
*''Two-regular'' A deterministic function <math>\{f_k : D \rightarrow R\}k\epsilon {0,1}</math> is two-regular if <math>\forall y \epsilon Im(f)</math>, we have <math>|f^{-1}(y)| = 2</math> | *''Two-regular'' A deterministic function <math>\{f_k : D \rightarrow R\}_{k\epsilon {0,1}}</math> is two-regular if <math>\forall y \epsilon Im(f)</math>, we have <math>|f^{-1}(y)| = 2</math> | ||
*''Trapdoor Function'' A family of functions <math>\{f_k : D \rightarrow R\}k\epsilon {0,1}</math> is a trapdoor function if there exists a QPT algorithm Gen which on input <math>1^n</math> outputs <math>(k,t_k)</math>, where k represents the index of a function, <math>\{f_k : D \rightarrow R\}k\epsilon {0,1}</math>, where <math>f_k</math> is a one-way function, then there exists a QPT algorithm Inv, which on inputs <math>t_k</math> (which is called the trapdoor information) which was output by Gen(<math>1^n</math>), and <math>y = f_k(x)</math> can invert y (by returning all pre-images of y with non-negligible probability over the choice of <math>(k,t_k)</math> and uniform choice of x. | *''Trapdoor Function'' A family of functions <math>\{f_k : D \rightarrow R\}_{k\epsilon {0,1}}</math> is a trapdoor function if there exists a QPT algorithm Gen which on input <math>1^n</math> outputs <math>(k,t_k)</math>, where k represents the index of a function, <math>\{f_k : D \rightarrow R\}_{k\epsilon {0,1}}</math>, where <math>f_k</math> is a one-way function, then there exists a QPT algorithm Inv, which on inputs <math>t_k</math> (which is called the trapdoor information) which was output by Gen(<math>1^n</math>), and <math>y = f_k(x)</math> can invert y (by returning all pre-images of y with non-negligible probability over the choice of <math>(k,t_k)</math> and uniform choice of x. | ||
== Properties == | == Properties == | ||