Crypto-attack Let N = = {1,2, 3,...} denote the set of positive integers. The size of...

Transcribed Image Text:

Crypto-attack Let N = = {1,2, 3,...} denote the set of positive integers. The size of an integer a ≥ 1 is a [log₂ (a) + 1], the number of bits in the binary representation of a. E.g. the size of 20231004 is 25 since there are 25 bits in its binary representation 1001101001011001101011100. = Our good friend Beeblebrox uses a function f: N→ N for all their encryptions. We know the following three properties about their one-way function: f(1) = 1 a ≤ f(a)| ≤ 3|a| f(a) ≤ f(a + 1). for all a2 1. That is, the output string is within a factor of 3 of the length of the input string, and the function is monotone. We can access the function f in the following manner: For any a > 1, we can query "What is f on a?" to which Beeblebrox provides the answer f(a). The cost of the query is lal, the size of a. We can not access f in any other ways. Our only method to learn information about f is through queries to Beeblebrox. Decryption problem Input: (1) (2) The decryption problem is: We are given an integer y ≥ 1, and our task is to find an input x such that f(x) = y. We are promised that such an x exists. The input size of the instance y is n ly, the number of bits in the binary representation of y. = An integer y. A function f that can be accessed only through queries to Beeblebrox. There exists at least one x for which f(x) = y. Promise: Output: An integer x for which f(x) = y. 1. Give an algorithm D that solves the decryption problem and that has polynomial cost, i.e., cost O(ly) for some constant c> 0. State your algorithm clearly, unambiguously and succinctly. (See D2L Discussion board for details.) If an asymptotically faster algorithm exists, then give the faster algorithm. 2. Succinctly illustrate how your algorithm works on a non-trivial example. 3. Concisely argue why D solves the decryption problem. 4. Compute the complexity of your algorithm D. State your bound is terms of the input size ly. Show your calculations and justify. Crypto-attack Let N = = {1,2,3,...} denote the set of positive integers. The size of an integer a ≥ 1 is a [log₂ (a) + 1], the number of bits in the binary representation of a. E.g. the size of 20231004 is 25 since there are 25 bits in its binary representation 1001101001011001101011100. = Our good friend Beeblebrox uses a function f: N→ N for all their encryptions. We know the following three properties about their one-way function: f(1) = 1 a ≤ f(a)| ≤3|a| f(a) ≤ f(a + 1). for all a2 1. That is, the output string is within a factor of 3 of the length of the input string, and the function is monotone. We can access the function f in the following manner: For any a > 1, we can query "What is f on a?" to which Beeblebrox provides the answer f(a). The cost of the query is lal, the size of a. We can not access f in any other ways. Our only method to learn information about f is through queries to Beeblebrox. Decryption problem Input: (1) (2) The decryption problem is: We are given an integer y ≥ 1, and our task is to find an input x such that f(x) = y. We are promised that such an x exists. The input size of the instance y is n ly, the number of bits in the binary representation of y. = An integer y. A function f that can be accessed only through queries to Beeblebrox. There exists at least one x for which f(x) = y. Promise: Output: An integer x for which f(x) = y. 1. Give an algorithm D that solves the decryption problem and that has polynomial cost, i.e., cost O(ly) for some constant c> 0. State your algorithm clearly, unambiguously and succinctly. (See D2L Discussion board for details.) If an asymptotically faster algorithm exists, then give the faster algorithm. 2. Succinctly illustrate how your algorithm works on a non-trivial example. 3. Concisely argue why D solves the decryption problem. 4. Compute the complexity of your algorithm D. State your bound is terms of the input size ly. Show your calculations and justify. Crypto-attack Let N = = {1,2, 3,...} denote the set of positive integers. The size of an integer a ≥ 1 is a [log₂ (a) + 1], the number of bits in the binary representation of a. E.g. the size of 20231004 is 25 since there are 25 bits in its binary representation 1001101001011001101011100. = Our good friend Beeblebrox uses a function f: N→ N for all their encryptions. We know the following three properties about their one-way function: f(1) = 1 a ≤ f(a)| ≤ 3|a| f(a) ≤ f(a + 1). for all a2 1. That is, the output string is within a factor of 3 of the length of the input string, and the function is monotone. We can access the function f in the following manner: For any a > 1, we can query "What is f on a?" to which Beeblebrox provides the answer f(a). The cost of the query is lal, the size of a. We can not access f in any other ways. Our only method to learn information about f is through queries to Beeblebrox. Decryption problem Input: (1) (2) The decryption problem is: We are given an integer y ≥ 1, and our task is to find an input x such that f(x) = y. We are promised that such an x exists. The input size of the instance y is n ly, the number of bits in the binary representation of y. = An integer y. A function f that can be accessed only through queries to Beeblebrox. There exists at least one x for which f(x) = y. Promise: Output: An integer x for which f(x) = y. 1. Give an algorithm D that solves the decryption problem and that has polynomial cost, i.e., cost O(ly) for some constant c> 0. State your algorithm clearly, unambiguously and succinctly. (See D2L Discussion board for details.) If an asymptotically faster algorithm exists, then give the faster algorithm. 2. Succinctly illustrate how your algorithm works on a non-trivial example. 3. Concisely argue why D solves the decryption problem. 4. Compute the complexity of your algorithm D. State your bound is terms of the input size ly. Show your calculations and justify. Crypto-attack Let N = = {1,2,3,...} denote the set of positive integers. The size of an integer a ≥ 1 is a [log₂ (a) + 1], the number of bits in the binary representation of a. E.g. the size of 20231004 is 25 since there are 25 bits in its binary representation 1001101001011001101011100. = Our good friend Beeblebrox uses a function f: N→ N for all their encryptions. We know the following three properties about their one-way function: f(1) = 1 a ≤ f(a)| ≤3|a| f(a) ≤ f(a + 1). for all a2 1. That is, the output string is within a factor of 3 of the length of the input string, and the function is monotone. We can access the function f in the following manner: For any a > 1, we can query "What is f on a?" to which Beeblebrox provides the answer f(a). The cost of the query is lal, the size of a. We can not access f in any other ways. Our only method to learn information about f is through queries to Beeblebrox. Decryption problem Input: (1) (2) The decryption problem is: We are given an integer y ≥ 1, and our task is to find an input x such that f(x) = y. We are promised that such an x exists. The input size of the instance y is n ly, the number of bits in the binary representation of y. = An integer y. A function f that can be accessed only through queries to Beeblebrox. There exists at least one x for which f(x) = y. Promise: Output: An integer x for which f(x) = y. 1. Give an algorithm D that solves the decryption problem and that has polynomial cost, i.e., cost O(ly) for some constant c> 0. State your algorithm clearly, unambiguously and succinctly. (See D2L Discussion board for details.) If an asymptotically faster algorithm exists, then give the faster algorithm. 2. Succinctly illustrate how your algorithm works on a non-trivial example. 3. Concisely argue why D solves the decryption problem. 4. Compute the complexity of your algorithm D. State your bound is terms of the input size ly. Show your calculations and justify.

Answer rating: 100% (QA)

The given problem outlines a cryptographic scenario where we have a onew... View the full answer