陷门求逆群Controlled Algebras and GII

1、Controlled Algebras and GIIsRonald L. RivestMIT CSAILIPAM Workshop October 9, 2006 OutlineuControlled algebrasuTrapdoor discrete log groupsuBlack box & pseudo-free groupsuGroups with infeasible inversesuTransitive signaturesuTrapdoor pairingsAlgebrau( S1 , S2 , op1 , op2, , opn )uAlgebra is set(

2、s) with operation(s).uAbstract algebra is mathematical object.uInstantiation is computational object: Each element of set has one or more representations. Each operation has associated computational procedure.Controlled Algebrau( S , op1 , op2, op3, op4, , opn )u F F I T TuControl computation of eac

3、h operation: F (feasible or public: public poly-time algorithm) I (infeasible: no poly-time alg. exists) T (trapdoor: polytime only with trapdoor information)uWhich controlled algebras can we make?Controlled GroupsuGroup operations: Identity: produces identity element e Generator(s): produces genera

4、tor(s) Sample: produces random element Multiply: group operation Invert: given x , compute x-1 Equal: test equality of elements Canonical: give canonical rep of element Discrete log, root, DDH, CDH, hash, uEach separately controlledAnalogy: gene expressionuOne of the marvelous features of the way DN

5、A works is that the semantics of the gene (i.e., what protein is made) is decoupled from the control of its expression. Semantics and control may evolve separately.controlproteinExample: Trapdoor DL groupsu(See Dent and Galbraith 2006)uGenerator g: public, generates G = uMultiplication (group opn):

6、publicuDiscrete logarithm: trapdooruApplications: key agreement, encryption. (Publish group description as public key)Trapdoor DL groupsuOpen problem to construct practical trapdoor DL groups. uPaillier cryptosystem comes close.uDent & Galbraith also propose pairing-based approach; large tables

7、required. Black box groupuControlled group related to notion of black box group (group operation efficient; others, such as discrete log, may not be) which is “essentially the same” as (“just”) the mathematical object.uSome attempts to have “computational black box group” (Frey; Galbraith) via “disg

8、uised elliptic curves” or other techniques, for specific groups.“Pseudo-free” GroupuNotion introduced by Hohenberger (2003), refined by Rivest (2004).uGroup is (strongly) “pseudo-free” if adversary cant find solution to any “non-trivial” equation (i.e. one that has no solution in free group).uMiccia

9、ncio (2005) showed that Zn* where n=pq is pseudo-free (given “strong RSA assumption”).Groups with Infeasible Inverses (GIIs)uWant group operation to be easy, but computing inverses to be hard (for everyone).uGIIs introduced by Susan Hohenberger in her MS thesis; also studied by David Molnar, Vinod V

10、aikuntanathan.uOpen problem to make GIIs under reasonable assumptions.GIIs imply Key Agreementu(Hohenberger; Rabi/Sherman)uAlice draws random elts: x, y uAlice sends Bob: xy, yuBob draws random elt: zuBob sends Alice yzuBoth compute K = (xy)z = x(yz)Security Argument HuAn Eve who can guess K=xyz fro

11、m (xy,y,yz) can invert random elts. uChoose a at randomuGive Eve xy = ai , y = aj , yz = ak where i-j+k=-1. uThen K = ai-j+k = a-1 .Strongly Associative OWFsu(Introduced by Rabi/Sherman)uAssociative function f(.,.) on set SuEasy to compute f(x,y) given x, yuGiven f(x,y) and y , hard to compute any x

12、 such that f(x,y) = f(x,y).uHemaspaandra and Rothe show that SAOWF and OWF are black-box equivalent on non-structured domains.uBut on a group, SAOWF = GIIs. Trapdoor GIIs (TGIIs)uGII except some trapdoor information allows computation of inverses.uAny finite GII is really TGII, since knowing group o

13、rder allows computation of inverses. However, it may be possible to generate a GII without anyone knowing group orderApplications of TGIIsuVaikuntanathan (2003) has shown how to implement IBE using any TGII that has an efficient algorithm for sampling a random element together with its inverse. u Is

14、 this only known sufficient condition for IBE outside of bilinear maps?Vaikuntanathans IBE constructionuLet G be a TGII, h1 h2 hash functions.uGiven ID, define gID = h1(ID)uDefine skID = gID-1 (using trapdoor)uTo encrypt m, pick r randomly, then: C = (r gID, mh2(r)uTo decrypt (s,t) compute m = t h2(

15、s skID)u(Sampling of pairs (a,a-1) needed, but only in reduction proof, for ID-CPA security.)How to construct GII or TGII?uOrder of group must be hidden.uRSA group (Zn*) has hidden order, but inverses are unfortunately easy.uMaybe use “trusted oracle” to provide interface for composition / sampling

16、/ comparing elements, but not inversion. All reps are encrypted. (Saxena and Soh)uOpen problem!Transitive Signaturesu(due to Micali/Rivest)uSignature scheme on pairs of elts (think of (a,b) as sig on edge (a,b) ) uDTS (Directed Transitive Signatures) Given (a,b) and (b,c) , anyone can compute (a,c)

17、uUTS (Undirected TS) Given (a,b), easy to compute (b,a) Transitive signaturesacb(a,b)(b,c)(a,c)Potential applications to cert chainsSome relationships (see H)KAGIITGIITDPPKEOWFOTDTSUTSSDSTDLBMConstructing a DTS from TGIIuSimple way to build a directed transitive signature scheme from a TGII: Signatu

18、re on (a,b) is just a/b uBut is this secure?Trapdoor pairingsuA group with a bilinear map, except that one needs trapdoor information to compute the pairing function.(Rivest (2004), Dent & Galbraith (2006) Applications of trapdoor pairingsuID scheme (Dent & Galbraith): Alice is only one who can correctly compute DDH results on challenges (ga, gb, gab) or (ga, gb, gc)uMaking various flavors of signature schemes (ID-based, aggregate,