ZKP Algorithms for Efficient Cryptographic Operations 1 (MSM Pippenger)
MIT IAP 2023 Modern Zero Knowledge Cryptography课程笔记
Lecture 6: Algorithms for Efficient Cryptographic Operations (Jason Morton)
-
Multi-scalar Multiplication(MSM)
- Naive: nP = (((P + P) + P) + P)… = (2(2P))…
- Binary expand
- $n = e_0+e_1\alpha+e_2\alpha2+\dots+\e_{\lambda-1}{\lambda-1}
- Accumulator
- Q = P;
- R = 0 if e_0 = 0
- R = P if e_0 = 1
- For i = 1 to t
- Q = 2Q
- If e_i = 1
- R = R+Q
- Return R
- Overhead: \log_2 n doubling + \log_2 n add
-
Pippenger [Reference:drouyang.eth, https://hackmd.io/@drouyang/SyYwhWIso]

- P = ∑ i = 0 n k i P i P=\sum_{i=0}^n k_i P_i P=∑i=0nkiPi
- Step 1: partition scalars into windows
- Let’s first partition each scalar into m m m windows each has w w w bits, then
- k i = k i , 0 + k i , 1 2 w + . . . + k i , ( m − 1 ) 2 ( m − 1 ) w k_i = k_{i,0} + k_{i,1} 2^{w} + ... + k_{i,(m-1)} 2^{(m-1)w} ki=ki,0+ki,12w+...+ki,(m−1)2(m−1)w
- You can think of each scalar k i k_i ki as a bignum and representing it as a multi-precision integer with limb size w w w. Then we have,
- ∑ i k i P i = ∑ i ∑ j = 0 m − 1 k i , j 2 j w P i \sum_i k_i P_i = \sum_i \sum_{j=0}^{m-1} k_{i,j} 2^{jw} P_i ∑ikiPi=∑i∑j=0m−1ki,j2jwPi
- By reordering the sums, we get
- ∑ i k i P i = ∑ j 2 j w ( ∑ i k i , j P i ) = ∑ j 2 j w W j \sum_i k_i P_i= \sum_j 2^{jw} \left( \sum_i k_{i,j} P_i \right) = \sum_j 2^{jw} W_j ∑ikiPi=∑j2jw(∑iki,jPi)=∑j2jwWj
- It means we can calculte the MSM for each window W j W_j Wj first, then aggregate the results
- Then, let’s examine W j = ∑ i = 0 n k i , j P i W_j = \sum_{i=0}^n k_{i,j} P_i Wj=∑i=0nki,jPi
- Let’s first partition each scalar into m m m windows each has w w w bits, then
- Step 2: for each window, add points by bucket
- Because each window has w w w bits, k i , j k_{i,j} ki,j has a value range of [ 0 , 2 w − 1 ] [0, 2^w-1] [0,2w−1].Therefore, we can put n n n points into 2 w 2^w 2w buckets according to the value of k i , j k_{i,j} ki,j. We can first calculate W j W_j Wj by,
- for bucket t t t, t ∈ { 0 , 2 w − 1 } t \in \{0, 2^w-1\} t∈{0,2w−1}, calculate the sum of points in this bucket and get B t B_t Bt.
- W j = ∑ t = 0 2 w − 1 t B t W_j = \sum_{t=0}^{2^w-1} t B_t Wj=∑t=02w−1tBt
- Because each window has w w w bits, k i , j k_{i,j} ki,j has a value range of [ 0 , 2 w − 1 ] [0, 2^w-1] [0,2w−1].Therefore, we can put n n n points into 2 w 2^w 2w buckets according to the value of k i , j k_{i,j} ki,j. We can first calculate W j W_j Wj by,
- Step 3: reduce window results
- P = ∑ i = 0 n k i P i = ∑ j 2 j w W j P=\sum_{i=0}^n k_i P_i = \sum_j 2^{jw} W_j P=∑i=0nkiPi=∑j2jwWj
相关文章:
ZKP Algorithms for Efficient Cryptographic Operations 1 (MSM Pippenger)
MIT IAP 2023 Modern Zero Knowledge Cryptography课程笔记 Lecture 6: Algorithms for Efficient Cryptographic Operations (Jason Morton) Multi-scalar Multiplication(MSM) Naive: nP (((P P) P) P)… (2(2P))…Binary expand $n e_0e_1\alphae_2\alpha2\dots\e_{\…...
Windows系统安装 ffmpeg
下载及解压 ffmpeg官方下载地址:https://ffmpeg.org/download.html 下载好后将其解压至你想保存的位置中。 环境变量设置 打开Windows设置,在搜索框输入:系统高级设置。 新建环境变量,并输入bin目录具体位置。 安装检查 按住 w…...
油猴脚本教程案例【键盘监听】-编写 ChatGPT 快捷键优化
文章目录 1. 元数据namenamespaceversiondescriptionauthormatchgranticon 2. 编写函数.1 函数功能2.1.1. input - 聚焦发言框2.1.2. stop - 取消回答2.1.3. newFunction - 开启新窗口2.1.4. scroll - 回到底部 3. 监听键盘事件3.1 监听X - 开启新对话3.2 监听Z - 取消回答3.3 …...
数据结构 | 查漏补缺
目录 数据的基本单位 冒泡排序 DFS和BFS中文 Prim 比较 中序线索二叉树 顺序栈 链栈 时间复杂度 循环队列 求第K个结点的值 数据的基本单位 数据元素 循环队列sq中,用数组elem[0‥25]存放数据元素,设当前sq->front为20,sq-&g…...
回溯算法练习题
78. 子集 中等 1.9K 相关企业 给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1: 输入:nums [1,2,3] 输出&#x…...
代码随想录算法训练营 | day60 单调栈 84.柱状图中最大的矩形
刷题 84.柱状图中最大的矩形 题目链接 | 文章讲解 | 视频讲解 题目:给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩形的最大面积。 1 < heights.len…...
vscode中vue项目报错
当在vscode中写代码时,报错报错报错......... 已经头大,还没写就报错, 这是因为eslint对语法的要求太过严格导致的编译时,出现各种语法格式错误 我们打开vue.config.js,加上这句代码,就OK啦 lintOnSave:…...
「数据结构」二叉树2
🎇个人主页:Ice_Sugar_7 🎇所属专栏:初阶数据结构 🎇欢迎点赞收藏加关注哦! 文章目录 🍉前言🍉链式结构🍉遍历二叉树🍌前序遍历🍌中序遍历&#x…...
数据处理系列课程 01:谈谈数据处理在数据分析中的重要性
一、数据分析 可能很多朋友第一次听到这个名词,那么我们先来谈一谈什么是数据分析。 数据分析是指用适当的统计分析方法对收集来的大量数据进行分析,将它们加以汇总和理解,以求最大化地开发数据的功能,发挥数据的作用。数据分析是…...
C++卡码网题目55--右旋字符串
卡码网题目链接 字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k,请编写一个函数,将字符串中的后面 k 个字符移到字符串的前面,实现字符串的右旋转操作。 例如,对于输入字符…...
八股文打卡day8——计算机网络(8)
面试题:什么是强缓存和协商缓存? 我的回答: 强缓存:浏览器不需要发送请求到服务器,直接从浏览器缓存中获取数据。浏览器不需要和服务器进行交互就可以获取数据,这样极大提高了页面访问速度。 协商缓存&am…...
亚马逊推出 Graviton4:具有 536.7 GBps 内存带宽的 96 核 ARM CPU
如今,许多云服务提供商都设计自己的芯片,但亚马逊网络服务 (AWS) 开始领先于竞争对手,目前其子公司 Annapurna Labs 开发的处理器可以与 AMD 和英特尔的处理器竞争。本周,AWS 推出了 Graviton4 SoC,这是一款基于 ARM 的…...
跨域问题的解决
1.什么是跨域? 浏览器从一个域名的网页去请求另外一个域名的资源时,域名、端口或者协议不同都是跨域 2.跨域的解决方案 设置CORS响应头∶后端可以在HTTP响应头中添加相关的CORS标头,允许特定的源(域名、协议、端口)访问资源。S…...
Typro+PicGo自动上传图片(图床配置)
文章目录 所需工具主要配置 TyproPicGo自动上传图片(图床配置) 使用Typro编写 的markdown(md)文件如果存在图片,并且想快速发布博文的话,常使用PiGO工具配置图床服务器来管理图片。 所需工具 TyporaPicGo(依赖Nodejs和插件super…...
uniapp实战 -- 个人信息维护(含选择图片 uni.chooseMedia,上传文件 uni.uploadFile,获取和更新表单数据)
效果预览 相关代码 页面–我的 src\pages\my\my.vue <!-- 个人资料 --><view class"profile" :style"{ paddingTop: safeAreaInsets!.top px }"><!-- 情况1:已登录 --><view class"overview" v-if"membe…...
企业如何建立价值评估体系?
企业绩效评价体系是指由一系列与绩效评价相关的评价制度、评价指标体系、评价方法、评价标准以及评价机构等形成的有机整体。企业的评价系统大致可以分为以下四个层次: 第一、岗位评价系统,主要针对不同岗位之间的评估。例如,企业中一般业务…...
华为安防监控摄像头
华为政企42 华为政企 目录 上一篇华为政企城市一张网研究报告下一篇华为全屋wifi6蜂鸟套装标准...
[node] Node.js 缓冲区Buffer
[node] Node.js 缓冲区Buffer 什么是BufferBuffer 与字符编码Buffer 的方法概览Buffer 的实例Buffer 的创建写入缓冲区从 Buffer 区读取数据将 Buffer 转换为 JSON 对象Buffer 的合并Buffer 的比较Buffer 的覆盖Buffer 的截取--sliceBuffer 的长度writeUIntLEwriteUIntBE 什么是…...
【ARM Cortex-M 系列 5 -- RT-Thread renesas/ra4m2-eco 移植编译篇】
文章目录 RT-Thread 移植编译篇编译os.environ 使用示例os.putenv使用示例python from 后指定路径 编译问题_POSIX_C_SOURCE 介绍编译结果 RT-Thread 移植编译篇 本文以瑞萨的ra4m2-eco 为例介绍如何下载rt-thread 及编译的设置。 RT-Thread 代码下载: git clone …...
功能强大的开源数据中台系统 DataCap 1.18.0 发布
推荐一套基于 SpringBoot 开发的简单、易用的开源权限管理平台,建议下载使用: https://github.com/devlive-community/authx 推荐一套为 Java 开发人员提供方便易用的 SDK 来与目前提供服务的的 Open AI 进行交互组件:https://github.com/devlive-commun…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
莫兰迪高级灰总结计划简约商务通用PPT模版
莫兰迪高级灰总结计划简约商务通用PPT模版,莫兰迪调色板清新简约工作汇报PPT模版,莫兰迪时尚风极简设计PPT模版,大学生毕业论文答辩PPT模版,莫兰迪配色总结计划简约商务通用PPT模版,莫兰迪商务汇报PPT模版,…...
nnUNet V2修改网络——暴力替换网络为UNet++
更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...
【阅读笔记】MemOS: 大语言模型内存增强生成操作系统
核心速览 研究背景 研究问题:这篇文章要解决的问题是当前大型语言模型(LLMs)在处理内存方面的局限性。LLMs虽然在语言感知和生成方面表现出色,但缺乏统一的、结构化的内存架构。现有的方法如检索增强生成(RA…...
WEB3全栈开发——面试专业技能点P8DevOps / 区块链部署
一、Hardhat / Foundry 进行合约部署 概念介绍 Hardhat 和 Foundry 都是以太坊智能合约开发的工具套件,支持合约的编译、测试和部署。 它们允许开发者在本地或测试网络快速开发智能合约,并部署到链上(测试网或主网)。 部署过程…...
Vue.js教学第二十一章:vue实战项目二,个人博客搭建
基于 Vue 的个人博客网站搭建 摘要: 随着前端技术的不断发展,Vue 作为一种轻量级、高效的前端框架,为个人博客网站的搭建提供了极大的便利。本文详细介绍了基于 Vue 搭建个人博客网站的全过程,包括项目背景、技术选型、项目架构设计、功能模块实现、性能优化与测试等方面。…...
.Net Framework 4/C# 面向对象编程进阶
一、继承 (一)使用继承 子类可以继承父类原有的属性和方法,也可以增加原来父类不具备的属性和方法,或者直接重写父类中的某些方法。 C# 中使用“:”来表示两个类的继承。子类不能访问父类的私有成员,但是可以访问其公有成员,即只要使用 public 声明类成员,就既可以让一…...
