Security
If H is a random oracle, i.e. its output is truly random in then, forging a signature on any message m is as hard as calculating the square root of a random element in . To see that taking a random square root is as hard as factoring, we first note that any square modulo n has four square roots since n has two square roots modulo p and two square roots modulo q, and each pair gives a unique square root modulo n by the chinese remainder theorem. Now, if we have two different square roots, x,y such that but, then this immediately leads to a factorization of n since n divides but it does not divide either factor. Thus taking will lead to a nontrivial factorization of n. Now, there exists an algorithm to take square roots, we pick a random r modulo n and square it, then, using the algorithm to take the square root of R modulo n, we will get a new square root, and with probability half .
Read more about this topic: Rabin Signature Algorithm
Famous quotes containing the word security:
“... most Southerners of my parents’ era were raised to feel that it wasn’t respectable to be rich. We felt that all patriotic Southerners had lost everything in defense of the South, and sufficient time hadn’t elapsed for respectable rebuilding of financial security in a war- impoverished region.”
—Sarah Patton Boyle, U.S. civil rights activist and author. The Desegregated Heart, part 1, ch. 1 (1962)
“I think the girl who is able to earn her own living and pay her own way should be as happy as anybody on earth. The sense of independence and security is very sweet.”
—Susan B. Anthony (1820–1906)
“Learned institutions ought to be favorite objects with every free people. They throw light over the public mind which is the best security against crafty and dangerous encroachments on the public liberty.”
—James Madison (1751–1836)