Publish on 03rd November 2019
Category: Birds
0

Cryptography

Lecture 23

Cyclic groups

Let G be a finite group of orderq(written multiplicatively)Let g be some element of GConsider the set <g> = {g0, g1, …}We knowgq= 1 = g0, so the set has ≤qelementsIf the set hasqelements, then it is all of G !In this case, we say g is ageneratorof GIf G has a generator, we say G iscyclic

Examples

ℤNCyclic (for any N); 1 is always a generator:{0, 1, 2, …, N-1}ℤ8Is 3 a generator?{0, 3, 6, 1, 4, 7, 2, 5} – yes!Is 2 a generator?{0, 2, 4, 6} – no!

Example

ℤ*11Is 3 a generator?{1, 3, 9, 5, 4} – no!Is 2 a generator?{1, 2, 4, 8, 5, 10, 9, 7, 3, 6} – yes!Is 8 a generator?{1, 8, 9, 6, 4, 10, 3, 2, 5, 7} – yes!Note that elements appear in a different order from above…

Example

ℤ*13<2> = {1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7},so 2 is a generator<8> = {1, 8, 12, 5},so 8 is not a generator

Important examples

Theorem:Any group of prime order is cyclic, and every non-identity element is a generatorTheorem:If p is prime, thenℤ*pis cyclicNote: the order is p-1, which is not prime for p > 3

Uniform sampling

Given cyclic group G of order q along with generator g, easy to sample a uniformhG:Choose uniform x{0, …, q-1}; set h :=gx

Discrete-logarithm problem

Fix cyclic group G of order q, and generator gWe know that {g0, g1, …, gq-1} = GFor everyhG, there is a uniquexℤqs.t.gx= hDefinelogghto be this x –the discrete logarithmof h with respect to g(in the group G)

Examples

Inℤ*11What is log29?<2> ={1, 2, 4, 8, 5, 10, 9, 7, 3,6},so log29 = 6What is log89?<8> ={1, 8, 9, 6, 4, 10, 3, 2, 5,7}, so log89 = 2Inℤ*13What is log29?<2> ={1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10,7}, so log29 = 8

Discrete-logarithm problem (informal)

Dlogproblem in G:Givengenerator g and element h, computelogghDlogassumption in G:Solving the discrete log problem in G ishard

Example

Inℤ*3092091139What is log21656755742 ?

Discrete-logarithm problem

LetGbe a group-generation algorithmOn input 1n, outputs a(description of a) cyclicgroup G, its order q (withǁqǁ=n), and a generator gFor algorithm A, defineexp’tDlogA,G(n):Compute (G, q, g)G(1n)Choose uniformhGRun A(G, q, g, h) to get xExperiment evaluates to 1 ifgx= h

Discrete-logarithm problem

Thediscrete-logarithm problem is hard relative toGif for all PPT algorithms A,Pr[DlogA,G(n) = 1]≤negl(n)

Diffie-Hellman problems

Fix cyclic group G and generator gDefineDHg(h1, h2) =DHg(gx,gy) =gxy

Example

Inℤ*11<2> ={1, 2, 4, 8, 5, 10, 9, 7, 3, 6}So DH2(7, 5) = ?Inℤ*3092091139What is DH2(1656755742,938640663)?Is 1994993011 the answer, or is it just a random element ofℤ*3092091139?

Diffie-Hellman assumptions

ComputationalDiffie-Hellman (CDH) problem:Given g, h1, h2, computeDHg(h1, h2)DecisionalDiffie-Hellman (DDH) problem:Given g, h1, h2, distinguishDHg(h1, h2) from a uniform element of G

DDH problem

LetGbe a group-generation algorithmOn input 1n, outputs a cyclic group G, its order q (withǁqǁ=n), and a generator gThe DDH problem is hard relative toGif for all PPT algorithms A:|Pr[A(G, q, g,gx,gy,gz)=1] –Pr[A(G, q, g,gx,gy,gxy)=1] | ≤(n)

Relating theDiffie-Hellman problems

Relative toG:If the discrete-logarithm problem is easy, so is the CDH problemIf the CDH problem is easy, so is the DDH problemI.e., the DDH assumption isstrongerthan the CDH assumptionI.e., the CDHassumption isstrongerthan thedlogassumption

Group selection

The discrete logarithm is not hard in all groups!For example, it is easy inℤN(for any N, and for any generator)Nevertheless, there are certain groups where the problem is believed to be hardNote: since all cyclic groups of the same order are isomorphic, the group representation matters!

Group selection

For cryptographic applications, best to useprime-ordergroupsThedlogproblem becomes easier if the order of the group has small prime factorsPrime-order groups have several nice featuresE.g., every element except identity is a generatorTwo common choices of groups…

Group selection: choice 1

Prime-order subgroup ofℤ*p, p primeE.g., p =tq+ 1 for q primeTake the subgroup oftthpowers, i.e.,G = { [xtmod p]| xℤ*p}This is a groupIt has order (p-1)/t = qSince q is prime, the group must be cyclicGeneralizations based on finite fields also used

Group selection: choice 2

Prime-order subgroup of anelliptic curvegroupSee book for details…

Group selection

We will describealgorithms in “abstract” groupsCan ignore details of the underlying group in the analysisCan instantiate with any (appropriate) group for animplementation

0

Embed

Upload

Cryptography - cs.umd.edu