2L

原文：https_blog_cryptographyengineering_com/2014/11/27/zero-knowledge-proofs-illustrated-primer/
题目：Zero Knowledge Proofs: An illustrated primer

零知识证明：启蒙解读
现代密码学中有许多很巧妙的术语，你可以发现许多朋克乐队（例如Tumblr？）都是以这些术语命名的，比如hard-core predicate?，陷门函数，impossible differential cryptanalysis？还有一个比这些更吸引人，这个属于就是零知识。
事实上，零知识这个术语吸引了许多人的关注，但是也带来了问题。许多人没有理解，只是觉得可能就是非常、十分安全。因此这个术语常常会出现在各种各样的研究中，比如加密系统和匿名网络，这些研究和零知识协议关系不大。
但这一切也都说明一点，那就是零知识证明确实是密码学家创造的最有影响力的工具之一。遗憾的是很多人并不理解这个术语。在这个系列的帖子中，我将讨论一些实际使用中的零知识协议。
零知识的起源
零知识这一概念是由MIT的研究学者于1980提出。这些人当时正在研究交互证明系统，由证明者和验证者互相交换信息来使得验证者相信某个数学语句是true。
在这些人研究以前，大部分工作都是着重于系统的Soundness，也就是考虑可能会有恶意的证明者使验证者误以为某个语句是false。而那时这些人就在想能不能换个角度看这个问题，与其只担心证明着，不如说验证者本身就存在问题，为什么要相信验证者。
这并不是理论上的疑问，这种情况在现实中也存在。
举个例子：现实中的用户用密码登录服务器，一般情况下会把哈希后的密码存在服务器中。登录的过程就可以看正是一种证明，因为对于某个哈希后的密码一定就是某个密码进行哈希后的结果，所以用户实际上知道这个密码。
然而大部分现实中的系统在实现证明过程时存在很大的问题。用户只是把原来的密码传输给服务器，服务器重新计算哈希值，然后比较存储在服务器中的值。这个问题很明显：在协议结束后，服务器就知道用户的密码了。所以如今使用密码的人都会担心服务器会不会遭到攻击。
MIT的这些人所提出的理论正是为了实现这样的证明。如果完全实现了，那么通过零知识证明，我们就可以直接登录服务器，但是服务器可能最多知道这个登录是合法的。
现实中的例子
目前为止可能感觉还是很抽象，这里通过一个现实中零知识的协议具体化这一概念。
为了解释讲述这个例子，假设有一个电信公司的老板正在部署新的蜂窝通信网络，网络的结构如下图所示。每个节点都代表一个蜂窝无限电塔，连接的线条（边）表示两个蜂窝互相重叠，也就是说它们的传输可能会互相干扰。
这种重叠是有问题的，相邻的电塔可能会在接收到混乱的信号。但是这个人在设计时考虑了这点，他一共设置了三种不同的频带来避免互相干扰了。
因此，要部署网络就要为每个电塔分配一个频带，目的是相邻的节点没有共享频带。如果我们用颜色来表示频带，下面就是一种解决方案。
这个问题实际上也是著名的理论问题：图的三色着色问题。对于某些图，要找到一个解决方案可能很困难，甚至很难判断是否存在解决方案。实际上，判断是否有解决方案是一个NP完全问题。
通过手算，我们可以很轻松地就知道上面的例子有解。但是要是没有解怎么办？比方说某个网络很复杂，复杂到自己的计算机也难以找到解。在这种情况下，通常可以向请求外援，找一个有很多算力的人，例如我可能会让在谷歌的朋友帮我算一下。
但这就是我们要说的问题了。
假设谷歌花了大部分计算设备来为这个网络寻找一个着色方案。而需要这个方案的人在不知道是否有解的情况下肯定不会向谷歌支付费用。而另一边，如果这个人不给钱，谷歌也肯定不会把解交给他。这样一来双方就陷入了僵局。
在现实生活中，可能会按常理解决这种局面，例如法律途径，或者由第三方保管约定。但这个帖子不是要讨论真实世界中的情况，而是密码学怎么处理。而且如果你读过密码学相关的论文，你就会知道要解决这个问题必须想出一个非常疯狂的技术方案。

解决方案
在谷歌的工程师向MIT的研究学者请教了这个问题，而这个研究学者和他的同事便想到了下面这个解决方案，这个方法不需要任何计算机，只需要大工厂、画笔和白纸。
首先电信公司的老板进入工厂，铺上白纸，画上蜂窝网络的图，然后离开工厂。接着谷歌进来了，用彩色画笔画出他们的解，如上图所示一共是三种颜色红蓝紫。
谷歌在离开前用白纸覆盖住节点，当需要解的人进入时，他看到的就是

