看关于program obfuscation相关的内容已经近两个多月了，却难以说有什么真正的进展。断断续续的进行着，很难将工作有整体性的一直深入下去。

但时间不等人，这一个项目目前如果在短时间内仍然在solution的寻找上没有突破很可能就要流产了。所以必须打起十二分的精神来！多看多思。

今天（314）重新再看论文《OC13》，由于multilinear无论其原理还是实现都十分困难，而且可以预见，在当前的研究水平下，其效率必然将是完全的unpractical！所以一直试图只吸收其scheme的核心思想，允许牺牲一定的安全性，希望能自我设计出一个较为实用的OC，但是通过对该偏论文的再次critical reading，尝试了使用RSA、ElGamal等具有同态性的密码系统解决问题，但都是在好像光亮就在前方时发现无法克服的障碍！这时，你才不得不承认在密码学上想要突破一点都是极不容易的，这一篇发表在CRTPTO上的论文也确实是十分巧妙的利用了Multilinear map的。

从我的失败构造经历来看，主要是对于一般的同态性加密系统，是可以通用其同态性或多密文对应的特性，但是都很难兼顾保护W位不被发现以及最后的Zero Test。而只有Multilinear map的特点---它在各个Gi中有一个hardness的单向加密，同时在map的过程中又有一个hardness的映射，同态性是通过这个map在目标group Gt中实现的，而不是在各个Gi自身之内实现同态的。这样的一种空间映射确实可以解决许多的问题！

所以如果使用这种基于multilinear map作为我们problem的解决方案，也只能作为方案之一，必须找到其他更加高效实用的密码保护方案才行。我们最多可以在论文中提一下这种方案解决我们方案的可能性。

阅读笔记：

first， what is program obfuscation?

>> the problem of compiling a computer program so as to make it unintelligible to a adversary, or impossible to reverse-engineer, while preserving its input-output functionality. The goal of a obfuscator is generating a program that preserves the functionality of the original program, but reveals nothing else.

>>previous work: 在【BGI+12】中已经从理论上对通用的PO给出了一个否定的答案，但是这个否定答案的证明中说明的是一些很contived的functionality，所以密码学家将重点放在对于一些实际中有用的program functionality之上。但即使如此，目前的相关进展也是比较有限的。有些工作则是使用降低了安全性的模型（indistinguishability of several programs) 。 

>>This work：对于conjunction进行obfuscating: An obfuscator for conjunctions needs to produce a program that hides which bits are ignored, and which ones are influential.

>>security:本文的这种scheme的安全性得到了一定的证明：对于满足一定信息量要求的conjunction是可以完全证明其安全性的，而对于一般所有的各种conjunction则只是提出猜想，并有实例来验证猜想很有可能是真的。We prove the security of our obfuscator when the conjuction is choosen from a distribution with sufficient entropy. We conjecture that the construction is secure for every conjunction. As supportive evidence for the conjectured security,we prove that the obfuscator is secure against generic adversaries.

接下来重点介绍了本文自己的构造思想，这里是基于multilinear map这一抽象工具而进行的，没有过多的涉及具体初步实现multilinear map的graded encoding scheme的内容。

（315状态不佳，头比较昏昏沉沉，所以有一点想法却很难深入，本来是打算早起多投入时间好好思考的，却没想到会如此不适应！真是的！）

这一construction的基本思想看似简单，其实却十分的巧妙，而且将multilinear map的特点充分的加以了利用。

encoding，pair化隐藏选择的0还是1对应的数、maping、zero test。

（相关密码security证明相关的部分由于相关基本知识的缺乏，目前只能浏览一下，无法深入去理解）

接下来重要的是2.2部分的具体的对于GGH13中Graded Encoding Scheme GES的介绍，Definition 2.5形式感很强，用集合来定义往往让自学的人难以看到其背后设计者所真正想要表达的意思，从程序角度看，这以部分就是在介绍data structure、object的静态数据。Definition 2.5则相当于介绍object中的functions，InstGen、Samp、encRand、Add、negate、mult、isZero等。这些operation到后面的描述这一obfuscation工作的Figure 1时才真正的显示它的威力。

