1. (15 Points) There is nothing exclusively special about strings and XOR in one-time pad. We...
Fantastic news! We've Found the answer you've been seeking!
Question:
![1. (15 Points) There is nothing exclusively special about strings and XOR in one-time pad. We can get the](https://dsd5zvtm8ll6.cloudfront.net/questions/2023/11/654378e1ab8a5_1698920672298.jpg)
![3. (10 Points) The following scheme encrypts a plaintext by simply reordering its bits, according to the](https://dsd5zvtm8ll6.cloudfront.net/questions/2023/11/65437900b8274_1698920703767.jpg)
Transcribed Image Text:
1. (15 Points) There is nothing exclusively special about strings and XOR in one-time pad. We can get the same properties using integers mod n and addition mod n. This problem considers a variant of one-time pad, in which the keys, plaintexts, and ciphertexts are all elements of Zn instead of {0, 1}". (a) What is the decryption algorithm that corresponds to the following encryption algo- rithm? Enc (k, m) : c = (k + m) mod n Show that the resulting scheme satisfies correctness (b) Show that the above scheme satisfies one-time uniform ciphertext security (c) It's not just the distribution of keys that is important. The way that the key is combined with the plaintext is also important. Show that a scheme with the following encryption algorithm does not satisfy one-time uniform ciphertext security Enc(k, m): c = (k m) mod n 2. (10 Points) Alice is using one-time pad and notices that when her key is the all-zeroes string k = 0", then Enc(k, m) = m and her message is sent in the clear! To avoid this problem, she decides to modify KeyGen to exclude the all-zeroes key. She modifies KeyGen to choose a key uniformly from {0, 1}"\{0"}, the set of all n-bit strings except 0. In this way, she guarantees that her plaintext is never sent in the clear. (a) Describe an attack demonstrating that the modified scheme does not satisfy one-time uniform ciphertext security 3. (10 Points) The following scheme encrypts a plaintext by simply reordering its bits, according to the secret permutation k: K = { permutations of {1, ..., n}} M = {0,1}" C = {0,1}" Key Gen(1"): k + K return k Enc(k, m): for i:= 1 to n : Ck(i) := mi return C1...Cn Dec (k, c): for i:= 1 to n : mi - Ck(i) return mı...mn Describe an attack demonstrating that the scheme does not satisfy one-time perfect se- curity. 4. (10 Points) Consider the following variant of one-time perfect security, where Eve can ob- tain two ciphertexts (on chosen plaintexts) encrypted under the same key, called two-time perfect security We say that an encryption scheme is two-time perfectly secure if Vm11, m12, m21, M22 EM chosen by Eve, the following distributions are identical: 1-2 • D₁ := {c₁ Enc(k, m11), C₂ = Enc(k, m12); k ← KeyGen (1")} • D₂ = {c₁ = Enc(k, m21), C2 = Enc(k, m22); k ← KeyGen (1")} Describe an attack demonstrating that one-time pad does not satisfy this security definition. 5. (15 Points) Let &₁ = (KeyGen₁, Enc₁, Dec₁) and E2 = (KeyGen2, Enc2, Dec₂) be two encryption schemes such that only one of them satisfies one-time perfect security, but you don't know which one. Using both &₁ and E2 (but no other encryption scheme), construct an encryption scheme with one-time perfect security and prove its security. 6. (extra credit, 15 Points) Prove that if an encryption scheme has |K| < |M (i.e. there are fewer possible keys than there are possible messages), then it cannot satisfy one-time perfect security. Try to structure your proof as an explicit attack on the scheme, i.e. a distinguisher between the distributions D₁ and D₂. Hint: There is no restriction on the running time of the attacker. Exhaustive brute-force attacks are therefore valid. 1. (15 Points) There is nothing exclusively special about strings and XOR in one-time pad. We can get the same properties using integers mod n and addition mod n. This problem considers a variant of one-time pad, in which the keys, plaintexts, and ciphertexts are all elements of Zn instead of {0, 1}". (a) What is the decryption algorithm that corresponds to the following encryption algo- rithm? Enc (k, m) : c = (k + m) mod n Show that the resulting scheme satisfies correctness (b) Show that the above scheme satisfies one-time uniform ciphertext security (c) It's not just the distribution of keys that is important. The way that the key is combined with the plaintext is also important. Show that a scheme with the following encryption algorithm does not satisfy one-time uniform ciphertext security Enc(k, m): c = (k m) mod n 2. (10 Points) Alice is using one-time pad and notices that when her key is the all-zeroes string k = 0", then Enc(k, m) = m and her message is sent in the clear! To avoid this problem, she decides to modify KeyGen to exclude the all-zeroes key. She modifies KeyGen to choose a key uniformly from {0, 1}"\{0"}, the set of all n-bit strings except 0. In this way, she guarantees that her plaintext is never sent in the clear. (a) Describe an attack demonstrating that the modified scheme does not satisfy one-time uniform ciphertext security 3. (10 Points) The following scheme encrypts a plaintext by simply reordering its bits, according to the secret permutation k: K = { permutations of {1, ..., n}} M = {0,1}" C = {0,1}" Key Gen(1"): k + K return k Enc(k, m): for i:= 1 to n : Ck(i) := mi return C1...Cn Dec (k, c): for i:= 1 to n : mi - Ck(i) return mı...mn Describe an attack demonstrating that the scheme does not satisfy one-time perfect se- curity. 4. (10 Points) Consider the following variant of one-time perfect security, where Eve can ob- tain two ciphertexts (on chosen plaintexts) encrypted under the same key, called two-time perfect security We say that an encryption scheme is two-time perfectly secure if Vm11, m12, m21, M22 EM chosen by Eve, the following distributions are identical: 1-2 • D₁ := {c₁ Enc(k, m11), C₂ = Enc(k, m12); k ← KeyGen (1")} • D₂ = {c₁ = Enc(k, m21), C2 = Enc(k, m22); k ← KeyGen (1")} Describe an attack demonstrating that one-time pad does not satisfy this security definition. 5. (15 Points) Let &₁ = (KeyGen₁, Enc₁, Dec₁) and E2 = (KeyGen2, Enc2, Dec₂) be two encryption schemes such that only one of them satisfies one-time perfect security, but you don't know which one. Using both &₁ and E2 (but no other encryption scheme), construct an encryption scheme with one-time perfect security and prove its security. 6. (extra credit, 15 Points) Prove that if an encryption scheme has |K| < |M (i.e. there are fewer possible keys than there are possible messages), then it cannot satisfy one-time perfect security. Try to structure your proof as an explicit attack on the scheme, i.e. a distinguisher between the distributions D₁ and D₂. Hint: There is no restriction on the running time of the attacker. Exhaustive brute-force attacks are therefore valid.
Expert Answer:
Answer rating: 100% (QA)
Information encoding techniques This same body of something like the transmission and the fingerprint among other components are encrypted and decrypted using this methodology type The methodology uni... View the full answer
Related Book For
Management Accounting
ISBN: 978-0132570848
6th Canadian edition
Authors: Charles T. Horngren, Gary L. Sundem, William O. Stratton, Phillip Beaulieu
Posted Date:
Students also viewed these computer network questions
-
Big Tex decides to hire a new manager to help him out around the hotel, and he will pay her $40,000 per year. Calculate the rooms sold, occupancy %, and sales dollars he will need to break even after...
-
Physics Concepts in Scuba Diving 1. Provide an analysis of scuba diving in relation to physics including one physics concept relating to forces and newton's laws and one physics concept relating to...
-
how to solve this problems in cryptography? Problems 1. (15 Points) There is nothing exclusively special about strings and XOR in one-time pad. We can get the same properties using integers mod n and...
-
Why does Erasmus attack Church officials in his In Praise of Folly? O For spending money on lavish art O For not allowing clergy to marry O For supporting military campaigns O For selling pardons and...
-
If a friend asked you how much money you had to spend, what items would you include in your response?
-
In the Payday Loans feature on page 129, we examined these short-term, high-interest loans. Go to the Responsible Lending Organization website at www.responsiblelending.org/payday-lending/. What are...
-
The financial statements for the Columbia Sportswear Company can be found in Appendix A at the end of this book. Required Answer the following questions: a. How many shares of common stock are...
-
A firm that sells software services has been piloting a new product and has records of 500 customers who have either bought the services or decided not to. The target value is the estimated profit...
-
An inventor has developed a new, energy-efficient lawn mower engine. He claims that the engine will run continuously for 310 minutes on a single gallon of regular gasoline. From his stock of...
-
Design a beam of ASTM A36 steel with allowable bending stress of 160 MPa to support the load shown in Figure P4-33. Assume a standard wide flange beam from Appendix F, or some other source can be...
-
Elora must have RM120,000 in order to buy a piece of vacant land. She plans to save RM2,000 per year in her saving account with Amanah Bank that pays 12 percent interest rate compounded...
-
During June, 2022, Ms. Janet Houston sells capital property with an ACB of $112,500, for $172,300. She receives a down payment of $33,000 in cash, with the balance only due at the end of the...
-
(A) How do the following expressions simplify? x, x, x7 What do these expressions have in common? Write a summary statement. (B) How do the following expressions simplify? 2, 6, What do these...
-
Roberta's salary is $163,865.00 in 2023. Roberta is paid on a semimonthly basis, is unmarried and has one qualifying dependent under the age of 17 per her Form W-4. Use the Percentage Method Tables...
-
What are the implications of allostasis and allostatic load in the context of homeostasis, and how do these concepts expand our understanding of the physiological impact of chronic stress and...
-
There are numerous models for Health, safety and security management systems, all of which need to be customized to the individual workplace. List three Health, safety and security management...
-
Please think about your firm's (or others') code of ethics and how codes are (or should be) related to codes of ethics. What is the role of an ethics hotline? How are laws related to ethical codes?...
-
We all experience emotions, but some people disguise their true feelings better than others. Do you think this is a helpful or harmful thing to do? Under what conditions do you think it would be most...
-
Give three examples of industries where process-costing systems are probably used.
-
Maritime Desserts Inc. (MDI) produces a variety of premium cheesecakes and sells them in individual packages directly to retail customers and in packages of 10 cakes to restaurants in New Brunswick,...
-
Fill in the unknowns: * Degree of completion: direct materials, 80%; conversion costs, 40%. Degree of completion: direct materials, 40%; conversion costs, 10%. (Step 2) Equivalent Units (Step 1)...
-
Monopoly is unlike perfect competition in that a. a monopolists price is greater than marginal cost. b. there are no barriers to entry into a monopoly industry. c. a monopolist earns an economic...
-
A price-taking firm and a monopolist are alike in that a. price equals marginal revenue for both. b. both maximize profits by choosing an output where marginal revenue equals marginal cost, provided...
-
Which of the following statements is true? a. Monopoly results in smaller output and a higher price than would be the case under perfect competition. b. The monopolist produces at an output where P >...
![Mobile App Logo](https://dsd5zvtm8ll6.cloudfront.net/includes/images/mobile/finalLogo.png)
Study smarter with the SolutionInn App