### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Calculus for Business and Economics MATH 1071

UCONN

GPA 3.97

### View Full Document

## 70

## 0

## Popular in Course

## Popular in Mathematics (M)

This 7 page Class Notes was uploaded by Mary Veum on Thursday September 17, 2015. The Class Notes belongs to MATH 1071 at University of Connecticut taught by Jessica Todd in Fall. Since its upload, it has received 70 views. For similar materials see /class/205807/math-1071-university-of-connecticut in Mathematics (M) at University of Connecticut.

## Popular in Mathematics (M)

## Reviews for Calculus for Business and Economics

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/17/15

1 Broadcast Encryption Suppose there is a system with N users A broadcast encryption scheme enables someone called the Center to send a message to a select group of N excluding whomever he chooses For example cable companies use broadcast encryption to distribute various cable packages to subscribers Each subscriber obtains the package they paid for but everyone has access to the same networ Let N 1111 N be the set of all users and R Q N be the subset of users excluded from a transmission We de ne the enabled set E N R to be the intended recipients of a ciphertexti In this section we assume that all encryption schemes use symmetric encryption 06771 and 39D km m for a message m and key kl U1 ntkey U 1 C mm m gt U2 U1 Figure 1 A broadcast encryption scheme where users Ui with i E E can decrypt m but U with j E R cannoti R denotes the description of R and m is a message After the network initializes the system with Initkey the Center sends the ciphertext C to all users Ui with i E E in such a way that no U with j E R can decrypt mi The trivial solution is to give every user a distinct key kin If R 7 the Center encrypts m with each of the N 7 7 appropriate keys The ciphertext C lt5 kl1 mi i kiN7Tmgt then has length N 7 Ti To decrypt the message each enabled user tries their key on every entry ciphertexti While this works it requires a very long ciphertexti One of our primary goals is to minimize the length of Cl Consider an alternate solutioni Instead of giving a key to each user give a key to every possible subset of This is called the power set ll of To send a message the Center now only needs the key corresponding to the set E For example take N 123 and R In Figure 2 each node corresponds to a key Nodes containing R are open to show that they cannot be used While there are four solid nodes only the node for E 1 3 is needed Recall that P 2N so each user needs 2N1 keysi Using the power set enables the Center to send a ciphertext with a minimal number of keys The largest possible ciphertext has length A Tlog39r where A 5keymi This indicates that this solution is most helpful when 7 is small The power set method is inef cient however in that each user must store the maximum number of keys Our goal is now to nd a medium between minimizing the number of keys required by the center to encrypt a message and minimizing the number of keys required by each user to decrypt a message 11 Complete Binary Trees One effective way to minimize both the ciphertext size and user memory space for broadcast en cryption is to use complete binary trees 1 1 COMPLETE BINARY TREES 2 3 Figure 2 All possible subsets of N users for N 3 and R De nition 1 A complete binary tree CRT is a tree diagram in which every level is full and all levels have the same depthli Any CBT has 2 leaves for some t E Zli Leaves Figure 3 A complete binary tree with N 8 leaves and depth 3 Lemma 1 In a complete binary tree with N leaves there are 2N 7 1 nodes Proof We prove this by induction on Ni When N 17 it holds trivially that there are 2 7 l 1 nodes Assume if N 2 7 there are 22 7 l 2 1 7 1 nodes Now take any CBT with N 2 4r1 leavesi By removing the root7 we can divide the into two symmetric complete binary subtrees7 each with 2 leaves By our inductive assumption7 each subtree has 2 4r1 7 1 nodes The entire tree then has 22 1 711 22 171 2N 71 nodes I Figure 4 illustrates how N 8 users can be represented in a CBT7 where each leaf denotes one user Each node then corresponds to a key assigned to that subset of users 1The depth of a tree is the number of steps it takes to move from a leaf to the root 1 1 COMPLETE BINARY TREES 3 Figure 4 A complete binary tree representing N 8 users It is clear that any CBT has depth logN base 2 so each user needs 1 logN keysi To communicate With all N users the Center only needs the root s key to encrypt his message In an ideal situation the members of R form a complete subtree so 7 275 In order to then exclude R from a transmission the center refrains from using the root of Rs subtree and any ancestral node the subtree hangs fromi Each user then needs a maximum of log N7 log 7 logNT keysi This is illustrated in Figure 5 Where open nodes denote omitted keysi Figure 5 Excluding R When R forms a single complete subtreei As R grows or disperses into different subtrees users may need up to TlOgN7 keysi This implies that the ciphertext Will also have length between TlogN and TlogNTi This is a superior method for broadcast encryptioni CRYPTO PRIMITIVES AND PROTOCOLS PROFESSOR KIAYIAS LECTURE 4 FALL 2008 1 The Dif e Hellman Key Exchange Protocol Part II In Lecture 3 we introduced the Dif e Hellman key exchange protocol and examined its security against passive adversaries Here we will continue our discussion and look at the security of the protocol against stronger adversaries The Decisional Dif e Hellman DDH assumption assumes that it is hard to distinguish tuples of the form lt10 mgg gyg ygt from ltpmgg gygzgt where Ly and 2 are randomly chosen elements 11 Suitable Group Generators for the DDH Assumption In this section we examine the DDH assumption over two groups First consider lt9 Z for a large prime p This group is potentially a poor choice in fact we can construct a PPT algorithm A as in Figure 1 that breaks the DDH assumptioni Algorithm Apm 9707177 0 4 21vbm21Acm21 then output 1 else output 0 Figure l A PPT algorithm that breaks the DDH assumption when ltggt Z abc E ltggt and m ordg is even By Eulerls Theorem Z has order m p 7 1 Since p is odd for all primes greater than 2 m is even for any nontrivial groupi Let 7 ltpmgabcgt where a 9112 93 and c gxyi If I is even write I 21 for some k E Z Then am2 9 m2 gkm 1 If I is odd write I 2jl for somej E Z Then am2 92111 m2 gm2 ill The same result holds for gy depending on if y is even or odd The parity of my clearly depends on the parity of z and y so cm2 giant2 l as long as one of z or y is even T us 3 gmmu1 If instead 7 lt7 R so 5 92 for a randomly chosen 2 there is an equal probability that 2 will be even or odd So 3 gmmug Based on this information A 3 3 3 Adv 7 1 7 g g In an ideal situation both probabilities are close to 12 so their difference is negligible Since AdVA 38 A can distinguish between the two tuplesi It is therefore ineffective to build a key exchange over Z3 One group we can build a key exchange over is the quadratic residue QRp of Z For example if p 2g l for a prime 4 QRp has order q To the best of our knowledge this is an adequate groupi Recall that QRp lt92 for a generator 9 of Z so QRp is a cyclic group of even order 12 Modi ed Di ie Hellman Protocol Under the DDH assumption the generated key is a random element from a group whose structure we typically know very little about This becomes problematic when using the key in cryptographic CRYPTO PRIMITIVES AND PROTOCOLS PROFESSOR KIAYIAS LECTURE 4 FALL 2008 applications Here we look at how to extract a random integer from a random group element This is useful in that we do understand the structure of integers One approach is to de ne a predicate V such that Prob gltggtVz 1 121 V then de nes one unpredictable bit from the adversary7s point of viewi It is unclear however how to nd even one such predicatei One must completely understand the structure of the group in oder to discern a random biti lnstead take p 2m 1 and de ne the map H Zm QRp by z gt gt z 12 mod p This is a bijection To show it is injective assume for some I y E Zmi Then 112 2 lty1gt2modp ltz1gt27lty1gt220modp z22172y7y230modp ziyIy2EOmodpi So either 17yEOmodpor zy230modpi SincezyEZm wehave0 zy mi1i Then zy2 2m7122m lt2m1EOmodpi Thus I y2 0 mod p which leaves only I 7 y E 0 mod p or equivalently z E y mod p Because Ly E Zm C Z17 we have I y H is surjective by the following preimage of any y E QRp H71 7 yp14 mod p 1 if yp14 mod p 6 12111721 y 7 p yp14 mod p 71 otherwise Using this we can modify the key exchange protocol as is seen in Figure 2 dz 13an yAngA modp 13ng3 modp Common Input p m g M e H 1y2 mod 19 kB F H WZB mod 19 Output kA Output k3 Figure 2 The modi ed Dif e Hellman key exchange protocol where p is a large prime 9 generates the group QRp of order m and H Zm QRp by z gt gt z 12 mod p Under the modi ed Dif e Hellman key exchange protocol we can now use the bijection H to pass from a random element from a group whose structure we do not fully understand to a random integer modulo mi Exercise We have shown how to derive a random element from Zmi This enables us to access cryptographic applications requiring a random integer modulo m as a key Most applications how ever necessitate that the key be a bit stringi Determine how to extract the longest possible bit string from an integer modulo mi It is interesting to note that in a A bit key the probability that the least signi cant bit is 1 is very close to 12 while the probability that the most signi cant bit is 1 can be far from 121 CRYPTO PRIMITIVES AND PROTOCOLS PROFESSOR KIAYIAS LECTURE 4 FALL 2008 13 Stronger Adversaries While the Dif e Hellman key exchange protocol as given in Section 7 is secure against an eaves dropper it does not remain so against a more active adversary In Figure 3 we show the manin themiddle attack in which the adversary Malorie participates in the exchange of information between Alice and Bob The adversary is now the communication channel itselfi Malorie can inject messages into the conversation and impersonate the identity of each party to the other In doing so Malorie creates two keys one to share with Alice and one to share with o i This attack exempli es the need to authenticate and verify authentication on each exchanger Next we introduce a digital signature which is an important cryptographic primitive essential in defending against tactics like the maninthemiddle attac Common Input p m g IA Zm IMIM lt12 x3 lt12 yAngA modp yMegwM modp 13ng3 modp yM H gwM mod p M yM yM M3 lt lt kAHHAQjf modp kMeHil ZM modp kBHHAQjf modp kM H HAWEM mod p Output 1 Output kM kM Output CB Figure 3 The maninthemiddle attack on the Dif e Hellman key exchange protocoli 0Notes by S Pehlivanoglu J Todd amp HVS Zhou

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.