下载 - CCS-清华大学密码理论与技术研究中心

Report
973项目年度总结交流会
现代密码学中若干关键数学问题
研究及其应用
(2013CB834200)
报 告 人:王小云
报告日期:2014年4月21日
报告提纲
研究内容与总体目标
研究工作的主要进展
组织管理、队伍建设和人才培养
经费情况
总结
2
报告提纲
研究内容与总体目标
研究工作的主要进展
组织管理、队伍建设和人才培养
经费情况
总结
3
项目总体信息
现代密码学中若干关键数学问题研究及其应用
项目编号:2013CB834200
执行时间:2013.1-2017.8
依托部门:教育部
承担单位:清华大学 北京大学
中国科学院数学与系统科学研究院
南开大学
中国科学院信息工程研究所
山东大学
中国科学技术大学
项目列名成员:29人(另有博士生57人,硕士生36人)
4
项目概览
现代密码学中若干关键数学问题研究及其应用
球的格堆积与格覆盖问题
椭圆曲线有理点与离散对数问题
有限域代数方程求解问题
格理论核心
问题研究
椭圆曲线
有理点问题
研究
相关数学问
题研究在密
码分析和设
计中的应用
代数编码构
造与译码问
题研究
有限域上代
数方程算法
问题研究
课题一
课题二
课题五
课题四
课题三
随着项目进展,课题一和课题五对关键科学问题二进行深度交叉
5
主要研究内容
• 格理论的基本问题
球的格堆积与格覆盖
• 格困难问题的快速算法,计算复杂性理论
• 基于格的编码构造及其译码
• 整体理论和椭圆曲线有理点理论
椭圆曲线有理点与
离散对数问题
• p进方法在椭圆曲线有理点理论上的作用
• 椭圆曲线离散对数问题
• 研究新一代Groebner基算法
有限域代数方程求解
• 求解特殊代数方程的新方法
安
全
高
效
对
称
密
码
算
法
的
设
计
• 基于代数方程求解的密码分析新模型研究
6
五年预期目标
数学理论研究
在球的格堆积、椭圆曲线有理点理论与代数方程求解取得3
项突破性成果
密码理论研究
解决我国密码安全理论和技术难点,取得3项突破性成果
建设和培养国际水平的学术队伍
高水平论文120篇,权威国际大会(特邀)报告10次
专利3-5项,杰出人才奖、省部级或国家奖2-4项
培养博士生50名,博士后20名
7
2013年度任务完成情况
发表论文122篇,提交专利申请2项,国际特邀报告5次
国家杰青1名,国家万人计划领军人才1名,新世纪优秀人才1名
重要论文发表情况统计
权威期刊
PNAS (Proceedings of the
National Academy of Sciences)
篇数
权威会议
1
ISSAC 最佳论文
篇数
1
Advances in Mathematics
2
Asiacrypt
5
Expositiones Mathematicae
1
FSE
3
Israel J. Math
IEEE Transactions on
Information Theory
1
PKC
1
Theoretical Computer Science
Discrete Mathematics
2
3
2
8
报告提纲
研究内容与总体目标
研究工作的主要进展
研究工作的主要进展
组织管理、队伍建设和人才培养
经费情况
总结
9
关键科学问题1:球的格堆积与格覆盖问题
代表性成果
• 希尔伯特第十八问题
• 格密码体制的破解与快速实现
• 带GAP格的反转定理
• 网络纠错码的构造
• 有限域上稀疏多项式f (x)根存在性问题研究
发表论文36篇,代表性成果发表于
•
•
•
•
• ISSAC(最佳论文)
Advances in Mathematics
• Asiacrypt
Expositiones Mathematicae
• PKC
Discrete Mathematics
IEEE Transactions on Information Theory
课题组一、四、五共同完成
10
关键科学问题一代表性成果1
希尔伯特第十八问题第三部分的研究
背景
• 研究正四面体的最大堆积密度是最古老和著名的
几何数论问题之一
• 历史可以追溯到古希腊的亚里士多德
成果
• 得到正四面体平移堆积密度的第一个非平凡上界,
发表于Advances in Mathematics
• 二维的堆积、覆盖及铺砌理论综述文章,发表于
Expositiones Mathematicae
11
关键科学问题一代表性成果1
希尔伯特第十八问题第三部分的研究
国际影响
• J.C. Lagarias提议与宗传明教授合写该结
果的评述,作为封面文章发表在《美国数
学会纪要》
• 这是该杂志历史上第一篇由国内作者发表
的这类文章
J.C. Lagarias,著名数学家、密码学家;
在单纯形算法,低密度子集和问题
(密码数学问题),丢番图逼近问题
等方面做出了突出贡献
该杂志主要报
道美国数学会
重大事件,介
绍重要进展,
杰出数学家等
12
关键科学问题一代表性成果2
带GAP格的反转定理
背景
• 反转定理是数的几何的经典问题
• 数学家 Mahler, Cassels, Lagarias, Banaszczyk
等都研究过此类问题
• 实际中大部分密码格都具有一定GAP
成果
• 得到了带GAP格的三个最优反转定理,发表
于Discrete Mathematics
• 在格困难问题的计算复杂理论研究及格密码
体制的分析中有重要应用
13
关键科学问题一代表性成果3
有限域上稀疏多项式f (x)根存在性问题研究
背景
• 数域上多项式的解的存在性判定和求解是计
算代数的基本问题之一
• 该判定问题在有限域上是困难的
成果
• 首次给出了判定 Fq上多项式是否存在解的确
定性 sub-linear算法
• 解决了在sub-linear时间内,判定三项式在 Fq
上是否存在根的公开问题
获符号计算顶级会议ISSAC 2013最佳论文
14
关键科学问题一代表性成果4
格密码体制的破解与快速实现
背景
• 问题1:NTRUSign是实用的格签名体制,IEEE P1363.1 标准算法
• 问题2:格点高斯分布采样算法是格密码体制单向陷门函数设计的基
本算法,现有的采样算法实现效率低
成果
• 成果1:破解了IEEE P1363 标准中的NTRUSign-251
• 成果2:显著提高了格点高斯采样算法效率
• 两个结果均发表于ASIACRYPT 2012
引用情况
• 两篇论文他引10余次,其中包括顶级国际密码学会议
CRYPTO 2013, EUROCRYPT 2013
15
关键科学问题一代表性成果5
网络纠错码的构造
背景
• 网络编码理论是信息论中一个非常重要而且活跃的分支
• 网络纠错码的构造与分析至关重要
成果
•
•
•
•
简化了网络纠错编码中最重要的Singleton界的证明
构造性地证明了最优网络纠错码的存在性
给出线性网络纠错码的多项式时间构造算法
给出了随机线性网络纠错码的分析方法
引用情况
• 构造线性网络纠错码的重要算法,他引9次
16
关键科学问题2:椭圆曲线有理点与离散对数问题
代表性成果
• BSD(Birch-Swinnerton-Dyer)猜想的研究
• 代数簇有理点分析
发表论文21篇,代表性成果发表于
• PNAS (Proceedings of the National Academy of Sciences)
• Advances in Mathematics
课题组二完成
17
关键科学问题二代表性成果1
BSD (Birch-Swinnerton-Dyer) 猜想的研究
背景
• BSD猜想,千禧年七大数学问题之一,研究椭圆曲线有理点和
L-函数特殊值关系
• 同余数问题可以归结为同余椭圆曲线上的无限阶有理点存在性的
问题,本质是相关椭圆曲线的BSD 猜想等算术研究
成果
• 证明了任意给定正整数k,在每个模8余5、6、7的剩余类中,存在
无穷多个恰巧有k个奇素数因子的无平方因子的同余数
• 给出了一系列满足BSD 的秩为1 的同余椭圆曲线
18
关键科学问题二代表性成果2
代数簇有理点分析
背景
代数簇有理点的分析有很多中心问题如
Shimura 簇上的算术和Brauer 群的计算,
与椭圆曲线有理点分析密切相关
成果
• 给出了二次数域的两平方和问题的充
要条件
• 对一些经典环面的齐次空间,给出有
理点存在的充要条件
19
关键科学问题3:有限域代数方程求解问题
代表性成果
•
•
•
•
• Hash函数的分析
分组密码新型分析模型
认证加密算法的伪造攻击 • 代数方法设计对称密码组件
带噪方程组求解算法
非线性函数和泛Hash函数族的等价构造
发表论文65篇,代表性成果发表于
• 3 篇ASIACRYPT,5篇FSE
• IEEE Transactions on Information Theory等
课题组三、四、五共同完成
20
关键科学问题三代表性成果1
分组密码新型分析模型
背景
• 问题1:AES设计者等提出零相关分析,其高数据复杂度不被
认可
• 问题2:新型密码分析方法是密码领域共同关注问题
• 问题3:国际标准AES的分析是国际密码学家最关注问题之一
成果
• 成果1:提出多维零相关和积分零相关线性分析模型并成功
推广,已用于分析CLEFIA,SHACAL-2等十多个算法
• 成果2:提出了相关密钥线性分析的新方法
• 成果3:给出AES-192单密钥下最高轮数分析结果
21
关键科学问题三代表性成果1
分组密码新型分析模型
发表情况
• ASIACRYPT 2012,ASIACRYPT 2013
• FSE 2014
引用情况
• 被权威密码会议CRYPTO与DCC等引用
• 引用的密码学家有Kaisa Nyberg与Alex
Biryukov等
本项目在Asiacrypt 2012发表3篇论文,该会议共43篇
22
关键科学问题三代表性成果2
Hash函数的分析
背景
• Skein是SHA-3决赛的5个算法之一
成果
• 首次实现Skein-256的反弹攻击
• 给出约减轮最好的几乎碰撞攻击(32/72轮,国际上20轮)
引用情况
• 他引10次,被CRYPTO 2013、ASIACRYPT 2012、
FSE 2012等引用
FSE 2013, 10 - 13 March
Singapore
23
关键科学问题三代表性成果3
认证加密算法的伪造攻击
背景
• 国际认证加密标准算法征集“CAESAR”
• ALE是FSE 2013上公布的认证加密算法
成果
• 提出一种新的伪造攻击方法——泄露状
态伪造攻击
• 发表于ASIACRYPT 2013
引用情况
• 被知名密码学者I.Dinur和I.Nikolic分别引用
24
关键科学问题三代表性成果4
代数方法设计对称密码组件
背景
• 问题1:扩散层是对称密码的重要组件
• 问题2:C.Carlet于1998年提出的“任何一个几
乎Bent函数都扩展仿射等价于一个置换”的猜
想,是个公开问题
成果
• 成果1:给出了一系列硬件实现代价低的最优扩
散层的构造,发表于SAC 2012
• 成果2:否证了C.Carlet的猜想,发表于IEEE
Transactions on Information Theory
引用情况
• 成果1他引 9 次
25
关键科学问题三代表性成果5
带噪方程组求解算法
背景
二元域上带噪方程系统求解算法 Max-PoSSo是求解带噪方
程系统中的一类问题,当基域是GF(2)时,类似于著名的
Max-SAT问题
成果
• 提出一种逐步求解结合回溯搜索的方法 (ISBS)
• 用于AES 和Serpent的“冷启动密钥恢复”问题,实验结
果均优于现有结果
26
关键科学问题三代表性成果6
非线性函数和泛Hash函数族的等价构造
背景
非线性函数和Hash函数应用广泛
成果
完善非线性函数
等价构造
最优泛Hash函数族
• 构造了新的消息认证码,比Carlet等构造的
消息认证码能更好地抵抗替换攻击
• 给出具有给定差分均匀性的函数与某些泛
Hash族的联系
• 发表于Theoretical Computer Science
27
报告提纲
研究内容与总体目标
研究工作的主要进展
组织管理、队伍建设和人才培养
组织管理、队伍建设和人才培养
经费情况
总结
28
举办会议情况
ASIACRYPT 2012
项目首席 王小云教授作为程序委员会联合主席组织该会议
ASK 2013
课题五
王美琴教授、于红波副教授组织该会议
密码数学理论专委会2013年度会议
课题四
符方伟教授组织该会议
Summer Workshop on Arithmetic Geometry
课题二
田野研究员与清华大学合办
29
课题内部交流情况
课题组
时间
地点
北京大学
会议名称
课题一
2013年12月27日
年度总结会
课题二
2013年4月24日-28日
合肥
课题组会议
课题二
2014年3月7日-9日
北京
年度总结会
课题三
2013年7月19日-22日
北京
年度总结会
课题四
2014年4月4日
南开大学
年度总结会
课题五
2014年1月13日
清华大学
年度总结会
30
国际学术任职
王小云:CRYPTO 2013[美国], ASIACRYPT 2013[印度]
程序委员会委员,Journal of Cryptology编委
Phong Nguyen:EUROCRYPT 2013/2014[希腊/丹麦]程序
委员会联合主席
王美琴:ISC 2013[美国],ASIACRYPT 2014[台湾]程序委
员会委员
于红波:FSE 2014[英国]程序委员会委员
国际三大密码会议: CRYPTO, EUROCRYPT, ASIACRYPT
31
人才培养与获奖情况
人才培养
宗传明教授入选国家万人计划领军人才
田野研究员获国家杰出青年科学基金
王美琴教授入选2013年新世纪优秀人才
获奖情况
田野研究员获2013年华人数学家大会晨兴数学
金奖
田野研究员2013年Abdus Salam国际理论物理
中心和国际数学联盟拉马努金奖
毕经国和程岐教授等获ISSAC 2013最佳论文奖
32
国际特邀报告
报告人
会议名称
报告名称
地点和时间
宗传明
ASIACRYPT
2012
Some Mathematical Mysteries
in Lattices
北京
2012/12
王美琴
ESC 2013
Zero-Correlation Linear
Cryptanalysis of ReducedRound Camellia and CLEFIA
卢森堡
2013/1
田野
ICCM 2013
Congruent Number Problems
台北
2013/7
田野
AMC 2013
Congruent Number Problem
and Special Values of Lfunctions
韩国釜山
2013/7
田野
PANT 2013
Congruent Number Problem
and genus Heegner Points
越南河内
2013/7
33
报告提纲
研究内容与总体目标
研究工作的主要进展
组织管理、队伍建设和人才培养
经费情况
总结
34
项目经费情况
前两年预算批复总额1401万元
已拨经费796万元,截止2014年4月累计支出约398万元,
占已拨经费的50%
各课题经费执行情况如下:(单位:万元)
课题一
课题二
课题三
课题四
课题五
合计
预算总额
233
267
245
232
424
1401
2013年拨款
132
152
139
132
241
796
支出总额
42
66
51
60
179
398
35
课题经费执行情况
36
报告提纲
研究内容与总体目标
研究工作的主要进展
组织管理、队伍建设和人才培养
经费情况
总结
37
总结
围绕三个关键问题,五个课题深度交叉融合,发挥各自
优势和特色,做出多项标志性成果
每个关键问题有两个以上课题组参加
项目管理顺利
及时传达并落实项目主管部门的通知与要求
重要研究成果及时交流,积极推进关键科学问题攻关
国家财政政策及时传达,介绍经费管理经验
38
总结
不足与建议
关键科学问题方面进一步深度交叉,取得更有突破性
的成果
望各课题组根据经费预算合理支出
建设本项目交流平台网站,实现成果共享
39
谢 谢!
40

similar documents