显然这个方法可以把谷歌的解隐藏住，但是对那个人却毫无帮助，他只知道谷歌可能只是给了一个随机的无用解，或者谷歌根本没有着色。
为了让他能够相信谷歌，谷歌给了他一个挑战的机会。他可以随机选择一条边让谷歌去掉连接的两个节点上覆盖的白纸。

注意这个挑战实验会有两中结果：
1、如果两个节点是同色，或者根本没有上色，那么就可以知道谷歌在说谎，可以不用付钱了。
2、如果两个节点不同色，谷歌可能确实没说谎。
第一种结果很清楚，但第二种结果却没有直接结果，因为即使在挑战实验后，谷歌仍然有可能在说谎，毕竟现在只是看了两个节点。假设有E条不同的边，那么在多次实验后谷歌仍然有可能还是给出错误的解，具体来说，在一次实验后，谷歌成功地让他相信的谷歌有解的概率是(E-1)/E （如果E是1000，那么概率就是99.9%）
再重复一次实验。
铺上白纸，复制网络图，这次谷歌依旧用三种颜色进行上色，但是顺序上随机打乱。
再次再节点上覆盖上白纸，那个人进来以后又随机选一条边的两个节点。这一次，如果一切正常的话，那个人会更相信谷歌一些。因为如果谷歌在说谎的话就需要连续两次的运气，这种情况是可以发生，但是概率相对就小了。谷歌连续两次说谎的概率是(E-1)/E * (E-1) / E （E=1000时 大约是99.8%）
这样的实验可以不断重复到那个人相信谷歌为止。
但是你并不需要和他一起重复，可以试试这个http_web_mit_edu/~ezyang/Public/graph/svg.html。
再次注意我们不可能完全确定谷歌没有说谎，总存在一个非常小的概率使得我们没有发现谷歌确实说谎了。但是经过多次迭代后，（E^2，当这么多次以后），我们就能确定谷歌欺骗我们的概率已经可以忽略了，以至于完全不用担心可能发生的实际情况。接下来就可以安安心心交钱了。
另外一点就是谷歌实际上也在保护他的解，即使想要在协议中了解到一点解的信息也没有关系，因为谷歌每次都把颜色次序打乱，根本获取不到任何数据。

原文：https_pdfs_semanticscholar_org/5cf5/681383f142c9d58440375615d4677ea4600f_pdf
题目：An Efficient Receiver Deniable EncryptionScheme and Its Applications

摘要：可否定加密是密码学中重要的基本工具（primitive）之一，尤其当密码学协议中存在强制攻击者时，这一工具显得更加重要。可否定加密在网络投票、投标、拍卖以及多方安全通信中起着巨大的作用。略
1、简介
传统的加密方法可以保护信息安全，不让被动攻击者或者未授权者获取该信息。在某些场合中，强制攻击者在获取到密文后，主动要求发送者/接收者为其解密，让他们提供随机数、密钥和被加密解密的明文。对于传统加密来说，发送者/接收者不可能解密出不合法的明文，因为用错误的密钥解密时会得到无用的信息。因此强制攻击者可以验证解密后的信息。
可否定加密可以让信息的拥有者用另一种方式去解密密文，从而得到不同的信息明文。也就是说如果这个人把所有信息都公开给攻击者，包括攻击者要求的密文信息，那么攻击者无法判断解密后的信息是否合法。对于接收者可否定加密来说，发送者可以发送一个看起来是mTrue加密后的密文C，但实际上C是mFalse加密后的密文。接收者可以解密C得到mTrue或者mFalse。
------
待续

原文：https_www_topcoder_com/community/data-science/data-science-tutorials/the-best-questions-for-would-be-c-programmers-part-1/
题目：未来C++程序员必须了解的问题

1、什么是class（类）？
类用于数据封装、定义抽象数据，随之定义数据的初始化方法、数据操作，也用于隐藏具体的实现、在数据之间共享数据操作行为和属性。
------------------------------------
2、C的struct（结构体）和C++的有什么不同？
》C的结构体只是整合数据，只能包含属性（即成员变量），不能有操作（即成员函数，但是可以通过使用带有该结构体参数的函数）。
》C的结构体的类型名并没有自动为程序定义，需要自己用typedef myStruct someStruct;
》C的结构体不提供OOP（面向对象编程）的概念，C的结构体不能有静态成员或成员函数。而C++结构体实际上是一个类，唯一的不同在于默认的访问控制符是public。
-----------------------------------
3、const和define
》const意味着只读，和普通变量一样，但是const变量的值不能改变，任何数据类型都可以是const。
》define容易出错，编译器不会像const一样检查define。define只是声明了一种替换，让预处理器不做检查地执行该操作。相反，const保证了正确的使用类型。同时define的变量没有放入对象表中，所以难以调试。
》const变量有作用域，而define是全局的，同时会引发冲突。const必须在声明的时候定义（附上一个值），而define则可以是空的。
》用了const修饰的代码会受到编译器的保护：在类中const成员变量不允许改变，const成员函数不允许改变类的状态，在函数参数中const修饰的参数不能在函数体中改变其值。一个已命名的const变量会被编译器优化（注：可能是指将const变量值直接替代为数字，类似define？）。
》结论，多用const，少用define，程序bug相对会少一些。

