Ask Computer Engineering Expert

1. Consider the one time pad encryption scheme to encrypt a 1-bit message. Replace the XOR operation with another operation X. For which X does the resulting scheme satisfy perfect secrecy? (Recall: OR(a,b)=1 if and only if at least one of a,b=1; AND(a,b)=1 if and only if both a,b=1; NOT(a)=1 if and only if a=0.)

A. X = AND

B. X = OR

C. X = NOT(XOR)

D. none of the above

 

2. Which of these are valid properties of the one time pad? 

 

A. satisfies perfect secrecy

B. the length of the key is equal to the length of the message

C. encryption and decryption are very efficient

D. all of the above

3. Which of these statements summarizes an equivalent form of the perfect secrecy notion?

A.The probability of the ciphertext conditioned by one plaintext is the same as the probability of the ciphertext conditioned by another plaintext

B. Knowledge of the plaintext does not affect the probability of the ciphertext

C. The probability that an adversary, after returning two plaintexts, guesses from a ciphertext c which of these two plaintexts was encrypted as c is 1/2

D. All of the above

4. Consider the one-time pad encryption scheme to encrypt a 1-bit message m. For b=0,1, let E[b] be the event "message m is = b", assume prob(E[0])=p and prob(E[1])=1-p, for some p in [0,1], and let F be the event "ciphertext C is = 1". Compute the probability of event E[0] given that event F happens, when p=0.3. Then select the answer that is closest to this probability.

A. 0.125

B. 0.375

C. 0.625

D. 0.875

5. You know that a meaningful plaintext in a language with a 26-letter alphabet, like English, is encrypted using either the mono-alphabetic substitution cipher or the poly-alphabetic substitution cipher (with a key of t random numbers in [1,26], for a known value of t; here, assume t=20), but you do not know which one. You want to find the plaintext (with probability 1) and are planning to first use an exhaustive (or brute-force) search attack assuming that the mono-alphabetic substitution cipher was used, and then use another exhaustive (or brute-force) search attack assuming that the poly-alphabetic substitution cipher was used. Unfortunately you realize that you have no time for both attacks, and thus decide to run the attack that requires the smallest number of decryption attempts. Answer the following questions: (a) Which cipher do you assume in the attack you run? (b) Which number is closer to the number of decryption attempts made by your attack? 

A. mono-alphabetic substitution cipher; (b) 2^{120}

B. mono-alphabetic substitution cipher; (b) 2^{140}

C. poly-alphabetic substitution cipher; (b) 2^{120}

D. poly-alphabetic substitution cipher; (b) 2^{140}

 

Explain your rationale for choosing this answer and why you rejected each of the others.

6. In an encryption scheme, let Enc denote the encryption algorithm, Dec denote the decryption algorithm, and A denote the adversary's algorithm. Furthermore, let e(n), d(n), denote the running times of algorithms Enc, Dec, respectively, and let a(n) denote the minimum running time that an attacker takes to break any such scheme, where n is the security parameter. When designing this scheme following the principles of modern cryptography, which of these relationships would you use to choose your algorithms?

A. e(n),d(n),a(n)=O(n^c) for some constant c

B. e(n)=O(n^c) and d(n),a(n)=Omega(2^{cn}) for some constant c

C. e(n),d(n)=O(n^c) and a(n)=Omega(2^{cn}) for some constant c

D. e(n),d(n),a(n)=Omega(2^{cn}) for some constant c

7. For which X,Y in {o, O, Theta, Omega, omega}, do the relationships t(n)+t'(n) = X(max(t(n),t'(n))) and  t(n)+t'(n) = Y(min(t(n),t'(n))) hold for all t,t' such that t(n),t'(n)>0 ?

 

A. X=Theta, Y=Theta

B. X=Theta, Y=Omega

C. X=Omega, Y=Theta

D. X=omega, Y=Theta

. Assume you want to construct a public-key cryptosystem using the principles of modern cryptography, and you are allowed to choose a language L such that your cryptosystem can be proved secure assuming that deciding L is hard; from which of the following complexity classes would you pick L?

A. P

B. BPP

C. NP minus P

D. NP minus BPP

9. Let L1, L2 be languages and let X,Y be either P or NP. Consider the statement: if L1 is polynomial-time reducible to L2, and L2 is in X, then L1 is in Y. Which of the following holds:

A. When X=P and Y=P, then the statement is true

