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

Posted Date: 2/10/2013 1:44:48 PM | Location :

Ask an Expert

Related Discussions:- Cryptography, Basic Computer Science, Assignment Help, Ask Question on Cryptography, Basic Computer Science, Get Answer, Expert's Help, Cryptography, Basic Computer Science Discussions

Write discussion on Cryptography, Basic Computer Science
Your posts are moderated

Write your message here..

Related Questions

Designing computer based system-systems life cycle approach, Systems Life C... Systems Life Cycle Approach Systems Analysis and Design follows a life cycle for development, as shown below. Brief discussion on this approach is given here: Figure

Memory, why do computer have internal memory as a part of cpu and the inter... why do computer have internal memory as a part of cpu and the internal bulk memory seprately?

Goals of autonomous rational agents, Goals of Autonomous Rational Agents: A... Goals of Autonomous Rational Agents: Artificial intelligence One possible way to improve an agent's performance is to enable it to have some kind of details about what it is tr

What is the main principle of an operating system?, The operating system i... The operating system is the layer among the hardware and the programs you run. It provides programs a standard interface to the hardware; or else every program would need to includ

Unix Shell, Write a shell script, change-lines, which will substitute a str... Write a shell script, change-lines, which will substitute a string for a replacement string for each occurance of the string in files specified. The original file will be saved,

Types of operating systems, Operating Systems:  An operating system is a se... Operating Systems:  An operating system is a set of programs that manage computer hardware resources and provide common services for application software.  There are following kind

Computer science, Explain Canonical cover and Extraneous Attributes with ex... Explain Canonical cover and Extraneous Attributes with examples.

Purchasing a database program, When purchasing a database program, you must... When purchasing a database program, you must have a clear idea of what you need it for. Ask yourself the following questions. (1) Will it perform all (he operations necessary f

Machine Learning, Hi I have a 8 question machine learning problem sheet due... Hi I have a 8 question machine learning problem sheet due to the 25th of december. The exercises require knowledge of basic classifiers, logistic regression, naive bayes, mixture o

Computer Networking and configuaration, Ask queYou are hired as a Chief Tec... Ask queYou are hired as a Chief Technology Officer (CTO) of a startup company, which has two branches; one Los Angeles and one in San Francisco. The company hired employees to begi