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:
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...
-
Use a graphing calculator to complete (a) and (b). 1. 2. lim f(x)? lim f(x).
-
How does depreciation spread the capital expenditure of a project over the life of the capital asset? Why is using MACRS usually beneficial to a company versus using straight-line depreciation?
-
The customer billing function of the Robinson Company, a small paint manufacturer, is attended to by a receptionist, an accounts receivable clerk and a cashier who also serves as a secretary. The...
-
James Burrow is the loan officer for the National Bank of Dallas. National has a loan of $325,000 outstanding to Regional Delivery Service, a company specializing in delivering products of all types...
-
Payton took a friend for a birthday dinner. The total bill for dinner was $44.32 (including tax and a tip). If Payton paid a 19.6% tip, what was his bill before adding the tip? (Round your answer to...
-
KYC's stock price can go up by 15 percent every year, or down by 10 percent. Both outcomes are equally likely. The risk free rate is 5 percent, and the current stock price of KYC is 100. (a) Price a...
-
Determine the moment of inertia for the centroidal axes on x and y-axis of the area shown if radiuses of gyration for x and y are the following rxc = 9.76 in. and ryc = 3.82 in. PL1 1/2 x 15 PL1 1/2...
-
List three ways to get input from the console and convert that input to the desired data type.
-
What experiences have you had using stress management techniqueseither formally or informally? For example, do you meditate? Do you find that physical exercise helps you relieve stress? Does talking...
-
The Nelson partnership begins business on July 17, 2019. It is not able to use business purpose to support a tax year. The four partners, their interests in partnership capital and profits, and their...
-
Write ARM assembly language code that handles a breakpoint. It should save the necessary registers, call a subroutine to communicate with the host, and upon return from the host, cause the...
-
Study the Heisenberg model of a ferromagnet, based on the interaction (12.3.6), in the mean field approximation and show that this also leads to a phase transition of the kind met in the Ising model....
-
Communication Case: Simba Clark, the director of Shareholder Services of a large multinational corporation head- quartered in the U.S., has asked you for help. Simba will address the shareholders...
-
Dr. Chan obtained a $15,000 demand loan at prime plus 1.5% on September 13 from the Bank of Montreal to purchase a new dental X-ray machine. Fixed payments of $700 will be deducted from the dentists...
-
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)...
-
Derive the mass matrix of the system shown in Fig. 5.42. 00000 2m 8(t) * 2m ellee x(t) m 00000 FIGURE 5.42 Rigid bar connected to masses and springs.
-
Four identical springs, each having a stiffness \(k\), are arranged symmetrically at \(90^{\circ}\) from each other, as shown in Fig. 2.65. Find the influence coefficient of the junction point in an...
-
Derive the equations of motion of the system shown in Fig. 6.34. 000 m 00000 m 2m k 000000 2k 000 3k FIGURE 6.34 Three-degree-of-freedom spring-mass system.
Study smarter with the SolutionInn App