B. When X=P and Y=NP, then the statement is true

C. When X=NP and Y=NP, then the statement is true

D. All of the above

10. Informally, BPP is the class of languages that can be decided by a probabilistic algorithm in polynomial time with an error probability of at most 1/3 on any instance. More formally, a language L is in BPP if there exists a probabilistic algorithm A (i.e., an algorithm that is allowed to use a polynomial-length string of random bits) that runs in polynomial time and satisfies the following: if x is in L then A(x) returns 1 with probability at least 2/3; if x is not in L then A(x) returns 1 with probability at most 1/3. By performing independent repetitions of algorithm A and taking the majority output, one can amplify the (2/3; 1/3) gap to (1 - 2^{-k}; 2^{-k}), which is extremely close to (1,0). BPP seems to well capture the class of problems that can be efficiently computed

by a computer today. It is known that P is in BPP, and while it is conjectured that P = BPP, this is actually unknown. It is also unknown whether BPP is in NP. Consider the following statements:
1) if L1 is polynomial-time reducible to L2, and L2 is in P, then L1 is in BPP;
2) if L1 is polynomial-time reducible to L2, and L2 is in BPP, then L1 is in NP.
They are, respectively:

 

A. true, unknown

B. unknown, unknown

C. unknown, false

D. true, false

Explain your rationale for choosing this answer and why you rejected each of the others.

11. Consider the following functions.
1) g1:{0,1}n-->{0,1}n, defined as g1(x)=x xor p, for each x in {0,1}n and for some known value p in {0,1}n
2) g2:{0,1}n-->{0,1}n, defined as a monotone function over the set {0,1}n
3) g3:{0,1}2n-->{0,1}n, defined as g3(x1,x2)=x1 xor x2 for each (x1,x2) in {0,1}2n

Which of the following is true?

A. g1 is one-way, g2 and g3 are not one-way

B. g2 is one-way, g1 and g3 are not one-way

C. g3 is one-way, g1 and g2 are not one-way

D. none of them is one-way

 

12. For a still merely intuitive notion of "secure" (e.g., it is hard to guess info about the plaintext from the ciphertext), which cryptographic primitives are sufficient to construct a "secure" public-key cryptosystem? 

 

A. a one-way function f and a hard-core predicate P for f

B. a one-way trapdoor function f and a hard-core predicate P for f

C. a one-way trapdoor permutation f

D. a hard-core predicate P for f

 

13. Consider algorithms the following algorithms.  Which one(s) among these does not run in polynomial time in its input length?

ALGORITHM A

The extended Euclidean algorithm eGCD

Input: Integers a, b with a >= b > 0

Output: (d,X,Y ) with d = gcd(a, b) and Xa + Y b = d

 

if b divides a:

     return (b,0, 1)

else

      Compute integers q, r with a = qb + r and 0 <= r < b

      (d,X,Y) := eGCD(b; r) /* note that Xb + Y r = d */

      return (d,Y,X - Y q)

 

ALGORITHM B

Computing modular inverses

 

Input: Modulus N; element a

Output: a-1 mod n (if it exists)

 

(d,X,Y) := eGCD(a,N) /* note that Xa + Y N = gcd(a, N) */

if d ~=  1 return "a is not invertible modulo N"

else return (X mod N)

ALGORITHM C

A naive algorithm for modular exponentiation

 

Input: Modulus N; base a contained in ZN; exponent b > 0

Output: ab mod N

 

x := 1

for i = 1 to b:

    x := x * a mod N

return x

ALGORITHM D

Algorithm ModExp for efficient modular exponentiation

 

Input: Modulus N; base a contained in  ZN; exponent b > 0

Output: ab mod N

 

if b = 1 return a

else

    if b is even:

        t := ModExp (N, a, b/2)

        return (t2 mod N)

if b is odd:

        t := ModExp (N, a, (b-1)/2)

        return a * t2 mod N

 

A. A and B

B. A and C 

C. B and D

D. C

 

14. Factoring is the problem of computing, on input a positive integer n, a factorization of n in terms of prime powers. This problem can be "easy (i.e., there exists a polynomial-time algorithm that solves it) or "(conjectured to be) hard" (i.e., there seems to be no polynomial-time algorithm that solves it) depending on the (sub)set of integers from which n is chosen. In which of these cases factoring n is easy?

A. n is a power of 2

B. n is a prime

