1. (15 Points) There is nothing exclusively special about strings and XOR in onetime pad. We...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
1. (15 Points) There is nothing exclusively special about strings and XOR in onetime pad. We can get the same properties using integers mod n and addition mod n. This problem considers a variant of onetime 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 onetime 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 onetime uniform ciphertext security Enc(k, m): c = (k m) mod n 2. (10 Points) Alice is using onetime pad and notices that when her key is the allzeroes 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 allzeroes key. She modifies KeyGen to choose a key uniformly from {0, 1}"\{0"}, the set of all nbit 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 onetime 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 onetime perfect se curity. 4. (10 Points) Consider the following variant of onetime perfect security, where Eve can ob tain two ciphertexts (on chosen plaintexts) encrypted under the same key, called twotime perfect security We say that an encryption scheme is twotime perfectly secure if Vm11, m12, m21, M22 EM chosen by Eve, the following distributions are identical: 12 • 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 onetime 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 onetime perfect security, but you don't know which one. Using both &₁ and E2 (but no other encryption scheme), construct an encryption scheme with onetime 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 onetime 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 bruteforce attacks are therefore valid. 1. (15 Points) There is nothing exclusively special about strings and XOR in onetime pad. We can get the same properties using integers mod n and addition mod n. This problem considers a variant of onetime 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 onetime 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 onetime uniform ciphertext security Enc(k, m): c = (k m) mod n 2. (10 Points) Alice is using onetime pad and notices that when her key is the allzeroes 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 allzeroes key. She modifies KeyGen to choose a key uniformly from {0, 1}"\{0"}, the set of all nbit 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 onetime 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 onetime perfect se curity. 4. (10 Points) Consider the following variant of onetime perfect security, where Eve can ob tain two ciphertexts (on chosen plaintexts) encrypted under the same key, called twotime perfect security We say that an encryption scheme is twotime perfectly secure if Vm11, m12, m21, M22 EM chosen by Eve, the following distributions are identical: 12 • 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 onetime 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 onetime perfect security, but you don't know which one. Using both &₁ and E2 (but no other encryption scheme), construct an encryption scheme with onetime 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 onetime 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 bruteforce 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: 9780132570848
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...

how to solve this problems in cryptography? Problems 1. (15 Points) There is nothing exclusively special about strings and XOR in onetime 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...

A section of sheet steel 3 mm thick is cut and bent into the machine component shown. Knowing that the density of the steel l is 7860 kg/m3, determine the mass products of inertia Ixy, Iyz, and Izx...

On March 1, 2014, JenStar Inc. issued at par an $80,000, 6%, threeyear bond. Interest is to be paid quarterly beginning May 31, 2014. JenStars yearend is July 31. A partial payment schedule is...

Consider two alternatives, each of which will accomplish the same EPAmandated pollution control. Using an incremental IRR analysis, determine the preferred alternative assuming MARR is 20...

Use Solver to create a Sensitivity Report for question 20 at the end of Chapter 3 and answer the following questions: a. How much would electric trimmers have to cost for the company to consider...

TheOnlyWizKid, Montclair State University Download and connect to the raw data Market Caps of S_P500 Companies 20082015.xls on Canvas>Files> Tableau Data Files using Tableau. The Excel file lists...

A sequential circuit is given in Figure 413. Figure 413 (a) Add the necessary logic and/or connections to the circuit to provide an asynchronous reset to state A = 1, B = 0 for signal Reset = 0....

You are asked to do the preliminary design calculations of a container ship of 1400 TEU. A litterature search yields the following results: TEU DWT 1499 22447 1453 23617 1346 21002 1417 22620 1467...

After reading the article "Television and the Decline of Deference" what does "deference" mean? Are we currently a society without much "deference"  and that mass media has played a major role in...

Discuss how the health care external environment differs from that faced by the average U.S. company. Explain this in terms of both the industry and macroenvironment levels ?

In the Case: Great Western Hospital: Highrisk Pregnancy Care What risk issues that are confronting the hospital.? What options they had to "manage" those risk issues ? And which of those options...

1. Why do you think people are so motivated to come up with attributions for behavior? 2. Can you think of a situation when you have committed the error of over attribution with someone? What...

The three types of face needsfellowship face, competence face, autonomy facewhich is the most important to you? Under what circumstances do the others become more important? Can you think of a...

Present value and future value of annuityimmediate and annuitydue. Prove the following identities : (1) (i) 1 (m) a nli m + i(m); 'nli 1 (ii) (m) 'nli 1 + d(m); (m) 'nli (iii) = [ + : ;(m) + m...

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 processcosting 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)...

What ethical issues might arise during the factfinding process, and how should they be handled?

Why are conventional files easy to design and implement?

Determine the business's or organization's requirements through interviews, forms, surveys, JAD, and the like, and create the appropriate models and studies for the Web site. Don't forget to consider...
Study smarter with the SolutionInn App