Let G K {0, 1}n be a secure PRG. (a) Define G' (k1, k2, k3) = (G(k1) (b) Define G' (k1, k2, k3) = G(K1) G(K2)) @ G(K3). (G(k2) G(K3)). Consider the following statistical test A on {0, 1}n: A(x) outputs LSB(x), the least significant bit of x. What is AdvP RG[A, G'] for each case? You may assume that LSB (G(k)) is for exactly half the seeds k in K. Note that represents the bitwise AND operation.

Let G K {0, 1}n be a secure PRG. (a) Define G' (k1, k2, k3) = (G(k1) (b) Define G' (k1, k2, k3) = G(K1) G(K2)) @ G(K3). (G(k2) G(K3)). Consider the following statistical test A on {0, 1}n: A(x) outputs LSB(x), the least significant bit of x. What is AdvP RG[A, G'] for each case? You may assume that LSB (G(k)) is for exactly half the seeds k in K. Note that represents the bitwise AND operation.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

6. Let M = (Q,Sigma,s, q0, F) be a dfa and define cfg g= (v,sigma, R,S) as follows: 1. V=Q; 2. For each q in Q and a in sigma, define rule q->aq' where q' = s(q,a); 3. S = q0 Prove L(M) = L(G)
Logistic regression aims to train the parameters from the training set D = {(x(i),y(i)), i 1,2,...,m, y ¤ {0,1}} so that the hypothesis function h(x) = g(0¹ x) 1 (here g(z) is the logistic or sigmod function g(z) can predict the probability of a 1+ e-z new instance x being labeled as 1. Please derive the following stochastic gradient ascent update rule for a logistic regression problem. 0j = 0j + a(y(¹) — hz(x)))x; ave. =
Many forms of cryptography are based on the following discrete log problem. Choose a cyclic group G (produced by one generator g) with finitely many elements. Alice and Bob want to set up a secret communication and need a secret key for that, which becomes a group element from G. They set up the following exchange (the so-called Diffie-Hellman protocol): 1. Alice chooses a secret group element a and sends unsecured g^a to Bob 2.Bob chooses a secret group element b and sends unsecured g^b to Alice 3. Alice calculates (g^b )^a and keeps this group element secret 4.Bob calculates (g^a )^b and keeps this group element secret Since a cyclic group is abelian, Alice and Bob now share the secret key (g^b )^a=(g^a )^b. The blue group elements are publicly known, the red elements are secret. The discrete log problem presented to an eavesdropper is computing say a from the publicly known data G,g,g^a. The naming of the problem comes from the solution a= glog⁡(ga ) which is generally difficult to…
1.Extended token-based mutual exclusion to k-mutual exclusion where at most k processes can enter the critical section. 2.Give an example of consistent cuts and inconsistent cuts.
Consider the following version of Knapsack. Given are two weight limits W 1 and W 2 , whereW 1 ≤ W 2 . Given are also n items (w 1 , c 1 ), (w 2 , c 2 ), . . . , (w n , c n ), where w i is the weight and c ithe cost of the i-th item. We want to find a subset of these items of the highest cost, wherethe subset weights at least W 1 and at most W 2 . Give an O(nW 2 ) algorithm for this problem.(Recall that the cost (respectively weight) of a subset is the sum of the costs (respectivelyweights) of the items in the subset.)
Correct answer will be upvoted else downvoted. Nastia has a concealed change p of length n comprising of integers from 1 to n. You, for reasons unknown, need to sort out the change. To do that, you can give her an integer t (1≤t≤2), two unique records I and j (1≤i,j≤n, i≠j), and an integer x (1≤x≤n−1). Contingent upon t, she will reply: t=1: max(min(x,pi),min(x+1,pj)); t=2: min(max(x,pi),max(x+1,pj)). You can ask Nastia at most ⌊3⋅n2⌋+30 times. It is ensured that she won't change her stage contingent upon your questions. Would you be able to figure the change? Input The input comprises of a few experiments. First and foremost, you get the integer T (1≤T≤10000) — the number of experiments. Toward the start of each experiment, you get an integer n (3≤n≤104) — the length of the change p. It's reliable that the change is fixed ahead of time and that the amount of n in one test doesn't surpass 2⋅104. Connection To pose an inquiry, print "? t I j x" (t=1…
One potential limitation of a digital signature is that for a given signature σ of a message m corresponding to a public key pk, one could generate a pk', sk' that produces a signature σ' for m, such that σ' = σ. Given a signing function S, a verification function V, that each takes corresponding private and public keys for generating and verifying a signature and is vulnerable to these duplicate keys, please generate S' and V' that are immune to a duplicate keys attack.
Notice that Ro1(h) can be interpreted as the misclassification rate. That is, if R01(h) .7, then predicting h would result in the wrong answer for 70% of the data points. Given the data set {4, 2, 4, 1, 3, 4, 4, 3, 2, 5}, plot the empirical risk Ro1(h) for h = [0, 5]. Hint: the function should have point discontinuities. = c) Is gradient descent useful for minimizing the risk with zero-one loss? Why or why not? Make reference to your plot of the risk in your answer. Hint: the risk is indeed non-convex, but gradient descent can still be useful for minimizing non-convex functions. Is there some other reason?
Consider the first round of DES. Let us assume that the round key K, is the vector of all ones and we have the following input to the encryption round: X = Lo || Ro, where Lo vector (i.e., 32 zeros). = 1011 0100 1000 1101 1010 0100 1110 0101 and R, is the all-zero What would be the output of the first round of encryption? Show your work for each step (output of expansion box, the S-boxes, and the permutation inside the f-function).
Exercise Consider the following pseudocode for a knapsack problem heuristic with capacity b, and n objects with rewards c and weights a. 1. Set S = (). b = b, I= (1,2.n) 2. repeat 3. Let jl be the index such that cj z ci, i l. 4. I =1-0), S= S () 5. b = b - aj 6. Remove from I all indices i where ai >b 7. until I = ) 8. The objects in set S are the objects in the solution. Implement this algorithm in VBA with n objects and capacity b. First take from the user the values for n and b. Then let rewards be random integer numbers between 5 and 10, and weights be random integer numbers between 1 and 10. Your inputs and solution should be exhibited on an Excel worksheet as well.
Consider an RSA key set for Alice with p = 23, q = 17, n = 391 and e = 15.a) Her public key is (e, n) = (15, 391). Is her private key (d, n) = (47, 391)? Justffy your answer. b) Suppose Bob wants to encrypt a message 90 for Alice using RSA keys for confidenVality. Whatis the corresponding cipher text?Justify your answer.
Consider the encryption function for a symmetric cryptosystem E(k, m) described below, where K = M = {0, 1, 2, 3}, C = {0, 1, 2, 3}: E(k, m) = (2 ∗ k + m) mod 4 (a) Give the corresponding decryption function(b) Is this cryptosystem information-theoretically secure(or perfectly secure)? Why or why not?