Crypto-attack Let N = = {1,2, 3,...} denote the set of positive integers. The size of...
Fantastic news! We've Found the answer you've been seeking!
Question:
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.
Expert Answer:
Answer rating: 100% (QA)
The given problem outlines a cryptographic scenario where we have a onew... View the full answer
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these programming questions
-
Discuss the two concept Marginal Costing and Absorption costing. Please be detail and also provide examples.
-
Let V denote the set of positive real numbers. Define the operation of scalar multiplication, denoted , by x = x for each x R+ and for any real number a. Define the operation of addition, denoted...
-
Let D18 denote the set of positive divisors of 18. For d D18 let Sd = {n|0 < n 18 and gcd(n, 18) = d}. (a) Show that the collection Sd, d D18, provides a partition of {1, 2, 3, 4, ... , 17, 18}....
-
In Problems 4158, fill in the blank to form a correct inequality statement. If x < 5, then x - 5_ 0.
-
In a double-slit arrangement of Figure 37.5, d = 0.150 mm, L = 140 cm, A = 643 nm, and y = 1.80 cm. (a) What is the path difference = for the rays from the two slits arriving at P? (b) Express this...
-
A triploid plant has 18 chromosomes (i.e., 6 chromosomes per set). If we assume a gamete has an equal probability of receiving one or two copies of each of the six types of chromosome, what are the...
-
To study the effect of using digital devices in the classroom on exam performance, researchers divided 726 undergraduate students into three groups, including a group that was allowed to use digital...
-
It costs a pharmaceutical company $40,000 to produce a 1000-pound batch of a drug. The average yield from a batch is unknown but the best case is 90% yield (that is, 900 pounds of good drug will be...
-
85,000 and that the price p is a P Suppose that the demand function for a product is given by D(p) = function of time given by p= 1.7t+7, where t is in days. a) Find the demand as a function of time...
-
The half-life for a link on Twitter is 2.8 hours. Write an exponential function T that gives the percentage of engagements remaining on a typical Twitter link after 1 hours. Estimate this percentage...
-
10. You calculated the following cashflows for a machine: t=0 t=1 t=3 -1200 600 320 The current interest rate is 6%. If you could sell the machine in year 2. What must be the minimum selling price...
-
Derive and explain the Dual Problem of the Consumer Theory assuming that U(x,y) = xy and P x x+P y y = B .
-
In the competing values framework (CVF), the action imperative to _____ arises because an effective manager is expected to have the skills to promote and encourage adaptability and innovation in his...
-
Modify the implementation of queue data structure such that the array used to implement the queue is dynamically allocated. And deallocate the dynamically allocate queue and implement the main.cpp...
-
a) In the U.S., there is a severe kidney shortage, where thousands of individuals die annually waiting for a kidney. On the graph , demonstrate what would happen if the U.S. allowed a market for...
-
Medfarm came up with a new treatment (Drug F) that costs 100,000 for life-threatening Lymphangitis that infects the fishermen. The market has the following treatments Drug Cost Life A |@|||m| B C D E...
-
Nancy has W-2 gross earnings of $137000. A total of $9700 of her income was deferred to her company's retirement plan, and $5800 was used to pay for her healthcare premiums. What will be her W-2...
-
The nitrogen atoms in N2 participate in multiple bonding, whereas those in hydrazine, N2H4, do not. (a) Draw Lewis structures for both molecules. (b) What is the hybridization of the nitrogen atoms...
-
Draw a state-transition diagram for a string-matching automaton for the pattern ababbabbababbababbabb over the alphabet = {a, b}.
-
Consider a sorting problem in which we do not know the numbers exactly. Instead, for each number, we know an interval on the real line to which it belongs. That is, we are given n closed intervals of...
-
Prove that by using the linearity property of summations. E=1 0(ft(i)) = 0(E-1 fi(i)) un Lk=1 Lk=1
-
The universal gas constant \(R_{0}\) is equal to \(49,700 \mathrm{ft}^{2} /\left(\mathrm{s}^{2} \cdot{ }^{\circ} \mathrm{R} ight)\), or \(8310 \mathrm{~m}^{2} /\left(\mathrm{s}^{2} \cdot \mathrm{K}...
-
Dimensionless combinations of quantities (commonly called dimensionless parameters) play an important role in fluid mechanics. Make up five possible dimensionless parameters by using combinations of...
-
A tank contains \(500 \mathrm{~kg}\) of a liquid whose specific gravity is 2. Determine the volume of the liquid in the tank.
Study smarter with the SolutionInn App