4、解释说明private public protected访问符
》略
-----------------------------
5、解释说明 public 和 private 继承
》public 继承是C++中默认的继承方式，意味着base（基类、父类）的public private protected成员被继承到子类后，仍旧是public private protected，也就是说成员保持原有的访问符。
》private继承意味着所有基类的成员，不论其访问符，在子类中都变成了private成员。也就是说private继承将访问符降级到private。
》从基类、子类的角度看，public继承是指B “is a” A，而private继承是指B “is implemented in terms of” A（注：B按照A的内容继承？）
-------------------------------
6、“friend”关键字
》friend允许一些非成员函数或其他类访问当前类的private 成员。
》friend函数也作为一个类的接口，可以出现在class中的任何地方，但是friend必须在类的声明中出现。
》friend关系不可以继承，也没有传递性和双向性。
》friend在某些场合下更合适：重载运算符、一个涉及2个类的函数（例如Matrix*Vector）
》结论，friend有其用处，但是该用成员函数的时候就不要使用friend关键字了。

7、对于一个类，编译器会生成哪些默认方法？
》不带参数的构造函数
》析构函数
》拷贝构造函数、赋值构造函数
》所有生成的函数都是public
》所有这些函数只在需要的时候被生成
》默认的拷贝、赋值操作采用的是对所有非static成员进行拷贝、赋值。如果成员中有引用、const变量，那么赋值操作不会自动生成。（如果想让类可以被赋值，则必须自己定义）
》编译器会自动生成&操作符？
-----------------------------------------------
8、如何强制编译器不生成上述方法？
》自己声明并定义。如果类中定义并声明了至少一个带有参数的构造函数，则无参数的构造函数不会生成。
》将其声明为private（类外不能调用），同时不要去定义（类内不能调用，否则会有链接错误）。
-------------------------------------------
9、构造函数初始化列表
》只出现在定义时，内容是一系列构造函数的调用，用逗号隔开
》在任何构造函数体执行之前，这个很重要，这样就可以在函数体内访问已经构造的成员。
》初始化列表不一定适合初始化，例如需要测试某个参数是否符合初始化要求。
》建议初始化列表的初始化顺序按照如下进行：调用基类的相应构造函数（注：即先初始化当前类中基类的成员）、再按照成员定义的顺序初始化当前类中的成员（按照定义顺序）。
------------------------------------------
10、什么时候必须使用初始化列表？
》const变量和引用只能被初始化，而不能赋值，所以必须在初始化列表中初始化。
》在继承中，如果基类没有默认构造函数，或者想要改变默认构造函数的一个默认参数，这个时候必须在初始化列表中调用基类的构造函数。
》可以保证初始化的正确性和效率（非初始化列表可能会调用：默认构造+赋值构造）。

Part2
1、什么是虚函数？
》虚函数是C++实现面向对象中多态的一种机制。虚函数允许程序员在子类中重新定义基类中的函数，当某个函数是通过对象的指针、引用调用的时候，程序会做出正确的函数选择。
》virtual关键字必须在基类函数第一次声明的时候出现。在子类中可以重新定义一个虚函数，这样的重定义称之为重写（覆盖，override，complete rewrite）或者扩展（重写的同时调用了基类的函数）。
》通过C++的虚函数，可以实现延迟绑定（动态绑定、运行时绑定），也就是调用一个函数后需要等到运行时知道对象的类型才能确定具体执行函数体，而不是在编译时就知道了。
------------------------------------------
2、什么是虚析构函数？什么时候用到？
》虚析构函数是和C++的多态机制不谋而合的。把析构函数声明为虚函数，就确保了析构函数被放置在类的VTABLE（虚表）中。
》当类可能是某个类的子类（形成一个阶级关系），那么当释放该类对象的指针（指针本身是基类指针，但是指向了子类）时，可以确保正确的资源释放，即释放掉子类的资源。
》注意C++编译器可能不会提醒我们是否正在释放一个只想子类的基类指针（同时没有定义虚析构函数）。当你释放这样一个指针时，其行为是未定义的（undefined）？？通常来说子类的资源就不会被释放，从而导致内存泄漏。
》另一点需要注意的是，并不需要把所有类的虚构函数声明为虚函数，这样会浪费资源（每个类的vtable都会由编译器生成），只有当类可能成为某个阶级体系中的基类时，才应当声明为虚析构函数。
-----------------------------------
3、如何实现Java中的interface？
》C++中没有interface的概念，但可以通过abstract类实现。
》一个抽象类包括至少一个纯虚函数，而纯虚函数是将虚函数初始化为0，即virtual void fn() = 0;该函数不需要定义。抽象类不能实例化，但可以作为继承体系中的基类，而子类必须实现所有基类中的纯虚函数，否则子类也是抽象类。
》通过声明一个抽象类可以实现接口的功能。

4、指针和引用的不同
》引用必须初始化，因为引用的对象必须存在；而指针可以不用初始化（不建议）。
》没有NULL引用这样的概念，因为引用必须引自某个对象；而指针可以是NULL，即指向空。
》引用效率更高，因为不需要去验证是否为空。而指针通常需要和NULL比较。
》指针可以重新赋值，指向不同的对象（除了const指针），但是引用不能重新引用（引用就像是const指针，由编译器自动解引）
》引用是与某个存储（内存）相互绑定的，而指针有其自己占用的内存。
》对象引用通过dot操作符访问成员，对象指针通过->访问。
-------------------------------------------
5、什么时候选择使用引用？
》当知道某个东西一定存在，且不想引用其他东西时，又或者是某些语法强制？？使用时。否则一律使用指针。
------------------------------------------
6、new和malloc的区别
》new是C++中内置的运算符，malloc是C标准函数。
》new会调用构造函数，malloc不会，只是分配了内存空间，该内存空间由free释放。相同的，new构造了对象后需要由delete进行释放，delete在释放资源的同时，调用了对象的析构函数。
》用free释放malloc申请的资源，用delete/delete[] 释放 new/new[]
------------------------------------------
7、operator new 和 new 的区别
》new是C++内置的操作符，其意义不能改变，operator new 是一个函数（注：类似operator <？？），定义了new这个操作符如何分配内存，其函数签名为 void * operator new(size_t size)
》new操作符可以调用构造函数，这是因为new是为了分配并构造对象：第1步会调用operator new分配足够的内存，第2步会调用构造函数在已分配的内存中构造对象。
》operator new可以被重写（override），这意味着可以改变new分配内存的方式，但不可以改变new的行为。这是因为new的行为是由C++语言定义的。
-----------------------------------------
8、什么是placement new？
》这是一种通过给定内存的方式构造新对象。
》调用者知道对象指针所在内存的位置，placement new返回传递进来的指针。
》使用placement new就意味着，当需要释放对象时，必须调用对象的析构函数，因为该内存并不是通过new生成的，而是通过传递进来的已有内存。例如：MyClass * myObject = new (buffer) MyClass(name);这里假定buffer是一块由malloc分配的足够大的内存。接下来要释放1）对象和2）内存：myObject->~MyClass(); free(buffer);

9、什么是“虚构造函数”？
》C++中并不存在这样的虚构造函数，因为在构造新的对象时必须知道对象的实际类型，而虚函数恰恰于这个相反。
》但是可以使用间接的方式来构造对象，这样方法俗称“虚构造函数”。例如，可以实现一个clone函数作为间接的拷贝构造函数；或者create方法作为间接的默认构造函数。
》这些都称为工厂模式，定义构造对象的接口，让子类决定实例化哪一个类。工厂模式允许类延迟实例化到子类中，例如

例如：
Product是Page，
ConcreateProduct是SkillsPage、ExperiencePage和IntroducingPage，
Creator是Document，
ConcreteCreator有Resume和Reort，
Creator定义了一个FactoryMethod的虚函数CreatePages，并且在构造函数中调用了该方法。
不同子类根据其需求实现了这一工厂函数，eg：resume可能创建了两个不同的page。
当调用子类的构造函数时，由于子类继承了基类的构造函数，而基类的构造函数调用了工厂函数，实际上调用的是重写后的工厂函数，所以使得类的初始化延迟到了子类中工厂函数。
---------------------------------------------
10、什么是RAII？
》RAII——Resource Aquisition Is Initialization，指的是C++中的一种技术（不限于C++语言），用于把资源的获取、释放和初始化、析构化结合在一起。例如在初始化时打开文件，在析构化中关闭文件。
》如果不用RAII技术，那么类的初始化和文件的资源管理将叠在一起，同时当出现异常的时候必须自己重新处理文件的资源。
》RAII最有用的场景在于当局部变量离开作用域时能够自动调用析构函数，就像C++里一样。在其他语言中，例如JAVA、C#，这些语言依赖于垃圾回收器去析构局部变量，这中情况下则需要使用finalization，例如try-catch-finally来释放资源。
》RAII的典型案例有标准库中的文件流、STL的auto_ptr类（这只是非常少的一部分，还有很多）。

原文：http_www_math_ubc_ca/~oantolin/math340/comp-slack_html
题目：Complementary Slackness