CAREER: Algebraic Methods for the Computation of Approximate Short Vectors in Ideal Lattices

职业：理想格子中近似短向量计算的代数方法

基本信息

批准号：
1846166
负责人：
Jean-Francois Biasse
金额：
$ 45万
依托单位：
University of South Florida
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-06-01 至 2024-05-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1846166&HistoricalAwards=false
关键词：
CAREER Algebraic Methods Computation Approximate

项目摘要

This project involves research into the computational hardness of the search for short elements of the so-called Euclidean lattices. The hardness of this task is the measure of the security of one of the most promising family of cryptographic protocols that are conjectured to resist attacks from quantum computers. The transition toward such protocols is an immediate priority for the cryptography community. Indeed, quantum-safe primitives will need to be ready and deployed long before the construction of large scale quantum computers to account for the shelf life of encrypted data. The results from this research are disseminated to a large audience ranging from industrials willing to adopt quantum-safe primitives, university students, and K-12 students. This project supports a week-long cybersecurity camp for high school students who discover the fundamentals for security and cryptography through hands-on activities.This project specifically focuses on the hardness of the search for short vectors in Euclidean lattices that are ideals of a number field. This special class of lattices, called ideal lattices, is very popular in lattice-based cryptography because it allows interesting optimizations including the use of significantly shorter keys. However, the restriction to a smaller class of lattices having more algebraic structure could also mean that the search for short elements is not as hard as in general lattices. Building on previous work of the investigator on the computation of invariants of number fields, this project investigates the algebraic methods allowing the search for short elements in ideal lattices.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

该项目涉及搜索所谓欧几里得晶格的短元素的计算难度的研究。这项任务的难度在于衡量最有前途的密码协议系列之一的安全性，这些协议被认为可以抵御量子计算机的攻击。向此类协议的过渡是密码学界的当务之急。事实上，量子安全原语需要在建造大规模量子计算机之前就准备好并部署，以考虑加密数据的保质期。这项研究的结果被传播给广大受众，包括愿意采用量子安全原语的工业界、大学生和 K-12 学生。该项目为高中生提供为期一周的网络安全训练营，让他们通过实践活动发现安全和密码学的基础知识。该项目特别关注在欧几里得格子中搜索作为数域理想的短向量的难度。这种特殊的格子，称为理想格子，在基于格子的密码学中非常流行，因为它允许有趣的优化，包括使用明显更短的密钥。然而，对具有更多代数结构的较小类格的限制也可能意味着搜索短元素并不像一般格中那么困难。该项目以研究者之前计算数域不变量的工作为基础，研究了允许在理想格中搜索短元素的代数方法。该奖项反映了 NSF 的法定使命，并通过使用基金会的评估进行评估，被认为值得支持。智力价值和更广泛的影响审查标准。