Cryptography, computer science, Basic Computer Science

Assignment Help:
Question 1

Consider the one-time pad encryption scheme to encrypt a 1-bit message m,
and assume m is chosen with uniform distribution from message space M={0,1}.
Let E1 be the event "message m is = 1" and let E2 be the event
"ciphertext c is = 0". What is the probability that both event E1 and
event E2 happen?

Answer

a.0
b.0.5
c.0.25
d.1


Question 2

Consider the one-time pad encryption scheme to encrypt a 1-bit message m,
and assume m is chosen with uniform distribution from message space M={0,1}.
For b=0,1, let E[b] be the event "message m is = b" and let F be the event
"ciphertext c is = 1". What is the probability that event F happens?


Answer

a.0
b.0.5
c.0.25
d.1

Question 3

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".
What is the probability of event E[0] given that event F happens?
Use the Bayes theorem to find your answer.

Answer

a.1
b.0.5
c.1-p
d.p

Question 4

Assume a meaningful plaintext is encrypted using the shift cipher.
How many encryption attempts are sufficient for an exhaustive (or brute-force)
search attack to find the plaintext with probability at least 1/2?

Answer

a.1
b.2
c.13
d.26

Question 5

Assume a meaningful plaintext is encrypted using the mono-alphabetic substitution cipher. How many encryption attempts are sufficient for an exhaustive (or brute-force)
search attack to find the plaintext (with probability 1)?

Answer

a.1
b.2
c.26
d.26!

Question 6

Assume a meaningful plaintext is encrypted using the poly-alphabetic substitution
cipher (with t random numbers in [0,26], for a known t).
How many encryption attempts are sufficient for an exhaustive (or brute-force)
search attack to find the plaintext (with probability 1)?

Answer


a.1
b.t
c.26
d.26 to the t-th power


Question 7

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

Answer

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


Question 8

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

Answer

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

Question 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:

Answer

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

Question 10

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?


Answer

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

Question 11

For which X,Y in {o, O, Theta, Omega, omega}, do the relationships (log n)^2 = X(n^{1/2}) and n^2 = Y(2^n) hold?


Answer

a.X=o, Y=o
b.X=O, Y=Theta
c.X=o, Y=Theta
d.X=Theta, Y=O

Question 12

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 ?

Answer

a.X=Theta, Y=Theta
b.X=Theta, Y=Omega
c.X=Omega, Y=Theta
d.X=omega, Y=Theta


Question 13

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:

Answer

a.true, unknown
b.unknown, unknown
c.unknown, false
d.true, false



Question 14

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?

Answer

a.P
b.BPP
c.NP minus P
d.NP minus BPP

Question 15

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

Answer

a.X = AND
b.X = OR
c.X = NOT(XOR)
d.none of the above

Related Discussions:- Cryptography, computer science

Explain data transfer and arithmetic operations, Question 1 Convert the fo...

Question 1 Convert the following binary numbers to decimal 101110 1110101 110110 101010 110010 Question 2 Explain CPU module and types of transfers betwe

Uniform path cost search-artificial intelligence, Uniform Path Cost Search-...

Uniform Path Cost Search-Artificial intelligence A breadth first search will search the solution with the shortest path length from the first state to the goal state. Though, t

What is the importance of using digital certificates, QUESTION a) Crypt...

QUESTION a) Cryptography is a set of techniques and mathematical algorithms. Describe four important areas where cryptography must be applied b) What is the importance of us

Perverse software, Perverse software: Perverse software is a program w...

Perverse software: Perverse software is a program which causes hindrances in other programs execution in such a way resulting in modification or complete destruction of data w

Find shortest path in network, Find shortest path from node 1 to node 10 in...

Find shortest path from node 1 to node 10 in the network shown in figure, also find shortest path from node 3 to node 10. Please write all steps to finding shortest path mechanism

Mini computers and micro computers, Mini Computers and Micro Computers: ...

Mini Computers and Micro Computers: The mini computers are intermediate in power, and may function as small mainframe computers. They are often dedicated to a particular purpo

Computer science, You recently returned some homework I completed but i lef...

You recently returned some homework I completed but i left of the final 10 questions. Should not take long just needs some commands interpreted. How much will it cost for me to get

File sharing architecture, File Sharing Architecture:   The developmen...

File Sharing Architecture:   The development of microprocessor, PC and LAN transformed dumb terminals into -smart? clients. This brought a complete change in the computing env

Explain need for model view controller(mvc), Question 1 What is HTTP? How ...

Question 1 What is HTTP? How does it work? Question 2 What are the various methods of HttpServletResponse interface? Question 3 What is Web server? What are the va

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd