[{"content":" 转载自：https://blog.csdn.net/m0_46422300/article/details/104645072\n一、基础知识 1.1 linux系统的文件结构 /bin 二进制文件，系统常规命令 /boot 系统启动分区，系统启动时读取的文件 /dev 设备文件 /etc 大多数配置文件 /home 普通用户的家目录 /lib 32位函数库 /lib64 64位库 /media 手动临时挂载点 /mnt 手动临时挂载点 /opt 第三方软件安装位置 /proc 进程信息及硬件信息 /root 临时设备的默认挂载点 /sbin 系统管理命令 /srv 数据 /var 数据 /sys 内核相关信息 /tmp 临时文件 /usr 用户相关设定 1.2 linux系统命令行的含义 示例：root@app00:~# root //用户名，root为超级用户 @ //分隔符 app00 //主机名称 ~ //当前所在目录，默认用户目录为~，会随着目录切换而变化，例如：（root@app00:/bin# ，当前位置在bin目录下） # //表示当前用户是超级用户，普通用户为$，例如：（\u0026#34;yao@app00:/root$\u0026#34; ，表示使用用户\u0026#34;yao\u0026#34;访问/root文件夹） 1.3 命令的组成 示例：命令 参数名 参数值 二、基础操作 2.1 关闭系统 (1)立刻关机 shutdown -h now 或者 poweroff (2)两分钟后关机 shutdown -h 2 (3)立刻重启 shutdown -r now 或者 reboot (4)两分钟后重启 shutdown -r 2 2.2 帮助命令（help） ifconfig --help //查看 ifconfig 命令的用法 man shutdown //打开命令说明后，可按\u0026#34;q\u0026#34;键退出 2.3 切换用户（su） su yao //切换为用户\u0026#34;yao\u0026#34;,输入后回车需要输入该用户的密码 exit //退出当前用户 ![[imgs/2.3.png]]\n三、目录操作 3.1 切换目录（cd） cd //切换到home目录 cd / //切换到根目录 cd /bin //切换到根目录下的bin目录 cd ../ //切换到上一级目录 或者使用命令：cd .. cd ~ //切换到home目录 cd - //切换到上次访问的目录 cd xx(文件夹名) //切换到本目录下的名为xx的文件目录，如果目录不存在报错 cd /xxx/xx/x //可以输入完整的路径，直接切换到目标目录，输入过程中可以使用tab键快速补全 3.2 查看目录（ls） ls //查看当前目录下的所有目录和文件 ls -a //查看当前目录下的所有目录和文件（包括隐藏的文件） ls -l //列表查看当前目录下的所有目录和文件（列表查看，显示更多信息），与命令\u0026#34;ll\u0026#34;效果一样 ls /bin //查看指定目录下的所有目录和文件 3.3 创建目录（mkdir） mkdir tools //在当前目录下创建一个名为tools的目录 mkdir /bin/tools //在指定目录下创建一个名为tools的目录 3.3 删除目录与文件（rm） rm 文件名 //删除当前目录下的文件 rm -f 文件名 //删除当前目录的的文件（不询问） rm -r 文件夹名 //递归删除当前目录下此名的目录 rm -rf 文件夹名 //递归删除当前目录下此名的目录（不询问） rm -rf * //将当前目录下的所有目录和文件全部删除 rm -rf /* //将根目录下的所有文件全部删除【慎用！相当于格式化系统】 3.4 修改目录（mv） mv 当前目录名 新目录名 //修改目录名，同样适用与文件操作 mv /usr/tmp/tool /opt //将/usr/tmp目录下的tool目录剪切到 /opt目录下面 mv -r /usr/tmp/tool /opt //递归剪切目录中所有文件和文件夹 3.5 拷贝目录（cp） cp /usr/tmp/tool /opt //将/usr/tmp目录下的tool目录复制到 /opt目录下面 cp -r /usr/tmp/tool /opt //递归剪复制目录中所有文件和文件夹 3.6 搜索目录（find） find /bin -name \u0026#39;a*\u0026#39; //查找/bin目录下的所有以a开头的文件或者目录 find /bin -size \u0026#39;-10k\u0026#39;\t//查找/bin目录下的小于10kb的文件或目录 3.7 查看当前目录（pwd） pwd //显示当前位置路径 四、文件操作 4.1 新增文件（touch） touch a.txt //在当前目录下创建名为a的txt文件（文件不存在），如果文件存在，将文件时间属性修改为当前系统时间 4.2 删除文件（rm） rm 文件名 //删除当前目录下的文件 rm -f 文件名 //删除当前目录的的文件（不询问） 4.3 编辑文件（vi,vim） vi 文件名 //打开需要编辑的文件 --进入后，操作界面有三种模式：命令模式（command mode）、插入模式（insert mode）和底行模式（last line mode） 命令模式 -刚进入文件就是命令模式，通过方向键控制光标位置， -使用命令\u0026#34;dd\u0026#34;删除当前整行 -使用命令\u0026#34;/字段\u0026#34;进行查找 -按\u0026#34;i\u0026#34;在光标所在字符前开始插入 -按\u0026#34;a\u0026#34;在光标所在字符后开始插入 -按\u0026#34;o\u0026#34;在光标所在行的下面另起一新行插入 -按\u0026#34;：\u0026#34;进入底行模式 插入模式 -此时可以对文件内容进行编辑，左下角会显示 \u0026#34;-- 插入 --\u0026#34;\u0026#34; -按\u0026#34;esc\u0026#34;进入底行模式 底行模式 -退出编辑： :q -强制退出： :q! -保存并退出： :wq ## 操作步骤示例 ## 1.保存文件：按\u0026#34;esc\u0026#34; -\u0026gt; 输入\u0026#34;:\u0026#34; -\u0026gt; 输入\u0026#34;wq\u0026#34;,回车 //保存并退出编辑 2.取消操作：按\u0026#34;esc\u0026#34; -\u0026gt; 输入\u0026#34;:\u0026#34; -\u0026gt; 输入\u0026#34;q!\u0026#34;,回车 //撤销本次修改并退出编辑 ## 补充 ## vim +10 filename.txt //打开文件并跳到第10行 vim -r /etc/passwd //以只读模式打 开文件 ![[imgs/4.3.1.png]] ![[imgs/4.3.2.png]]\n4.4 查看文件( cat,less,more,tail ) cat a.txt //查看文件最后一屏内容 less a.txt //pgup向上翻页，pgdn向下翻页，\u0026#34;q\u0026#34;退出查看 more a.txt //显示百分比，回车查看下一行，空格查看下一页，\u0026#34;q\u0026#34;退出查看 tail -100 a.txt //查看文件的后100行，\u0026#34;ctrl+c\u0026#34;退出查看 五、文件权限 5.1 权限说明 文件权限简介：\u0026lsquo;r\u0026rsquo; 代表可读（4），\u0026lsquo;w\u0026rsquo; 代表可写（2），\u0026lsquo;x\u0026rsquo; 代表执行权限（1） 括号内代表\u0026quot;8421法\u0026quot;\n##文件权限信息示例：-rwxrw-r\u0026ndash; -第一位：\u0026rsquo;-\u0026lsquo;就代表是文件，\u0026rsquo;d\u0026rsquo;代表是文件夹 -第一组三位：拥有者的权限 -第二组三位：拥有者所在的组，组员的权限 -第三组三位：代表的是其他用户的权限\n5.2 用户，用户组 ![[imgs/5.2.png]] getent passwd //查看当前系统中有那些用户\n5.3 文件权限( chmod ) 普通授权 chmod +x a.txt 8421法 chmod 777 a.txt //1+2+4=7，\u0026ldquo;7\u0026quot;说明授予所有权限\n![[imgs/5.3.1.png]] ![[imgs/5.3.2.png]]\n六、打包与解压 6.1 说明 .zip、.rar //windows系统中压缩文件的扩展名 .tar //linux中打包文件的扩展名 .gz //linux中压缩文件的扩展名 .tar.gz //linux中打包并压缩文件的扩展名\n6.2 打包文件（tar -zcvf） tar -zcvf (打包压缩后的文件名) (要打包的文件) 参数说明： z：调用gzip压缩命令进行压缩; c：打包文件; v：显示运行过程; f：指定文件名;\n示例： tar -zcvf a.tar file1 file2,\u0026hellip; //多个文件压缩打包\n6.3 解压文件（tar -zxvf ） tar -zxvf a.tar //解包至当前目录 tar -zxvf a.tar -c /usr\u0026mdash;\u0026mdash; //指定解压的位置 unzip test.zip //解压*.zip文件 unzip -l test.zip //查看*.zip文件的内容\n七、其他常用命令 7.1 find find . -name \u0026ldquo;*.c\u0026rdquo; //将目前目录及其子目录下所有延伸档名是 c 的文件列出来 find . -type f //将目前目录其其下子目录中所有一般文件列出 find . -ctime -20 //将目前目录及其子目录下所有最近 20 天内更新过的文件列出 find /var/log -type f -mtime +7 -ok rm {} ; //查找/var/log目录中更改时间在7日以前的普通文件，并在删除之前询问它们 find . -type f -perm 644 -exec ls -l {} ; //查找前目录中文件属主具有读、写权限，并且文件所属组的用户和其他用户具有读权限的文件 find / -type f -size 0 -exec ls -l {} ; //为了查找系统中所有文件长度为0的普通文件，并列出它们的完整路径\n7.2 whereis whereis ls //将和ls文件相关的文件都查找出来\n7.3 which 说明：which指令会在环境变量$path设置的目录里查找符合条件的文件。 which bash //查看指令\u0026quot;bash\u0026quot;的绝对路径\n7.4 sudo 说明：sudo命令以系统管理者的身份执行指令，也就是说，经由 sudo 所执行的指令就好像是 root 亲自执行。需要输入自己账户密码。 使用权限：在 /etc/sudoers 中有出现的使用者 sudo -l //列出目前的权限 $ sudo -u yao vi ~www/index.html //以 yao 用户身份编辑 home 目录下www目录中的 index.html 文件\n7.5 grep grep -i \u0026ldquo;the\u0026rdquo; demo_file //在文件中查找字符串(不区分大小写) grep -a 3 -i \u0026ldquo;example\u0026rdquo; demo_text //输出成功匹配的行，以及该行之后的三行 grep -r \u0026ldquo;ramesh\u0026rdquo; * //在一个文件夹中递归查询包含指定字符串的文件\n7.6 service 说明：service命令用于运行system v init脚本，这些脚本一般位于/etc/init.d文件下，这个命令可以直接运行这个文件夹里面的脚本，而不用加上路径 service ssh status //查看服务状态 service \u0026ndash;status-all //查看所有服务状态 service ssh restart //重启服务\n7.7 free 说明：这个命令用于显示系统当前内存的使用情况，包括已用内存、可用内存和交换内存的情况 free -g //以g为单位输出内存的使用量，-g为gb，-m为mb，-k为kb，-b为字节 free -t //查看所有内存的汇总\n7.8 top top //显示当前系统中占用资源最多的一些进程, shift+m 按照内存大小查看\n7.9 df 说明：显示文件系统的磁盘使用情况 df -h //一种易看的显示\n7.10 mount mount /dev/sdb1 /u01 //挂载一个文件系统，需要先创建一个目录，然后将这个文件系统挂载到这个目录上 dev/sdb1 /u01 ext2 defaults 0 2 //添加到fstab中进行自动挂载，这样任何时候系统重启的时候，文件系统都会被加载\n7.11 uname 说明：uname可以显示一些重要的系统信息，例如内核名称、主机名、内核版本号、处理器类型之类的信息 uname -a\n7.12 yum 说明：安装插件命令 yum install httpd //使用yum安装apache yum update httpd //更新apache yum remove httpd //卸载/删除apache\n7.13 rpm 说明：插件安装命令 rpm -ivh httpd-2.2.3-22.0.1.el5.i386.rpm //使用rpm文件安装apache rpm -uvh httpd-2.2.3-22.0.1.el5.i386.rpm //使用rpm更新apache rpm -ev httpd //卸载/删除apache\n7.14 date date -s \u0026ldquo;01/31/2010 23:59:53\u0026rdquo; ///设置系统时间\n7.15 wget 说明：使用wget从网上下载软件、音乐、视频 示例：wget http://prdownloads.sourceforge.net/sourceforge/nagios/nagios-3.2.1.tar.gz //下载文件并以指定的文件名保存文件 wget -o nagios.tar.gz http://prdownloads.sourceforge.net/sourceforge/nagios/nagios-3.2.1.tar.gz\n7.16 ftp ftp ip/hostname //访问ftp服务器 mls *.html - //显示远程主机上文件列表\n7.17 scp scp /opt/data.txt 192.168.1.101:/opt/ //将本地opt目录下的data文件发送到192.168.1.101服务器的opt目录下\n八、系统管理 8.1 防火墙操作\nservice iptables status //查看iptables服务的状态 service iptables start //开启iptables服务 service iptables stop //停止iptables服务 service iptables restart //重启iptables服务 chkconfig iptables off //关闭iptables服务的开机自启动 chkconfig iptables on //开启iptables服务的开机自启动 ##centos7 防火墙操作 systemctl status firewalld.service //查看防火墙状态 systemctl stop firewalld.service //关闭运行的防火墙 systemctl disable firewalld.service //永久禁止防火墙服务\n8.2 修改主机名（centos 7）\nhostnamectl set-hostname 主机名\n8.3 查看网络\nifconfig\n8.4 修改ip\n修改网络配置文件，文件地址：/etc/sysconfig/network-scripts/ifcfg-eth0 主要修改以下配置：\ntype=ethernet //网络类型 bootproto=static //静态ip device=ens00 //网卡名 ipaddr=192.168.1.100 //设置的ip netmask=255.255.255.0 //子网掩码 gateway=192.168.1.1 //网关 dns1=192.168.1.1 //dns dns2=8.8.8.8 //备用dns onboot=yes //系统启动时启动此设置 修改保存以后使用命令重启网卡：service network restart\n8.5 配置映射\n修改文件： vi /etc/hosts 在文件最后添加映射地址，示例如下： 192.168.1.101 node1 192.168.1.102 node2 192.168.1.103 node3 配置好以后保存退出，输入命令：ping node1 ，可见实际 ping 的是 192.168.1.101。\n8.6 查看进程\nps -ef //查看所有正在运行的进程\n8.7 结束进程\nkill pid //杀死该pid的进程 kill -9 pid //强制杀死该进程\n8.8 查看链接\nping ip //查看与此ip地址的连接情况 netstat -an //查看当前系统端口 netstat -an | grep 8080 //查看指定端口\n8.9 快速清屏\nctrl+l //清屏，往上翻可以查看历史操作 8.10 远程主机 ssh ip //远程主机，需要输入用户名和密码\n九、yum命令 9.1 yum命令 ![[imgs/9.1.png]] 9.2 systemctl ![[imgs/9.2.png]] 9.3 ln -s 命令 ![[imgs/9.3.png]] 9.4 hostname ![[imgs/9.4.png]] 9.5 域名解析 ![[imgs/9.5.png]]\n","date":"2024-05-10","permalink":"http://54rookie.com/posts/linux%E6%93%8D%E4%BD%9C%E6%8C%87%E4%BB%A4/","summary":"转载自：https://blog.csdn.net/m0_46422300/article/details/104645072 一、基础知识 1.1 Linux系统的文件","title":"linux"},]
[{"content":"\n密码学小常识： 什么是iacr：\n密码学中最著名的学术会议当属国际密码学协会（iacr，international association of cryptological research）所主办的三个⼤会了：crypto、eurocrypt、asiacrypt，即美密会、欧密会、 亚密会，其中欧密会和美密会的⽔平最⾼（亚密会的资历最浅，虽然近⼏年上升很快，但要完全赶上还需要⼀定的时间）。密码学中最重要的⽂章⼀般都会在这三个会议中发布。 什么是dblp：\n定义： dblp（database systems and logic programming） 是计算机领域内对研究的成果以作者为核心的一个计算机类英文文献的集成数据库系统。 简介： dblp按年代列出了作者的科研成果。包括国际期刊和会议等公开发表的论文。dblp没有提供对中文文献的收录和检索功能，国内的权威期刊及重要会议的论文缺乏一个类似的集成检索系统。dblp所收录的期刊和会议论文质量较高，dblp的文献更新速度很快，很好地反应了国外学术研究的前沿方向。 特征： dblp在学术界有很好的声誉，给人们带来了极大的便利，其权威性也得到了研究界的高度认可。但dblp没有提供对中文文献的收录和检索功能，国内的权威期刊及重要会议的论文缺乏一个类似的集成检索系统。dblp项目是德国特里尔大学的michael ley负责开发和维护。它提供计算机领域科学文献的搜索服务，但只储存这些文献的相关元数据，如标题，作者，发表日期等。截至2009年7月已经有超过1,200,000文献。和一般流行的情况不同，dblp并没有使用数据库而是使用xml存储元数据。 dblp地址： https://dblp.org/ 参考文献：\niacr：https://blog.csdn.net/a33280000f/article/details/117929248 dblp：https://zhuanlan.zhihu.com/p/595538578 ccf-a的会议和期刊（网络与信息安全）： 三大顶会:\n_eurocrypt _ international conference on the theory and applications of cryptographic techniques crypto international cryptology conference. asiacrypt annual international conference on the theory and application of cryptology and information security. 会议:\nccs acm conference on computer and communications security _eurocrypt _ international conference on the theory and applications of cryptographic techniques crypto international cryptology conference. s\u0026amp;p ieee symposium on security and privacy _usenix security _ usenix security symposium 期刊:\n_ ieee transactions on dependable and secure computing _ ieee transactions on information forensics and security journal of cryptology 论文中常用的符号 i.e. ：\n是id est（“that is” , \u0026ldquo;in other words\u0026rdquo;。进一步解释用，意为：也就是，换句话说）的缩写。目的是用来进一步解释前面所说的观点（不像后文的e.g.那样引入实例来形象化），意思是“那就是说，换句话说”。 e.g. ：\n是exempli gratia（\u0026ldquo;for example; for instance;such as\u0026rdquo;。举例用，意为：例如）的缩写，其目的用若干例子来让前面说法更具体，更易感知。 etc. ：\n是et cetera(“and so forth; and the others; and other things; and so on\u0026quot;。举例用，意为：等等)的缩写。它放在列表的最后，表示前面的例子还没列举完，最后加个词“等等”。 viz. ：\n是videlicet（ \u0026ldquo;namely\u0026rdquo;, \u0026ldquo;towit\u0026rdquo;, \u0026ldquo;precisely\u0026rdquo;, \u0026ldquo;that is to say\u0026rdquo;。进一步解释用，意为：即）的缩写，与e.g.不同，viz位于同位列表之前，要把它前面单词所包含的项目全部列出。 et al. ：\n是et alia（\u0026ldquo;and others; and co-workers\u0026rdquo;。在引用文献作者时用，意为:等其他人）的缩写。它几乎都是在列文献作者时使用，即把主要作者列出后，其它作者全放在et al. 里面。 w.r.t. ：\n是with respect to（\u0026ldquo;with respect to\u0026rdquo;。在引用文献作者时用，意为:关于,谈到）的缩写。是 关于；谈及，谈到的意思。 参考文献：\nhttps://zhuanlan.zhihu.com/p/63640148 密码学常用名词介绍 ![[imgs/3.png]] pki系统的介绍：\n参考文献：https://www.jianshu.com/p/c65fa3af1c01 半诚实的模型：\n半诚实的参与方指的是遵循了协议的执行，但保存了协议的中间计算状态的参与方。实际上，半诚实的参与方需要做的是：保存内部的掷硬币过程（产生随机数的过程）和所有从其他参与方接收到的消息。特别的，一个半诚实的参与方会选择随机数和根据预定的程序进行操作，即根据预定的程序公平的产生随机数和执行输入与输出。值得注意的是，一个半诚实参与方相当于是零知识中的诚实验证者。 既然积极的恶意敌手更有攻击能力，那么我们到底为什么还要考虑攻击能力更弱的半诚实模型？即半诚实的敌手模型的必要性在哪里？其实在一般情况下，发动主动攻击要比监听整个计算过程在攻击复杂的多，原因是，对于一个运行在计算机上程序，主动的攻击需要用一些非常复杂的程序去攻击他，但是对于单纯的获取计算过程中的数据而言，这是比较容易的，所以半诚实敌手模型在实际的生产生活中更加的普遍存在，就是单独考虑半诚实敌手的必要性。 参考文献： https://blog.csdn.net/zmrlinux/article/details/103068525 加盐哈希：\n在密码学中，是指通过在密码任意固定位置插入特定的字符串，让散列后的结果和使用原始密码的散列结果不相符，这种过程称之为“加盐”。 加盐哈希早用户名密码中应用非常广泛。 参考文献： https://zhuanlan.zhihu.com/p/22860282?from_voters_page=true 数字签名的分类 ![[imgs/4.png]] 参考文献:\nhttps://blog.csdn.net/weixin_43851783/article/details/110391153 双线性映射 双线性映射的定义 一般的双线性映射定义如下： ![[imgs/bp1.png]]\n注意： 现在的密码学相关论文中，习惯将g1,g2设置为乘法循环群。但是，基于椭圆曲线的双线性群构造中，g1,g2是加法群。在大约2005年以前的论文中，g1，g2是加法循环群。 双线性映射可以通过有限域上的超椭圆曲线上的tate对或weil对来构造。 现代习惯性的双线性映射定义：\n![[imgs/bp2.png]]\n双线性映射的分类 根据$\\mathbb{g}_1$与$\\mathbb{g}_2$是否为同一个群，可以划分为 对称式与非对称式。 最重要的还是双线性这条性质，几乎所有的构造都是依赖于此。\n$g_1×g_1→g_t$：对称式双线性映射，即$g_1=g_2$。\t【\u0026ldquo;type-1型配对\u0026rdquo;：安全性最低】 $g_1×g_2→g_t$：存在一个$g_1到g_2$的同态映射。 【\u0026ldquo;type-2型配对\u0026rdquo;：安全性适中】 $g_1×g_2→g_t$：$g_1$和$g_2$之间不存在同态关系。 【\u0026ldquo;type-3型配对\u0026rdquo;：安全性较高】 注意：\ntype-3配对在带宽和计算效率方面提供了最有效的实现选择。 非对称的双线性映射由于两个群$g_1,g_2$的大小可以取为不一样的，这样就会导致在两个群上计算点乘运算的计算开销不同。合理利用这一点，可以实现一些特殊的功能。【参考sm9算法】 假设加法循环群$g_1$的生成元为$p$，则双线性映射具有以下性质：\n$e(a+b,c)=e(a,c)*e(b,c)$ 由于$a$和$b$是群$g_1$上的两个元素，故存在a,b满足 $a=ap，b=bp$；则 $\\begin{align} \u0026amp;\\ \\ e(a+b,c)\\ \u0026amp;=e((a+b)p,c)\\ \u0026amp;=e(p,c)^{a+b}\\ \u0026amp;=e(p,c)^a*e(p,c)^b\\ \u0026amp;=e(ap,c)*e(bp,c)\\ \u0026amp;=e(a,c)*e(b,c)\\ \\end{align}$ $e(a,b+c)=e(a,b)*e(a,c)$ 证明同上 $e(xa,b)=e(a,xb)=e(a,b)^x$ $e(a+b,c+d)=e(a,c)*e(a,d)*e(b,c)*e(a,d)$ $e(a,b)^x*e(a,b)^y=e(a,b)^{x+y}$ $e(a,b)*e(c,d)=e(a+c,b+d)*e(a,d)^{-1}*e(b,c)^{-1}$ 补充：\n用上述的证明方法可以证明，在非对称的双线性映射中，上述性质也是成立的。即： $e(a+b,c)=e(a,c)*e(b,c)$ $e(a,b+c)=e(a,b)*e(a,c)$ $e(a^x,b)=e(a,b^x)=e(a,b)^x$ $e(a+b,c+d)=e(a,c)*e(a,d)*e(b,c)*e(a,d)$ $e(a,b)^x*e(a,b)^y=e(a,b)^{x+y}$ $e(a,b)*e(c,d)=e(a+c,b+d)*e(a,d)^{-1}*e(b,c)^{-1}$ 乘法循环群下的性质为： $e(ab,c)=e(a,c)*e(b,c)$ $e(a,bc)=e(a,b)*e(a,c)$ $e(a^x,b)=e(a,b^x)=e(a,b)^x$ $e(ab,cd)=e(a,c)*e(a,d)*e(b,c)*e(a,d)$ $e(a,b)^x*e(a,b)^y=e(a,b)^{x+y}$ $e(a,b)*e(c,d)=e(ac,bd)*e(a,d)^{-1}*e(b,c)^{-1}$ 注意： $e(a,c)^x*e(b,c)^y≠e(ab,c)^{x+y}$ 零知识证明 与 schnoor 签名： 零知识签名的概念 定义：\n零知识证明的定义为：证明者（prover）能够在不向验证者（verifier）提供任何有用的信息的情况下，使验证者（verifier）相信某个论断是正确的。 性质：\n完备性（completeness）：只要证明者拥有相应的知识，那么就能通过验证者的验证，即证明者有足够大的概率使验证者确信。； 可靠性（soundness）：如果证明者没有相应的知识，则无法通过验证者的验证，即证明者欺骗验证者的概率可以忽略。 零知识性（zero-knowledge）：证明者在交互过程中仅向验证者透露是否拥有相应知识的陈述，不会泄露任何关于知识的额外信息。 举例说明：\nalice是色盲，bob不是色盲，在bob手上有两个大小，形状完全一样的球，但这两个球的颜色不一样，一个球是蓝色的，另一个球是红色的，由于alice是色盲，所以alice无法分辨这两个球是否是一样的，bob需要向alice证明这两个球是不一样的。在这里，alice被称为验证者，他需要验证bob的陈述正确与否，bob被称为证明者，他需要证明自己的陈述（存在两个颜色不一样的球），bob需要在alice不能获得两个球的颜色的情况下，向alice证明这两个球的颜色是不一样的这个事实，这与零知识证明的定义是相符合的。 alice当bob的面拿起两个球，左手拿蓝球，右手拿红球，然后将双手放到背后，这样bob就看不到alice手上的球了，alice在背后随机交换左右手上的球，交换完成后alice将手伸出，并询问bob两个球是否交换过位置，如果bob能看到球上的颜色，那么每次alice换过球的位置后，bob都能正确回答出alice的问题。 第一次，alice偷偷交换了手中球的位置，然后alice问bob是否交换了球的位置，如果bob回答yes，那么alice有50%的概率相信bob是可以区分这两个球的颜色，因为bob有1/2的概率蒙对，所以alice可以在进行一次测试。如果bob回答no，那么alice可以肯定bob不能区分两个球的颜色。 第二次，alice没有交换手中球的位置，然后alice问bob是否交换了球的位置。如果bob回答no，那么alice有75%的概率相信bob是可以区分两个球的颜色。 第一次迭代后，alice可以说bob陈述的断言为真的概率为50％。如果bob第二次回答正确，那么alice可以说bob陈述为真的概率达75％。在第三次迭代后，它将是87.5％。如果连续n次bob都通过了检查，则alice有1-(1/2)^n 的概率可以认为 bob 说的是真的，这两个球的确是有红蓝两种颜色。 零知识证明是一种基于概率的验证方式，验证者（verifier）基于一定的随机性向证明者（prover)提出问题，如果证明者都能给出正确回答，则说明证明者大概率拥有他所声称的“知识”。零知识证明并不是数学意义上的证明，因为它存在小概率的误差，欺骗的证明者有可能通过虚假的陈诉骗过验证者。换句话说，零知识证明是概率证明而不是确定性证明，但是也存在技术能将误差降低到可以忽略的值。 知识签名： 签名者利用数学知识和公共信息，非交互和不泄露某个秘密的情况下，向别人证明他知道这个秘密。\n常见的知识签名有三种： 离散对数的知识签名 双离散对数的知识签名 离散对数e次方根的知识签名 离散对数的知识签名：(零知识证明)\n符号表示为：\n![[imgs/零知识1.png]]\n离散对数的知识签名是针对这样一个问题：$y = g^x mod(n)$; x 是私钥，y 是公钥，g 和 n 都是公开的系统参数，m是消息，现在需要让别别人证明自己拥有私钥 x，并且不泄露 x 的信息。 这里只需要证明者给出一个（c，s）对，符合以下的等式要求即可： $c = h( m||y||g||(g^s) (y^c) )$ 具体的操作过程如下：\n1. 选择一个随机数 $r$ 2. 计算c：根据公式 $c=h(m||y||g||g^r)$ 3. 计算s：根据公式 $s = r - c * x$ 4. (c,s)即为知识签名。 解释说明 ![[imgs/零知识2.png]] 如果知道密钥x，执行通过上面操作过程中的四个步骤就可以轻松计算出(c,s)对的值， 如果不知道密钥x，而想算出(c,s)，只能通过3式计算，这在计算上是不可行的。 所以，如果能给出一个满足条件的（c,s）对，就能说明其拥有私钥x。\n双离散对数的知识签名 ![[imgs/知识签名1.png]]\n详细见参考文献【1】 离散对数e次方根的知识签名\n![[imgs/知识签名2.png]]\n见参考文献【1】 参考文章：\n【1】知识签名(signature of knowledge)_zhang-hui的博客-csdn博客 【2】零知识证明介绍 schnorr协议 简介：\nschnorr机制由德国数学家和密码学家claus-peter schnorr在1990年提出，是一种基于离散对数难题的知识证明机制。 schnorr本质上是一种零知识的技术，即prover声称知道一个密钥x的值，通过使用schnorr加密技术，可以在不揭露x的值情况下向verifier证明对x的知情权。即可用于证明你有一个私钥。 schnorr中涉及到的技术有哈希函数的性质、椭圆曲线的离线对数难题。椭圆曲线的离线对数难题：已知椭圆曲线e和点g，随机选择一个整数d，容易计算q=d*g，但是给定的q和g计算d就非常困难**。** schnorr协议分为交互式的和非交互式的。 \u0026lt;交互式的schnorr协议\u0026gt;具体方案如图：\n![[imgs/schnnor1.png]] 解释上图如下：\nalice：随机地选择一个标量r，然后计算出r=r*g（椭圆曲线上的一点），将r发送给bob； bob：回应一个随机标量 c ； alice：通过计算$z=r+c*sk$，将标量 z 回应给bob； bob：将s转换为椭圆曲线上的点，即zg，然后验证$zg=c*pk+r$。 说明：\n由于z=r+csk，等式两边同时添加相同的生成元可得：zg=c*pk+r。即可验证alice确实拥有私钥sk，但是验证者bob并不能得到私钥sk的值，因此这个过程是零知识的，且是交互式的。此协议也叫做sigma protocol。 安全性分析\n由于椭圆曲线上的离散对数问题，知道r和g的情况下通过r=r*g解出r是不可能的，所以保证了r的私密性。但是，这也是在证明者和验证者在私有安全通道中执行的。这是由于此协议存在交互过程，此方案只对参与交互的验证者有效，参与交互的双方如果串通了随机数c，那么不参与交互的验证者也无法判断出 证明者是否真的拥有私钥。因此，是无法公开验证的。 不妨来个数学理论推导：在公开验证的条件下，两个验证者分别提供两个不同的随机值c1和c2，并要求证明者计算z1 = r + c1sk，z2 = r + c2sk，即可计算出sk =（z1-z2）/（c1-c2）。因此，这个过程便无法公开验证。 进一步分析，为什么需要验证者回复一个随机标量c呢？防止alice造假！如果bob不回复一个c，就变成如下一次性交互。由于椭圆曲线上的离散对数问题，知道pk和g的情况下通过pk = a * g 计算a是不可能的，所以保证了 a 的私密性。但是这种方案是存在问题的，a 和 r 都是alice自己生成的，她知道bob会用pk和 r 相加然后再与z * g进行比较。所以不知道a的攻击者可以进行以下构造： - r = r * g - pk - z = r。 这样bob的验证过程就变成：z * g = r * g = pk + r。这是永远成立的，这就导致不知道私钥的人也能通过证明。 加入随机数 c 之后可以完美的避免这个问题。因为如果敌手a想要在不知道 sk 的情况下以同样的方式欺骗alice，需要构造： - r = r * g - c * pk - z = r。 由于a要首先把 r 发给 bob，然后bob才将 c 发给 a，而 r 需要 c 才能计算出来，故敌手不能成功。 非交互式的schnorr协议具体方案：\n将交互式的schnorr协议改造为非交互式的非常简单。根据fiat-shamir启发式方法，改造如下： alice：随机选择 r，计算$r=r*g$ （椭圆曲线上的一点）； alice：计算 $c = h(r,pk)$； alice：通过计算 $z=r+c*sk$， 将$(r,c,z)$给bob； bob： bob验证 $zg = cpk+r$。 安全性分析： 这里同理，敌手需要构造以下信息才能欺骗bob - $r = r * g - c * pk$ - $c = h(r,pk)$ - $z = r$。 由于计算 r 需要用到 c ，计算 c 需要用到 r ；故导致敌手无法完美构造满足条件的上式： 如果先构造r，需要先知道 c，由于 c 的计算需要用到 r ，且哈希函数是单向的，因此不可行。 先构造 c 同理. sigma协议和fiat-shamir启发式：\nhttps://www.yuque.com/xiaozeng-lhkfj/guc7a3/egsn1gzebrmkfcz1#fumtk【笔记】 参考文献：\nhttp://blockchain.whu.edu.cn/uploads/soft/201105/1_1954088811.pdf ecdsa签名 ecdsa简介： 椭圆曲线数字签名算法（ecdsa）是使用椭圆曲线密码（ecc）对数字签名算法（dsa）的模拟。ecdsa于1999年成为ansi标准，并于2000年成为ieee和nist标准。它在1998年既已为iso所接受，并且包含它的其他一些标准亦在iso的考虑之中。与普通的离散对数问题（discrete logarithm problem dlp）和大数分解问题（integer factorization problem ifp）不同，椭圆曲线离散对数问题（elliptic curve discrete logarithm problem ecdlp）没有亚指数时间的解决方法。因此椭圆曲线密码的单位比特强度要高于其他公钥体制。 ecdsa具体方案： 参数生成： 选择有限域$f_p$上的一个椭圆曲线$e(a,b)：y^2=x^3+ax+b \\ (mod \\ p)$且对于$e(a,b)$来说，它满足$4a^3+27b^2≠0\\ (mod \\ p)$ 选择$e(a,b)$上的一个点$p$作为基点，其中$p$的阶为$n$ 选择随机数$sk$作为私钥(其中k\u0026lt;n)，计算公钥$p_{pub}=skp$ 则最终的参数为$params={e(a,b),p,p_{pub}}$ 签名（假设要对消息m进行签名）： 选择随机数$r$，计算$rp=（r,y）$ 计算$h=h(m)$ 计算$s = r^{-1}(h + skr)\\ (mod\\ n)$ （这里，$k^{-1}$是k在模n下的乘法逆元） 则最终签名为$σ=（r,s）$。（注意，如果r,s中任意一个为零，重新选择随机数计算签名） 验签（收到了签名${m,σ}={m,r,s}$） 计算$h = h(m)$ 计算$s^{-1}hp+s^{-1}rp_{pub}=(x_1,y_1)$ 计算$r_1≡x_1\\ (mod\\ p)$ 比较$r_1=r$是否成立，如果成立，验签成功。否则，验签失败 bls短签名 bls签名简介 bls签名算法是斯坦福大学计算机系三人提出：dan boneh，ben lynn以及hovav shacham。bls的主要思想是待签名的消息散列到一个椭圆曲线上的一个点，并利用双线性映射e函数的交换性质，在不泄露私钥的情况下，验证签名。bls的算法在签名合并，多签，m/n多签有丰富的应用。\nbls具体方案 预备知识：\n新型散列函数（hash函数）： 一般的hash（散列）函数的结果都是数值。在bls签名算法中需要用的散列函数的结果是椭圆曲线上的一个点。也就是说，散列结果对应椭圆曲线上的一个点。以 ecc 和 sha-256 为例。比特币用的椭圆曲线是secp256k1，也就是该曲线由2²⁵⁶个点组成。sha-256普通hash函数的结果也是256位。如果用hash函数的数值结果，对应于椭圆曲线上点横坐标x，有两个点y和-y都在椭圆曲线y²=x³+ax+b上。说明sha-256的结果，有50%的概率，要么找到两个点，要么找不到点。 为了解决这个问题，需要用到直接从消息计算到一个点的哈希，给定消息m，计算h(m)，使得h(m)∈ g，其中g是椭圆曲线点构成的群。dan boneh在文章中给出了一个具体的做法，例如采用的仍然是普通哈希，把结果（先看成一个数）当作是一个点的x坐标，然后带入椭圆曲线公式计算相应的y坐标。如果不存在，则把第一步的x坐标作为输入继续算哈希得到另一个x坐标，计算相应y坐标，直到求出y为止。根据二次剩余理论，平均算2次即可得出一个对应的y。这样确保首先是一个确定性的算法，可以在有限步骤内(数学期望为2次)完成计算；其次，如果采用的哈希函数本身是安全的，则整体的计算过程也是安全的。这样整个计算称为map-to-point哈希。 双线性映射： 本方案验证阶段用到了双线性映射，双线性映射的内容参考本文介绍___【在本文的上面】 具体方案【概述】：\n假设alice的私钥为$pk$，公钥为$p = pk×g$，想对消息$m$签名，则： 签名方案： 计算$s = pk×h(m)$作为签名 验签方法： 判断$e(p, h(m)) = e(g, s)$是否成立，成立则验签成功。 具体方案【展开来说】： 给定私钥$pk$，公钥$p = pk×g$，以及待签名的消息为$m$。签名的计算公式如下：\n$s = pk×h(m)$ ； 其中$h(m)$是第一节中讲述的新型散列函数。 上述过程如下图所示：\n![[imgs/bls1.png]]\n验证过程涉及e函数，计算如下的等式是否成立：\n$e(p, h(m)) = e(g, s)$ 证明过程如下：\n$\\begin{align} \u0026amp; \\ e(p, h(m)) \\ \u0026amp; = e(pk×g, h(m)) \\ \u0026amp; = e(g, pk×h(m)) \\ \u0026amp; = e(g, s) \\end{align}$ 证明过程示意如下：\n![[imgs/bls2.png]]\nbls签名的应用【聚合签名】 签名合并：\nbls签名算法有很多应用，其中一个是签名的合并。想象一下，一个区块中有n个交易，每个交易都有独立的公钥$p_i$，签名$s_i$，以及交易内容$m_i$。如果需要知道区块中的交易的签名是否都正确，传统的方式，区块中的交易需要一个个的验证签名。\n然而，区块中需要存储所有交易的签名。用bls算法进行签名的合并只需要存储一个33个字节的bls签名。\n合并签名为$s = s_1+s_2+…+s_n$ 其中 $s_i = p_i×h(m_i)$ ； $i={1,2,\u0026hellip;,n}$ 验证过程是：\n$e(g, s) = e(p_1, h(m_1))⋅e(p_2, h(m_2))⋅…⋅e(p_{n}, h(m_{n}))$ 证明过程如下：\n$\\begin{align} \u0026amp;e(g, s) = e(g, s_1+s_2+…+s_{n}) \\ \u0026amp;= e(g, s_1)⋅e(g, s_2)⋅…⋅e(g, s_{n}) \\ \u0026amp;= e(g, pk_1×h(m_1))⋅…⋅e(g, pk_{n}×h(m_{n})) \\ \u0026amp;= e(pk_1×g, h(m_1))⋅…⋅e(pk_{n}×g, h(m_{n})) \\ \u0026amp;= e(p_1, h(m1))⋅e(p_2, h(m_2))⋅…⋅e(p_{n}, h(m_{n})) \\end{align}$ 从证明过程可见，主要是用了e函数的交换规则。bls算法在多签以及m/n签名还有更多应用，这里不详细展开。\n国密sm9算法 sm9简介 sm9 是和 sm2/rsa 类似的非对称加密算法。在传统的非对称加密算法中，密钥对的生成存在不少的限制如：rsa2048_sha256和适用这个加密算法的密钥对是有适配关系的，特定的非对称加密算法是要用专门的手段生成密钥对。 传统的非对称加密算法在政务或商业用途中需要一种叫ca（certification authority）的机构来做身份认证、颁发数字证书并管理这些数字证书。你以后的签名（就是用你的私钥来加密电子数据，比如签电子合同）需要用到数字证书以及密钥。 在sm9算法中，用户将自己的公钥给kgc（key generating centre），kgc为用户生成一个该公钥对应的私钥。 sm9算法特别的地方是：用易于记忆的用户特征字符串（如：邮箱地址、身份证号码等）来作为公钥，目的就是为了降低公钥系统中密钥和证书管理的复杂性。所以sm9算法不需要申请数字证书，如果国家统一管理私钥（相当于充当kgc），ca机构有可能要被干掉了。 sm是“商密”的拼音。sm9的家族里还有sm1/2/3/4等对称、非对称、摘要算法。是我国“自主知识产权”的算法。虽然只是ecc的一种实现，但是还是有很多创新的。rsa的应用太广泛啦，生态方面sm系列还有待努力。这个sm9用户体验好，应该是很好的助推工具。 因为动了ca的蛋糕，广泛运用还需要一定时间。 sm9签名算法 预备知识：\nh(a，q)：表示一种哈希函数，对a进行哈希，得到一个小于 q 的哈希值。\nkgc：密钥生成中心，用户将自己的身份作为公钥传输给kgc，kgc为用户生成这个公钥对应的私钥。\n双线性映射: 本文使用$g_1×g_2→g_t$的双线性映射，其中$g_2$上的点的大小是$g_1$上的2倍。$g_1$和$g_2$是加法循环群，$g_t$是乘法循环群。\n详细方案\n密钥生成： 在这个阶段，用户将自己的标识符 $id$作为公钥发给kgc，kgc为其生成对应的私钥$d_{id}$。除此之外，用户还会生成整个系统的公私钥对$(ks,p_{pub_s})$，并将公钥$p_{pub_s}$公开。 具体过程如下： ![[imgs/sm91.png]]\nsm9签名 在这个阶段，alice使用自己的私钥$d_{id}$和系统公钥$p_{pub_s}$对消息进行签名,得到签名$(h,s)$ 具体过程如下: ![[imgs/sm92.png]]\nsm9验签: 在这个阶段,任何人都可以使用alice的公钥$id$对他的签名$(h,s)$进行验签. 具体过程如下: ![[imgs/sm93.jpg]]\n整个流程如下:\n![[imgs/sm94.jpg]]\n参考资料：\n国家标准全文阅读|标准检索 【区块链与密码学】第6-7讲：sm9数字签名算法 sm9加密算法 预备知识:\nkdf($\\cdot$)：密钥导出函数，根据输入输出一个密钥 $k＝（k_1,k_2）$， mac(k,m): 消息认证码，通过k认证消息m的完整性。 注意：kdf在sm9中有专门的介绍，这里省略了这一部分。 sm9加解密算法： ![[imgs/sm95.jpg]]\n正确性的证明： ![[imgs/sm96.png]]\n伪随机函数（prf）与（oprf） 概念 简要介绍：\n![[imgs/伪随机1.png]]\n正式定义：\n![[imgs/伪随机2.png]]\n基于prf的cpa加密方案 ![[imgs/伪随机3.png]]\n证明备注：\n当d面对的是一个真随机函数时，a为了在游戏中获得优势，选择$m_0,m_1$之前一共进行了q(n)次oracle查询，如果他这q(n)次全部查询的是$m_0$的密文，最好的情况是：a每次询问得到的密文$\u0026lt;r,y\\oplus m\u0026gt;$中 r都不同，则他能获得$m_0$的q(n)个不同的密文。由于加密时选择的$r$一共有$2^n$种可能，也就是$m_0$至少有$2^n$个不同的密文。所以a区分$m_0$的密文成功率不超过$q(n)/2^n$,故 ![[imgs/伪随机4.png]] 上面的$ε(n)$表示当d面对的是伪随机函数的时候，a赢得游戏的优势 参考文献：\nhttps://blog.csdn.net/weixin_39578432/article/details/120405776 prf的应用 ![[imgs/伪随机5.png]] 参考文献：\nhttps://www.cnblogs.com/pam-sh/p/16216240.html 盲签名算法【基于rsa的】 盲签名(blind signature) 是由chaum,david提出的一种数字签名方式，其中消息的内容在签名之前对签名者是不可见的（盲化）。经过盲签名得到的签名值可以使用原始的非盲消息使用常规数字签名验证的方式进行公开验证。盲签名可以有效的保护隐私，其中签名者和消息作者不同，在电子投票系统和数字现金系统中会被使用。 盲签名常常被类比成下面的场景：alice想让bob在自己的文件上签名，但是不希望bob看到文件内容，于是alice在文件上方叠放了一张复写纸，然后将文件和复写纸放入信封密封起来交给bob。bob再拿到信封后验证了alice的身份后，直接在密封好的信封上签字，这样虽然bob是对密封后的信封签字，但是alice拿到签名后的信封后，拆开信封就可以拿到经过bob签字的文件。\n基于rsa的盲签名实现 ![[imgs/盲签名1.png]]\n群签名 群签名的概念 群签名是这样一个数字签名：在一个群签名的方案中，一个群体中的任意一个成员可以代表这个群体对消息进行签名，并且其他人可以使用群公钥对这个签名进行公开验证。在验证时，验证者只能验证签名是来自这个群组的，但是无法知道到底是群中的哪个成员对消息进行了签名。 在群签名中，存在一个群管理员，该管理员可以通过对签名进行操作得到签名者的真实身份。\n群签名的步骤 一个群签名是一个包含下面过程的数字签名方案： （1）创建：一个用以产生群公钥和私钥的概率多项式时间算法。\n（2）加入：一个用户和群管理员之间的使用户成为群管理员的交互式协议。执行该协议可以产生群员的私钥和成员证书，并使群管理员得到群成员的私有密钥。\n（3）签名：一个概率算法，当输入一个消息和一个群成员的私钥后，输出对消息的签名。\n（4）验证：一个概率算法，当输入一个群成员的签名和群公钥后，可以判断签名是否属于这个群。\n（5）打开：一个在给定一个签名及群私钥的条件下确认签名人的合法身份的算法。 群签名新的属性：\n公钥大小固定： 公钥的大小和生成的签名可以不依赖于组的大小【cs97方案】，这一特性对于群签名方案的构建和应用是非常重要的，它避免了公钥和签名的大小随着有效组成员数量的增加而过度膨胀。 opener和manager分开： 将组管理员的权限稀释为两部分，opener用来对群成员的签名进行追踪，得到群成员的真实身份乐；而manager用来管理群成员的加入和撤销。 有些方案还存在一个tracer，他可以判断两个群签名是否来自同一个群成员。通过这种权力的稀释，可以降低用户对群管理员信任程度。 半动态模型： 允许用户再需要的时候动态的加入群组，或者允许群管理员动态的对群成员进行撤销。实现撤销常见的方法如下： ① 组管理员更新组公钥，并将其发送给为被撤销的用户 ② 使用累加器：它可以高效的队组成员进行撤销和加入 ③ 签名者在签署消息，或者根据组的变化更新自己的密钥时，需要提供合格的成员资格证明。常见的方法是把非法用户的id放入黑名单，在更新密钥的时候，将黑名单内的用户证书将面临除零异常 ④ 验证者本地撤销：gm发现恶意用户的签名之后，将签名者的身份发给签名的验证者。这种撤销方式只有验证者拥有撤销列表。 全动态模型： 允许动态注册用户，又允许动态撤销组成员，使得该算法具有更强的安全性和更高的实用性 群签名的一个实例（基于rsa的群签名） 系统初始化：\n群管理员选择ras的公钥（n，e）\n群管理员选择生成元为g的循环群g，g的阶为n\n选择一个$a∈z_n^*$，这里a对于n的两个素数因子p，q都有较大的乘法阶\n选择密钥长度的上界 λ ，和一个常数 ε ，其中 ε \u0026gt; 1\n该群的公共参数为 params = {n，e，g，g，a，λ，ε}\n成员加入：\n假设alice想要加入这个群组，她首先选择一个私钥 x ，\nalice计算:\n$y = a^x (mod\\ n)$ $z = g^y$（z作为成员密钥） alice发送 y，z 和自己对 z 的个人签名给群管理员gm，并使用知识签名证明自己知道满足$y=a^x(mod\\ n)$的 x 。\ngm验证y和z的合法性，验证知识签名从而确定alice是知道 x 的。\ngm保留（y，z）用于日后打开群签名。\ngm生成alice的群成员证书$v = (y + 1) ^ {1/e}\\ (mod\\ n)$,并将 v 发送给alice。\nalice可以通过计算验证 v 的正确性。\n成员进行群签名：\n随机选择 $r∈z_n^*$\n计算$\\widetilde{g}=g^r$\n计算$\\widetilde{z}=\\widetilde{g}^{\\ y}(mod \\ n)$\n计算$v_1$ = skloglog[ $x:\\widetilde{z}=\\widetilde{g}^{α^x}$ ]\n计算$v_2$ = skrootlog[ $v:\\widetilde{z}\\widetilde{g}=\\widetilde{g}^{v^e}$ ]\n群签名的结果为$sig={\\widetilde{g},\\widetilde{z},v_1,v_2}$\n群签名的验证：\n验证$v_1$即可证明签名者知道私钥 x，且验证者知道了$\\widetilde{z}$是$\\widetilde{g}^{α^x}$的形式。则$\\widetilde{z}\\widetilde{g}$是$\\widetilde{g}^{\\ a^x+1}$的形式。\n用知识证明验证$v_2$时可知：\n$\\widetilde{z}\\widetilde{g}$的结果的形式是$\\widetilde{g}^{\\ a^x+1}$ 验证$v_2$如果成功，证明alice知道$a^x+1$的e次根，即$(a^x+1)^{1/e}=v$这意味着alice知道秘钥x和她的成员密钥的成员证书v。 综上：只要验证了上述群签名就能验证签名 sig 确实来自这个群组的某个成员。（上述验证中验证了签名者群成员证书v的合法性）\n打开群签名\n当遇到特殊情况时，需要知道签名者的真实身份，这是群管理员可以做到这一点：\n由于$\\widetilde{z}=\\widetilde{g}^{\\ y}(mod \\ n)$，且gm存储了每个群成员的（y，z） 所以，gm遍历所有的 y ，如果满足上述等式，就能找到签名者的真实身份。 参考文献：\n97年发表的论文《 efficient group signature schemes for large groups 》 csdn：https://blog.csdn.net/zhang_hui_cs/article/details/8965338 其他群签名实例 bbs签名方案 基于ecdsa的群签名方案 cl群签名方案 具体内容见：\n群签名方案 环签名 环签名的概念 环签名的概述：\n环签名(ring signature)是一种数字签名方案，最初由rivest等人提出，环签名是一种简化的群签名,环签名中只有环成员没有管理者,不需要环成员间的合作。【在群签名中需要事先生成一个群，随后用户才能加入该群，从而代表该群进行签名】 环签名的定义：\n假定有 n 个用户，每一个用户 ![[imgs/环签名1.png]]\n和与之对应的私钥\n![[imgs/环签名2.png]] 。 环签名是一个能够实现签名者无条件匿名的签名方案，它主要由下述算法组成：\n1）生成gen：一个概率多项式时间（ppt）算法，输入为安全参数k，输出为公钥和私钥。这里假定 gen 为每一个用户 ![[imgs/环签名3.png]] ， 产生一个公钥和私钥 ，并且不同用户的公私钥可能来自不同的公钥体制，如有的来自rsa，有的来自dl。\n2）签名sign：一个ppt 算法，在输入消息m和 n 个环成员的公钥 l={ y1 , y2 ,⋯, yn }以及其中一个成员的私钥 xs 后，对消息 m 产生一个签名 r，其中r 中的某个参数根据一定的规则呈环状。 3）验证verify：一个确定性算法，在输入(m,r)后，若 r 为m 的环签名则算法输出“true”，否则算法输出“false”。 环签名因为其签名隐含的某个参数按照一定的规则组成环状而得名。而在之后提出的许多方案中不要求签名的构成结构成环形，只要签名的形成满足自发性、匿名性和群特性，也称之为环签名。 环签名的性质：\n正确性：如果按照正确的签名步骤对消息进行签名，并且在传播过程中签名没被篡改，那么环签名满足签名验证等式。 无条件匿名性：攻击者即使非法获取了所有可能签名者的私钥，他能确定出真正的签名者的概率不超过1/n这里n为所有可能签名者的个数。 不可伪造性：外部攻击在不知道任何成员私钥的情况下，即使能从一个产生环签名的随机预言者那里得到任何消息m的签名，他成功伪造一个合法签名的概率也是可以忽略的。 环签名与群签名的比较：\n一般形式比较： 标准群签名分为5步：【创建】【加入】【签名】【验签】【打开】 标准环签名分3步：【选择环成员】【签名】【验签】 相同点： 都实现了匿名性。 在群签名中，签名者代表这个群进行签名，任何人都可以使用群公钥对这个签名进行验证。在验证过程中，验证者只知道签名者来自这个群，但是不知道签名者是群中的哪一个成员。 在环签名中，签名者代表这个环进行签名，任何人都可以对这个环签名进行验证，在验证过程中，验证者只知道签名者来自这个环，但是不知道签名者具体是环中的哪一个成员。 不同点： 匿名性不同： 群签名实现了有条件的隐私保护，群管理员可以从群签名中找出签名者的真实身份。 环签名是无条件的匿名性。没有任何人可以去除环签名的匿名性。 创建签名的难度方法不同： 用户想要代表某个群对某个消息进行签名，必须由群管理员完成群的【创建】，然后用户【加入】该群后才能进行。 环签名中，用户可以将自己的身份添加到他选择的任何其他用户集合中，并在这个集合上生成一个环签名，该签名只显示出签名者属于该集合，而不暴露其他信息。特别是，未签名的成员甚至可能完全不知道他们参与了这样的签名。 签名长度不同： 群签名的长度很多都是固定的，与群成员的个数无关 环签名中，大多数的环签名方案中，签名的长度随环成员个数的增加而增加。 环签名方案 基于rsa的环签名方案【历史上第一个环签名方案】 假设环签名中有n个人，则一个真实用户的签名泄露自己身份的概率是$1 / n$，为了简单起见，下面令n = 5 来举例说明rsa环签名方案。假设有5个用户，分别为1,2,3,4,5，且用户3要对消息m进行签名，则：\ngen： 为五个用户分别生成rsa公私钥对【（$e_i,n_i$）,（$d_i,n_i$）】。（ i = 1,2,3,4,5 ） ![[imgs/环签名3.png]]\nsign： 签名需要用到一个对称加密算法，这里使用aes算法。环签名的计算过程如下：\n![[imgs/环签名4.png]] 为了简化上述过程，不妨设有一个操作$r_i(c_i)$如下:\t- $r_i(c_i)$=$c_{i+1}$，计算过程如下： - 其中$x_i$为随机数，$\\begin{align} \u0026amp;y_i=rsa_enc_{pk_i}(x_i)=x_i^{e_i}\\ mod \\ n_i \\ \u0026amp;z_{i+1}=c_i \\oplus y_i \\ \u0026amp;c_{i+1}=aes_enc_{key}(z_{i+1}) \\end{align}$ - 为了展示计算过程，上述操作表示为：$r_i(c_i)=c_{i+1}$\u0026mdash;-【】\n通过上述假设，上述的计算过程可以简化为：\n签名者【用户3】选择随机数$c_4$，然后依次计算： $r_4(c_4)=c_5$ \u0026mdash;-【$x_4,y_4,z_{5},c_{5}$】 $r_5(c_5)=c_1$ \u0026mdash;-【$x_5,y_5,z_{1},c_{1}$】 $r_1(c_1)=c_2$ \u0026mdash;-【$x_1,y_1,z_{2},c_{2}$】 $r_2(c_2)=c_3$ \u0026mdash;-【$x_2,y_2,z_{3},c_{3}$】 $r_3(c_3)\u0026rsquo;=c_4\u0026rsquo;$ \u0026mdash;-【$x_3\u0026rsquo;,y_3\u0026rsquo;,z_{4}\u0026rsquo;,c_{4}\u0026rsquo;$】 上面计算的$r_3(c_3)\u0026rsquo;$=【$x_3\u0026rsquo;,y_3\u0026rsquo;,z_{4}\u0026rsquo;,c_{4}\u0026rsquo;$】中，$c_4\u0026rsquo;$满足$c_4\u0026rsquo;=c_4$的概率可以忽略不计，因为上述等式成立的概率仅为为$1/2^{256}$（因为aes加密的输出是256比特） 为了使其相等，令$c_4‘=c_4$，反向计算出$z_4$,然后异或计算出$y_3$，随后【用户3】可以使用自己的私钥（$d_3,n_3$）解密$y_3$得到$x_3$； 将$r_3(c_3)\u0026rsquo;=c_4\u0026rsquo;$\u0026mdash;-【$x_3\u0026rsquo;,y_3\u0026rsquo;,z_{4}\u0026rsquo;,c_{4}\u0026rsquo;$】替换为$r_3(c_3)=c_4$\u0026mdash;-【$x_3,y_3,z_{4},c_{4}$】;这样即可得到环签名$σ={(e_1,n_1),(e_2,n_2),(e_3,n_3),(e_4,n_4),(e_5,n_5),c_1,x_1,x_2,x_3,x_4,x_5}$。 上述签名者【用户3】通过将正向运算替换为反向运算，得到了一个$x_3$，从而得到了环签名 σ 。\n环签名的计算过程正好形成一个环，如下图：\n![[imgs/环签名4.png]]\nverify： 验证者计算： $r_1(c_1)=c_2$ \u0026mdash;-【$x_1,y_1,z_{2},c_{2}$】 $r_2(c_2)=c_3$ \u0026mdash;-【$x_2,y_2,z_{3},c_{3}$】 $r_3(c_3)=c_4$ \u0026mdash;-【$x_3,y_3,z_{4},c_{4}$】 $r_4(c_4)=c_5$ \u0026mdash;-【$x_4,y_4,z_{5},c_{5}$】 $r_5(c_5)=c_1\u0026rsquo;$ \u0026mdash;-【$x_5,y_5,z_{1},c_{1}\u0026rsquo;$】 检查 $c_1\u0026rsquo;=c_1$是否成立，如果成立，输出true ，否则输出 false 这里的解密的实质就是等式$r_5(r_4(r_3(r_2(r_1(c_1)))))=c_1$成立。 参考文献：\nhttps://zhuanlan.zhihu.com/p/450180396 https://zhuanlan.zhihu.com/p/510078836 基础密码学系列课程3: rsa、环签名、同态加密-p1_哔哩哔哩_bilibili 其它环签名 基于rsa的环签名方案 基于离散对数的环签名方案 基于椭圆曲线的环签名方案 代理重加密 什么是代理重加密（pre） 代理重加密（proxy re-encryption）\n主要是通过代理服务器将一个用户用自己公钥加密的密文转换为另一个用户可以用自己私钥解密的密文，且不泄露用户的私钥和明文信息，从而实现密码共享。 基于用户数据隐私性考虑，用户存放在云端的数据都是加密形式存在的。而云环境中存在着大量数据共享的场景。由于数据拥有者对云服务提供商并不完全信任，不能将解密密文的密钥发送给云端，由云端来解密并分享出去。数据拥有者自己下载密文解密后，再用数据接收方的公钥加密并分享，无疑给数据拥有者带来很大的麻烦，同时也失去了云端数据共享的意义。代理重加密可以在不泄漏数据拥有者解密密钥的情况下，实现云端密文数据共享。 具体过程 直观的理解:\n将明文m用自己的公钥$pk_a$加密，得到$c_{pk_a}=e_{nc}(pk_a, m)$，其中的m就是a想要给b的明文内容。 a：将$c_{pk_a}$发给半诚实代理商，并为其生成转化密钥，它是由a为代理商计算好的生成密钥$rk_{a→b}$； proxy：用a生成的密钥 $rk_{a→b}$将密文$c_{pk_a}$转化为b的私钥能够解密的密文 $c_{pk_b}$\n，其中proxy只是提供计算转化服务，无法获取明文； proxy：将生成好的$c_{pk_b}$发给b； b：解密获得a想要密钥共享的明文m； 该过程主要解放了a，a只需生成代理密钥，具体文件的传输，文件的转化，文件的存放都是半诚实代理商完成的。\n专业描述为： ![[imgs/proxy1.png]] 下面为图解：\n![[imgs/proxy2.png]] 具体实例 基于随机预言机模型的pre算法实现：\n我们假设alice和bob已经生成了他们自己的密钥对（基于p256曲线），g是曲线g的生成器，p是一个大素数，也是g的阶。$h_i$，i=2,3,4是哈希函数。m是alice想要共享的消息或明文。server是第三方服务器。 根据离散对数问题生成密钥的方法为alice和bob分别生成公私钥对： ![[imgs/proxy3.png]]\n![[imgs/proxy4.png]] ![[imgs/proxy5.png]]\n![[imgs/proxy6.png]] ![[imgs/proxy7.png]]\ngithub上有参考价值的实现：\njava：pre java-sdk，https://github.com/geghamjivanyan/java-sdk go：gorecrypt，https://github.com/sherlzp/gorecrypt 代理重加密的优化 由于非对称公私钥加密的效率低下，对于较大文件的数据共享是不合适，所以需要对pre流程进行优化。我们可以使用对称加密来保护数据，使用pre来保护对称加密的密钥。详细流程如下所示。 ![[imgs/proxy8.png]] 解释如下：\nalice生成sk1, pk1，同时随机生成一个对称密钥k bob 生成sk2, pk2 alice用自己的公钥pk1加密对称密钥k，得到密文c1；用k加密大文件m得到密文c；然后将（c，c1）发送给代理proxy 当bob想要使用消息m时，他首先向alice发送自己的公钥pk2 alice根据bob的公钥pk2和自己的私钥sk1生成重加密密钥delkey，并请求proxy得到密文c1，解密c1得到对称密钥k，随后用pk2加密k得到c2发给bob proxy用delke重加密密文c。得到newc，并将newc发送给bob bob用自己的私钥sk2分别解密newc和c2得到c和k，并用k解密c得到m 可证明安全理论 证明一个方案是安全的通常只需要证明敌手攻破这个方案的概率是可忽略的就行了。如果在实验中，任何ppt（polynomialtime 多项式时间）敌手成功公婆方案的概率中，最大值高于1/2的部分可以忽略不记，那么就称这个加密方案是安全的。 这里提到了一个概念，“可忽略的概率”。那么到底什么样的概率是可以忽略的呢？\n可忽略的概率 函数f是可忽略的，如果对于每个多项式p(·)，存在一个n，使得所有的整数n\u0026gt;n，都满足f(n)\u0026lt;(1/p(n))。 我们通常将一个可忽略函数称为negl。 对于可忽略的函数 negl1 和 negl2，他有如下性质“\n函数negl3被定义为negl3(n) = negl1(n) + negl2(n)，则函数是可忽略。 对于任何多项式p，函数negl4(n)被定义为negl4(n) = p(n) · negl1(n)，则函数是可忽略的。 第二点可以理解为一个事件发生的概率是多项式的，那么这个实验重复多项式次，依旧是可以忽略的。例如，中彩票的概率是忽略不计的，那么我们买n个多项式次彩票，依旧是可以忽略的。\n参考文献：\nhttps://blog.csdn.net/weixin_39032619/article/details/109569769 基于模拟的安全 基于模拟的安全是指\n基于模拟的安全性的精髓在于, 模拟没有使用到需要保密的信息, 但是攻击者却无法区分模拟场景和真实场景. 此时experiment(无论是real还是ideal(即模拟的那个))中, 敌手到底输出什么已经不重要, 因为experiment中的敌手只是个陪衬, 真正的敌手是两个experiment的区分器. 根据定义, 区分器无法说出哪个experiment是含有要保护的信息的, 那么自然也就不可能从真实的experiment中拿到想要的信息了. 个人理解，在simulation-based security中，敌手的目标没有被明确定义，仅仅可证模拟环境与真实环境不可区分，假设敌手从模拟脚本中学到的知识为 l\\mathbb{l} （泄露量leakage），那么敌手从真实脚本中学到的知识亦为 l\\mathbb{l} ，否则敌手就可以区分模拟环境和真实环境。若敌手在真实环境中可以达成某种目标（对“攻破方案”的具体定义），那么敌手在模拟环境中同样可以达成该目标，我们可以在模拟环境中尝试分析泄漏量 l\\mathbb{l} （这样就不用管实际应用中用户的密钥成分是什么）。 ","date":"2024-05-05","permalink":"http://54rookie.com/posts/%E7%90%86%E8%AE%BA%E7%9F%A5%E8%AF%86/","summary":"密码学小常识： 什么是IACR： 密码学中最著名的学术会议当属国际密码学协会（IACR，International Association of Cryptological Research）所主办的三个⼤会了：Cry","title":"理论知识"},]
[{"content":" 这里给出零知识证明的详细内容\n零知识证明的相关概念 定义： 证明者（prover）在不向验证者（verifier）提供任何有用的信息的情况下，使验证者（verifier）相信某个论断是正确的。 需要满足的满足的条件： 完备性（completeness）：只要证明者拥有相应的知识，那么就能通过验证者的验证，即证明者有足够大的概率使验证者确信。； 可靠性（soundness）：如果证明者没有相应的知识，则无法通过验证者的验证，即证明者欺骗验证者的概率可以忽略。 零知识性（zero-knowledge）：证明者在交互过程中仅向验证者透露是否拥有相应知识的陈述，不会泄露任何关于知识的额外信息。 直观举例 交互式零知识证明： 交互式的零知识证明指的是：证明者（prover）与验证者（verifier）通过若干轮的交互，使得验证者相信证明者确实拥有某个秘密，且证明者不能得到这个秘密的任何信息。 色盲游戏 alice是色盲，bob不是色盲，在bob手上有两个大小，形状完全一样的球，但这两个球的颜色不一样，一个球是蓝色的，另一个球是红色的，由于alice是色盲，所以alice无法分辨这两个球是否是一样的，bob需要向alice证明这两个球是不一样的。在这里，alice被称为验证者，他需要验证bob的陈述正确与否，bob被称为证明者，他需要证明自己的陈述（存在两个颜色不一样的球），bob需要在alice不能获得两个球的颜色的情况下，向alice证明这两个球的颜色是不一样的这个事实，这与零知识证明的定义是相符合的。 alice当bob的面拿起两个球，左手拿蓝球，右手拿红球，然后将双手放到背后，这样bob就看不到alice手上的球了，alice在背后随机交换左右手上的球，交换完成后alice将手伸出，并询问bob两个球是否交换过位置，如果bob能看到球上的颜色，那么每次alice换过球的位置后，bob都能正确回答出alice的问题。 第一次，alice偷偷交换了手中球的位置，然后alice问bob是否交换了球的位置，如果bob回答yes，那么alice有50%的概率相信bob是可以区分这两个球的颜色，因为bob有1/2的概率蒙对，所以alice可以在进行一次测试。如果bob回答no，那么alice可以肯定bob不能区分两个球的颜色。 第二次，alice没有交换手中球的位置，然后alice问bob是否交换了球的位置。如果bob回答no，那么alice有75%的概率相信bob是可以区分两个球的颜色。 第一次迭代后，alice可以说bob陈述的断言为真的概率为50％。如果bob第二次回答正确，那么alice可以说bob陈述为真的概率达75％。在第三次迭代后，它将是87.5％。如果连续n次bob都通过了检查，则alice有1-(1/2)^n 的概率可以认为 bob 说的是真的，这两个球的确是有红蓝两种颜色。 零知识证明是一种基于概率的验证方式，验证者（verifier）基于一定的随机性向证明者（prover)提出问题，如果证明者都能给出正确回答，则说明证明者大概率拥有他所声称的“知识”。零知识证明并不是数学意义上的证明，因为它存在小概率的误差，欺骗的证明者有可能通过虚假的陈诉骗过验证者。换句话说，零知识证明是概率证明而不是确定性证明，但是也存在技术能将误差降低到可以忽略的值。 非交互式零知识证明： 交互式零知识证明协议依赖于验证者的随机尝试，需要证明者和验证者进行多次交互才能完成。非交互式零知识证明（non-interactive zero-knowledge, nizk）将交互次数减少到一次，可实现离线证明和公开验证。在区块链等零知识证明应用场景中，非交互的性质是必须的，因为在区块链系统中，不能假设双方一直在线进行交互，在区块链网络上，证明者只要向全网广播一条证明交易，网络上的矿工在将这条交易打包到区块中的时候就帮验证者完成了零知识证明的校验。 数独游戏 数独是源自18世纪瑞士的一种数学游戏，是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。【下图给出了一个数独游戏的题目，将空白部分填满即可赢得游戏】 alice为了向bob证明他已经解决了一个数独难题，创建了一个防篡改的机器m。alice将生成好的数独答案放入到机器m中，机器m可以向bob发送证明。alice的机器遵循以下公开可验证的协议： 首先，alice在机器中放入尚未被解决的原始数独题目，数独中的谜题卡片三张正面朝上，例如，单元格c3具有3张正面朝上的9号卡片。【即，在3行9列的位置正面朝上放三张数字9的卡片】 则上述题目在机器m中的样子如下图： 机器中每个位置都放了三张卡片，这是因为最后验证的时候，每个位置需要验证“行，列，九宫格”，故需要三张卡片。 接下来，alice上机器将他的答案正面朝下放置在相应的单元格上，同样也是每个单元格放三张。得到如下结果： 最后bob向机器获取证明，机器返回给bob27个袋子： 机器将数独中每一行9张卡片取出，并分别混淆后放入一个袋子中，一共有9行，所以9个袋子 机器将数独中每一列9张卡片取出，并分别混淆后放入一个袋子中，一共有9列，所以9个袋子 机器将数独中每个粗线宫（3*3）内卡片取出，并分别混淆后放入一个袋子中，一共有9个，所以9个袋子 bob分别对这27个袋子进行检查，如果每个袋子中的卡片都包含数字1到9，而且没有任何数字丢失或重复，那么bob可以确认alice的确解开了数独，并且bob并没有从机器返回的证明中获取任何关于数独解的知识，因为机器返回给bob袋子中的数据是被随机打乱的。 参考文献\n零知识证明介绍 sigma协议 预备知识 definition 1: (effective relation)【有效关系】\n指的是一组二元关系$r ⊆ x × y$ 其中 $x,y,r$ 为有效的可辨认的有限集合。 $y$ 中的元素被称作statements【声明】。如果$(x,y) ⊆ r$，则称 x 为 y 的witness【证据】 \u003e **definition 1: (homomorphisms maps)【同态映射】** \u003e  \u003e 参考文献：[https://zhuanlan.zhihu.com/p/622105041](https://zhuanlan.zhihu.com/p/622105041) sigma的定义 **definition 2: (sigma protocol)【sigma协议】 **\n设 $r ⊆ x × y$是一个effective relation。那么一对 $(p,v)$ 构建在 $r$ 上的一个sigma protocol 为： p 是一个叫做 prover 的交互式协议，其输入为一个（witness，statement）对。即$(x,y) ⊆ r$\nv 是一个叫做 verifier 的交互式协议，其输入为一个 statement ，即 $y ⊆ y$\np 和 v 的三轮交互满足下面三个性质，即【正确性】【知识可靠性】和【hvzk】\np 和 v 的交互过程为：【如下图】\n首先 p 计算一个承诺(commitment) t ，将其发送给 v ； 在收到了来自 p 的消息 t 后， v在有限的挑战空间c中随机选取一个挑战(challenge) c，并将其发送给 p ； 在接收到来自 v 的挑战 c 后， p 计算出一个响应(response) z ,将其发送给 v ； 在收到了来自 p 的消息 t 后,v 输出accept或者reject。 v 的输出由statement y 和交互中的消息 conversation$(t,c,z)$ 严格计算得出。 协议的要求是，对于所有的 $(x,y) \\in r$ ，当$p(x,y) 与 v(y)$交互后， $v(y)$ 总是输出accept。为了系统的安全性，挑战空间的大小应该为sup-poly（超过多项式大小）。\ndefinition 3: (correctness)【正确性】\n设$(p,v)$是关于关系$r ⊆ x × y$ 的一个sigma协议。如果对于任意的$(x,y)∈r$，验证者 v 都接受证明者 p 的证明，那么称这个sigma协议具有正确性。\n关于correctness的一些说明：\n正确性显然是一个协议应该满足的最基本的是性质，如果协议不满足正确性，那么就无法达成构造这个协议最初的目的\u0026ndash;向别人证明自己拥有秘密。 definition 4: (special honest verifier zero knowledge)【hvzk】\n设 $(p,v)$是关于关系 $r ⊆ x × y$ 的一个sigma协议，且挑战空间为 c 。如果存在一个高效的概率性算法 $sim(y,c)$(称作simulator），其输入为 $(y,c) \\in y\\times c$ 且满足：\n对于所有的输入$(y,c) \\in y\\times c$，模拟器$sim(y,c)$ 能够输出一对 $(t,z)$使得$(t,c,z)$对于statement$y$来说是一个被 accpeted 的 conversation。 对于全体$(x,y) \\in r$，我们随机选择$c\u0026rsquo;\\stackrel{r}{\\longleftarrow}c$，然后用模拟器计算$(t\u0026rsquo;,z\u0026rsquo;)\\stackrel{}{\\longleftarrow}sim(y,c)$。使得**《模拟器产生的**$(t\u0026rsquo;,c\u0026rsquo;,z\u0026rsquo;)$的分布》与《正常运行sigma协议$(p,v)$得到的$(t,c,z)$**的分布》**相同，我们称sigma协议$(p,v)$是 special hvzk 。special的原因在于： 1） sim 需要 c 作为额外输出； 2）就算 y 的 witness 不存在，sim 也可以输出一个被 accepted 的 conversation。 hvzk的一些说明: - 由于** sim **产生的$(t\u0026rsquo;,c\u0026rsquo;,z\u0026rsquo;)$与正常运行sigma协议产生的$(t,c,z)$在计算上不可区分,所有敌手不可能从$(t,c,z)$得知到任何关于秘密 x 的信息.\n- 这是因为, 如果敌手能从$(t,c,z)$中得到秘密 x 的信息 , 那么由于$(t,c,z)$和$(t\u0026rsquo;,c\u0026rsquo;,z\u0026rsquo;)$不可区分,则这个敌手也能从$(t\u0026rsquo;,c\u0026rsquo;,z\u0026rsquo;)$中得知秘密 x 的信息. 这是不可能的 , 因为$(t\u0026rsquo;,c\u0026rsquo;,z\u0026rsquo;)$中根本不含由秘密 x . - 上述模拟器$sim(y,c)$不具备秘密值 x ，但拥有一个能力 **决定或者预知 **验证者的挑战值 c 。\n- 如果能够构造出一个式sim，它产生的三元组$(t,c,z)$与sigma协议产生的三元组是不可区分的。由于sim产生的三元组跟秘密并没有任何关系，且诚实的验证者不能区分两个二元组，所以诚实的验证者不能从sigma协议的三元组中得到任何秘密的信息。【否则他可以根据这个秘密信息区分两个三元组】 \u003e **definition 5: (knowledge soundness)【知识可靠性】** \u003e - 设$(p,v)$是关于关系$r ⊆ x × y$ 的一个sigma协议。如果存在一个高效的确定性的算法$ext$【称作一个witness extractor】使得： \u003e - 给定一个statement $y$ ，以及两个关于 $y$ 被 accepted 的 conversation $(t,c,z) 和 (t,c',z')$，并且$c \\ne c'$，存在**《提取器**$ext$**》**能够输出 $x \\in x$使得$(x,y) \\in r$（ x 是 y 的witness） \u003e - 即存在一个**《提取器**$ext$**》**使得：$ext((t,c,z),(t,c',z'))=x$；则我们称$(p,v)$提供 【知识可靠性】knowledge soundness。 \u003e \u003e - knowledge soundness的一些说明： \u003e - 如果协议具备这一性质，那么一个不诚实的证明者至多只能伪造一个可以被接受的响应。 因为，如果他能够伪造多于1个的响应，他必然知道秘密值 x 。 \u003e - 这是因为，不诚实的证明者不知道秘密 x ，而如果他伪造了两个被接受的响应，那么就可以使用上面所说的**《提取器**$ext$**》**提取出秘密 x 。这与证明者不知道秘密 x 相矛盾。 \u003e - 上述性质说明，任何人都可以通过公开交互信息获取证明者的秘密 x 。 \u003e - 这个性质主要约束了恶意的prover p，保证verifier v能通过交互推出来 p 到底有没有骗自己；换句话说，如果证明方 p 没有witness $x$，那么p无法说服 v 相信他确实有证据$x$。所以可以理解为：它存在的意义就是让 p 不要说谎，否则作为验证者就能发现，可视为对 p 的约束。(【5】中大佬的观点 ) \u003e sigma协议的例子 说明：\n下面的协议中，只有schnorr协议给出了三个性质的证明，其它证明可以去参考文献【5】中查看。 schnorr协议过程：\n设 $\\mathbb{g}$是一个阶为素数 q 的循环群，其生成元为$g \\in \\mathbb{g}$ 。设证明人 p 保存私钥$\\alpha \\in \\mathbb{z}_q$，对应的公钥匙为 $u = g^{\\alpha} \\in \\mathbb{g}$ 。 p 需要向 v 证明其拥有$\\alpha$。这里 $\\alpha$是 witness， $u=g^{\\alpha}$是 statement。schnorr 身份认证协议过程为：【如下图】 - p 计算$\\alpha_t \\stackrel{r}{\\longleftarrow}\\mathbb{z}_q,\\ u_t\\stackrel{r}{\\longleftarrow}g^{α_t}$，并将 $u_t$发送给 v ;\t【$commitment=u_t$】 - v 计算$c\\stackrel{r}{\\longleftarrow}c ,\\ \\ \\ c \\subset \\mathbb{z}_q$并将 c 发送给 p ；\t【$challenge=c$】 - p 计算$\\alpha_z \\leftarrow \\alpha_t + \\alpha c$，并将$\\alpha_z$发送给 v ；\t【$response=\\alpha_z$】 - v 检查如果 $g^{a_z} = u_t \\cdot u^c$ ；v 输出accept，否则输出reject。 安全性： schnorr\u0026rsquo;s protocol 的安全性是构建在离散对数问题上的，其证明的方式为假设攻击者在不知道 $\\alpha$ 可以构建对于一个 u 合法的 conversations，那么我们就可以利用攻击者的能力来解决离散对数问题。由于逆否命题是等价，如果离散对数问题无法攻破，那么schorr\u0026rsquo;s protocol 就是安全的。 proof： 假设攻击者对于 u 可以产生两个被 accepted 的 conversation$(u_t,c,\\alpha_z)$ 和 $(u_t,c\u0026rsquo;,\\alpha\u0026rsquo;_z)$且他们满足$c \\neq c\u0026rsquo;$，则有$g^{\\alpha_z}=u_t \\cdot u^c$以及 $g^{\\alpha\u0026rsquo;z}=u_t \\cdot u^{c\u0026rsquo;}$成立，将两式相除得 $g^{\\delta \\alpha}= u^{\\delta c}$,其中 $\\delta \\alpha = \\alpha_z - \\alpha\u0026rsquo;{z}$；$\\delta c = c-c\u0026rsquo;$。由于$\\delta c \\ne 0$ ，且群$\\mathbb{g}$ 是素数阶得循环群，因此有$1/ \\delta c \\in \\mathbb{g}$，则有 $g^{\\delta z/\\delta c} = u$，故我们得到了离散对数问题$dlog_gu$ 的解 $\\delta z/ \\delta c$。 hvzk： 证明 hvzk 在于如何构建一个产生 conversation 并被 verifier 接受的 sim(u) ，且由 sim 产生出来的conversation 中元素的分布和正常 p，v 交互产生的 conversation 中元素的概率分布相同。如果我们设 vk = u ，则 sim 计算：$\\begin{align} \u0026amp;α_z \\stackrel{r}{\\leftarrow} z_q \u0026amp;c \\stackrel{r}{\\leftarrow} c \\ \\ \\ \u0026amp;u_t ←g^{α_z}/u^c \\end{align}$ 在真实的交互过程中， c 和 $\\alpha_z$分别在挑战空间 c 和 $\\mathbb{z}_q$ 中服从均匀分布，且 $c,\\alpha_z$ 相互独立。此外 $u_t$是由$g^{\\alpha_z}=u_t \\cdot u^c$唯一确定的，因此可以明显看出， sim 产生的 conversation 中元素的概率分布同正常交互所产的 conversation 中元素的概率分布相同。 knowledge soundness： 由knowledge soundness 的定义以及schnorr\u0026rsquo;s protocol的安全性分析可知，schnorr\u0026rsquo;s protocol满足knowledge soundness。 okamoto协议过程\n设$\\mathbb{g}$是一个阶为素数 q 的循环群，其生成元为 $g \\in \\mathbb{g}。 h \\in \\mathbb{g}$是群中任意一个元素。okamoto’s protocol中的关系为：$r={ (\\alpha,\\beta),u) \\in \\mathbb{z}^2_q \\times \\mathbb{g} : g^{\\alpha}h^{\\beta}=u }$ 协议的过程如下图：【其中 $c \\subset \\mathbb{z}_q$】 - 【$commitment=u_t$】 - 【$challenge=c$】 - 【$response=(\\alpha_z,\\beta_z)$】 the chaum-pedersen协议过程\n该协议基于dh-triples。设$\\mathbb{g}$是一个阶为素数 q 的循环群，其生成元为 $g \\in \\mathbb{g}$。对于 $(\\alpha,\\beta,\\gamma) \\in \\mathbb{g}$如果$\\alpha \\beta = \\gamma$我们就说$(g^\\alpha,g^\\beta,g^\\gamma)$是一个dh-triples【dh三元组】。等价的，如果$(u,v,w)$是一个dh-tripes，当且仅当存在一个$\\beta \\in \\mathbb{z_q}$ 使得$v= g^\\beta , w = u^\\beta$ 。在chaum-pedersen 协议中的关系 r为：$r:= { (\\ \\beta,(u,v,w)\\ ) \\in \\mathbb{z}_q \\times \\mathbb{g}^3 : v=g^\\beta ,w=u^\\beta }$; 协议的过程为：【其中$c \\subset \\mathbb{z}_q$】 - 【$commitment=(w_t,v_t)$】 - 【$challenge=c$】 - 【$response=\\beta_z$】 线性sigma协议 线性sigma协议：\n上述schnorr, okamoto, 和 chaum- pedersen 协议都是一种更加一般的 sigma protocol 的特例。这种更加一般的 sigma protocol 是要证明元素之间的线性关系。设$\\mathbb{g}$是一个阶为素数 q 的循环群，它的生成元为$g \\in \\mathbb{g}$我们考虑一个布尔函数 $\\phi$： $\\phi (x_1,x_2,\u0026hellip;,x_n):={u_1=\\prod_{j=1}^{n}g_{1j}^{x_j}\\ \\wedge \\ u_2=\\prod_{j=1}^{n}g_{2j}^{x_j} \\wedge \u0026hellip; \\wedge u_m=\\prod_{j=1}^{n}g_{mj}^{x_j} }$\n在函数 $\\phi$ 中， $g_{ij} ,u_i \\in \\mathbb{g}$。这些群元素一部分可以是系统参数甚至是常量，另一些元素是针对函数的特殊变量。$x_i \\in \\mathbb{z}_q$是函数$\\phi$的入参，当函数中的所有等式成立则$\\phi$返回true。对于这样函数的一个特定的类 f ，我们可以定义一个关系： $r:= {((\\alpha_1,\u0026hellip;,\\alpha_n),\\phi) \\in \\mathbb{z}_q^n \\times f: \\phi(\\alpha_1,\u0026hellip;,\\alpha_n)= true }$ 在** r** 中，一个函数$\\phi$是一个 statement，而一个使得这个函数$\\phi$为 true 的 $(\\alpha_1,\u0026hellip;,\\alpha_n) \\in \\mathbb{z}_q^n$ 是这个函数 $\\phi$ 的 witness 。而我们称这样的协议为 linear protocols 的原因在于如果我们对函数$\\phi$中的等式取对数可以得到： $dlog_g({u_j})= \\sum_{j=1}^n x_i \\cdot dlog_g(g_{ij}) \\ \\ \\ \\ \\ (i=1,\u0026hellip;,m)$\n对于一般 linear sigma protocol 的过程为： 补充：\n在上述 schnorr‘s protocol 中 - $p((\\alpha_1,\u0026hellip;,\\alpha_n),\\phi)$中，n = 1，$\\phi(x):= {u=g^x}$ - $\\alpha_{tj}$中，j = 1 ; - $u_{tm}$中，m = 1 ; 【$u_{tm}$事实上就是承诺$\\phi(\\alpha_{t1})$】 - 将上面的条件代入即可得到 schnorr协议\n在上述 okamoto\u0026rsquo;s protocol 中 - $p((\\alpha_1,\u0026hellip;,\\alpha_n),\\phi)$中，n = 2 ; $\\phi(x,y) := {u=g^xh^y}$ - $\\alpha_{tj}$中，j = 2 ; - $u_{tm}$中，m = 1 ;\t【$u_{tm}$事实上就是承诺$\\phi(\\alpha_{t1},\\alpha_{t2})$】 - 将上面的条件代入即可得到 okamoto 协议\nthe chaum-pedersen protocol中 - $p((\\alpha_1,\u0026hellip;,\\alpha_n),\\phi)$中，n = 1 $\\phi(x) := { v=g^x \\wedge w=u^x}$ - $\\alpha_{tj}$中，j = 1 ; - $u_{tm}$中，m = 2 ;\t【$u_{tm}$事实上就是承诺$\\phi(\\alpha_{t1})$】 - 将上面的条件代入即可得到 the chaum-pedersen 协议\n对于一般的 linear protocol 是一个关于关系 r 的 sigma协议并且满足knowledge soundness以及special hvzk。\n基于同映射的sigma协议 基于同态映射的sigma协议\n我们可以利用群同态来更加清晰高效的来描述到目前为止的介绍的所有sigma协议。设$\\mathbb{h}_1,\\mathbb{h}_2$是两个不知道阶的交换群，以及一个同态映射$\\varphi: \\mathbb{h}_1 \\to \\mathbb{h}_2$。为了表达的方便， 群$\\mathbb{h}_1$中的运算为群加法， 群$\\mathbb{h}_2$中的运算为群乘法。设$u \\in \\mathbb{h}_2$，证明者需要向验证着证明他知道在映射$\\varphi$下 u 的原象。在这种sigma protocol中，关系为： $r:={(\\alpha,(u,\\varphi)) \\in \\mathbb{h}_1 \\times (\\mathbb{h}_2 \\times f):\\varphi(\\alpha)=u}$\n其中$\\alpha \\in \\mathbb{h}_1$是映射 $\\varphi$ 对于 $u \\in \\mathbb{h}_2$ 的原象。协议的过程如下： 在$|\\mathbb{h}_1| \\times |\\mathbb{h}_2|$最小素因子至少为 |c| 的情况下，基于同态映射的sigma protocol满足knowledge soundness以及special hvzk。 schnorr 协议中 - $\\mathbb{h}_1 := \\mathbb{z}_q,\\ \\mathbb{h}_2 := \\mathbb{g},and \\ \\ \\ \\ \\varphi_1(x):=(g^x)$ - $r:={(\\alpha,(u,\\varphi)) \\in \\mathbb{h}_1 \\times (\\mathbb{h}_2 \\times f):\\varphi(\\alpha)=u}$\nokamoto协议中 - $\\mathbb{h}_1 := \\mathbb{z}_q^2,\\ \\mathbb{h}_2 := \\mathbb{g},and \\ \\ \\ \\ \\varphi_1(x,y):=(g^xh^y)$ - $r:={((\\alpha,\\beta),(u,\\varphi)) \\in \\mathbb{h}_1^2 \\times (\\mathbb{h}_2 \\times f):\\varphi(\\alpha,\\beta)=u}$\nthe chaum-pedersen协议中 - $\\mathbb{h}_1 := \\mathbb{z}_q, \\mathbb{h}_2 := \\mathbb{g}^2,and \\ \\ \\ \\ \\varphi_2(x):=(g^x,u^x)$ - $r:={(\\alpha,(u_1,u_2,\\varphi)) \\in \\mathbb{h}_1 \\times (\\mathbb{h}_2^2 \\times f):\\varphi(\\alpha)=(u_1,u_2}$\n一般linear protocol中 $\\mathbb{h}1:= (\\mathbb{z}q)^n, \\ \\mathbb{h}2:=\\mathbb{g}^m,and \\ \\ \\ \\ \\varphi_3(x_1,\u0026hellip;,x_n) := (\\prod{j=1}^ng{1j}^{x_j},\u0026hellip;,\\prod{j=1}^ng_{mj}^{x_j})$\nfait-shamir启发式 定义 知识签名【sok】 定义：\n知识签名实际上就是零知识证明，这里给出一个知识签名的例子，该例子经常会用到，目前我遇到最多的是在群签名中使用。 离散对数知识签名：\n基本形式：\n离散对数的知识签名是针对这样一个问题：$y = g^x mod(n)$; x 是私钥，y 是公钥，g 和 n 都是公开的系统参数，m是消息，现在需要让别别人证明自己拥有私钥 x，并且不泄露 x 的信息。 符号表示为： 这里只需要证明者给出一个（c，s）对，符合以下的等式要求即可： $c = h( m||y||g||(g^s) (y^c) )$ 知识签名生成： 1. 选择一个随机数 $r$ 2. 计算c：根据公式 $c=h(m||y||g||g^r)$ 3. 计算s：根据公式 $s = r - c * x$ 4. (c,s)即为知识签名。 验证知识签名： 1. 计算$c\u0026rsquo;=h( m||y||g||(g^s) (y^c) )$ 2. 比较$c\u0026rsquo;=c$是否成立。 解释说明 如果知道密钥x，执行通过上面操作过程中的四个步骤就可以轻松计算出(c,s)对的值， 如果不知道密钥x，而想算出(c,s)，只能通过3式计算，这在计算上是不可行的。 所以，如果能给出一个满足条件的（c,s）对，就能说明其拥有私钥x。 \u003e **拓展形式**： \u003e - 离散对数的知识签名是针对这样一个问题：$y_1 = g_1^x\\ mod(n);y_2 = g_2^x\\ mod(n)$; x 是秘密值，$y_1,y_2$是公开的。$g_1,g_2$ 和 n 都是公开的系统参数，m是消息，现在需要向别人证明自己拥有秘密值 x ，且这个 x满足$y_1 = g_1^x\\ mod(n);y_2 = g_2^x\\ mod(n)$，并且证明过程中不泄露 x 的信息。 \u003e - 这里只需要证明者给出一个（c，s）对，符合以下的等式要求即可： \u003e - $c = h(\\ m||y||g||g_1^s y_1^c||g_2^sy_2^c \\ )$ \u003e - 具体的操作过程如下：【证明过程如上】 \u003e 1. 选择一个随机数 $r$ \u003e 2. 计算c：根据公式 $c=h(\\ m||y||g||g_1^r||g_2^r \\ )$ \u003e 3. 计算s：根据公式 $s = r - c * x$ \u003e 4. (c,s)即为知识签名。 \u003e \u003e **更一般的形式：** \u003e - 离散对数的知识签名：$y_1 = g_1^{x_1} \\ mod(n);\\ ...\\ ;y_m = g_m^{x_m} \\ mod(n)$; $x_i\\ (i=1,2,...,m)$ 是秘密值，并且$y_i\\ (i=1,2,...,m)$是公开的。$g_i\\ (i=1,2,...,m)$ 和 n 都是公开的系统参数，m是消息，现在需要向别人证明自己拥有秘密值 $x_i\\ (i=1,2,...,m)$ ，且$x_i$满足$y_i = g_i^{x_i} \\ mod(n) \\ (i=1,2,...,m)$，并且证明过程中不泄露$x_i\\ (i=1,2,...,m)$ 的信息。 \u003e - 这里只需要证明者给出一个$(c,s_1,s_2,...,s_m)$对，符合以下的等式要求即可： \u003e - $c = h(\\ m||y||g||g_1^s y_1^c||...||g_m^sy_m^c \\ )$ \u003e - 具体的操作过程如下：【证明过程如上】 \u003e 1. 选择随机数 $r_1,r_2,...,r_m$ \u003e 2. 计算c：根据公式 $c=h(\\ m||y||g||g_1^{r_1}||...||g_m^{r_m} \\ )$ \u003e 3. 计算s：根据公式 $s_i = r_i - c * x_i \\ \\ (i=1,2,...,m)$ \u003e 4. 则$(c,s_1,s_2,...,s_m)$即为知识签名。 \u003e - 说明： \u003e - 在群签名中，经常用到这个知识签名。 zk-snark 参考文献：\nhttps://blog.csdn.net/qq_35739903/article/details/119455825 https://zhuanlan.zhihu.com/p/38205067 参考文献 【1】https://zhuanlan.zhihu.com/p/144899541 【2】https://zhuanlan.zhihu.com/p/622105041 【3】https://zhuanlan.zhihu.com/p/152065162 【4】http://blockchain.whu.edu.cn/uploads/soft/201105/1_1954088811.pdf【pdf】 【5】https://zhuanlan.zhihu.com/p/343756241【讲的很好】 【6】https://zhuanlan.zhihu.com/p/144899541【讲的较详细】 补充： sigma协议在其它资料中的表述 sigma协议簇： sigma协议簇是指一类的协议，这些协议满足一些指定的要求。值得注意的是，sigma协议簇中的协议都是零知识证明。也就是满足sigma协议簇的协议一定是一个零知识证明。\n二元关系（预备知识）： 例如：实数中的关系“大于”可记作 $r={(x,y)|x,y是实数且x\u0026gt;y}$ 其中 r 表示这个关系，它是一个集合，集合中的元素有二元组（x,y）组成 r 中的元素是所有满足 x,y 是实数且 x\u0026gt;y 的二元组 (x,y) 其它二元关系的例子（零知识证明常用到的） sigma协议内容： 以sigma协议为标准构造零知识证明 可以按照以下步骤证明该问题： 证明过程如图所示： 说明：\n该协议是满足sigma协议的三个性质的。因此他是一个零知识证明 sigma协议的扩展 or证明： or证明的性质： ","date":"2024-04-05","permalink":"http://54rookie.com/posts/%E9%9B%B6%E7%9F%A5%E8%AF%86%E8%AF%81%E6%98%8E/","summary":"这里给出零知识证明的详细内容 零知识证明的相关概念 定义： 证明者（prover）在不向验证者（verifier）提供任何有用的信息的情况下，使验证者（verifie","title":"零知识证明"},]
[{"content":"this is my first blog!\nhello 你在干什么 $x_q+x^2$ 你在肝肾恶魔$x_1+\\varepsilon$\n你在肝肾恶魔$$x_1+\\varepsilon$$\n","date":"2024-04-04","permalink":"http://54rookie.com/posts/first/","summary":"This is my first blog! Hello 你在干什么 $x_q+x^2$ 你在肝肾恶魔$x_1+\\varepsilon$ 你在肝肾恶魔$$x_1+\\varepsilon$$","title":"first"},]
[{"content":"this is my second blog!\nhello this is your new vault.\nmake a note of something, [[create a link]], or try the importer!\nwhen you\u0026rsquo;re ready, delete this note and make the vault your o\ndada dada da你在干 head1 head 2 1 1 234 this is your new vault. make a note of something, [[create a link]], or try the importer!\nwhen you\u0026rsquo;re ready, delete this note and make the vault your o\ndada dada da你在干 head1 head 2 1 1 234 ![[imgs/wukong.jpg]]\n","date":"2024-04-04","permalink":"http://54rookie.com/posts/second/","summary":"This is my second blog! Hello This is your new vault. Make a note of something, [[create a link]], or try the Importer! When you\u0026rsquo;re ready, delete this note and make the vault your o dada dada da你在干 head1 head 2 1 1 234 This is your new vault. Make a note of something, [[create a link]], or try the Importer! When you\u0026rsquo;re ready, delete this note and make the vault your o dada dada d","title":"second"},]
[{"content":"","date":"0001-01-01","permalink":"http://54rookie.com/archive/","summary":"","title":"archive"},]
[{"content":"\r🌞 分类 one 进制转换器 工具大全 百度 🔨 实用工具 进制转换器 工具大全 百度 📑 分类 three 进制转换器 工具大全 百度 🔖 标签 bookmarks bookmark item one https://bookmark-item-one.com bookmark item two https://bookmark-item-two.com bookmark item three https://bookmark-item-three.com ","date":"0001-01-01","permalink":"http://54rookie.com/nav/","summary":"🌞 分类 ONE 进制转换器 工具大全 百度 🔨 实用工具 进制转换器 工具大全 百度 📑 分类 THREE 进制转换器 工具大全 百度 🔖 标签 BOOKMARKs bookmark item one https://bookmark-item-one.com bookmark item two https://bookmark-item-two.com bookmark item three https://bookmark-item-three.com","title":"nav"},]
[{"content":"","date":"0001-01-01","permalink":"http://54rookie.com/search/","summary":"","title":"search"},]
✖