第二部分剩下的部分继续为后面安全性的证明进行概念以及assumption上的准备。

第三部分才是将第二部分（preliminaries）的construction与GES完美结合起来，给出了一个算法，介绍了如何构造Obfuscator，而使用者又如何进行Ealuation。

接下来的几部分是密码学（毕竟是理论分支）所关心的形式化证明，内容较多，暂不细看。

【GGH13】<candidate multilinear maps from ideal lattices>介绍了如何通过ideal lattice（不太了解，就把这种数学结构当成某一种特殊性质的代数结构group好了，black-box）上的hardness以及相关的变换（“encoding”）为基础，在上层构建出GES，看了57页的加长版后才发现发表在EUROCRYPTO上的论文中还是只介绍了symmetric的情况的，在完整的加长版中介绍了如何加以modification使得其可以有多个source group。

相关基本的基础数学知识：

Polynomial ring

In mathematics, especially in the field of abstract algebra, a polynomial ring is a ring formed from the set of polynomials in one or more indeterminates(traditionally also called variables) with coefficients in another ring, often a field. 

Lattice-based cryptography

(http://en.wikipedia/wiki/Post-quantum_cryptography )

Post-quantum cryptography

From Wikipedia, the free encyclopedia

Post-quantum cryptography refers to research on cryptographic primitives (usually public-key cryptosystems) that are not efficiently breakable using quantum computers more than classical computer architectures. This term came about because most currently popular public-key cryptosystems rely on the integer factorization problem or discrete logarithm problem, both of which would be easily solvable on large enough quantum computers using Shor's algorithm.^{[1][2] Even though current publicly known experimental quantum computing is nowhere near powerful enough to attack real cryptosystems,[citation needed] many cryptographers are researching new algorithms, in case quantum computing becomes a threat in the future. This work is popularized by the PQCrypto conference series since 2006.[3][4]}

In contrast, most current symmetric cryptographic systems (symmetric ciphers and hash functions) are secure from quantum computers.^{[2][5] The quantum Grover's algorithm can speed up attacks against symmetric ciphers, but this can be counteracted by increasing key size.[6] Thus post-quantum cryptography does not focus on symmetric algorithms.}

Post-quantum cryptography is also unrelated to quantum cryptography, which refers to using quantum phenomena to achieve secrecy.

Currently post-quantum cryptography is mostly focused on four different approaches:^[2][4]

• Lattice-based cryptography such as NTRU and GGH
• Multivariate cryptography such as Unbalanced Oil and Vinegar
• Hash-based signatures such as Lamport signatures and Merkle signature scheme
• Code-based cryptography that relies on error-correcting codes, such as McEliece encryption and Niederreiter signatures

abstract Algebra 的研究的三个源头：There are three historical roots ofgroup theory: the theory of algebraic equations, number theory and geometry.

Modern algebra

The end of the 19th and the beginning of the 20th century saw a tremendous shift in the methodology of mathematics. Abstract algebra emerged around the start of the 20th century, under the namemodern algebra. Its study was part of the drive for more intellectual rigor in mathematics. Initially, the assumptions in classical algebra, on which the whole of mathematics (and major parts of the natural sciences) depend, took the form of axiomatic systems. No longer satisfied with establishing properties of concrete objects, mathematicians started to turn their attention to general theory. Formal definitions of certainalgebraic structures began to emerge in the 19th century. For example, results about various groups of permutations came to be seen as instances of general theorems that concern a general notion of anabstract group. Questions of structure and classification of various mathematical objects came to forefront.

These processes were occurring throughout all of mathematics, but became especially pronounced in algebra. Formal definition through primitive operations and axioms were proposed for many basic algebraic structures, such asgroups,rings, and fields. Hence such things as group theory and ring theory took their places in pure mathematics. The algebraic investigations of general fields by Ernst Steinitz and of commutative and then general rings by David Hilbert, Emil Artin and Emmy Noether, building up on the work of Ernst Kummer, Leopold Kronecker and Richard Dedekind, who had considered ideals in commutative rings, and of Georg Frobenius and Issai Schur, concerning representation theory of groups, came to define abstract algebra. These developments of the last quarter of the 19th century and the first quarter of 20th century were systematically exposed inBartel van der Waerden's Moderne algebra, the two-volume monograph published in 1930–1931 that forever changed for the mathematical world the meaning of the wordalgebra fromthe theory of equations to thetheory of algebraic structures.

Basic concepts

Main article:Algebraic structures

By abstracting away various amounts of detail, mathematicians have created theories of various algebraic structures that apply to many objects. For instance, almost all systems studied aresets, to which the theorems of set theory apply. Those sets that have a certain binary operation defined on them formmagmas, to which the concepts concerning magmas, as well those concerning sets, apply. We can add additional constraints on the algebraic structure, such as associativity (to formsemigroups); associativity, identity, and inverses (to form groups); and other more complex structures. With additional structure, more theorems could be proved, but the generality is reduced. The "hierarchy" of algebraic objects (in terms of generality) creates a hierarchy of the corresponding theories: for instance, the theorems of group theory apply to rings (algebraic objects that have two binary operations with certain axioms) since a ring is a group over one of its operations. Mathematicians choose a balance between the amount of generality and the richness of the theory.

Examples of algebraic structures with a singlebinary operation are:

• Magmas
• Quasigroups
• Monoids
• Semigroups
• Groups

More complicated examples include:

• Rings
• Fields
• Modules
• Vector spaces
• Algebras over fields
• Associative algebras
• Lie algebras
• Lattices
• Boolean algebras

Group (mathematics)

 The abstract formalization of the group axioms, detached as it is from the concrete nature of any particular group and its operation, allows entities with highly diverse mathematical origins in abstract algebra and beyond to be handled in a flexible way, while retaining their essential structural aspects. The ubiquity of groups in numerous areas within and outside mathematics makes them a central organizing principle of contemporary mathematics

Groups share a fundamental kinship with the notion ofsymmetry. For example, asymmetry group encodes symmetry features of a geometrical object: the group consists of the set of transformations that leave the object unchanged and the operation of combining two such transformations by performing one after the other.（回想一下在组合数学的复杂计数中，我们采用了group模型来严格的count出一些对称的情况！）。

A group is a set, G, together with an operation • (called the group law of G) that combines any twoelementsa andb to form another element, denoted a •b orab. To qualify as a group, the set and operation,(G, •), must satisfy four requirements known as thegroup axioms:^[4]

Closure

For all a, b in G, the result of the operation, a • b, is also in G.^b[›]

Associativity

For all a, b and c in G, (a • b) • c = a • (b •c).

Identity element

There exists an element e inG, such that for every elementa inG, the equatione •a =a •e =a holds. Such an element is unique (see below), and thus one speaks ofthe identity element.

Inverse element

For each a in G, there exists an elementb inG such that a • b = b • a =e, wheree is the identity element.

Groups for which the commutativity equationa •b = b • a always holds are calledabelian groups (in honor ofNiels Abel). 

example: a symmetry group（这个例子真是awesome!)

Two figures in the plane are congruent if one can be changed into the other using a combination of rotations, reflections, and translations. Any figure is congruent to itself. However, some figures are congruent to themselves in more than one way, and these extra congruences are calledsymmetries. A square has eight symmetries. These are:

id (keeping it as is)	r1 (rotation by 90° right)	r2 (rotation by 180° right)	r3 (rotation by 270° right)
fv (vertical flip)	fh (horizontal flip)	fd (diagonal flip)	fc (counter-diagonal flip)
The elements of the symmetry group of the square (D4). The vertices are colored and numbered to distinguish between them.

• the identity operation leaving everything unchanged, denoted id;
• rotations of the square around its center by 90° right, 180° right, and 270° right, denoted by r1, r2 and r3, respectively;
• reflections about the vertical and horizontal middle line (fh and fv), or through the twodiagonals (fd and fc).

These symmetries are represented by functions. Each of these functions sends a point in the square to the corresponding point under the symmetry. (注意！这里的基本element、object就是函数哦！）For example, r1 sends a point to its rotation 90° right around the square's center, and fh sends a point to its reflection across the square's vertical middle line. Composing two of these symmetry functions gives another symmetry function. These symmetries determine a group called thedihedral group of degree 4 and denoted D4. The underlying set of the group is the above set of symmetry functions, and the group operation isfunction composition.^{[6]（群中的operation是“函数的复合操作”！）} Two symmetries are combined by composing them as functions, that is, applying the first one to the square, and the second one to the result of the first application. The result of performing firsta and thenb is written symbolicallyfrom right to left as

b •a ("apply the symmetryb after performing the symmetry a").

The right-to-left notation is the same notation that is used for composition of functions.

The group table on the right lists the results of all such compositions possible. For example, rotating by 270° right (r3) and then flipping horizontally (fh) is the same as performing a reflection along the diagonal (fd). Using the above symbols, highlighted in blue in the group table:

fh • r3 = fd.

Group table of D4

•	id	r1	r2	r3	fv	fh	fd	fc
id	id	r1	r2	r3	fv	fh	fd	fc
r1	r1	r2	r3	id	fc	fd	fv	fh
r2	r2	r3	id	r1	fh	fv	fc	fd
r3	r3	id	r1	r2	fd	fc	fh	fv
fv	fv	fd	fh	fc	id	r2	r1	r3
fh	fh	fc	fv	fd	r2	id	r3	r1
fd	fd	fh	fc	fv	r3	r1	id	r2
fc	fc	fv	fd	fh	r1	r3	r2	id
The elements id, r1, r2, and r3 form asubgroup, highlighted in red (upper left region). A left and right coset of this subgroup is highlighted in green (in the last row) and yellow (last column), respectively.

Given this set of symmetries and the described operation, the group axioms can be understood as follows:

1. The closure axiom demands that the compositionb •a of any two symmetriesa andb is also a symmetry. Another example for the group operation is

   r3 • fh = fc,

   i.e. rotating 270° right after flipping horizontally equals flipping along the counter-diagonal (fc). Indeed every other combination of two symmetries still gives a symmetry, as can be checked using the group table.
2. The associativity constraint deals with composing more than two symmetries: Starting with three elementsa,b andc of D4, there are two possible ways of using these three symmetries in this order to determine a symmetry of the square. One of these ways is to first composea andb into a single symmetry, then to compose that symmetry withc. The other way is to first composeb andc, then to compose the resulting symmetry witha. The associativity condition

   (a •b) •c = a • (b •c)

   means that these two ways are the same, i.e., a product of many group elements can be simplified in any order. For example,(fd • fv) • r2 = fd • (fv • r2) can be checked using the group table at the right

   (fd • fv) • r2	=	r3 • r2	=	r1, which equals
   fd • (fv • r2)	=	fd • fh	=	r1.

   While associativity is true for the symmetries of the square and addition of numbers, it is not true for all operations. For instance, subtraction of numbers is not associative:(7 − 3) − 2 = 2 is not the same as7 − (3 − 2) = 6.

3. The identity element is the symmetry id leaving everything unchanged: for any symmetrya, performing id aftera (ora after id) equalsa, in symbolic form,

   id • a =a,

   a • id =a.

4. An inverse element undoes the transformation of some other element. Every symmetry can be undone: each of the following transformations—identity id, the flips fh, fv, fd, fc and the 180° rotation r2—is its own inverse, because performing it twice brings the square back to its original orientation. The rotations r3 and r1 are each other's inverses, because rotating 90° and then rotation 270° (or vice versa) yields a rotation over 360° which leaves the square unchanged. In symbols,

   fh • fh = id,

   r3 • r1 = r1 • r3 = id.

In contrast to the group of integers above, where the order of the operation is irrelevant, it does matter in D4:fh • r1 = fc butr1 • fh = fd. In other words, D4 is not abelian（该群显然是不满足交换律的！不是Abelian群）, which makes the group structure more difficult than the integers introduced first.

Basic concepts

To understand groups beyond the level of mere symbolic manipulations as above, more structural concepts have to be employed.^{c[›] There is a conceptual principle underlying all of the following notions: to take advantage of the structure offered by groups (which sets, being "structureless", do not have), constructions related to groups have to becompatible with the group operation.(group内部structure的本质必须要保持不变！） This compatibility manifests itself in the following notions in various ways. For example,groups can be related to each other via functions called group homomorphisms. By the mentioned principle, they are required to respect the group structures in a precise sense. The structure of groups can also beunderstood by breaking them into pieces called subgroups and quotient groups. The principle of "preserving structures"—a recurring topic in mathematics throughout—is an instance of working in acategory, in this case the category of groups.}

Group homomorphisms

Main article:Group homomorphism

Group homomorphisms^{g[›] are functions that preserve group structure.} A functiona:G →H between two groups (G,•) and (H,∗) is called ahomomorphism if the equation

a(g •k) =a(g) ∗a(k)

holds for all elements g, k in G. In other words, the result is the same when performing the group operation after or before applying the mapa.This requirement ensures thata(1G) = 1H, and alsoa(g)−1 =a(g−1) for allg inG. Thus a group homomorphism respects all the structure ofG provided by the group axioms.^[28]

Two groups G and H are calledisomorphic if there exist group homomorphismsa:G →H andb: H → G, such that applying the two functionsone after another in each of the two possible orders gives the identity functions of G and H. That is, a(b(h)) = h and b(a(g)) =g for anyg inG andh inH.（体会一下与密码学中基本的DEC(ENC(m))=m的联系）From an abstract point of view, isomorphic groups carry the same information. For example, proving thatg •g = 1G for some elementg ofG isequivalent to proving thata(g) ∗a(g) = 1H, because applyinga to the first equality yields the second, and applyingb to the second gives back the first.

Cosets

Main article:Coset

In many situations it is desirable to consider two group elements the same if they differ by an element of a given subgroup.（这句话不太好理解，其意思是说这两个可以归为一类（the same）的元素之间的difference与自己中元素之间的difference是同一种“结构”，别的方面无法将他们区分开来，如下面的Z8所示，1与5是“相同的”，这种在『0，4』子群中就已经存在的差异只在这一子群的结构内部存在！，其他的元素与其作用(用1+H）无法分来他们）。For example, in D4 above, once a flip is performed, the square never gets back to the r2 configuration by just applying the rotation operations (and no further flips), i.e.the rotation operations are irrelevant to the question whether a flip has been performed. Cosets are used to formalize this insight: a subgroupH defines left and right cosets, which can be thought of as translations ofH by arbitrary group elementsg.（由此可见，其实历史的发展可能与定义所表面诠释的完全不同，这里我们是先知道了这样之后得到的cosets是一个等价类，即原group的一个划分） In symbolic terms, theleft andright cosets of H containingg are

gH = {g • h:h ∈H} andHg = {h • g:h ∈H}, respectively.^[31]

The cosets of any subgroup H form a partition of G; that is, the union of all left cosets is equal to G and two left cosets are either equal or have anemptyintersection.^{[32]The first caseg1H = g2H happensprecisely wheng1−1 • g2 ∈H, i.e. if the two elements differ by an element ofH.Similar considerations apply to the right cosets ofH. The left and right cosets ofH may or may not be equal. If they are, i.e. for allg inG,gH = Hg, then H is said to be anormal subgroup.}

In D4, the introductory symmetry group, the left cosetsgR of the subgroupR consisting of the rotations are either equal toR, ifg is an element ofR itself, or otherwise equal toU = fcR = {fc, fv, fd, fh} (highlighted in green). The subgroupR is also normal, becausefcR =U = Rfc and similarly for any element other than fc.

G is the group , theintegers mod 8 under addition. The subgroup H contains only 0 and 4, and is isomorphic to. There are four left cosets of H: H itself, 1+H, 2+H, and 3+H (written using additive notation since this is theadditive group). Together they partition the entire group G into equal-size, non-overlapping sets. The index [G : H] is 4.

Quotient groups

Main article:Quotient group

In some situations the set of cosets of a subgroup can be endowed with a group law, giving aquotient group orfactor group. For this to be possible, the subgroup has to benormal. Given any normal subgroupN, the quotient group is defined by

G / N = {gN,g ∈G}, "G moduloN".^[33]

This set inherits a group operation (sometimes called coset multiplication, or coset addition) from the original groupG:(gN) • (hN) = (gh)N for allg andh in G. This definition is motivated by the idea (itself an instance of general structural considerations outlined above) that the mapG →G /N that associates to any elementg its cosetgN be a group homomorphism, or by general abstract considerations calleduniversal properties. The coseteN = N serves as the identity in this group, and the inverse ofgN in the quotient group is(gN)−1 = (g−1)N.^e[›]

•	R	U
R	R	U
U	U	R
Group table of the quotient groupD4 /R.

The elements of the quotient group D4 / R areR itself, which represents the identity, andU = fvR. The group operation on the quotient is shown at the right. For example,U •U = fvR • fvR = (fv • fv)R =R. Both the subgroupR = {id, r1, r2, r3}, as well as the corresponding quotient are abelian, whereas D4 is not abelian. Building bigger groups by smaller ones, such as D4 from its subgroupR and the quotientD4 / R is abstracted by a notion calledsemidirect product.

Quotient groups and subgroups together form a way of describing every group by itspresentation: any group is the quotient of thefree group over thegenerators of the group, quotiented by the subgroup ofrelations. The dihedral group D4, for example, can be generated by two elementsr andf (for example, r = r1, the right rotation andf = fv the vertical (or any other) flip), which means that every symmetry of the square is a finite composition of these two symmetries or their inverses. Together with the relations

r 4 = f2 = (r •f)2 = 1,^[34]

the group is completely described. A presentation of a group can also be used to construct theCayley graph, a device used to graphically capture discrete groups.

Sub- and quotient groups are related in the following way: a subsetH ofG can be seen as an injective map H → G, i.e. any element of the target has at most oneelement that maps to it. The counterpart to injective maps are surjective maps (every element of the target is mapped onto), such as the canonical mapG →G /N.^{y[›] Interpreting subgroup and quotients in light of these homomorphisms emphasizes the structural concept inherent to these definitions alluded to in the introduction. In general, homomorphisms are neither injective nor surjective.Kernel and image of group homomorphisms and the first isomorphism theorem address this phenomenon.}

Group-like structures
	Totality*	Associativity	Identity	Divisibility	Commutativity
Magma	Yes	No	No	No	No
Semigroup	Yes	Yes	No	No	No
Monoid	Yes	Yes	Yes	No	No
Group	Yes	Yes	Yes	Yes	No
Abelian Group	Yes	Yes	Yes	Yes	Yes
Loop	Yes	No	Yes	Yes	No
Quasigroup	Yes	No	No	Yes	No
Groupoid	No	Yes	Yes	Yes	No
Category	No	Yes	Yes	No	No
Semicategory	No	Yes	No	No	No
	*Closure, which is used in many sources to define group-like structures, is an equivalent axiom to totality, though defined differently.

Coset

In mathematics, if G is a group, and H is a subgroup of G, and g is an element of G, then

gH = {gh : h an element of H } is a left coset of H inG, and

Hg = {hg : h an element ofH } is aright coset of H in G.

Only when H is normal will the right and left cosets of H coincide, which is one definition of normality of asubgroup. Although derived from a subgroup, cosets are not usually themselves subgroups ofG, only subsets.

A coset is a left or right coset ofsomesubgroup in G. 

The map gH→(gH)−1=Hg−1 defines abijection between the left cosets and the right cosets of H, so the number of left cosets is equal to the number of right cosets. The common value is called theindex ofH in G.

For abelian groups, left cosets and right cosets are always the same. If the group operation is written additively then the notation used changes tog+H orH+g.

Cosets are a basic tool in the study of groups; for example they play a central role inLagrange's theorem.