C. n is a prime power

D. All of the above

15. Factoring is the problem of computing, on input a positive integer n, a factorization of n in terms

of integer powers of prime numbers. This problem can be "easy" (i.e., there exists a polynomial-time algorithm that solves it) or "(conjectured to be) hard" (i.e., there seems to be no polynomial-time algorithm that solves it) depending on the (sub)set of integers from which n is chosen. De?ne the trial division algorithm D to solve the factoring problem and study its running time t_D(n). Given this algorithm and its running time, we want to infer considerations on factoring n being easy or conjectured to be hard when n is chosen among products of two primes (i.e., n = pq for some primes p, q). Let m_easy(n) be a value for min(p, q) such that factoring n is easy and m_hard(n) be a value for min(p, q) such that factoring n may be conjectured to be hard. Which functions would you select as most meaningful for t_D(n), m_easy(n), m_hard(n)?

A.t_D(n)=O(n 2); m_easy(n)=O(log n); m_hard(n)=O(square root of n) 

B. t_D(n)=O(square root of n); m_easy(n)=O(square root of n); m_hard(n)=O(n)

C. t_D(n)=O(square root of n); m_easy(n)=O(polylog n); m_hard(n)=O(n)

D. t_D(n)=O(square root of n); m_easy(n)=O(polylog n); m_hard(n)=O(square root of n)

Explain your rationale for choosing this answer and why you rejected each of the others.

Computer Engineering, Engineering

  • Category:- Computer Engineering
  • Reference No.:- M9171563
  • Price:- $75

Priced at Now at $75, Verified Solution

Have any Question?


Related Questions in Computer Engineering

Does bmw have a guided missile corporate culture and

Does BMW have a guided missile corporate culture, and incubator corporate culture, a family corporate culture, or an Eiffel tower corporate culture?

Rebecca borrows 10000 at 18 compounded annually she pays

Rebecca borrows $10,000 at 18% compounded annually. She pays off the loan over a 5-year period with annual payments, starting at year 1. Each successive payment is $700 greater than the previous payment. (a) How much was ...

Jeff decides to start saving some money from this upcoming

Jeff decides to start saving some money from this upcoming month onwards. He decides to save only $500 at first, but each month he will increase the amount invested by $100. He will do it for 60 months (including the fir ...

Suppose you make 30 annual investments in a fund that pays

Suppose you make 30 annual investments in a fund that pays 6% compounded annually. If your first deposit is $7,500 and each successive deposit is 6% greater than the preceding deposit, how much will be in the fund immedi ...

Question -under what circumstances is it ethical if ever to

Question :- Under what circumstances is it ethical, if ever, to use consumer information in marketing research? Explain why you consider it ethical or unethical.

What are the differences between four types of economics

What are the differences between four types of economics evaluations and their differences with other two (budget impact analysis (BIA) and cost of illness (COI) studies)?

What type of economic system does norway have explain some

What type of economic system does Norway have? Explain some of the benefits of this system to the country and some of the drawbacks,

Among the who imf and wto which of these governmental

Among the WHO, IMF, and WTO, which of these governmental institutions do you feel has most profoundly shaped healthcare outcomes in low-income countries and why? Please support your reasons with examples and research/doc ...

A real estate developer will build two different types of

A real estate developer will build two different types of apartments in a residential area: one- bedroom apartments and two-bedroom apartments. In addition, the developer will build either a swimming pool or a tennis cou ...

Question what some of the reasons that evolutionary models

Question : What some of the reasons that evolutionary models are considered by many to be the best approach to software development. The response must be typed, single spaced, must be in times new roman font (size 12) an ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Why might a bank avoid the use of interest rate swaps even

Why might a bank avoid the use of interest rate swaps, even when the institution is exposed to significant interest rate

Describe the difference between zero coupon bonds and

Describe the difference between zero coupon bonds and coupon bonds. Under what conditions will a coupon bond sell at a p

Compute the present value of an annuity of 880 per year

Compute the present value of an annuity of $ 880 per year for 16 years, given a discount rate of 6 percent per annum. As

Compute the present value of an 1150 payment made in ten

Compute the present value of an $1,150 payment made in ten years when the discount rate is 12 percent. (Do not round int

Compute the present value of an annuity of 699 per year

Compute the present value of an annuity of $ 699 per year for 19 years, given a discount rate of 6 percent per annum. As