Editing Pseudo-Secret Random Qubit Generator (PSQRG)
Jump to navigation
Jump to search
The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 86: | Line 86: | ||
*''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. | ||
<div style='text-align: right;'>''*contributed by Shraddha Singh''</div> | <div style='text-align: right;'>''*contributed by Shraddha Singh''</div> |