Article(id=1329456537199817633, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1329456279791186761, articleNumber=null, orderNo=null, doi=10.7544/issn1000-1239.202220980, pmid=null, cstr=null, oa=null, hot=null, price=null, onlineType=0, articleFormat=0, articleType=null, articleTypeStr=null, receivedDate=1669737600000, receivedDateStr=2022-11-30, revisedDate=1684080000000, revisedDateStr=2023-05-15, acceptedDate=null, acceptedDateStr=null, onlineDate=1794896738575, onlineDateStr=2026-11-17, pubDate=1711900800000, pubDateStr=2024-04-01, doiRegisterDate=null, doiRegisterDateStr=null, onlineIssueDate=1794896738575, onlineIssueDateStr=2026-11-17, onlineJustAcceptDate=null, onlineJustAcceptDateStr=null, onlineFirstDate=null, onlineFirstDateStr=null, sourceXml=null, magXml=null, createTime=1794896738575, creator=13701087609, updateTime=1794896738575, updator=13701087609, issue=Issue{id=1329456279791186761, tenantId=1146029695717560320, journalId=1324759914146529478, year='2024', volume='61', issue='4', pageStart='809', pageEnd='1084', issueExtLink='null', onlineDate='null', pubDate='1711900800000', pubDateStr='2024-04-01', beforeIssueId=null, nextIssueId=null, price=null, status=1, issueComplete=1, articleOrder=1, issueType=-1, specialIssue=null, createTime=1794896677204, creator='13701087609', updateTime=1794899232988, updator='13701087609', preIssue=null, nextIssue=null, articleTotal=null, ext={EN=IssueExt(id=1329466999882756515, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1329456279791186761, language=EN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=), CN=IssueExt(id=1329466999882756516, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1329456279791186761, language=CN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=)}, issueFiles=null, downloadFileDto=null}, startPage=1049, endPage=1069, ext={EN=ArticleExt(id=1329456537443087266, articleId=1329456537199817633, tenantId=1146029695717560320, journalId=1324759914146529478, language=EN, title=An Efficient and Compact Key Encapsulation Mechanism Based on NTRU Lattice, columnId=1325493671541474142, journalTitle=Journal of Computer Research and Development, columnName=Network and Information Security, runingTitle=null, highlight=null, articleAbstract=

Constructing post-quantum key encapsulation mechanism based on NTRU lattice is one of the popular research fields in lattice-based cryptography. To reduce the ciphertext size, some current schemes compress the ciphertext with the aid of extra hardness assumptions and error correction codes, which leads to idealistic underlying assumption and complicated implementation. To address the issues, an efficient and compact key encapsulation mechanism, named LTRU, is proposed. LTRU is only based on NTRU one-wayness assumption and enables ciphertext compression without using any error correction codes. The performance-balanced parameter set of LTRU is provided, featuring 128 b quantum security level along with the matching and negligible error probability, and smaller public key size and ciphertext size. LTRU is based on the NTT-friendly polynomial ring. To compute the polynomial operations of LTRU, an efficient mixed-radix NTT is presented. At last, both C implementation and AVX2 implementation of LTRU are provided. When compared with NIST Round 3 finalist NTRU-HRSS, the classical and quantum security of LTRU are strengthened by 6 b and 5 b, respectively. LTRU reduces the public key size, ciphertext size and total bandwidth by 14.6%, 26.0% and 20.3%, respectively. LTRU is 10.9 times faster in key generation and 1.7 faster in decapsulation with respect to AVX2 implementation, respectively.

, authors=Zhichuang Liang1, Jieyu Zheng1, Yunlei Zhao1, 2, *, authorsList=Zhichuang Liang, Jieyu Zheng, Yunlei Zhao, authorCompany=null, correspAuthors=Yunlei Zhao, authorNote=

born in 1997. PhD candidate. His main research interest includes lattice-based cryptography

born in 2000. PhD candidate. Her main research interests include post-quantum cryptography and cryptographic engineering

born in 1974. PhD, distinguished professor. His main research interests include post-quantum cryptography, cryptographic protocols, and theory of computing

, correspAuthorsNote=null, copyrightStatement=Copyright © 2024 Journal of Computer Research and Development. All rights reserved., copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=null, magXml=null, pdfUrl=null, pdf=null, pdfFileSize=null, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=null, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=null, mapNumber=null, fund=null), CN=ArticleExt(id=1329456538906899373, articleId=1329456537199817633, tenantId=1146029695717560320, journalId=1324759914146529478, language=CN, title=NTRU格上高效紧凑密钥封装方案, columnId=1325493672690713440, journalTitle=计算机研究与发展, columnName=网络与信息安全, runingTitle=null, highlight=null, articleAbstract=

基于NTRU格设计后量子密钥封装方案是格密码领域主流方向之一. 为降低密文尺寸,现有方案会引入额外的困难性假设和使用纠错码来辅助压缩密文,但这会导致方案的假设过强和实现更复杂. 为克服这些障碍,提出了一个仅基于NTRU单向困难性假设、不使用纠错码也能压缩密文的高效紧凑的密钥封装方案LTRU. 给出一套性能均衡的LTRU参数集:具有128 b量子安全强度、与之匹配且可忽略的错误率、较小的公钥尺寸和密文尺寸.LTRU基于NTT友好环构造,给出一种高效的混合基数论变换算法来计算该环上多项式运算还给出了LTRU的C实现和AVX2实现. 与NIST第3轮决赛方案NTRU-HRSS相比,LTRU的经典安全强度和量子安全强度分别增强6 b和5 b,LTRU的公钥尺寸降低14.6%,密文尺寸降低26.0%,总带宽降低20.3%;在AVX2实现的密钥生成和解封装算法上分别快了10.9倍和1.7倍.

, authors=梁志闯1, 郑婕妤1, 赵运磊1, 2, *, authorsList=梁志闯, 郑婕妤, 赵运磊, authorCompany=null, correspAuthors=赵运磊, authorNote=

1997年生. 博士研究生. 主要研究方向为格密码

2000年生. 博士研究生. 主要研究方向为后量子密码、密码工程

1974年生. 博士,特聘教授. 主要研究方向为后量子密码、密码协议、计算理论

, correspAuthorsNote=
赵运磊()
, copyrightStatement=版权所有 © 2024 计算机研究与发展编辑部, copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=8d3FN+HFnL3vrneY2avRKA==, magXml=pPuj5A5dPXINq1TrR7Tbtg==, pdfUrl=null, pdf=N3b8kXx3uEPdWs0AlLbPDQ==, pdfFileSize=1759747, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=JKya9AnY93VqJI7SUqtjXg==, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=0Dt0+r+sMTh+zte8paLcxA==, mapNumber=null, fund=null)}, authors=[Author(id=1329456539468936117, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=zcliang21@m.fudan.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329456539544433591, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, authorId=1329456539468936117, language=EN, stringName=Zhichuang Liang, firstName=Zhichuang, middleName=null, lastName=Liang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Science, Fudan University, Shanghai 200433, bio={"content":"

born in 1997. PhD candidate. His main research interest includes lattice-based cryptography

"}, bioImg=null, bioContent=

born in 1997. PhD candidate. His main research interest includes lattice-based cryptography

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329456539611542456, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, authorId=1329456539468936117, language=CN, stringName=梁志闯, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1复旦大学计算机科学技术学院 上海 200433, bio={"img":"Z74dYP/zU5vaScRjK/GNdw==","content":"

1997年生. 博士研究生. 主要研究方向为格密码

"}, bioImg=Z74dYP/zU5vaScRjK/GNdw==, bioContent=

1997年生. 博士研究生. 主要研究方向为格密码

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329456539271803822, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, xref=1, ext=[AuthorCompanyExt(id=1329456539280192431, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539271803822, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science, Fudan University, Shanghai 200433), AuthorCompanyExt(id=1329456539292775344, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539271803822, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1复旦大学计算机科学技术学院 上海 200433)])]), Author(id=1329456539678651322, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329456539749954492, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, authorId=1329456539678651322, language=EN, stringName=Jieyu Zheng, firstName=Jieyu, middleName=null, lastName=Zheng, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Science, Fudan University, Shanghai 200433, bio={"content":"

born in 2000. PhD candidate. Her main research interests include post-quantum cryptography and cryptographic engineering

"}, bioImg=null, bioContent=

born in 2000. PhD candidate. Her main research interests include post-quantum cryptography and cryptographic engineering

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329456539812869053, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, authorId=1329456539678651322, language=CN, stringName=郑婕妤, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1复旦大学计算机科学技术学院 上海 200433, bio={"img":"M3nnGPm69/pj5oi7LLJXog==","content":"

2000年生. 博士研究生. 主要研究方向为后量子密码、密码工程

"}, bioImg=M3nnGPm69/pj5oi7LLJXog==, bioContent=

2000年生. 博士研究生. 主要研究方向为后量子密码、密码工程

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329456539271803822, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, xref=1, ext=[AuthorCompanyExt(id=1329456539280192431, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539271803822, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science, Fudan University, Shanghai 200433), AuthorCompanyExt(id=1329456539292775344, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539271803822, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1复旦大学计算机科学技术学院 上海 200433)])]), Author(id=1329456539867395007, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=ylzhao@fudan.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1329456539951281090, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, authorId=1329456539867395007, language=EN, stringName=Yunlei Zhao, firstName=Yunlei, middleName=null, lastName=Zhao, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, *, address=1School of Computer Science, Fudan University, Shanghai 200433
2State Key Laboratory of Cryptology, Beijing 100036, bio={"content":"

born in 1974. PhD, distinguished professor. His main research interests include post-quantum cryptography, cryptographic protocols, and theory of computing

"}, bioImg=null, bioContent=

born in 1974. PhD, distinguished professor. His main research interests include post-quantum cryptography, cryptographic protocols, and theory of computing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329456540026778563, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, authorId=1329456539867395007, language=CN, stringName=赵运磊, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, *, address=1复旦大学计算机科学技术学院 上海 200433
2密码科学技术国家重点实验室 北京 100036, bio={"img":"pqV4W/lGLW+uObgpwNbJPA==","content":"

1974年生. 博士,特聘教授. 主要研究方向为后量子密码、密码协议、计算理论

"}, bioImg=pqV4W/lGLW+uObgpwNbJPA==, bioContent=

1974年生. 博士,特聘教授. 主要研究方向为后量子密码、密码协议、计算理论

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329456539271803822, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, xref=1, ext=[AuthorCompanyExt(id=1329456539280192431, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539271803822, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science, Fudan University, Shanghai 200433), AuthorCompanyExt(id=1329456539292775344, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539271803822, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1复旦大学计算机科学技术学院 上海 200433)]), AuthorCompany(id=1329456539376661425, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, xref=2, ext=[AuthorCompanyExt(id=1329456539385050034, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539376661425, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2State Key Laboratory of Cryptology, Beijing 100036), AuthorCompanyExt(id=1329456539393438643, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539376661425, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2密码科学技术国家重点实验室 北京 100036)])])], keywords=[Keyword(id=1329456540119053252, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=EN, orderNo=1, keyword=post-quantum cryptography), Keyword(id=1329456540186162117, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=EN, orderNo=2, keyword=NTRU), Keyword(id=1329456540274242502, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=EN, orderNo=3, keyword=key encapsulation mechanism), Keyword(id=1329456540349739975, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=EN, orderNo=4, keyword=ciphertext compression), Keyword(id=1329456540433626056, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=EN, orderNo=5, keyword=number theoretic transform), Keyword(id=1329456540513317833, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=EN, orderNo=6, keyword=AVX2 implementation), Keyword(id=1329456540584621002, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=CN, orderNo=1, keyword=后量子密码), Keyword(id=1329456540647535563, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=CN, orderNo=2, keyword=NTRU), Keyword(id=1329456540735615948, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=CN, orderNo=3, keyword=密钥封装方案), Keyword(id=1329456540823696333, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=CN, orderNo=4, keyword=密文压缩), Keyword(id=1329456540886610894, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=CN, orderNo=5, keyword=数论变换), Keyword(id=1329456540949525455, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=CN, orderNo=6, keyword=AVX2实现)], refs=[Reference(id=1329456542228788188, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=1, rfOrder=0, authorNames=null, journalName=null, refType=null, unstructuredReference=Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Review, 1999, 41(2): 303−332, articleTitle=null, refAbstract=null), Reference(id=1329456542300091357, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=2, rfOrder=1, authorNames=null, journalName=null, refType=null, unstructuredReference=NIST. PQC standardization process: Announcing four candidates to be standardized, plus fourth round candidates [EB/OL]. (2022-07-05) [2023-04-10].https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4, articleTitle=null, refAbstract=null), Reference(id=1329456542371394526, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=3, rfOrder=2, authorNames=null, journalName=null, refType=null, unstructuredReference=中国密码学会. 关于全国密码算法设计竞赛算法评选结果的公示[EB/OL]. (2020-01-02)[2023-04-10].https://www.cacrnet.org.cn/site/content/854.html, articleTitle=null, refAbstract=null), Reference(id=1329456542484640736, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=3, rfOrder=3, authorNames=null, journalName=null, refType=null, unstructuredReference=Chinese Association for Cryptologic Research. Announcement of the selection results of the national cryptographic algorithm competitions [EB/OL](2020-01-02)[2023-04-10]. https://www.cacrnet.org.cn/site/content/854.html (in Chinese)., articleTitle=null, refAbstract=null), Reference(id=1329456542547555297, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=4, authorNames=null, journalName=null, refType=null, unstructuredReference=NIST. Post-quantum cryptography round 1 submissions [EB/OL]. (2017-01-03) [2023-04-10]. https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-1-submissions, articleTitle=null, refAbstract=null), Reference(id=1329456542614664162, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=5, authorNames=null, journalName=null, refType=null, unstructuredReference=NIST. Post-quantum cryptography round 2 submissions [EB/OL]. (2019-01-30) [2023-04-10].https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-2-submissions, articleTitle=null, refAbstract=null), Reference(id=1329456542681773027, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=6, rfOrder=6, authorNames=null, journalName=null, refType=null, unstructuredReference=NIST. Post-quantum cryptography round 3 submissions [EB/OL]. (2020-07-23) [2023-04-10].https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions, articleTitle=null, refAbstract=null), Reference(id=1329456542778242020, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=7, rfOrder=7, authorNames=null, journalName=null, refType=null, unstructuredReference=Regev O. On lattices, learning with errors, random linear codes, and cryptography[J]. Journal of the ACM, 2009, 56(6): 1−40, articleTitle=null, refAbstract=null), Reference(id=1329456542853739493, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=8, rfOrder=8, authorNames=null, journalName=null, refType=null, unstructuredReference=Banerjee A, Peikert C, Rosen A. Pseudorandom functions and lattices [C] // Proc of the 31st Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2012: 719–737, articleTitle=null, refAbstract=null), Reference(id=1329456542916654054, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=9, rfOrder=9, authorNames=null, journalName=null, refType=null, unstructuredReference=Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings[C] // Proc of the 29th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2010: 1–23, articleTitle=null, refAbstract=null), Reference(id=1329456542996345831, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=10, rfOrder=10, authorNames=null, journalName=null, refType=null, unstructuredReference=Langlois A, Stehlé D. Worst-case to average-case reductions for module lattices[J]. Designs, Codes and Cryptography, 2015, 75(3): 565−599, articleTitle=null, refAbstract=null), Reference(id=1329456543059260392, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=11, rfOrder=11, authorNames=null, journalName=null, refType=null, unstructuredReference=Hoffstein J, Pipher J, Silverman J H. NTRU: A ring-based public key cryptosystem[C] //Proc of the 3rd Int Algorithmic Number Theory Symp. Berlin: Springer, 1998: 267–288, articleTitle=null, refAbstract=null), Reference(id=1329456543122174953, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=12, rfOrder=12, authorNames=null, journalName=null, refType=null, unstructuredReference=Howgrave-Graham N, Silverman J H, Whyte W. Choosing parameter sets for NTRUEncrypt with NAEP and SVES-3[C] //Proc of the Cryptographers’ Track at the RSA Conf. Berlin: Springer, 2005: 118–135, articleTitle=null, refAbstract=null), Reference(id=1329456543189283818, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=13, rfOrder=13, authorNames=null, journalName=null, refType=null, unstructuredReference=Howgrave-Graham N, Silverman J H, Singer A, et al. NAEP: Provable security in the presence of decryption failures [DB/OL]. IACR Cryptology ePrint Archive, 2003 [2023-04-10].https://eprint.iacr.org/2003/172, articleTitle=null, refAbstract=null), Reference(id=1329456543248004075, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=14, rfOrder=14, authorNames=null, journalName=null, refType=null, unstructuredReference=Hoffstein J, Pipher J, Silverman J H. NTRU: A new high speed public key cryptosystem[C] //Proc of the Rump Session of Crypto96. Berlin: Springer, 1996: 1–11, articleTitle=null, refAbstract=null), Reference(id=1329456543315112940, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=15, rfOrder=15, authorNames=null, journalName=null, refType=null, unstructuredReference=Coppersmith D, Shamir A. Lattice attacks on NTRU[C] //Proc of Int Conf on the Theory and Application of Cryptographic Techniques. Berlin: Springer, 1997: 52–61, articleTitle=null, refAbstract=null), Reference(id=1329456543403193325, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=16, rfOrder=16, authorNames=null, journalName=null, refType=null, unstructuredReference=Garg S, Gentry C, Halevi S. Candidate multilinear maps from ideal lattices[C] //Proc of the 32nd Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2013: 1–17, articleTitle=null, refAbstract=null), Reference(id=1329456543487079406, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=17, rfOrder=17, authorNames=null, journalName=null, refType=null, unstructuredReference=Langlois A, Stehlé D, Steinfeld R. GGHLite: More efficient multilinear maps from ideal lattices[C] //Proc of the 33rd Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2014: 239–256, articleTitle=null, refAbstract=null), Reference(id=1329456543545799663, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=18, rfOrder=18, authorNames=null, journalName=null, refType=null, unstructuredReference=Ducas L, Lyubashevsky V, Prest T. Efficient identity-based encryption over NTRU lattices[C] // Proc of the 20th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2014: 22–41, articleTitle=null, refAbstract=null), Reference(id=1329456543604519920, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=19, rfOrder=19, authorNames=null, journalName=null, refType=null, unstructuredReference=Fouque P A, Hoffstein J, Kirchner P, et al. Falcon: Fast-Fourier lattice-based compact signatures over NTRU[EB/OL]. NIST PQC Round 3 Submission, 2020 [2023-04-10].https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions, articleTitle=null, refAbstract=null), Reference(id=1329456543667434481, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=20, rfOrder=20, authorNames=null, journalName=null, refType=null, unstructuredReference=Chen Cong, Danba O, Hoffstein J. et al. NTRU submission[EB/OL]. NIST PQC round 3 submission, 2020 [2023-04-10]. https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions, articleTitle=null, refAbstract=null), Reference(id=1329456543759709170, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=21, rfOrder=21, authorNames=null, journalName=null, refType=null, unstructuredReference=Bernstein D J, Brumley B, Chen M S, et al. NTRU Prime: Round 3[EB/OL]. NIST PQC Round 3 Submission, 2020 [2023-04-10].https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions, articleTitle=null, refAbstract=null), Reference(id=1329456543826818035, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=22, rfOrder=22, authorNames=null, journalName=null, refType=null, unstructuredReference=Avanzi R, Bos J, Ducas L, et al. CRYSTALS-Kyber: Algorithm specifications and supporting documentation (version 3.01)[EB/OL]. NIST PQC Round 3 Submission, 2020 [2023-04-10].https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions, articleTitle=null, refAbstract=null), Reference(id=1329456543889732596, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=23, rfOrder=23, authorNames=null, journalName=null, refType=null, unstructuredReference=NIST. Status report on the third round of the NIST post-quantum cryptography standardization process [EB/OL]. (2022-07-30) [2023-04-10].https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413-upd1.pdf, articleTitle=null, refAbstract=null), Reference(id=1329456543961035765, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=24, rfOrder=24, authorNames=null, journalName=null, refType=null, unstructuredReference=Business Wire. Business wire security innovation’s NTRUEncrypt adopted as X9 standard for data protection [EB/OL]. (2011-04-11) [2023-04-10].https://www.businesswire.com/news/home/20110411005309/en/Security-Innovations-NTRUEncrypt-Adopted-X9-Standard-Data, articleTitle=null, refAbstract=null), Reference(id=1329456544036533238, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=25, rfOrder=25, authorNames=null, journalName=null, refType=null, unstructuredReference=OpenSSH. OpenSSH release notes [EB/OL]. (2022-10-04) [2023-04-10].https://www.openssh.com/releasenotes.html, articleTitle=null, refAbstract=null), Reference(id=1329456544112030711, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=26, rfOrder=26, authorNames=null, journalName=null, refType=null, unstructuredReference=Lyubashevsky V, Seiler G. NTTRU: Truly fast NTRU using NTT[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019, 2019(3): 180−201, articleTitle=null, refAbstract=null), Reference(id=1329456544212694008, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=27, rfOrder=27, authorNames=null, journalName=null, refType=null, unstructuredReference=Duman J, Hövelmanns K, Kiltz E, et al. A thorough treatment of highly-efficient NTRU instantiations [C] //Proc of the 26th IACR Int Conf on Practice and Theory of Public-Key Cryptography. Berlin: Springer, 2023: 65–94, articleTitle=null, refAbstract=null), Reference(id=1329456544275608569, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=28, rfOrder=28, authorNames=null, journalName=null, refType=null, unstructuredReference=Liang Zhichuang, Fang Boyue, Zheng Jieyu, et al. Compact and efficient KEMs over NTRU lattices [DB/OL]. IACR Cryptology ePrint Archive, 2022 [2023-04-10].https://eprint.iacr.org/2022/579, articleTitle=null, refAbstract=null), Reference(id=1329456544346911738, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=29, rfOrder=29, authorNames=null, journalName=null, refType=null, unstructuredReference=Fouque P A, Kirchner P, Pornin T, et al. BAT: Small and fast KEM over NTRU lattices[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022, 2022(2): 240−265, articleTitle=null, refAbstract=null), Reference(id=1329456544401437691, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=30, rfOrder=30, authorNames=null, journalName=null, refType=null, unstructuredReference=D’Anvers J P, Tiepelt M, Vercauteren F, et al. Timing attacks on error correcting codes in post-quantum schemes[C] //Proc of ACM Workshop on Theory of Implementation Security Workshop. New York: ACM, 2019: 2–9, articleTitle=null, refAbstract=null), Reference(id=1329456544468546556, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=31, rfOrder=31, authorNames=null, journalName=null, refType=null, unstructuredReference=Kocher P C. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[C] // Proc of the 16th Annual Int Cryptology Conf. Berlin: Springer, 1996: 104–113, articleTitle=null, refAbstract=null), Reference(id=1329456544548238333, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=32, rfOrder=32, authorNames=null, journalName=null, refType=null, unstructuredReference=Stehlé D, Steinfeld R. Making NTRU as secure as worst-case problems over ideal lattices[C] //Proc of the 30th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2011: 27–47, articleTitle=null, refAbstract=null), Reference(id=1329456544627930110, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=33, rfOrder=33, authorNames=null, journalName=null, refType=null, unstructuredReference=Wang Yang, Wang Mingqiang. Provably secure NTRUEncrypt over any cyclotomic field[C] //Proc of the 25th Int Conf on Selected Areas in Cryptography. Berlin: Springer, 2018: 391–417, articleTitle=null, refAbstract=null), Reference(id=1329456544695038975, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=34, rfOrder=34, authorNames=null, journalName=null, refType=null, unstructuredReference=Jarvis K, Nevins M. ETRU: NTRU over the Eisenstein integers[J]. Designs, Codes and Cryptography, 2015, 74(1): 219−242, articleTitle=null, refAbstract=null), Reference(id=1329456544749564928, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=35, rfOrder=35, authorNames=null, journalName=null, refType=null, unstructuredReference=Hülsing A, Rijneveld J, Schanck J, et al. High-speed key encapsulation from NTRU[C] //Proc of the 17th Int Conf on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2017: 232–252, articleTitle=null, refAbstract=null), Reference(id=1329456544816672768, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=36, rfOrder=36, authorNames=null, journalName=null, refType=null, unstructuredReference=Bernstein D J, Chuengsatiansup C, Lange T, et al. NTRU prime: Reducing attack surface at low cost[C] //Proc of the 24th Int Conf on Selected Areas in Cryptography. Berlin: Springer, 2017: 235–260, articleTitle=null, refAbstract=null), Reference(id=1329456544892170241, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=37, rfOrder=37, authorNames=null, journalName=null, refType=null, unstructuredReference=Bos J, Ducas L, Kiltz E, et al. CRYSTALS-Kyber: A CCA-secure module-lattice-based KEM[C] //Proc of 2018 IEEE European Symp on Security and Privacy. Piscataway, NJ: IEEE, 2018: 353–367, articleTitle=null, refAbstract=null), Reference(id=1329456544959279106, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=38, rfOrder=38, authorNames=null, journalName=null, refType=null, unstructuredReference=Bellare M, Rogaway P. Random oracles are practical: A paradigm for designing efficient protocols[C] //Proc of the 1st ACM Conf on Computer and Communications Security. New York: ACM, 1993: 62–73, articleTitle=null, refAbstract=null), Reference(id=1329456545043165187, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=39, rfOrder=39, authorNames=null, journalName=null, refType=null, unstructuredReference=Boneh D, Dagdelen Ö, Fischlin M, et al. Random oracles in a quantum world[C] //Proc of the 17th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2011: 41–69, articleTitle=null, refAbstract=null), Reference(id=1329456545106079748, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=40, rfOrder=40, authorNames=null, journalName=null, refType=null, unstructuredReference=Bernstein D J. Multidigit multiplication for mathematicians [EB/OL]. (2001-09-12) [2023-04-10]. http://cr.yp.to/papers.html#m3, articleTitle=null, refAbstract=null), Reference(id=1329456545173188613, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=41, rfOrder=41, authorNames=null, journalName=null, refType=null, unstructuredReference=Cooley J W, Tukey J W. An algorithm for the machine calculation of complex Fourier series[J]. Mathematics of Computation, 1965, 19(90): 297−301, articleTitle=null, refAbstract=null), Reference(id=1329456545261268998, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=42, rfOrder=42, authorNames=null, journalName=null, refType=null, unstructuredReference=Gentleman W M, Sande G. Fast Fourier transforms: For fun and profit[C] // Proc of the AFIPS’66 Fall Joint Computer Conf. New York: ACM, 1966: 563–578, articleTitle=null, refAbstract=null), Reference(id=1329456545332572167, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=43, rfOrder=43, authorNames=null, journalName=null, refType=null, unstructuredReference=Weimerskirch A, Paar C. Generalizations of the Karatsuba algorithm for efficient implementations [DB/OL]. IACR Cryptology ePrint Archive, 2006 [2023-04-10].https://eprint.iacr.org/2006/224, articleTitle=null, refAbstract=null), Reference(id=1329456545399681032, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=44, rfOrder=44, authorNames=null, journalName=null, refType=null, unstructuredReference=Fujisaki E, Okamoto T. Secure integration of asymmetric and symmetric encryption schemes[J]. Journal of Cryptology, 2013, 26(1): 80−101, articleTitle=null, refAbstract=null), Reference(id=1329456545466789897, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=45, rfOrder=45, authorNames=null, journalName=null, refType=null, unstructuredReference=Hofheinz D, Hövelmanns K, Kiltz E. A modular analysis of the Fujisaki-Okamoto transformation[C] //Proc of the 15th Theory of Cryptography Conf. Berlin: Springer, 2017: 341–371, articleTitle=null, refAbstract=null), Reference(id=1329456545538093066, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=46, rfOrder=46, authorNames=null, journalName=null, refType=null, unstructuredReference=Shoup V. Sequences of games: A tool for taming complexity in security proofs [DB/OL]. IACR Cryptology ePrint Archive, 2004 [2023-04-10].https://eprint.iacr.org/2004/332, articleTitle=null, refAbstract=null), Reference(id=1329456545605201931, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=47, rfOrder=47, authorNames=null, journalName=null, refType=null, unstructuredReference=Don J, Fehr S, Majenz C, et al. Online-extractability in the quantum random-oracle model [C] //Proc of the 41st Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2022: 677–706, articleTitle=null, refAbstract=null), Reference(id=1329456545668116492, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=48, rfOrder=48, authorNames=null, journalName=null, refType=null, unstructuredReference=Kannan R. Minkowski’s convex body theorem and integer programming[J]. Mathematics of Operations Research, 1987, 12(3): 415−440, articleTitle=null, refAbstract=null), Reference(id=1329456545731031053, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=49, rfOrder=49, authorNames=null, journalName=null, refType=null, unstructuredReference=Bai Shi, Galbraith S D. Lattice decoding attacks on binary LWE[C] //Proc of the 19th Australasian Conf on Information Security and Privacy. Berlin: Springer, 2014: 322–337, articleTitle=null, refAbstract=null), Reference(id=1329456545793945614, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=50, rfOrder=50, authorNames=null, journalName=null, refType=null, unstructuredReference=Schnorr C P, Euchner M. Lattice basis reduction: Improved practical algorithms and solving subset sum problems[J]. Mathematical Programming, 1994, 66(1): 181−199, articleTitle=null, refAbstract=null), Reference(id=1329456545869443087, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=51, rfOrder=51, authorNames=null, journalName=null, refType=null, unstructuredReference=Chen Yuanmi, Nguyen P Q. BKZ 2.0: Better lattice security estimates[C] //Proc of the 17th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2011: 1–20, articleTitle=null, refAbstract=null), Reference(id=1329456545936551952, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=52, rfOrder=52, authorNames=null, journalName=null, refType=null, unstructuredReference=Alkim E, Ducas L, Pöppelmann T, et al. Post-quantum key exchange—A new hope[C] //Proc of the 25th USENIX Security Symp. Berkeley: USENIX Association, 2016: 327–343, articleTitle=null, refAbstract=null), Reference(id=1329456546020438033, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=53, rfOrder=53, authorNames=null, journalName=null, refType=null, unstructuredReference=Albrecht M R, Curtis B R, Deo A, et al. Estimate all the {LWE, NTRU} schemes![C] //Proc of the 11th Int Conf on Security and Cryptography for Networks. Berlin: Springer, 2018: 351–367, articleTitle=null, refAbstract=null), Reference(id=1329456546079158290, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=54, rfOrder=54, authorNames=null, journalName=null, refType=null, unstructuredReference=Albrecht M, Bai Shi, Ducas L. A subfield lattice attack on overstretched NTRU assumptions[C] //Proc of the 36th Annual Int Cryptology Conf. Berlin: Springer, 2016: 153–178, articleTitle=null, refAbstract=null), Reference(id=1329456546150461459, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=55, rfOrder=55, authorNames=null, journalName=null, refType=null, unstructuredReference=Howgrave-Graham N. A hybrid lattice-reduction and meet-in-the-middle attack against NTRU[C] // Proc of the 27th Annual Int Cryptology Conf. Berlin: Springer, 2007: 150–169, articleTitle=null, refAbstract=null), Reference(id=1329456546217570324, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=56, rfOrder=56, authorNames=null, journalName=null, refType=null, unstructuredReference=Hassan C A, Yayla O. Radix-3 NTT-based polynomial multiplication for lattice-based cryptography [DB/OL]. IACR Cryptology ePrint Archive, 2022 [2023-04-10].https://eprint.iacr.org/2022/726, articleTitle=null, refAbstract=null), Reference(id=1329456546288873493, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=57, rfOrder=57, authorNames=null, journalName=null, refType=null, unstructuredReference=Barrett P. Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor[C] //Proc of Conf on the Theory and Application of Cryptographic Techniques. Berlin: Springer, 1986: 311–323, articleTitle=null, refAbstract=null), Reference(id=1329456546351788054, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=58, rfOrder=58, authorNames=null, journalName=null, refType=null, unstructuredReference=Montgomery P L. Modular multiplication without trial division[J]. Mathematics of Computation, 1985, 44(170): 519−521, articleTitle=null, refAbstract=null), Reference(id=1329456546418896919, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=59, rfOrder=59, authorNames=null, journalName=null, refType=null, unstructuredReference=Seiler G. Faster AVX2 optimized NTT multiplication for ring-LWE lattice cryptography [DB/OL]. IACR Cryptology ePrint Archive, 2018 [2023-04-10].https://eprint.iacr.org/2018/039, articleTitle=null, refAbstract=null), Reference(id=1329456546481811480, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=60, rfOrder=60, authorNames=null, journalName=null, refType=null, unstructuredReference=Bernstein D J, Lange T. eBACS: ECRYPT benchmarking of cryptographic systems [EB/OL]. (2022-06-19) [2023-04-10].https://bench.cr.yp.to, articleTitle=null, refAbstract=null)], funds=null, companyList=[AuthorCompany(id=1329456539271803822, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, xref=1, ext=[AuthorCompanyExt(id=1329456539280192431, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539271803822, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science, Fudan University, Shanghai 200433), AuthorCompanyExt(id=1329456539292775344, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539271803822, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1复旦大学计算机科学技术学院 上海 200433)]), AuthorCompany(id=1329456539376661425, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, xref=2, ext=[AuthorCompanyExt(id=1329456539385050034, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539376661425, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2State Key Laboratory of Cryptology, Beijing 100036), AuthorCompanyExt(id=1329456539393438643, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539376661425, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2密码科学技术国家重点实验室 北京 100036)])], figs=[ArticleFig(id=1329456541129880528, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=EN, label=Figure 1, caption=The tree map of CRT isomorphism, figureFileSmall=c0tW9nfjaowBf4ZOyste4Q==, figureFileBig=JKya9AnY93VqJI7SUqtjXg==, tableContent=null), ArticleFig(id=1329456541213766609, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=CN, label=图1, caption=CRT同构的树形图, figureFileSmall=c0tW9nfjaowBf4ZOyste4Q==, figureFileBig=JKya9AnY93VqJI7SUqtjXg==, tableContent=null), ArticleFig(id=1329456541402510290, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=EN, label=Figure 2, caption=The padding and extraction of coefficients, figureFileSmall=fiFsvYhtqP3PUo/Uzz0SyA==, figureFileBig=MeXZS1JeRVpiuH9CErGxpw==, tableContent=null), ArticleFig(id=1329456541469619155, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=CN, label=图2, caption=系数的填充与提取, figureFileSmall=fiFsvYhtqP3PUo/Uzz0SyA==, figureFileBig=MeXZS1JeRVpiuH9CErGxpw==, tableContent=null), ArticleFig(id=1329456541532533716, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=EN, label=Table 1, caption=

Recommended Parameter Set of LTRU

, figureFileSmall=null, figureFileBig=null, tableContent=
$ {\mathcal{R}_q} $$ n $$ q $$ p $$ d $$ \psi $|pk|/B|ct|/BB.W./BSec-(C, Q)/b$ \delta $
$ {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) $6482 917210$ {\bar B_2} $9728421 814(142, 129)$ {2^{ - 154}} $
), ArticleFig(id=1329456541612225493, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=CN, label=表1, caption=

LTRU的推荐参数集

, figureFileSmall=null, figureFileBig=null, tableContent=
$ {\mathcal{R}_q} $$ n $$ q $$ p $$ d $$ \psi $|pk|/B|ct|/BB.W./BSec-(C, Q)/b$ \delta $
$ {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) $6482 917210$ {\bar B_2} $9728421 814(142, 129)$ {2^{ - 154}} $
), ArticleFig(id=1329456541679334358, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=EN, label=Table 2, caption=

Comparison Between Mixed-Radix NTT and Unoptimized NTT

, figureFileSmall=null, figureFileBig=null, tableContent=
比较的项目类别混合基NTT(本文)未优化的NTT
乘法复杂度理论分析多项式环$ {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) $$ {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) $
正向变换$\dfrac{1}{2}n{l_2} + n{l_3} +\dfrac{1}{2}n $$\dfrac{1}{2}n{l_2} + 2n{l_3} +\dfrac{1}{2}n $
点乘$ 2n $$\dfrac{5}{2}n $
逆向变换$\dfrac{1}{2}n{l_2} + n{l_3} +\dfrac{3}{2}n $$\dfrac{1}{2}n{l_2} + 2n{l_3} +\dfrac{3}{2}n $
求逆矩阵2×2方阵2×2方阵
总计$ n{l_2} + 2n{l_3} + 4n $$ n{l_2} + 4n{l_3} +\dfrac{9}{2}n $
具体实现耗时/kcycle
(选取$ n = 648,q = 2\;917 $)
正向变换2158828756
点乘68748657
逆向变换2511934326
总计5358171739
), ArticleFig(id=1329456541784191959, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=CN, label=表2, caption=

混合基NTT和未优化的NTT的比较

, figureFileSmall=null, figureFileBig=null, tableContent=
比较的项目类别混合基NTT(本文)未优化的NTT
乘法复杂度理论分析多项式环$ {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) $$ {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) $
正向变换$\dfrac{1}{2}n{l_2} + n{l_3} +\dfrac{1}{2}n $$\dfrac{1}{2}n{l_2} + 2n{l_3} +\dfrac{1}{2}n $
点乘$ 2n $$\dfrac{5}{2}n $
逆向变换$\dfrac{1}{2}n{l_2} + n{l_3} +\dfrac{3}{2}n $$\dfrac{1}{2}n{l_2} + 2n{l_3} +\dfrac{3}{2}n $
求逆矩阵2×2方阵2×2方阵
总计$ n{l_2} + 2n{l_3} + 4n $$ n{l_2} + 4n{l_3} +\dfrac{9}{2}n $
具体实现耗时/kcycle
(选取$ n = 648,q = 2\;917 $)
正向变换2158828756
点乘68748657
逆向变换2511934326
总计5358171739
), ArticleFig(id=1329456541901632472, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=EN, label=Table 3, caption=

Comparison Between LTRU and Other Schemes

, figureFileSmall=null, figureFileBig=null, tableContent=
方案困难性假设底层PKE|pk|/B|ct|/BB.W. /BSec-(C, Q)/b$ \delta $
LTRU(本文)NTRU-OWIND-CPA RPKE9728421814(142, 129)$ {2^{ - 154}} $
NTRU-HRSSNTRU-OWOW-CPA DPKE113811382276(136, 124)$ {2^{ - \infty }} $
SNTRU Prime-761NTRU-OWOW-CPA DPKE115810392197(153, 137)$ {2^{ - \infty }} $
NTTRUNTRU-OWOW-CPA RPKE124812482496(153, 140)$ {2^{ - 1217}} $
$ {\text{NTRU - A}}_{2\;917}^{648} $NTRU+RLWEOW-CPA RPKE9729721 944(152, 137)$ {2^{ - 175}} $
CTRU-768NTRU+RLWEIND-CPA RPKE11529602112(181, 164)$ {2^{ - 184}} $
BAT-512NTRU+RLWRIND-CPA RPKE521473994(140, 124)$ {2^{ - 146}} $
Kyber-768MLWEIND-CPA RPKE118410882272(183, 166)$ {2^{ - 164}} $
), ArticleFig(id=1329456541985518553, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=CN, label=表3, caption=

LTRU和其他方案的对比

, figureFileSmall=null, figureFileBig=null, tableContent=
方案困难性假设底层PKE|pk|/B|ct|/BB.W. /BSec-(C, Q)/b$ \delta $
LTRU(本文)NTRU-OWIND-CPA RPKE9728421814(142, 129)$ {2^{ - 154}} $
NTRU-HRSSNTRU-OWOW-CPA DPKE113811382276(136, 124)$ {2^{ - \infty }} $
SNTRU Prime-761NTRU-OWOW-CPA DPKE115810392197(153, 137)$ {2^{ - \infty }} $
NTTRUNTRU-OWOW-CPA RPKE124812482496(153, 140)$ {2^{ - 1217}} $
$ {\text{NTRU - A}}_{2\;917}^{648} $NTRU+RLWEOW-CPA RPKE9729721 944(152, 137)$ {2^{ - 175}} $
CTRU-768NTRU+RLWEIND-CPA RPKE11529602112(181, 164)$ {2^{ - 184}} $
BAT-512NTRU+RLWRIND-CPA RPKE521473994(140, 124)$ {2^{ - 146}} $
Kyber-768MLWEIND-CPA RPKE118410882272(183, 166)$ {2^{ - 164}} $
), ArticleFig(id=1329456542061016026, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=EN, label=Table 4, caption=

Comparison of Implementation Efficiency of Schemes kcycle

, figureFileSmall=null, figureFileBig=null, tableContent=
方案C实现AVX2实现
KeyGenEncapsDecapsKeyGenEncapsDecaps
LTRU(本文)88.961.5108.823.124.133.3
NTRU-HRSS130.0×1033.6×1039.8×103254.024.959.2
SNTRU Prime-76116.9×1039.1×10324.5×103715.141.749.0
CTRU-768117.663.3134.710.611.835.6
BAT-51229.4×10311.159.7
Kyber-768165.9188.6210.241.556.844.3
LTRU-SHA2(本文)77.352.493.816.616.223.8
NTTRU160.5101.1141.66.46.17.9
$ {\text{NTRU - A}}_{2\;917}^{648} $6.25.67.3
), ArticleFig(id=1329456542128124891, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, language=CN, label=表4, caption=

方案的实现效率对比

, figureFileSmall=null, figureFileBig=null, tableContent=
方案C实现AVX2实现
KeyGenEncapsDecapsKeyGenEncapsDecaps
LTRU(本文)88.961.5108.823.124.133.3
NTRU-HRSS130.0×1033.6×1039.8×103254.024.959.2
SNTRU Prime-76116.9×1039.1×10324.5×103715.141.749.0
CTRU-768117.663.3134.710.611.835.6
BAT-51229.4×10311.159.7
Kyber-768165.9188.6210.241.556.844.3
LTRU-SHA2(本文)77.352.493.816.616.223.8
NTTRU160.5101.1141.66.46.17.9
$ {\text{NTRU - A}}_{2\;917}^{648} $6.25.67.3
)], attaches=null, journal=Journal(id=1324759606947315908, delFlag=0, nameCn=计算机研究与发展, nameEn=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, issn=1000-1239, eissn=null, cn=11-1777/TP, coden=null, periodic=0, language=CN, oaType=null, ccby=null, superviseOffice=null, ownerOffice=null, pubOffice=null, editorOffice=null, officeType=null, aims=null, clcCode=null, officeProv=null, officeCity=null, officeAddr=null, officeZip=null, officeEmail=null, officePhone=null, editDirector=null, officeDirector=null, officeDirectorPhone=null, officeStaffNum=null, officeEmpNum=null, coverPicUrl=k2l8zgqwstuxxevFX2qxVA==, journalPrice=null, startedYear=null, abbrevIsoEn=Journal of Computer Research and Development, journalRemark=null, publicationField=null, createdTime=1793776903141, updatedTime=1793850698612, createdBy=18614031015, updatedBy=13701087609, firstLetterCn=J, firstLetterEn=J, subjectCode=Electronic Information, subjectName=null, subjectCodeEn=Electronic Information, subjectNameEn=null, picCn=k2l8zgqwstuxxevFX2qxVA==, picEn=r6k0Ry+RD+c/VXj5QarmDw==, jcr=null, cjcr=null, exts=[JournalExt(id=1325069127710286688, language=CN, name=计算机研究与发展, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698640, updatedTime=1793850698640, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""}), JournalExt(id=1325069127777395553, language=EN, name=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698656, updatedTime=1793850698656, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""})], databaseList=null, tenantJournalId=1324759914146529478, websiteList=[Website(id=1325070300139892771, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN, language=CN, createTime=1793850978169, createBy=18614031015, updateTime=1793851040259, updateBy=18614031015, name=计算机研究与发展-中文, tplId=1146099689490845704, title=计算机研究与发展, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070893751349360, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=articleTextType, value=kx, createTime=1793851119697, updateTime=1793851119697, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893730377837, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=banner, value=null, createTime=1793851119692, updateTime=1793851119692, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893772320883, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=grayFlag, value=0, createTime=1793851119702, updateTime=1793851119702, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893721989228, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851119690, updateTime=1793851119690, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893784903797, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=minRunFlag, value=0, createTime=1793851119705, updateTime=1793851119705, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893742960751, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic, createTime=1793851119695, updateTime=1793851119695, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893780709492, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=silenceFlag, value=0, createTime=1793851119704, updateTime=1793851119704, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893738766446, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_cn_619/, createTime=1793851119694, updateTime=1793851119694, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893755543665, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeColor, value=null, createTime=1793851119698, updateTime=1793851119698, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893763932274, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeStyle, value=null, createTime=1793851119700, updateTime=1793851119700, creator=18614031015, updator=18614031015)]), Website(id=1325070300580294698, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN, language=EN, createTime=1793850978274, createBy=18614031015, updateTime=1793851036638, updateBy=18614031015, name=计算机研究与发展-英文, tplId=1146101810881728533, title=Journal of Computer Research and Development, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070925288321148, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=articleTextType, value=kx, createTime=1793851127216, updateTime=1793851127216, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925263155321, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=banner, value=null, createTime=1793851127210, updateTime=1793851127210, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925309292671, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=grayFlag, value=0, createTime=1793851127221, updateTime=1793851127221, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925254766712, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851127208, updateTime=1793851127208, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925326069889, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=minRunFlag, value=0, createTime=1793851127225, updateTime=1793851127225, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925279932539, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic, createTime=1793851127214, updateTime=1793851127214, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925317681280, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=silenceFlag, value=0, createTime=1793851127223, updateTime=1793851127223, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925271543930, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_en_623/, createTime=1793851127212, updateTime=1793851127212, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925292515453, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeColor, value=null, createTime=1793851127217, updateTime=1793851127217, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925300904062, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeStyle, value=null, createTime=1793851127219, updateTime=1793851127219, creator=18614031015, updator=18614031015)])], journalTitle=计算机研究与发展, weixinUrl=null, journalUrl=https://crad.ict.ac.cn/, iacademicId=null, status=1, seqNo=null, journalTitleEn=Journal of Computer Research and Development, journalPhotoCn=k2l8zgqwstuxxevFX2qxVA==, journalPhotoEn=r6k0Ry+RD+c/VXj5QarmDw==, journalFirstLetter=J, journalRecommend=null, journalNew=null, journalCollection=null, jcrJf=null, cjcrJf=null, jcrJfStr=null, cjcrJfStr=null, submissionFirstDecision=null, sciSubjectClassification=null, casSubjectClassification=null, citeScore=null, totalCitationFrequency=null, icpCode=null, psCode=null, advertisingLicenseCode=null, copyrightInformation=null, country=null, option=, provinceCode=null, provinceName=null, collectFlag=false, interPubPlatform=, interPubPlatformUrl=null), detailUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202220980, detailUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202220980, pdfUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/PDF/10.7544/issn1000-1239.202220980, pdfUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/PDF/10.7544/issn1000-1239.202220980, aliStartDate=0, aliEndDate=0, collectionFlag=false, citedCount=null, citedUrl=null, previewStatus=0, delFlag=0, hasFullText=1, orderTime=1711900800000, fullTextJson=null, articleText=null, reference=null)
收藏切换
NTRU格上高效紧凑密钥封装方案
梁志闯 1 , 郑婕妤 1 , 赵运磊 1, 2, *
计算机研究与发展 | 网络与信息安全 2024,61(4): 1049-1069
收起
收藏切换
计算机研究与发展 |网络与信息安全 2024 , 61 (4) : 1049 -1069
NTRU格上高效紧凑密钥封装方案
全屏
[Author(id=1329456539468936117, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=zcliang21@m.fudan.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329456539544433591, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, authorId=1329456539468936117, language=EN, stringName=Zhichuang Liang, firstName=Zhichuang, middleName=null, lastName=Liang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Science, Fudan University, Shanghai 200433, bio={"content":"

born in 1997. PhD candidate. His main research interest includes lattice-based cryptography

"}, bioImg=null, bioContent=

born in 1997. PhD candidate. His main research interest includes lattice-based cryptography

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329456539611542456, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, authorId=1329456539468936117, language=CN, stringName=梁志闯, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1复旦大学计算机科学技术学院 上海 200433, bio={"img":"Z74dYP/zU5vaScRjK/GNdw==","content":"

1997年生. 博士研究生. 主要研究方向为格密码

"}, bioImg=Z74dYP/zU5vaScRjK/GNdw==, bioContent=

1997年生. 博士研究生. 主要研究方向为格密码

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329456539271803822, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, xref=1, ext=[AuthorCompanyExt(id=1329456539280192431, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539271803822, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science, Fudan University, Shanghai 200433), AuthorCompanyExt(id=1329456539292775344, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539271803822, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1复旦大学计算机科学技术学院 上海 200433)])]), Author(id=1329456539678651322, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329456539749954492, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, authorId=1329456539678651322, language=EN, stringName=Jieyu Zheng, firstName=Jieyu, middleName=null, lastName=Zheng, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Science, Fudan University, Shanghai 200433, bio={"content":"

born in 2000. PhD candidate. Her main research interests include post-quantum cryptography and cryptographic engineering

"}, bioImg=null, bioContent=

born in 2000. PhD candidate. Her main research interests include post-quantum cryptography and cryptographic engineering

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329456539812869053, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, authorId=1329456539678651322, language=CN, stringName=郑婕妤, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1复旦大学计算机科学技术学院 上海 200433, bio={"img":"M3nnGPm69/pj5oi7LLJXog==","content":"

2000年生. 博士研究生. 主要研究方向为后量子密码、密码工程

"}, bioImg=M3nnGPm69/pj5oi7LLJXog==, bioContent=

2000年生. 博士研究生. 主要研究方向为后量子密码、密码工程

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329456539271803822, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, xref=1, ext=[AuthorCompanyExt(id=1329456539280192431, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539271803822, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science, Fudan University, Shanghai 200433), AuthorCompanyExt(id=1329456539292775344, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539271803822, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1复旦大学计算机科学技术学院 上海 200433)])]), Author(id=1329456539867395007, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=ylzhao@fudan.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1329456539951281090, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, authorId=1329456539867395007, language=EN, stringName=Yunlei Zhao, firstName=Yunlei, middleName=null, lastName=Zhao, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, *, address=1School of Computer Science, Fudan University, Shanghai 200433
2State Key Laboratory of Cryptology, Beijing 100036, bio={"content":"

born in 1974. PhD, distinguished professor. His main research interests include post-quantum cryptography, cryptographic protocols, and theory of computing

"}, bioImg=null, bioContent=

born in 1974. PhD, distinguished professor. His main research interests include post-quantum cryptography, cryptographic protocols, and theory of computing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329456540026778563, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, authorId=1329456539867395007, language=CN, stringName=赵运磊, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, *, address=1复旦大学计算机科学技术学院 上海 200433
2密码科学技术国家重点实验室 北京 100036, bio={"img":"pqV4W/lGLW+uObgpwNbJPA==","content":"

1974年生. 博士,特聘教授. 主要研究方向为后量子密码、密码协议、计算理论

"}, bioImg=pqV4W/lGLW+uObgpwNbJPA==, bioContent=

1974年生. 博士,特聘教授. 主要研究方向为后量子密码、密码协议、计算理论

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329456539271803822, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, xref=1, ext=[AuthorCompanyExt(id=1329456539280192431, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539271803822, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science, Fudan University, Shanghai 200433), AuthorCompanyExt(id=1329456539292775344, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539271803822, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1复旦大学计算机科学技术学院 上海 200433)]), AuthorCompany(id=1329456539376661425, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, xref=2, ext=[AuthorCompanyExt(id=1329456539385050034, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539376661425, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2State Key Laboratory of Cryptology, Beijing 100036), AuthorCompanyExt(id=1329456539393438643, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329456537199817633, companyId=1329456539376661425, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2密码科学技术国家重点实验室 北京 100036)])])]
梁志闯1 , 郑婕妤1, 赵运磊1, 2, *
作者信息
  • 1复旦大学计算机科学技术学院 上海 200433
  • 2密码科学技术国家重点实验室 北京 100036
通讯作者:
赵运磊()
作者简介:

1997年生. 博士研究生. 主要研究方向为格密码

2000年生. 博士研究生. 主要研究方向为后量子密码、密码工程

1974年生. 博士,特聘教授. 主要研究方向为后量子密码、密码协议、计算理论

An Efficient and Compact Key Encapsulation Mechanism Based on NTRU Lattice
Zhichuang Liang1 , Jieyu Zheng1, Yunlei Zhao1, 2, *
Affiliations
  • 1School of Computer Science, Fudan University, Shanghai 200433
  • 2State Key Laboratory of Cryptology, Beijing 100036
  • born in 1997. PhD candidate. His main research interest includes lattice-based cryptography

    born in 2000. PhD candidate. Her main research interests include post-quantum cryptography and cryptographic engineering

    born in 1974. PhD, distinguished professor. His main research interests include post-quantum cryptography, cryptographic protocols, and theory of computing

出版时间: 2024-04-01 doi: 10.7544/issn1000-1239.202220980
文章导航
收藏切换

基于NTRU格设计后量子密钥封装方案是格密码领域主流方向之一. 为降低密文尺寸,现有方案会引入额外的困难性假设和使用纠错码来辅助压缩密文,但这会导致方案的假设过强和实现更复杂. 为克服这些障碍,提出了一个仅基于NTRU单向困难性假设、不使用纠错码也能压缩密文的高效紧凑的密钥封装方案LTRU. 给出一套性能均衡的LTRU参数集:具有128 b量子安全强度、与之匹配且可忽略的错误率、较小的公钥尺寸和密文尺寸.LTRU基于NTT友好环构造,给出一种高效的混合基数论变换算法来计算该环上多项式运算还给出了LTRU的C实现和AVX2实现. 与NIST第3轮决赛方案NTRU-HRSS相比,LTRU的经典安全强度和量子安全强度分别增强6 b和5 b,LTRU的公钥尺寸降低14.6%,密文尺寸降低26.0%,总带宽降低20.3%;在AVX2实现的密钥生成和解封装算法上分别快了10.9倍和1.7倍.

后量子密码  /  NTRU  /  密钥封装方案  /  密文压缩  /  数论变换  /  AVX2实现

Constructing post-quantum key encapsulation mechanism based on NTRU lattice is one of the popular research fields in lattice-based cryptography. To reduce the ciphertext size, some current schemes compress the ciphertext with the aid of extra hardness assumptions and error correction codes, which leads to idealistic underlying assumption and complicated implementation. To address the issues, an efficient and compact key encapsulation mechanism, named LTRU, is proposed. LTRU is only based on NTRU one-wayness assumption and enables ciphertext compression without using any error correction codes. The performance-balanced parameter set of LTRU is provided, featuring 128 b quantum security level along with the matching and negligible error probability, and smaller public key size and ciphertext size. LTRU is based on the NTT-friendly polynomial ring. To compute the polynomial operations of LTRU, an efficient mixed-radix NTT is presented. At last, both C implementation and AVX2 implementation of LTRU are provided. When compared with NIST Round 3 finalist NTRU-HRSS, the classical and quantum security of LTRU are strengthened by 6 b and 5 b, respectively. LTRU reduces the public key size, ciphertext size and total bandwidth by 14.6%, 26.0% and 20.3%, respectively. LTRU is 10.9 times faster in key generation and 1.7 faster in decapsulation with respect to AVX2 implementation, respectively.

post-quantum cryptography  /  NTRU  /  key encapsulation mechanism  /  ciphertext compression  /  number theoretic transform  /  AVX2 implementation
梁志闯, 郑婕妤, 赵运磊. NTRU格上高效紧凑密钥封装方案. 计算机研究与发展, 2024 , 61 (4) : 1049 -1069 . DOI: 10.7544/issn1000-1239.202220980
Zhichuang Liang, Jieyu Zheng, Yunlei Zhao. An Efficient and Compact Key Encapsulation Mechanism Based on NTRU Lattice[J]. Journal of Computer Research and Development, 2024 , 61 (4) : 1049 -1069 . DOI: 10.7544/issn1000-1239.202220980
密码学是现代网络安全的基石. 现阶段广泛使用的公钥密码体制,如公钥加密、密钥封装、数字签名等,多数是基于经典的困难问题构造的,如求解大整数分解、(椭圆)离散对数等困难问题. 这些密码方案在当今互联网协议,如SSL/TLS,IPSec等中扮演了无可替代的角色,如保证通信内容的机密性、通信双方的身份认证、消息的完整性等. 尽管针对这些数论问题目前最好的经典求解算法的时间复杂度是指数或亚指数级别,至少是超多项式级别的,但近些年来随着量子计算的飞速发展,已有相关研究表明存在多项式时间的量子算法可以完全求解它们. 例如,美国科学家Shor[1]提出可在量子计算机中以多项式时间求解大整数分解和(椭圆)离散对数问题的量子算法. 量子计算相关技术的发展日新月异. 考虑到量子计算技术对现有公钥密码的颠覆性威胁,目前很多国家、公司和学术界已提前研究和布局能够抵抗量子攻击的密码学—后量子密码学(post-quantum cryptography,PQC).
事实上,早在2016年,美国国家标准技术研究所(National Institute of Standards and Technology,NIST)已经正式开启了对公钥加密(public key encryption,PKE)方案、密钥封装方案(key encapsulation mechanism,KEM)和数字签名这3种密钥原语的后量子密码方案标准征集活动,且目前已经评选出第3轮结果并选定拟标准化的方案[2]. 我国也在2019年举行后量子密码算法竞赛,并于2020年评选出获奖方案[3].
目前,后量子密码学的类型主要分为:基于哈希的、基于多变量的、基于同源的、基于编码的以及基于格的. 其中基于格构造的后量子密码方案不仅具有平均情形到最糟情形的困难性规约,还在安全性、通信带宽和计算效率等方面表现均衡. 在美国NIST和我国举办的后量子密码方案征集活动中,基于格的密码方案占据多数. 例如,NIST第1轮64个方案中的26个[4]、第2轮26个方案中的12个[5]、第3轮15个方案中的7个[6]以及拟标准化4个方案中的3个[2]均为基于格构造的密码方案. 我国后量子密码算法设计竞赛获奖方案共14个,其中有11个均为基于格构造的. 基于格的方案在设计PKE和KEM时主要基于一般格、理想格、模格和NTRU格. 常用的格困难问题主要分为2类:第1类是{R,M}LWE/LWR问题[7–10];第2类是NTRU格相关问题[11–13].
NTRU最早由Hoffstein等人[14]于1996年美密会讨论环节中提出,但它在1997年遭遇格攻击[15]. 随后Hoffstein等人对方案安全性方面进行补救,并于1998年正式提出NTRU加密方案(NTRU-HPS)[11]. 该方案是第1个基于格困难问题构造的现实的公钥加密方案. NTRU相关问题目前已经是许多密码方案中的基础元件[16–18]. 在NIST的后量子密码方案征集项目中,基于NTRU格的方案具有举足轻重的地位. 具体而言,Falcon数字签名[19]基于NTRU格构造,且是NIST后量子密码方案标准征集拟标准化的数字签名之一. 另外,在NIST第3轮中,NTRU KEM[20] (包含NTRU-HRSS和NTRUEncrypt)是4个决赛KEM方案之一,NTRU Prime KEM[21](包含SNTRU Prime和NTRU LPRime)是5个候选方案之一. 尽管目前NIST选择了基于模格的Kyber[22]作为唯一的拟标准化KEM方案[2],而基于NTRU格的方案没能被NIST选为拟标准化KEM方案,但NIST官方报告声称如果Kyber相关专利问题未能得到很好地解决,仍可能会放弃Kyber而启用NTRU KEM[23]. 另外,在2011年NTRUEncrypt方案便已入选X9.98标准并应用于金融服务企业之中[24]. 自2022年4月起,国际标准OpenSSH更新了版本9.0之后,OpenSSH便采用了NTRU Prime KEM方案结合X25519 ECDH方案的混合模式,以抵抗“先捕获后解密”攻击[25]. 另外,有关基于NTRU格的方案的研究并不应因此而止步不前,对基于NTRU格的方案的设计和分析理应得到更充分、深入和全面的研究.
基于NTRU格设计的KEM备受青睐,主要原因有3点:1)基于NTRU格的KEM具有坚固的安全保障. 自NTRU被提出至今,有关NTRU的攻击和密码分析对基于NTRU格的KEM安全性产生的影响非常有限. 事实上,大多数基于NTRU相关困难问题设计的密码方案至今没被攻破. 2)有关NTRU的专利已失效. 在1997 年,NTRU 加密系统获得了专利,但在2017 年NTRU 相关核心专利已到期. 3)大多数基于NTRU格的KEM结构简单,便于实现,同时加解密算法的运算速度快[20-21].
近些年来,针对基于NTRU格的KEM有2点可优化的方向:
1)计算效率方面. 基于NTRU格的KEM如NTRU-HRSS[20]和SNTRU Prime[21]在计算效率方面逊色于基于{R,M}LWE的方案. 主要是因为后者能够使用高效的数论变换(number theoretic transform,NTT)来计算多项式乘法. 近些年来,文献[26-27]基于NTT友好的多项式环来构造出基于NTRU格的KEM,使得方案中的多项式运算得到高效计算.
2)密文尺寸方面. 降低密文尺寸对网络协议,如TLS和IoT资源受限设备通信都具有积极的作用. 尽管密文压缩在基于LWE及其变体的KEM中是一项成熟的技术,但对基于NTRU格的KEM来说,目前相关研究极少. 常见的NTRU的加密方案的密文形式一般为$ c = phr + m\text{mod} q $,其中$ h $为公钥(一般$ h = g/f $),$q $为方案模数,$g $、$f $为秘密多项式;$ r $为采样得到的秘密多项式,$ m $为待加密的明文,$ p $为明文空间模数. 这可视为$ m $通过编码到密文$ c $的低位. 解密算法将$ c $乘以私钥$ f $,得到$ cf\text{mod} q = pgr + mf $. 随后通过乘$ f $的逆,或当$ f = pf' + 1 $时可通过模$ p $消除杂项来恢复明文. 这种解密机制要求被消除的杂项为$ p $的倍数. 所以一旦密文$ c $被压缩,压缩带来的误差往往集中在$ c $的低位,从而破坏$ m $的有效信息,此时便无法正确解密得到原始的$ m $.
文献[28-29]对基于NTRU格的KEM的密文压缩进行了探索,但是文献[28-29]的方案有2点不足. 第1点不足是这些方案都基于2种困难性假设来构建KEM.其中文献[28]是基于NTRU假设[11]和RLWE假设[9],文献[29]是基于NTRU假设和RLWR假设[8]. 引入过多的困难性假设会导致方案建立在更理想化的假设上. 同时,分析这些方案的安全强度则需要分析2种困难性问题的安全强度,并取2个安全强度的最小值. 所以,方案的安全性很大程度上取决于安全强度更低的困难性问题.NTRU相关困难问题的安全性经过20多年的密码分析现今仍然安全;RLWE和RLWR是较之更新的问题而需要进一步密码分析和验证. 为得到更为稳定的安全保障,仅基于NTRU相关困难问题设计的KEM值得深入地研究和探索. 第2点不足是文献[28-29]的方案均使用纠错码和复杂的纠错机制来恢复明文信息. 其中文献[28]使用可尺度E8格纠错码;文献[29]使用改进的Babai算法. 尽管纠错码具有良好的纠错能力从而有效恢复信息,但是KEM使用纠错码会带来2个缺点:1)纠错码增加了方案遭遇侧信道攻击的风险[30],特别是计时攻击[31];2)纠错码导致实现更复杂、更耗时,且更容易出错. 为了设计更安全且便于实现的KEM,设计者应该避免使用纠错码. 所以,对基于NTRU格的KEM来说,在不使用纠错码的情况下,如何得到可压缩密文的构造依然需要进一步探索.
在我国,后量子密码被我国科协列为60个我国亟待解决的重大科技难题之一. 尽管我国2019年密码算法设计竞赛的获奖方案大多数是基于格构造的,且包含基于NTRU格的FatSeal签名[3],但是在它们之中并没有基于NTRU格的PKE和KEM.在当前国内外网络空间安全愈发重要的大背景下,我国研究团队理应自主研制高性能、多样化的后量子密码方案. 考虑到基于NTRU格的方案在国际上(特别是NIST后量子密码标准征集项目)的重要地位,本文主要关注基于NTRU格构造高效的PKE和KEM,并针对目前可优化方向,如计算效率方面和密文尺寸方面,提出一套基于NTRU格构造的可压缩密文的实用化公钥密码系统. 本文旨在为后续同类后量子密码方案的研究和优化提供重要参考. 同时,这方面的研究工作对我国未来的后量子密码标准的选拔、制定、推广和实际应用都具有重要的现实意义.
本文的贡献主要有4点:
1) 基于NTT友好环$ {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) $构造了一个基于NTRU格的可压缩密文的密钥封装方案LTRU. 该方案包含了IND-CPA安全的公钥加密方案LTRU. PKE和IND-CCA安全的密钥封装方案LTRU.KEM. 本文的LTRU仅基于NTRU单向困难性假设构建. LTRU能够避免引入过多假设,从而避免方案假设过强和过于理想化. 同时LTRU不使用纠错码,从而实现更简单,且降低了遭遇侧信道攻击的风险. 已知LTRU是第1个仅基于NTRU类型假设且不使用纠错码也能压缩密文的密钥封装方案.
2) 提供了针对128 b安全强度的LTRU参数集. 这使得LTRU不仅达到了目标安全强度(实际上达到129 b量子安全强度),还具有与安全性匹配的、可忽略的错误率($ {2^{ - 154}} $),同时通信带宽小于其他NTRU方案. 具体而言,与NIST第3轮决赛方案NTRU-HRSS相比,LTRU的经典安全强度和量子安全强度分别增强6 b和5 b,并且LTRU的公钥尺寸降低14.6%,密文尺寸降低26.0%,总带宽降低20.3%.
3) 提出了一种高效的混合基NTT算法. 该算法能够有效计算环$ {\mathbb{Z}_{2\;917}}[x]/({x^{648}} - {x^{324}} + 1) $上的多项式运算,利用3次单位根的性质来有效减少基-3 FFT trick步骤中一半的乘法数量,并利用1-迭代Karatsuba算法来有效减少点乘中的乘法数量. 通过具体实现的效率分析可知,跟未使用1-迭代Karatsuba算法和单位根的性质优化乘法数量的NTT算法相比,本文NTT在正向变换、点乘和逆向变换的CPU周期数分别降低24.9%,20.6%,26.8%,总共降低25.3%.
4) 提供LTRU的C实现和AVX2实现. 实验结果表明,与NTRU-HRSS的AVX2实现相比,LTRU在密钥生成和解封装算法上分别快了10.9倍和1.7倍,封装算法的速度则与NTRU-HRSS的速度相当.
近些年来,陆续有基于NTRU格的方案被提出. Stehlé等人[32]基于2次幂分圆环$ \mathbb{Z}[x]/({x^n} + 1) $(其中$ n $为2次幂)来设计基于NTRU变体的PKE,并证明了公钥的安全性. 随后,Wang等人[33]将该方案推广至任意的分圆环. 但是这2个方案因为公钥尺寸过大而无法应用于实际的场景中. Jarvis等人[34]将NTRU-HPS推广至Eisenstein整数环$ \mathbb{Z}[\omega ]/({x^n} - 1) $(其中$ \omega = \exp (2{\text{π i}}/3) $). 该方案在密钥尺寸和性能方面比NTRU-HPS更有优势.Hülsing等人[35]全面提升NTRU-HPS的密钥尺寸、密文尺寸和效率,并提出了NTRU-HRSS. NTRU-HRSS曾是NIST后量子方案征集项目第3轮决赛方案之一[20]. Bernstein等人[36]考虑到NTRU类型方案使用的多项式环或因丰富的代数结构而遭受相关攻击,提出了使用代数结构更少的环$ {\mathbb{Z}_q}[x]/({x^n} - x - 1) $的NTRU变体方案:NTRU Prime(其中$ n,q $均为素数). NTRU-prime曾是NIST后量子方案征集项目第3轮候选方案之一[20].
为了追求更高的实现效率,Lyubashevsky等人[26]在多项式环$ {\mathbb{Z}_{7681}}[x]/({x^{768}} - {x^{384}} + 1) $上构造了针对128 b安全强度的NTTRU方案. 随后,Duman等人[27]将该方案推广至更一般的$ n $并选择对应的$ q $. 但是这些方案均是遵循传统NTRU的框架,并不能对密文进行压缩.
Fouque等人[29]提出BAT方案. BAT与传统NTRU类型的KEM的构造有所区别,但与Falcon数字签名方案[19]有众多相似之处. BAT的私钥是一组陷门基,这一点与Falcon相似,但区别于其他NTRU类型KEM的私钥$ f $. 直观地理解,BAT使用的纠错码机制相当于对含有2个未知数的方程求解出秘密多项式和噪音多项式,并用来恢复明文. BAT通过将密文构造为RLWR实例的方式来降低密文的尺寸. 然而,为生成陷门基作为私钥,BAT的密钥生成算法速度比常见的NTRU类型KEM的速度慢约1000倍. 其次,为降低密文尺寸而构造的RLWR实例使用二元的秘密分布(即秘密多项式的系数选自{0,1}),而关于该问题的安全性目前还是公开问题且还需要进一步研究. 另外,BAT缺少匹配128 b安全强度的参数集,因为它使用2次幂分圆环$ \mathbb{Z}[x]/({x^n} + 1) $,且$ n = 512 $和$ n = 1\;024 $,而前者的安全强度略低于128 b,后者的安全强度则远高于128 b.
本节主要介绍一些符号说明、基本定义和密码原语等.
1) 本文记$ \mathbb{Z} $为整数环,$ n $和$ q $为某些整数. 定义集合$ {\mathbb{Z}_q} = \mathbb{Z}/q\mathbb{Z} \cong \{ 0,1, … ,q - 1\} $. 对于实数$ x \in \mathbb{R} $,符号$ \lfloor x \rceil $表示对$ x $四舍五入后的值. 本文主要使用分圆多项式环$ \mathcal{R}: = \mathbb{Z}[x]/({x^n} - {x^{n/2}} + 1) $及其商环$ {{\mathcal{R}}}_{q}:={\mathcal{R}}/q{\mathcal{R}}={\mathbb{Z}}_{q}[x]/ ({x}^{n}-{x}^{n/2}+1) $,其中$ n = {2^i}{3^j} $,$ i \geqslant 0 $,$ j > 1 $,且此时$ {x^n} - {x^{n/2}} + 1 $是$ 3n $阶分圆多项式. 环$ \mathcal{R} $(或$ {\mathcal{R}_q} $)中的元素均是多项式,本文使用符号$ f $的幂级数形式$ f = \displaystyle\sum\limits_{i = 0}^{n - 1} {{f_i}{x^i}} $,$ {f_i} \in \mathbb{Z} $(或$ {f_i} \in {\mathbb{Z}_q} $). 一个函数$ \varepsilon : \mathbb{N} \to [0,1] $是可忽略的,指的是对任意的正数$ c $以及充分大的$ \lambda $,$ \varepsilon (\lambda ) < 1/{\lambda ^c} $成立.
2) 模约减. 对于某正整数$ q $,符号$ r' = r\text{mod} q $表示$ r $落在$ [0,q) \cap \mathbb{Z} $中的代表元$ r' $. 符号$ r' = r{\text{mod} ^ \pm }q $表示$ r $落在$ \left[ - \dfrac{q}{2},\dfrac{q}{2}\right) \cap \mathbb{Z} $中的代表元$ r' $. 另外,符号$ r' \equiv $ $r\text{mod} q $表示$ r' $和$ r $模$ q $同余.
3) 元素的范数[37]. 对于元素$ v \in {\mathbb{Z}_q} $,定义它的$ {\ell _\infty } $范数$ {\left\| v \right\|_\infty } $为$ \left| {v{{\text{mod} }^ \pm }q} \right| $. 对于环$ \mathcal{R} $(或$ {\mathcal{R}_q} $)中的元素$ w $,它的$ {\ell _\infty } $范数为$ {\left\| w \right\|_\infty } = \mathop {\max }\limits_i {\left\| {{w_i}} \right\|_\infty } $.
4) 压缩函数和解压缩函数[37]. 对于正整数$ q $和$ d $,定义压缩函数
$ Compres{s}_{q}(x,d)=\left\lfloor \frac{{2}^{d}}{q}x\right\rceil\mathrm{mod}\;{2}^{d},\;x\in {\mathbb{Z}}_{q} \text{,} $
以及解压缩函数
$ Decompres{s}_{q}(y,d)=\left\lfloor\frac{q}{{2}^{d}}y\right\rceil\mathrm{mod}\;q,\;y\in {\mathbb{Z}}_{{2}^{d}} \text{,} $
且对于任意的$ x \in {\mathbb{Z}_q} $,有
$ {\Big\Vert x-Decompres{s}_{q}(Compres{s}_{q}(x,d),d)\Big\Vert }_{\infty }\le\left\lfloor \frac{q}{{2}^{d+1}} \right\rceil. $
5) 集合和分布. 对于集合$ D $,记$ x \leftarrow \$ D $表示从$ D $中均匀随机选取$ x $. 如果$ D $是一个概率分布,$ x \leftarrow D $表示根据分布$ D $采样得到$ x $. 本文主要使用的分布$ {\bar B_\eta } $为:采样$ ({a_1},{a_2}, … ,{a_\eta },{b_1},{b_2}, … ,{b_\eta }) $$ \leftarrow \$ {\{ 0,1\} ^{2\eta }} $,然后输出$ \left[ {\displaystyle\sum\limits_{i = 1}^\eta {({a_i} - {b_i})} } \right]{\text{mod} ^ \pm }3 $. 根据分布$ D $,采样多项式$ f $指的是$ f $的每一个系数均根据$ D $采样得到.
1) 公钥加密方案
一个公钥加密方案PKE包含KeyGen, Enc, Dec 3个概率多项式时间(probabilistic polynomial time,PPT)算法,记其明文空间为$ \mathcal{M} $. 密钥生成算法KeyGen输出公私钥对$ (pk,sk) $. 加密算法Enc输入公钥$ pk $和明文$ m \in \mathcal{M} $,输出密文$ ct $. 本文在必要时使用$ Enc(pk,m; coin) $显式表示加密算法使用的随机数为$ coin $. 确定性的解密算法Dec输入密文$ ct $和私钥$ sk $,输出$ m \in \mathcal{M} $,或者$ \bot $表示解密失败. 公钥加密方案的解密错误率$ \delta $定义为
$ E[\mathop {\max }\limits_{m \in \mathcal{M}} Pr[Dec(sk,Enc(pk,m)) \ne m]] < \delta , $
其中期望作用于$ (pk,sk) \leftarrow KeyGen $上,式(1)概率取自加密算法Enc使用的随机数. 一个公钥加密方案是抗原像恢复意义下的选择明文PRE-CPA(preimage resistance under chosen-plaintext attacks)安全的[27],指的是对于任意PPT敌手$ \mathcal{A} $,其优势是可忽略的:
$ Adv_{{\text{PKE}}}^{{\text{PRE - CPA}}}(\mathcal{A}) = Pr\left[ {c = c^*:\begin{array}{*{20}{c}}{(pk,sk) \leftarrow KeyGen;} \\ {m^* \leftarrow \$ \mathcal{M};} \\ {c^* \leftarrow Enc(pk,m^*);} \\ {(m,coin) \leftarrow \mathcal{A}(pk,c^*);} \\ {c: = Enc(pk,m;coin)} \end{array}} \right] . $
一个公钥加密方案是不可区分意义下的选择明文IND-CPA(indistinguishability under chosen-plaintext attacks)安全的,指的是对于任意PPT敌手$ \mathcal{A} $,其优势是可忽略的:
$\begin{split} &Adv_{{\text{PKE}}}^{{\text{IND - CPA}}}(\mathcal{A}) = \\&\quad\left| {Pr\left[ {b' = b:\begin{array}{*{20}{c}}{(pk,sk) \leftarrow KeyGen;} \\ {({m_0},{m_1},s) \leftarrow \mathcal{A}(pk);} \\ {b \leftarrow \$ \{ 0,1\} ;c^* \leftarrow Enc(pk,{m_b});} \\ {b' \leftarrow \mathcal{A}(s,c^*)} \end{array}} \right] - \frac{1}{2}} \right| . \end{split}$
2) 密钥封装方案
一个密钥封装方案KEM包含KeyGen, Encaps, Decaps 3个PPT算法. 记其导出密钥空间为$ \mathcal{K} $. 密钥生成算法KeyGen输出公私钥对$ (pk,sk) $. 密钥封装算法Encaps输入公钥$ pk $,输出密文$ ct $和密钥$ K \in \mathcal{K} $. 确定性的解封装算法Decaps输入密文$ ct $和私钥$ sk $,输出$ K \in \mathcal{K} $,或者$ \bot $表示解封装失败. 密钥封装方案的错误率$ \delta $定义为
$ Pr\left[ {Decaps(sk,ct) \ne K:(ct,K) \leftarrow Encaps(pk)} \right] < \delta \text{,} $
其中概率取自$ (pk,sk) \leftarrow KeyGen $和封装算法Encaps使用的随机数. 一个密钥封装方案是不可区分意义下的选择密文IND-CCA(indistinguishability under chosen-ciphertext attacks)安全的,指的是对于任意PPT敌手$ \mathcal{A} $,其优势是可忽略的:
$ \begin{split}&Adv_{{\text{KEM}}}^{{\text{IND - CCA}}}(\mathcal{A}) = \\&\quad\left| {Pr\left[ {b' = b:\begin{array}{*{20}{c}}{(pk,sk) \leftarrow KeyGen;} \\ {b \leftarrow \$ \{ 0,1\} ;} \\ {(c^*,K_0^*) \leftarrow Encaps(pk);} \\ {K_1^* \leftarrow \$ \mathcal{K};} \\ {b' \leftarrow {\mathcal{A}^{Decaps( \cdot )}}(pk,c^*,K_b^*)} \end{array}} \right] - \frac{1}{2}} \right| . \end{split}$
定义1. NTRU单向困难性假设[12-13]. 给定NTRU公钥加密方案的公钥$ h $以及PPT加密算法Enc,则NTRU单向函数是指
$ \begin{split}&Enc:{\mathcal{L}_r} \times {\mathcal{L}_e} \to {\mathcal{L}_c}, \\ &(r,e) \mapsto c = Enc(h,(r,e)), \\ \end{split} $
其中$ Enc(h,(r,e)) $指的是以$ h $,$ e $,$ r $作为加密算法的输入,在NTRU公钥加密方案中$ {\mathcal{L}_e} $一般是它的明文空间,$ {\mathcal{L}_r} $一般是它的随机数空间.
NTRU单向问题NTRU-OW(NTRU one-wayness)指的是给定公钥$ h $和密文多项式$ c $,计算得到$ (r,e) $. NTRU单向问题是困难的,指的是对于任意PPT敌手$ \mathcal{A} $,其优势是可忽略的:
$ \begin{split} &Ad{v^{{\text{NTRU - OW}}}}(\mathcal{A}) = \\&\quad\left| {Pr\left[ {Enc(pk,(r,e)) = c^*:\begin{array}{*{20}{c}}{(pk,sk) \leftarrow KeyGen;} \\ {(r^*,e^*) \leftarrow {\mathcal{L}_r} \times {\mathcal{L}_e};} \\ {c^*: = Enc(pk,(r^*,e^*));} \\ {(r,e) \leftarrow \mathcal{A}(pk,c^*)} \end{array}} \right]} \right| .\end{split} $
通俗来讲,NTRU单向困难性假设是指没有PPT敌手能够从公钥$ h $和密文$ c $中恢复出$ (r,e) $. 原始的NTRU-HPS方案[11]便蕴含了NTRU单向困难性假设,直到文献[12-13]将NTRU单向困难性假设提炼出来,并应用在基于NTRU格的方案(如NAEP方案)的安全性证明之中.
定义2. ACWC0转换[27]. 记PKE1=(KeyGen1, Enc1, Dec1)为公钥加密方案,其明文空间记为$ {\mathcal{M}_1} $. 令$ {\mathcal{F}}: {\{0,1\}}^{*}\to {\{0,1\}}^{\lambda } $为哈希函数,$ \lambda $为某正整数.ACWC0通过算法1~3将PKE1=(KeyGen1, Enc1, Dec1)转换得到另一个公钥加密方案PKE2=(KeyGen2, Enc2, Dec2),其明文空间为$ {\mathcal{M}_2} = {\{ 0,1\} ^\lambda } $.
算法1. 密钥生成算法KeyGen2.
输入:安全参数$ \kappa $;
输出:公私钥对$ (pk,sk) $.
① $ (pk,sk) \leftarrow KeyGe{n_1} $.
算法2. 加密算法Enc2.
输入:公钥$ pk $,明文$ m \in {\mathcal{M}_2} $;
输出:密文$ ct: = (c,u) $.
① $ m' \leftarrow \$ {\mathcal{M}_1} $;
② $ c: = En{c_1}(pk,m') $;
③ $ u: = \mathcal{F}(m') \oplus m $.
算法3. 解密算法Dec2.
输入:私钥$ sk $,密文$ ct = (c,u) $;
输出:明文$ m \in {\mathcal{M}_2} $.
① $ m': = De{c_1}(sk,c) $;
② $ m: = \mathcal{F}(m') \oplus u $.
根据文献[27]中的引理2.2和定理3.3,PKE2方案在随机预言机模型(random oracle model,ROM)[38]下的IND-CPA安全性由定理1给出.
定理1. 在随机预言机模型下,对于任意的攻击PKE2的IND-CPA安全性的敌手$ \mathcal{A} $,存在攻击PKE1的PRE-CPA安全性的敌手$ \mathcal{B} $,其运行时间与$ \mathcal{A} $相当,使得
$ Adv_{{{PK}}{{{E}}_2}}^{{\text{IND - CPA}}}(\mathcal{A}) \leqslant Adv_{{{PK}}{{{E}}_1}}^{{\text{PRE - CPA}}}(\mathcal{B}) . $
另外,根据文献[27]中的引理2.2和定理3.4,可得定理2关于PKE2方案在量子随机预言机模型(quantum random oracle model,QROM)[39]下的IND-CPA安全性.
定理2. 在量子随机预言机模型下,对于任意的攻击PKE2的IND-CPA安全性的量子敌手$ \mathcal{A} $,存在攻击PKE1的PRE-CPA安全性的量子敌手$ \mathcal{B} $,其运行时间与$ \mathcal{A} $相当,使得
$ Adv_{{{PK}}{{{E}}_2}}^{{\text{IND - CPA}}}(\mathcal{A}) \leqslant 2{d_\mathcal{F}}\sqrt {Adv_{{{PK}}{{{E}}_1}}^{{\text{PRE - CPA}}}(\mathcal{B})} \text{,} $
其中$ {d_\mathcal{F}} $是$ \mathcal{A} $查询$ \mathcal{F} $的深度.
可见,ACWC0转换能够将一个PRE-CPA安全的公钥加密方案转换得到另一个IND-CPA安全的公钥加密方案. 本文将在3.1节中提出的公钥加密方案便是通过ACWC0转换得到的.
NTT是快速傅里叶变换(fast Fourier transform,FFT)在有限域上的特殊形式.NTT是计算高次多项式乘法最高效的算法,其复杂度为$ O(n\log n) $,其中$ n $为被乘多项式的维度. 简单地说,基于NTT计算多项式乘法$ h = fg $的过程为$ h = \mathcal{I}\mathcal{N}\mathcal{T}\mathcal{T}(\mathcal{N}\mathcal{T}\mathcal{T}(f) \circ \mathcal{N}\mathcal{T}\mathcal{T}(g)) $,其中$ \mathcal{N}\mathcal{T}\mathcal{T} $表示正向变换,$ \mathcal{I}\mathcal{N}\mathcal{T}\mathcal{T} $表示逆向变换,“$ \circ $”表示点乘. 本文沿用文献[40]有关多项式乘法的符号和术语,FFT trick是计算NTT的一种快速算法,其计算过程本质是基于多项式环形式的中国剩余定理(Chinese remainder theorem,CRT),即给定两两互素的多项式$ {g_1},{g_2}, … ,{g_k} $,有CRT同构
$ \varphi :{\mathbb{Z}_q}[x]/({g_1}{g_2} \cdots {g_k}) \cong \prod\limits_{i = 1}^k {{\mathbb{Z}_q}[x]/({g_i})} , $
并且$ \varphi (f) = (f\text{mod} {g_1},f\text{mod} {g_2}, … ,f\text{mod} {g_k}) $. 记$ \zeta $在$ {\mathbb{Z}_q} $中可逆. 对于经典的基-2 FFT trick的情况,有CRT同构:
$ {\mathbb{Z}_q}[x]/({x^{2m}} - {\zeta ^2}) \cong {\mathbb{Z}_q}[x]/({x^m} - \zeta ) \times {\mathbb{Z}_q}[x]/({x^m} + \zeta ) . $
正向FFT trick基于CT (Cooley-Tukey)蝴蝶操作[41]从$ ({f_i},{f_j}) $得到$ ({f_i} + \zeta {f_j},{f_i} - \zeta {f_j}) $,而逆向FFT trick基于GS (Gentleman-Sande)蝴蝶操作[42]从$ ({f_i}^\prime ,{f_j}^\prime ) $得到$ (({f_i}^\prime + {f_j}^\prime) , ({f_i}^\prime - {f_j}^\prime ){\zeta ^{ - 1}}) $. 对于经典的基-3 FFT trick,有CRT同构:
$ \begin{split}{\mathbb{Z}_q}[x]/({x^{3m}} - {\zeta ^3}) \cong& {\mathbb{Z}_q}[x]/({x^m} - \zeta ) \times {\mathbb{Z}_q}[x]/({x^m} - \rho \zeta ) \times \\&{\mathbb{Z}_q}[x]/({x^m} - {\rho ^2}\zeta ), \\ \end{split} $
其中$ \rho $是3次单位根. 混合基NTT指的是在计算NTT过程含有多种FFT trick.
定义3. 1-迭代Karatsuba算法[43]. 设$ a,b,c,d $为某些数或多项式.1-迭代Karatsuba算法指的是为了计算$ {t_1} = ac $,$ {t_2} = ad + bc $和$ {t_3} = bd $,可以先计算$ {t_1} $和$ {t_3} $,然后通过$ {t_2} = (a + b)(c + d) - {t_1} - {t_3} $计算$ {t_2} $. 该算法能在增加3个加(减)法的代价上,减少1个乘法.
下面介绍本文提出的基于NTRU格构造的可压缩密文的密钥封装方案LTRU. LTRU包括一个IND-CPA安全的公钥加密方案LTRU.PKE,以及一个IND-CCA安全的密钥封装方案LTRU.KEM,其中该KEM通过FO (Fujisaki-Okamoto)转换[44-45]得到. LTRU.PKE是由底层公钥加密方案$ {{PKE}}'$=(KeyGen, $ Enc' $, $ Dec' $)结合文献[27]的ACWC0转换得到的. 底层公钥加密方案$ {{PKE}}' $将在3.4节中展示,但它只能满足PRE-CPA安全性,并且目前还没有相关文献论证FO转换将PRE-CPA安全的公钥加密方案转换得到IND-CCA安全的KEM的规约上界. 本文通过增加ACWC0转换,将底层公钥加密方案$ {{PKE}}' $转换得到IND-CPA安全的LTRU.PKE,然后便能通过FO转换得到IND-CCA安全的KEM.
LTRU.PKE的具体构造见算法4~6.记其明文空间为$ \mathcal{M} = {\{ 0,1\} ^\lambda } $,其中$ \lambda $为正整数. 记多项式环为$ {\mathcal{R}_q} = {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) $,其中$ n $和$ q $是环参数. 记$ d $和$ p $为正整数,且$ p $和$ q $互素. 需要说明的是,在算法4~6中,为了给出一般的构造框架,本文使用的分布$ \psi $泛指$ \mathcal{R} $上的某分布,但事实上,在3.3节的具体参数选择方面,本文实例化$ \psi $为参数$ \eta {\text{ = }}2 $的$ {\bar B_\eta } $分布(定义见2.1节). 令$ {\mathcal{F}}:{\{0,1\}}^{*}\to {\{0,1\}}^{\lambda } $为哈希函数. 本文主要考虑$ p = 2 $以及$ \lambda = 256 $的情况. 可视$ {\{ 0,1\} ^n} $中的元素是维度为$ n $、系数为0或1的多项式. 压缩函数Compress和解压缩函数Decompress的具体计算过程见2.1节.
算法4. 密钥生成算法LTRU.PKE.KeyGen.
输入:安全参数$ \kappa $;
输出:公私钥对$ (pk,sk) $.
① repeat
② $ f',g \leftarrow \psi $;
③ $ f: = pf' + 1 $;
④ until $ {f^{ - 1}} $ exists in $ {\mathcal{R}_q} $;
⑤ $ h: = g/f $;
⑥ $ pk: = h $,$ sk: = f $.
算法5. 加密算法LTRU.PKE.Enc.
输入:公钥$ pk $,明文$ m \in \mathcal{M} $;
输出:密文$ ct: = (c,u) $.
① $ r \leftarrow \psi $,$ e \leftarrow \$ {\{ 0,1\} ^n} $;
② $ c:=Compres{s}_{q}(hr+\left\lfloor\dfrac{q}{2}\right\rceil e,d) $;
③ $ u: = m \oplus \mathcal{F}(e) $;
④ $ ct: = (c,u) $.
算法6. 解密算法LTRU.PKE.Dec.
输入:私钥$ sk $,密文$ ct: = (c,u) $;
输出:明文$ m \in \mathcal{M} $.
① $ c': = Decompres{s_q}(c,d) $;
② $ e': = Compres{s_q}(c'f{\text{mod} ^ \pm }q,1) $;
③ $ m: = u \oplus \mathcal{F}(e') $.
可见,LTRU.PKE应用了ACWC0转换[27],见算法5行③以及算法6行③. LTRU.KEM是由LTRU.PKE通过$ {\text{FO}}_m^ \bot $转换得到,其中$ {\text{FO}}_m^ \bot $是文献[45]提出的FO转换的一个变体. LTRU.KEM的密钥生成算法KeyGen与LTRU.PKE的KeyGen相同. LTRU.KEM的封装算法和解封装算法分别见算法7和算法8.记$ \mathcal{K} $为LTRU.KEM的导出密钥空间,为方便起见,本文令$ \mathcal{K} = {\{ 0,1\} ^{256}} $. 记$ \mathcal{C}\mathcal{O}\mathcal{I}\mathcal{N}\mathcal{S} $为LTRU公钥加密方案中加密算法所使用的随机数空间. 记$ \mathcal{H}:{\{ 0,1\} ^*} \to \mathcal{K} \times \mathcal{C}\mathcal{O}\mathcal{I}\mathcal{N}\mathcal{S} $为哈希函数. 实际上,$ \mathcal{H} $能够拆分为2部分${\mathcal{H}_1} $和${\mathcal{H}_2} $,记$ {\mathcal{H}_1} $为$ \mathcal{H} $映射到$ \mathcal{C}\mathcal{O}\mathcal{I}\mathcal{N}\mathcal{S} $的部分,$ {\mathcal{H}_2} $为$ \mathcal{H} $映射到$ \mathcal{K} $的部分. 在算法7的行②中可以先使用$ {\mathcal{H}_1} $生成$ coin $,在行③中计算得到密文$ c $之后,再使用$ {\mathcal{H}_2} $生成共享密钥$ K $.
算法7. 封装算法LTRU.KEM.Encaps.
输入:公钥$ pk $;
输出:密钥$ K $,密文$ c $.
① $ m \leftarrow \$ \mathcal{M} $;
② $ (K,coin): = \mathcal{H}(m) $;
③ $ c: = LTRU.PKE.Enc(pk,m;coin) $.
算法8. 解封装算法LTRU.KEM.Decaps.
输入:私钥$ sk $,密文$ c $;
输出:密钥$ K $.
① $ m': = LTRU.PKE.Dec(sk,c) $;
② $ (K',coin'): = \mathcal{H}(m') $;
③ if $ c = LTRU.PKE.Enc(pk,m';coin') $and $ m' \ne \bot $
④ return $ K' $;
⑤ else
⑥ return $ \bot $;
⑦ end if
定理3. 对于$ \mathcal{R} $上的分布$ \psi $、正整数$ d $和$ q $,令$ f' $,$ g $,$ r $$ \leftarrow \psi $,以及$ \varepsilon \leftarrow $$\chi $,其中$ \chi $为$ \mathcal{R} $上的分布且定义为:采样$ h \leftarrow \$ {\mathcal{R}_q} $,$ r \leftarrow \psi $,$ e \leftarrow \$ {\{ 0,1\} ^n} $,输出$ \left(\left\lfloor\dfrac{q}{{2}^{d}}\left\lfloor\dfrac{{2}^{d}}{q}Z\right\rceil\right\rceil-Z\right) {\mathrm{mod}}^{\pm }q $,其中$ Z=hr+\left\lfloor\dfrac{q}{2}\right\rceil e $. 记
$ 1 - \delta = Pr\left[ {{{\left\| {gr + \left(\frac{e}{2} + \varepsilon \right)f} \right\|}_\infty } < \frac{q}{4}} \right] \text{,} $
则LTRU的错误率为$ \delta $.
证明.
从2.1节的压缩函数Compress和解压缩函数Decompress的定义可知,算法6行①的$ c' $可以表示为
$ c' = Decompres{s_q}(Compres{s_q}(Z,d),d)= Z + \varepsilon , \\ $
其中$ Z=hr+\left\lfloor\dfrac{q}{2}\right\rceil e $,$ \varepsilon \in \mathcal{R} $. 所以,算法6行②的$ e' $为
$ \begin{split} e^{\prime }=& Compres{s}_{q}({c}^{\prime }f{\mathrm{mod}}^{\pm }q,1)=\\& \left\lfloor\dfrac{2}{q}[(Z+\varepsilon )f{\mathrm{mod}}^{\pm }q]\right\rceil\mathrm{mod}\;2=\\& \left\lfloor\dfrac{2}{q}\left[\left(hr+\dfrac{q+1}{2}e+\varepsilon \right)f{\mathrm{mod}}^{\pm }q\right]\right\rceil\mathrm{mod}\;2.\end{split} $
由于LTRU中$ h = g/f $和$ f = 2f' + 1 $,则可得
$ \begin{split}{e}^{\prime }=&\dfrac{2}{q}\left\lfloor\left[\left(hrf+\dfrac{q}{2}ef+\dfrac{1}{2}ef+\varepsilon f\right){\mathrm{mod}}^{\pm }q\right]\right\rceil\mathrm{mod}\;2 =\\&\left\lfloor\dfrac{2}{q}\left[hrf+\dfrac{q}{2}e(2{f}^{\prime }+1)+\dfrac{1}{2}ef+\varepsilon f{\mathrm{mod}}^{\pm }q\right]\right\rceil\mathrm{mod}\;2 =\\&\left\lfloor e+\dfrac{2}{q}\left(gr+\dfrac{1}{2}ef+\varepsilon f\right)\right\rceil\mathrm{mod}2.\end{split} $
于是,当$ {\left\| {\dfrac{2}{q}\left(gr + \dfrac{1}{2}ef + \varepsilon f\right)} \right\|_\infty } < \dfrac{1}{2} $时,可得$ e' = e $恒成立,继而解密算法能够成功解密以及解封装算法能够正确地解封装. 等价地,正确解密的条件为
$ {\left\| {gr + (\frac{e}{2} + \varepsilon )f} \right\|_\infty } < \frac{q}{4} . $
证毕.
本文计算错误率的方法论和Python脚本源自文献[22, 26, 37]. 值得注意的是,文献[26]将环$ \mathbb{Z}[x]/({x^n} - {x^{n/2}} + 1) $上的多项式的乘积的系数视为由$ n/2 $个形如$ ab + b'(a + a') $的元组构成,其中$ a,\;a',\;b,\;b' $的分布由被乘多项式的分布决定. 尽管该环上的多项式的乘积另外还包含形如$ ab + a'b' $的元组,文献[26]建议全部使用$ ab + b'(a + a') $的形式,因为该形式具有更宽泛的分布,且能得到更保守估计的错误率结果.
本节给出LTRU的推荐参数集,其主要针对128 b安全强度,如表1所示. $ {\mathcal{R}_q} $是多项式环,维数$ n $和模数$ q $是环参数. 本文选择NTT友好的$ q $,旨在$q $允许在$ {\mathcal{R}_q} $上执行高效的多项式乘法和除法,具体细节见第4节. $ p $是明文空间模数;$ d $是压缩参数;$ \psi $是概率分布,本文主要考虑分布$ {\bar B_2} $,即参数为$ \eta {\text{ = }}2 $的$ {\bar B_\eta } $分布,$ {\bar B_\eta } $的定义见2.1节;|pk|,|ct|,B.W.分别是公钥尺寸、密文尺寸和带宽(公钥尺寸+密文尺寸),单位均为B;Sec-(C, Q)是该参数集的NTRU安全强度(单位为b),C表示经典安全强度,Q表示量子安全强度,安全强度的分析见3.5节;$ \delta $是该参数集的错误率,其细节见3.2节.
下面将基于NTRU单向困难性假设,证明LTRU.PKE是IND-CPA安全的.
定理4. IND-CPA安全性. 对于任意的概率多项式时间敌手$ \mathcal{A} $,存在概率多项式时间敌手$ \mathcal{B} $,其运行时间与$ \mathcal{A} $相当,使得:
1) $ Adv_{{\text{LTRU}}{\text{.PKE}}}^{{\text{IND - CPA}}}(\mathcal{A}) \leqslant Ad{v^{{\text{NTRU - OW}}}}(\mathcal{B}) $,其中$ \mathcal{A} $为经典敌手,哈希函数$ \mathcal{F} $被建模为经典随机预言机;
2) $ Adv_{{\text{LTRU}}{\text{.PKE}}}^{{\text{IND - CPA}}}(\mathcal{A}) \leqslant 2{d_\mathcal{F}}\sqrt {Ad{v^{{\text{NTRU - OW}}}}(\mathcal{B})} $,其中$ \mathcal{A} $为量子敌手,哈希函数$ \mathcal{F} $被建模为量子随机预言机,且$ {d_\mathcal{F}} $为$ \mathcal{A} $查询$ \mathcal{F} $的深度.
证明. LTRU.PKE方案由底层公钥加密方案$ {{PKE}} '$=(KeyGen,$ Enc' $,$ Dec' $)结合文献[27]的ACWC0转换得到,其中底层公钥加密方案$ {{PKE}} '$的KeyGen算法与LTRU.PKE方案的一致,$ Enc' $算法和$ Dec' $算法分别见算法9和算法10.
算法9. 加密算法$ PKE' .Enc' $.
输入:公钥$ pk $,明文$ e \in {\{ 0,1\} ^n} $;
输出:密文$ c $.
① $ r \leftarrow \psi $;
② $ c:=Compres{s}_{q}(hr+\left\lfloor\dfrac{q}{2} \right\rceil e,d) $.
算法10. 解密算法$ PKE' .Dec' $.
输入:私钥$ sk $,密文$ c $;
输出:明文$ e' $.
① $ c': = Decompres{s_q}(c,d) $;
② $ e': = Compres{s_q}(c'f{\text{mod} ^ \pm }q,1) $.
由定理1和定理2可知,当底层公钥加密方案$ {{PKE}} '$满足PRE-CPA安全性时,经过ACWC0转换得到的LTRU.PKE方案满足IND-CPA安全性. 下面将通过Game-Hopping技术[46]来证明底层公钥加密方案$ {{PKE}} '$的PRE-CPA安全性.
记$ \mathcal{A} $是攻击$ {{PKE}} '$方案的PRE-CPA安全性的概率多项式时间敌手. 考虑游戏$ {G_0} $和$ {G_1} $. 记事件$ Suc{c_i} $为敌手$ \mathcal{A} $在游戏$ {G_i} $中获胜,即游戏$ {G_i} $的输出满足$ c = c^* $.
1)游戏$ {G_0} $
① repeat
②  $ f',g \leftarrow \psi $;
③  $ f: = pf' + 1 $;
④ until $ {f^{ - 1}} $ exists in$ {\mathcal{R}_q} $;
⑤ $ h: = g/f $;
⑥ $ r^* \leftarrow \psi $,$ e^* \leftarrow \$ {\{ 0,1\} ^n} $;
⑦ $ c^*:=Compres{s}_{q}\left(hr^*+\left\lfloor\dfrac{q}{2}\right\rceil e^*,d\right) $;
⑧ $ (e,r) \leftarrow \mathcal{A}(pk,c^*) $;
⑨ $ c:=Enc'(pk,e;r)=Compres{s}_{q}\left(hr+\left\lfloor\dfrac{q}{2}\right\rceil e,d\right) $;
⑩ if $ c = c^* $ then
⑪  return 1;
⑫ else
⑬  return 0;
⑭ end if
游戏$ {G_0} $是关于$ {{PKE}} '$方案原始的PRE-CPA游戏. 根据PRE-CPA安全性的定义,可知
$ Adv_{{\text{PKE'}}}^{{\text{PRE - CPA}}}(\mathcal{A}) = Pr[Suc{c_0}] . $
2)游戏$ {G_1} $
① repeat
②  $ f',g \leftarrow \psi $;
③   $ f: = pf' + 1 $;
④ until $ {f^{ - 1}} $ exists in $ {\mathcal{R}_q} $;
⑤ $ h: = g/f $;
⑥ $ r^* \leftarrow \psi $,$ e^* \leftarrow \$ {\{ 0,1\} ^n} $;
⑦ $ c^*:=hr^*+\left\lfloor\dfrac{q}{2}\right\rceil e^* $;
⑧ $ (e,r) \leftarrow \mathcal{A}(pk,c^*) $;
⑨ $ c:=Enc'(pk,e;r)=hr+\left\lfloor\dfrac{q}{2}\right\rceil e $;
⑩ if $ c = c^* $ then
⑪  return 1;
⑫ else
⑬  return 0;
⑭ end if
游戏$ {G_1} $是在游戏$ {G_0} $的基础上,取消对行⑦挑战密文$ c^* $的压缩操作. 所以,敌手$ \mathcal{A} $在游戏$ {G_1} $中拥有的挑战密文的信息至少比在游戏$ {G_0} $中的多. 可见,游戏$ {G_0} $的困难性至少与游戏$ {G_1} $的相同,则
$ Pr[Suc{c_0}] \leqslant Pr[Suc{c_1}] . $
如果存在一个概率多项式时间敌手$ \mathcal{A} $赢得游戏$ {G_1} $,则可以构造一个概率多项式时间敌手$ \mathcal{B} $解决NTRU单向困难性问题. 具体地,运行游戏$ {G_1} $中的行①~⑦,将得到的$ h $和$ c^* $给敌手$ \mathcal{B} $. 则敌手$ \mathcal{B} $的目标是在给定公钥$ h $和挑战密文$ c^* $的情况下输出一对$ (e,r) $,使得$ c^*=En{c}^{\prime }(pk,(e,r))=hr+\left\lfloor\dfrac{q}{2}\right\rceil e $成立. 敌手$ \mathcal{B} $将$ h $和$ c^* $作为$ \mathcal{A} $的输入并运行$ \mathcal{A} $. 敌手$ \mathcal{A} $输出一对$ (e,r) $,然后敌手$ \mathcal{B} $以$ (e,r) $作为自己的输出. 可见,敌手$ \mathcal{B} $完美模拟了游戏$ {G_1} $. 如果发生事件$ Suc{c_1} $,说明敌手$ \mathcal{A} $输出的$ (e,r) $能够使得$ c^*=hr+\left\lfloor\dfrac{q}{2}\right\rceil e $成立,即敌手$ \mathcal{A} $赢得游戏$ {G_1} $. 于是敌手$ \mathcal{B} $以该$ (e,r) $作为输出能够成功求解NTRU单向困难性问题. 否则,如果不发生事件$ Suc{c_1} $,说明敌手$ \mathcal{A} $输出的$ (e,r) $不能让$ c^*=hr+\left\lfloor\dfrac{q}{2}\right\rceil e $成立. 于是,敌手$ \mathcal{B} $以该$ (e,r) $作为输出,不能成功求解NTRU单向困难性问题. 所以,敌手$ \mathcal{A} $赢得游戏$ {G_1} $的优势等于敌手$ \mathcal{B} $求解该NTRU单向困难性问题的优势,即
$ Pr[Suc{c_1}] = Ad{v^{{\text{NTRU - OW}}}}(\mathcal{B}) . $
整合游戏$ {G_0} $和$ {G_1} $中的概率可知,对于概率多项式时间敌手$ \mathcal{A} $,存在概率多项式时间敌手$ \mathcal{B} $,使得
$ Adv_{{{PKE'}}}^{{\text{PRE - CPA}}}(\mathcal{A}) = Pr[Suc{c_0}] \leqslant Pr[Suc{c_1}] \leqslant Ad{v^{{\text{NTRU - OW}}}}(\mathcal{B}). $
再根据定理1和定理2,由$ {{PKE}} '$方案的PRE-CPA安全性可得到LTRU.PKE的IND-CPA安全性,其对应的规约上界正如定理4所示. 综上,命题得证. 证毕.
从定理4可知,若NTRU单向困难性问题是困难的,那么LTRU.PKE是IND-CPA安全的. 由于LTRU.KEM是从IND-CPA安全的LTRU.PKE通过$ {\text{FO}}_m^ \bot $变换得到,根据文献[45, 47],LTRU.KEM在经典随机预言机和量子随机预言机下的IND-CCA安全性由定理5给出.
定理5. IND-CCA安全性[45,47]. 在记$ \gamma $和$ \delta $分别是LTRU.PKE的弱spread参数[45,47]和解密错误率. 对于任意攻击LTRU.KEM的 IND-CCA安全性的概率多项式时间敌手$ \mathcal{A} $,存在攻击LTRU.PKE的IND-CPA安全性的概率多项式时间敌手$ \mathcal{B} $,使得:
1) 在经典随机预言机模型下,将$ \mathcal{H} $建模为经典随机预言机,$ \mathcal{A} $查询至多$ {q_\mathcal{H}} $次$ \mathcal{H} $,查询至多$ {q_{\text{D}}} $次解封装预言机,$ \mathcal{B} $的运行时间和$ \mathcal{A} $的相当,则有
$Adv_{{\text{LTRU}}{\text{.KEM}}}^{{\text{IND - CCA}}}(\mathcal{A}) \leqslant 2\left( {Adv_{{\text{LTRU}}{\text{.PKE}}}^{{\text{IND - CPA}}}(\mathcal{B}){\text{ + }}\dfrac{{{q_\mathcal{H}}}}{{|\mathcal{M}|}}} \right) + \dfrac{{{q_{\text{D}}}}}{{{2^\gamma }}} + {q_\mathcal{H}}\delta . $
2)在量子随机预言机模型下,$ \mathcal{A} $和$ \mathcal{B} $为量子敌手,且将$ \mathcal{H} $建模为量子随机预言机,$ \mathcal{A} $以量子方式查询至多$ {q_\mathcal{H}} $次$ \mathcal{H} $,以经典方式查询至多$ {q_{\text{D}}} $次解封装预言机,则有
$ \begin{gathered}Adv_{{\text{LTRU}}{\text{.KEM}}}^{{\text{IND - CCA}}}(\mathcal{A}) \leqslant {\text{2}}{q_{\text{T}}}\sqrt {Adv_{{\text{LTRU}}{\text{.PKE}}}^{{\text{IND - CPA}}}(\mathcal{B})} + 24q_{\text{T}}^2\sqrt \delta {\text{ + }}\\\quad24{q_{\text{T}}}\sqrt {{q_{\text{T}}}{q_{\text{D}}}} \times {2^{{{ - }}\gamma /4}}, \\ \end{gathered} $
其中$ {q_{\text{T}}}: = 2({q_\mathcal{H}} + {q_{\text{D}}}) $,并且
$ Time(\mathcal{B}) \approx Time(\mathcal{A}) + O({q_\mathcal{H}}{q_{\text{D}}}Time(LTRU.PKE.Enc) + q_{\text{T}}^2). $
对于基于NTRU格构造的KEM来说,格攻击是目前最有效的攻击. 本节主要从常用的格攻击来分析LTRU的安全强度.
1) NTRU格
起初,基于NTRU格构造的方案均是依赖于多项式环上的困难性问题. 然而,Coppersmith等人[15]提出针对基于NTRU格构造方案的格攻击,它的核心思想是构造NTRU格. 本文方案的公钥对应的NTRU格$ \mathcal{L}({\boldsymbol B}) \subset {\mathbb{Z}^{2n}} $的基矩阵为
$ {\boldsymbol{B }}= \left( {\begin{array}{*{20}{c}}{q{{\boldsymbol{I}}_n}}&{{\boldsymbol{Rot}}(h)} \\ {\boldsymbol{0}}&{{{\boldsymbol{I}}_n}} \end{array}} \right) \text{,} $
其中$ {{\boldsymbol{I}}_n} $是$ n $维单位矩阵,$ {\boldsymbol{Rot}}(h) $是$ h $的循环移位矩阵,即它的第$ i $行向量对应$ {x^i}h\text{mod} {x^n} - {x^{n/2}} + 1 $. 文献[15]提出,秘密$ (f,g) $及其循环移位向量是格$ \mathcal{L}({\boldsymbol B}) $的最短向量. 事实上,NTRU类型方案的格攻击流程为:通过格基约化算法求解格$ \mathcal{L}({\boldsymbol B}) $的唯一最短向量问题(unique-short vector problem,u-SVP),找到该最短向量之后转化得到方案的私钥[15].
2) 原始攻击
原始攻击通过构造一个整数嵌入格,如Kannan嵌入[48]和Bai-Galbraith嵌入[49]等来求解u-SVP问题. 目前主要的格基约化算法为BKZ算法[50-51]. 给定格$ \mathcal{L}({\boldsymbol B}) $的一组基,BKZ算法运行时将格划分为多个低维度格,并把这些低维度格的维度记为$ b $. 然后在$ b $维格中求解最短向量问题(short vector problem,SVP),所使用的方法有筛法和枚举. 根据文献[52]的core-SVP方法论,对于$ b $维格上求解SVP问题,目前最优的经典算法的复杂度为$ {2^{0.292b}} $,最优的量子算法的复杂度为$ {2^{0.265b}} $. core-SVP方法论将这些复杂度视为求解$ b $维格SVP问题的复杂度,并将得到的BKZ算法的复杂度作为原始攻击的复杂度估计. 本文将基于core-SVP方法论给本文方案提供一个保守估计的安全强度,并基于文献[22, 37, 52]提供的计算安全强度的Python脚本来计算LTRU在原始攻击下的经典安全强度和量子安全强度,其详细结果如表1所示.
3) 其他攻击
对偶攻击主要通过将判定型LWE问题规约为短整数解问题(short integer solution problem,SIS)的方式来求解判定型LWE问题. 由于对偶攻击不适用于NTRU类型的方案[53],故本文不考虑对偶攻击对LTRU的影响. 过度拉伸NTRU攻击[54]的适用范围为模数$ q $远大于秘密多项式系数的情况. 由于LTRU的模数$ q $数值较小,不满足该情况,故本文不考虑该攻击. 混合攻击[55]是格攻击和中间相遇攻击的提升版本,但混合攻击对于有着稀疏分布的秘密多项式系数和噪音多项式系数的方案能取得显著效果. 然而对于LTRU,混合攻击不如原始攻击有效,因为LTRU的秘密$ (f,g) $并非稀疏分布,不符合混合攻击的条件.
1) 多项式环
本文LTRU方案使用第$ 3n $个分圆多项式环$ {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) $,其中$ n $的形式为$ {3^l} \times {2^e} $,$ q $为某些素数. 主要原因是,当选择合适的$ q $,如NTT友好的$ q $时,存在高效的NTT算法计算该环上的多项式乘法和除法. 同时,$ n $的选择具有更大的灵活性,因为$ n $能够选择576,768,864,972,1152,1296等数值. 当选择其他的$ n $值时,LTRU能够达到其他的安全强度(如192 b和256 b),而不再局限于128 b的安全强度. 但是,本文主要针对128 b的安全强度,故选择$ n $=648. 相比而言,NTRU-HRSS[20]使用多项式环$ {\mathbb{Z}_q}[x]/({x^n} - 1) $,其中$ n $为素数,$ q $为2次幂;SNTRU Prime[21]使用多项式环$ {\mathbb{Z}_q}[x]/({x^n} - x - 1) $,其中$ n $,$ q $均为素数. 这些多项式环不是NTT友好环,所以这些多项式环上的多项式乘法和除法更复杂,且耗时更多.
2) 明文空间模数$ p $
与其他NTRU方案如文献[20-21, 26-27]中的方案不同,本文LTRU使用的明文空间模数$ p = 2 $,且只需出现在私钥$ f $中,即$ f = pf' + 1 $,而无需在公钥$ h $以及解密算法中出现. 但是,NTRU方案[20-21,26-27]使用模数$ p = 3 $. 甚至,由于NTRU类型方案要求$ q $和$ p $互素,而NTRU-HRSS[20]由于使用2次幂的模数$ q $,所以它使用了与$ q $互素的最小整数$ p = 3 $.
3) 纠错机制
常见的NTRU类型方案[20-21,26-27]的密文形式为$ c = phr + m\text{mod} q $,这可以视为明文$ m $编码在密文c的低位. 其恢复明文$ m $的方式主要通过计算$ cf\text{mod} q $之后再模$ p $来消去杂项. 这种纠错机制依赖于杂项是$ p $的倍数. 与之不同的是,LTRU在底层公钥加密方案$ {\text{PKE}} '$中首先将明文m提升$ q/2 $倍,相当于把明文$ m $编码到密文c的高位,随后在解密算法中只要求杂项的范数小于$ 1/2 $,而不必要求其为$ p $的倍数. 同时可以看到,LTRU不使用纠错码来恢复明文. 纠错码虽然能够高效地实现纠错来恢复明文,但是纠错码使得代码实现更复杂且增加遭遇侧信道攻击的风险,如文献[30]针对纠错码提出了有效的侧信道攻击.
4) 密文压缩
LTRU的密文压缩操作见算法5的行②. 本文的LTRU是第1个仅基于NTRU单向困难性假设构造的、不使用纠错码也能够压缩密文的密钥封装方案. LTRU的密钥压缩参数$ d $可根据需求自行调整. 对于其他NTRU类型方案[20-21,26-27],如果它们压缩密文,那么压缩过程会在密文的低位带来误差,而编码在密文低位的明文$ m $的有效信息会被这些误差破坏,使得正确的明文$ m $难以恢复出来;同时在解密算法中杂项也不再是$ p $的倍数,所以也无法通过模$ p $来消去杂项以恢复正确的明文$ m $.
本节将介绍本文提出的一种混合基NTT算法,其能高效地计算本文推荐参数集LTRU-648所使用的环$ {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) $,$ n = 648 $,$ q = 2\;917 $上的多项式乘法和除法,且利用了1-迭代Karatsuba算法和单位根的性质减少乘法的数量,以提高计算效率.
对于$ {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) $,$ n = 648 $,$ q = 2\;917 $,可知$ {\mathbb{Z}_q} $中存在$ 3n/2 $次本原单位根$ \zeta = 2 $,其中$ \zeta $为$ k $次本原单位根是指$ {\zeta ^k} \equiv 1\text{mod} q $且$ {\zeta ^i} \ne 1\text{mod} q $,$ 0 < i < k $.
为方便理解,图1展示了混合基NTT对应的CRT同构树形图. 本文的混合基NTT的计算过程主要依靠逐层CRT分解.
类似于文献[26]提出的第1层CRT同构,对于$ {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) $,有
$ \begin{split}& {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) \cong\\&\quad {\mathbb{Z}_q}[x]/({x^{n/2}} - {\zeta _1}) \times {\mathbb{Z}_q}[x]/({x^{n/2}} - {\zeta _2}), \end{split} $
其中$ {\zeta _1} + {\zeta _2} = 1 $和$ {\zeta _1}{\zeta _2} = 1 $. 容易求得,$ {\zeta _2} = 1 - {\zeta _1} $和$ {\zeta _2} = \zeta _1^5 $. 取$ {\zeta _1} = {\zeta ^{n/4}}\text{mod} q $以及$ {\zeta _2} = {\zeta ^{5n/4}}\text{mod} q $,对于任意的$ f \in {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) $,可得
$ \left\{ \begin{split}& f\text{mod} {x^{n/2}} - {\zeta _1} = ({f_0} + {\zeta _1}{f_{n/2}}) + \cdots +({f_{n/2 - 1}} + {\zeta _1}{f_{n - 1}}){x^{n/2 - 1}}, \\&f\text{mod} {x^{n/2}} - {\zeta _2} = ({f_0} + {f_{n/2}} - {\zeta _1}{f_{n/2}}) + \cdots + \\&({f_{n/2 - 1}} + {f_{n - 1}} - {\zeta _1}{f_{n - 1}}){x^{n/2 - 1}}.\end{split} \right. $
由于$ {\zeta _1}{f_{n/2}} $只需计算1次而可使用2次,故式(2)(3)总计只需$ n/2 $个乘法和$ n $个加(减)法.
1) 基-2 FFT trick步骤
可利用CRT对$ {\mathbb{Z}_q}[x]/({x^{n/2}} - {\zeta _1}) $和$ {\mathbb{Z}_q}[x]/({x^{n/2}} - {\zeta _2}) $进行基-2 FFT trick步骤的分解. 对于每个基-2 FFT trick步骤形如
$ {\mathbb{Z}_q}[x]/({x^{2m}} - {r^2}) \cong {\mathbb{Z}_q}[x]/({x^m} - r) \times {\mathbb{Z}_q}[x]/({x^m} + r) \text{,} $
其中$ r $为$ \zeta $的某次幂,对于$ f' \in {\mathbb{Z}_q}[x]/({x^{2m}} - {r^2}) $,可得
$ \left\{ \begin{aligned}{f_l} = f'\text{mod} {x^m} - r = ({{f'}_0} + r{{f'}_m}) + \cdots + ({{f'}_{m - 1}} + r{{f'}_{2m - 1}}){x^{m - 1}}, \\{f_r} = f'\text{mod} {x^m} + r = ({f_0}^\prime - r{{f'}_m}) + \cdots + ({{f'}_{m - 1}} - r{{f'}_{2m - 1}}){x^{m - 1}}, \\ \end{aligned} \right. $
其中每个$ r{f'_i} $只需计算1次而可使用2次. 这使得每层的基-2 FFT trick步骤所需乘法数量从$ n $个锐减到$ n/2 $个.
2) 基-3 FFT trick步骤
对于$ n = 648 $,基-2 FFT trick步骤可进行1层,直至得到4个形如$ {\mathbb{Z}_q}[x]/({x^{162}} - {\zeta ^{81}}) $的项. 此时本文采用基-3 FFT trick. 每个基-3 FFT trick步骤均形如
$ \begin{split}&{\mathbb{Z}_q}[x]/({x^{3m}} - {r^3}) \cong {\mathbb{Z}_q}[x]/({x^m} - r) \times {\mathbb{Z}_q}[x]/({x^m} - \rho r) \times \\&\quad{\mathbb{Z}_q}[x]/({x^m} - {\rho ^2}r), \\ \end{split} $
其中$ r $为$ \zeta $的某次幂,$ \rho = {\zeta ^{n/3}}\text{mod} q $为3次单位根. $ {\mathbb{Z}_q}[x]/({x^{3m}} - {r^3}) $中的多项式$ f'' $可以表示为
$ f'' = {f_a} + {f_b}{x^m} + {f_c}{x^{2m}} \text{,} $
其中$ {f_a},{f_b},{f_c} $均为$ m - 1 $次多项式. 由于$ {\rho ^3}{\text{ = }}1\text{mod} q $,可得
$ \left\{ \begin{gathered}{f_x} = f''\text{mod} {x^m} - r = {f_a} + r{f_b} + {r^2}{f_c}, \\{f_y} = f''\text{mod} {x^m} - \rho r = {f_a} + \rho r{f_b} + {\rho ^2}{r^2}{f_c}, \\{f_z} = f''\text{mod} {x^m} - {\rho ^2}r = {f_a} + {\rho ^2}r{f_b} + \rho {r^2}{f_c}. \\ \end{gathered} \right. $
注意到$ {\rho ^2} + \rho + 1 = 0\text{mod} q $,则$ {\rho ^2} = - \rho - 1\text{mod} q $. 类似于文献[56],此时有
$ \begin{split}{f_y} =& {f_a} + \rho r{f_b} + {\rho ^2}{r^2}{f_c} =\\& {f_a} + \rho r{f_b} + ( - \rho - 1){r^2}{f_c} =\\& {f_a} - {r^2}{f_c} + \rho (r{f_b} - {r^2}{f_c}), \end{split} $
以及
$ \begin{split}{f_z} = &{f_a} + {\rho ^2}r{f_b} + \rho {r^2}{f_c} =\\& {f_a} + ( - \rho - 1)r{f_b} + \rho {r^2}{f_c}= \\& {f_a} - r{f_b} - \rho (r{f_b} - {r^2}{f_c}). \end{split} $
于是可得
$ \left\{ \begin{gathered}{f_x} = {f_a} + r{f_b} + {r^2}{f_c}, \\{f_y} = {f_a} - {r^2}{f_c} + \rho (r{f_b} - {r^2}{f_c}), \\{f_z} = {f_a} - r{f_b} - \rho (r{f_b} - {r^2}{f_c}). \\ \end{gathered} \right. $
注意到,$ r{f_b},{r^2}{f_c},\;\rho (r{f_b} - {r^2}{f_c}) $都只需要计算1次而能够多次使用. 并且只需存储和使用本原单位根$ r $和$ {r^2} $以及3次单位根$ \rho $,而无需存储其他值如$ \rho r $,$ {\rho ^2}{r^2} $,$ {\rho ^2}r $,$ \rho {r^2} $. 易知,使用3次单位根的性质之后,每层的基-3 FFT trick步骤所需乘法数量从$ 2n $个锐减到$ n $个.
正向变换中基-3 FFT trick步骤可进行4层,直到将$ {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) $分解得到$ n/2 $个模2次多项式的环. 换句话说,即有
$ {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) \cong \prod\limits_{i = 0}^{n/2 - 1} {{\mathbb{Z}_q}[x]/({x^2} - {\zeta ^{\tau (i)}})} \text{,} $
其中$ \tau (i) $表示第$ i $个环中$ \zeta $的幂且序号从0开始. 对于$ f \in {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) $,其正向变换的结果记为
$ \hat f = ({\hat f_0},{\hat f_1}, … ,{\hat f_{n/2 - 1}}) \text{,} $
其中$ {\hat f_i} \in {\mathbb{Z}_q}[x]/({x^2} - {\zeta ^{\tau (i)}}) $为线性多项式.
为方便后文书写,本文使用符号$ \mathcal{N}\mathcal{T}\mathcal{T} $表示上述的正向变换过程. 正向变换$ \mathcal{N}\mathcal{T}\mathcal{T} $的伪代码见算法11.
算法11. 正向变换$ \mathcal{N}\mathcal{T}\mathcal{T} $.
输入:多项式$ f \in {\mathcal{R}_q} $的系数数组$ \{ f[i]\} _{i = 0}^{n - 1} $,按照树形图1从上而下排列的本原单位根$ \{ \zeta [k]\} _{k = 1}^{n/2} $,3次单位根$ \rho $;
输出:$ \hat f = \mathcal{N}\mathcal{T}\mathcal{T}(f) $的系数数组$ \{ \hat f[i]\} _{i = 0}^{n - 1} $.
①  $ k: = 1 $;
②  for $ j: = 0 $,$ j < n/2 $,$ j: = j + 1 $ do            /*进行首层CRT分解*/
③    $ t: = \zeta [k] \times f[j + n/2] $;
④   $ f[j + n/2]: = f[j] + f[j + n/2] - t $;
⑤   $ f[j]: = f[j] + t $;
⑥  end for
⑦  $ k: = k + 1 $;
⑧  for $ s: = 0 $,$ s < n $,$ s: = j + n/4 $ do            /*进行1层基-2 正向FFT trick*/
⑨   for $ j: = s $,$ j < s + n/4 $,$ j: = j + 1 $ do
⑩    $ t: = \zeta [k] \times f[j + n/4] $;
⑪    $ f[j + n/4]: = f[j] - t $;/*CT蝴蝶*/
⑫    $ f[j]: = f[j] + t $;
⑬   end for
⑭    $ k: = k + 1 $;
⑮  end for
⑯  for $ l: = n/12 $,$ l \geqslant 2 $,$ l: = l/3 $ do            /*进行4层基-3 正向FFT trick*/
⑰   for $ s: = 0 $,$ s < n $,$ s: = s + 3l $ do
⑱    for $ j: = s $,$ j < s + l $,$ j: = j + 1 $ do
⑲     $ u: = \zeta [k] \times f[j + l] $;
⑳     $ v: = \zeta [k + 1] \times f[j + 2l] $;
㉑     $ w: = \rho (u - v) $;
㉒      $ f[j + 2l]: = f[j] - u - w $;
㉓     $ f[j + l]: = f[j] - v + w $;
㉔     $ f[j]: = f[j] + u + v $;
㉕    end for
㉖    $ k: = k + 2 $;
㉗   end for
㉘  end for
逆向变换可由正向变换的逆过程得到. 本文使用符号$ \mathcal{I}\mathcal{N}\mathcal{T}\mathcal{T} $表示逆向变换. 值得注意的是,在计算基-3 逆向FFT trick时,同样可利用3次单位根的性质减少乘法的数量. 沿用4.1节的符号和$ {\mathbb{Z}_q}[x]/({x^{3m}} - {r^3}) $示例,在基-3 逆向FFT trick中,从$ {f_x},\;{f_y},\; {f_z} $计算得到$ f'' $. 由$ f'' = {f_a} + {f_b}{x^m} + {f_c}{x^{2m}} $可知,这等价于得到$ {f_a},{f_b},{f_c} $. 先计算
$ \left\{ \begin{gathered}{{\tilde f}_a} = {f_x} + {f_y} + {f_z}, \\{{\tilde f}_b} = {f_x} + {\rho ^2}{f_y} + \rho {f_z}, \\{{\tilde f}_c} = {f_x} + \rho {f_y} + {\rho ^2}{f_z}. \\ \end{gathered} \right. $
利用$ {\rho ^2} = - \rho - 1\text{mod} q $,进一步可得
$ \begin{split}{{\tilde f}_b} =& {f_x} + {\rho ^2}{f_y} + \rho {f_z} = \\& {f_x} + ( - \rho - 1){f_y} + \rho {f_z} = \\& {f_x} - {f_y} - \rho ({f_y} - {f_z}), \end{split} $
以及
$ \begin{split}{{\tilde f}_c} = &{f_x} + \rho {f_y} + {\rho ^2}{f_z} = \\& {f_x} + \rho {f_y} + ( - \rho - 1){f_z}=\\& {f_x} - {f_z} + \rho ({f_y} - {f_z}). \end{split} $
于是可得
$ \left\{ \begin{gathered}{{\tilde f}_a} = {f_x} + {f_y} + {f_z}, \\{{\tilde f}_b} = {f_x} - {f_y} - \rho ({f_y} - {f_z}), \\{{\tilde f}_c} = {f_x} - {f_z} + \rho ({f_y} - {f_z}). \\ \end{gathered} \right. $
注意到,$ \rho ({f_y} - {f_z}) $只需要计算1次而使用2次. 进一步可从$ {\tilde f_a},{\tilde f_b},{\tilde f_c} $分别得到$ {f_a},{f_b},{f_c} $为
$ \left\{ \begin{gathered}{f_a} = {3^{ - 1}} \times {{\tilde f}_a}, \\{f_b} = {3^{ - 1}} \times {r^{ - 1}} \times {{\tilde f}_b}, \\{f_c} = {3^{ - 1}} \times {r^{ - 2}} \times {{\tilde f}_c}, \\ \end{gathered} \right. $
其中倍数$ {3^{ - 1}} $可延迟处理. 故易知,基于3次单位根的性质,每层的基-3 逆向FFT trick步骤所需乘法数量从$ 2n $个锐减到$ n $个.
另外,对于基-2 逆向FFT trick,在此沿用4.1节的示例,从$ {f_l} = f'\text{mod} {x^m} - r $和$ {f_r} = f'\text{mod} {x^m} + r $计算得到$ f' \in {\mathbb{Z}_q}[x]/({x^{2m}} - {r^2}) $的步骤为
$ f' = \displaystyle\sum\limits_{i = 0}^{m - 1} {\frac{{{f_{l,i}} + {f_{r,i}}}}{2}{x^i}} + \displaystyle\sum\limits_{i = 0}^{m - 1} {\frac{{{f_{l,i}} - {f_{r,i}}}}{{2r}}{x^{i + m}}} \text{,} $
其中$ {f_{l,i}} $和$ {f_{r,i}} $分别表示$ {f_l} $和$ {f_r} $的第$ i $个系数,倍数$ {2^{ - 1}} $同样可延迟处理. 易知,每层的基-2 逆向FFT trick步骤共需要$ n/2 $个乘法. 再合计上基-3 逆向FFT trick步骤延迟处理的倍数,在整个逆向变换结束之时,需要乘以总的倍数$ {(n/2)^{ - 1}}\text{mod} q $.
逆向变换$ \mathcal{I}\mathcal{N}\mathcal{T}\mathcal{T} $的伪代码见算法12.
算法12. 逆向变换$ \mathcal{I}\mathcal{N}\mathcal{T}\mathcal{T} $.
输入:多项式$ \hat f $的系数数组$ \{ \hat f[i]\} _{i = 0}^{n - 1} $,按照树形图1从下而上排列的本原单位根的逆$ \{ \zeta [k]\} _{k = 1}^{n/2} $,3次单位根$ \rho $;
输出:$ f = \mathcal{I}\mathcal{N}\mathcal{T}\mathcal{T}(\hat f) $的系数数组$ \{ f[i]\} _{i = 0}^{n - 1} $.
①  $ k: = 1 $;
②  for $ l: = 2 $,$ l \leqslant n/12 $,$ l: = 3l $ do             /*进行4层基-3 逆向FFT trick*/
③  for $ s: = 0 $,$ s < n $,$ s: = s + 3l $ do
④    for $ j: = s $,$ j < s + l $,$ j: = j + 1 $ do
⑤     $ u: = \rho (\hat f[j + l] - \hat f[j + 2l]) $;
⑥     $ v: = \hat f[j] - \hat f[j + l] - u $;
⑦     $ w: = \hat f[j] - \hat f[j + 2l] + u $;
⑧     $ \hat f[j]: = \hat f[j] + \hat f[j + l] + \hat f[j + 2l] $;
⑨     $ \hat f[j + l]: = \zeta [k] \times v $;
⑩      $ \hat f[j + 2l]: = \zeta [k + 1] \times w $;
⑪    end for
⑫    $ k: = k + 2 $;
⑬   end for
⑭  end for
⑮  for $ s: = 0 $,$ s < n $,$ s: = j + n/4 $ do            /*进行1层基-2 逆向FFT trick*/
⑯   for $ j: = s $,$ j < s + n/4 $,$ j: = j + 1 $ do
⑰    $ t: = \hat f[j] $;
⑱    $ \hat f[j]: = t + \hat f[j + n/4] $;/*GS蝴蝶*/
⑲    $ \hat f[j + n/4]: = \zeta [k] \times (t - \hat f[j + n/4]) $;
⑳   end for
㉑   $ k: = k + 1 $;
㉒  end for
㉓  $ \zeta ': = {(2{\zeta _1} - 1)^{ - 1}} $;/*$ {\zeta _1} $如图1所示*/
㉔  for $ j: = 0 $,$ j < n/2 $,$ j: = j + 1 $ do            /*进行首层CRT同构*/
㉕   $ t: = \zeta ' \times (\hat f[j] - \hat f[j + n/2]) $;
㉖   $ \hat f[j]: = (\hat f[j] + \hat f[j + n/2] - t) \times {(n/2)^{ - 1}} $;
㉗   $ \hat f[j + n/2]: = t \times {(n/4)^{ - 1}} $;
㉘  end for
点乘“$ \circ $”由$ {\mathbb{Z}_q}[x]/({x^2} - {\zeta ^{\tau (i)}}) $中的乘法构成. 对于$ \hat f = ({\hat f_0},{\hat f_1}, … ,{\hat f_{n/2 - 1}}) $和$ \hat g = ({\hat g_0},{\hat g_1}, … ,{\hat g_{n/2 - 1}}) $有
$ \hat f \circ \hat g = ({\hat f_0}{\hat g_0},{\hat f_1}{\hat g_1}, … ,{\hat f_{n/2 - 1}}{\hat g_{n/2 - 1}}) \text{,} $
其中$ {\hat f_i},{\hat g_i} \in {\mathbb{Z}_q}[x]/({x^2} - {\zeta ^{\tau (i)}}) $,$ i = 0,1, … ,n/2 - 1 $.
本文使用1-迭代Karatsuba算法来减少点乘中的乘法数量. 具体而言,为了在$ {\mathbb{Z}_q}[x]/({x^2} - {\zeta ^{\tau (i)}}) $中计算$ {\hat f_i} $和$ {\hat g_i} $的积,即是
$ \begin{split}&{{\hat f}_i}{{\hat g}_i}\text{mod} {x^2} - {\zeta ^{\tau (i)}}= ({{\hat f}_{i,0}} + {{\hat f}_{i.1}}x)({{\hat g}_{i,0}} + {{\hat g}_{i,1}}x)\text{mod} {x^2} - {\zeta ^{\tau (i)}}=\\&\quad ({{\hat f}_{i,0}}{{\hat g}_{i,0}} + {\zeta ^{\tau (i)}}{{\hat f}_{i.1}}{{\hat g}_{i,1}}) + ({{\hat f}_{i,0}}{{\hat g}_{i,1}} + {{\hat f}_{i.1}}{{\hat g}_{i,0}})x, \end{split} $
可使用1-迭代Karatsuba算法首先计算$ {t_0} = {\hat f_{i,0}}{\hat g_{i,0}} $和$ {t_1} = {\hat f_{i.1}}{\hat g_{i,1}} $,然后计算$ {\zeta ^{\tau (i)}}{t_1} $,以及
$ {\hat f_{i,0}}{\hat g_{i,1}} + {\hat f_{i.1}}{\hat g_{i,0}} = ({\hat f_{i,0}} + {\hat f_{i.1}})({\hat g_{i,0}} + {\hat g_{i,1}}) - {t_0} - {t_1} . $
原本需要5个乘法,现在只需要4个乘法. 使用1-迭代Karatsuba算法计算点乘的伪代码见算法13.
算法13. 点乘.
输入:$ \hat f $的系数数组$ \{ \hat f[i]\} _{i = 0}^{n - 1} $,$ \hat g $的系数数组$ \{ \hat g[i]\} _{i = 0}^{n - 1} $,本原单位根$ \{ {\zeta ^{\tau (k)}}\} _{k = 0}^{n/2 - 1} $;
输出:点乘结果$ \hat h $的系数数组$ \{ \hat h[i]\} _{i = 0}^{n - 1} $.
①  for $ j: = 0 $,$ j < n/2 $,$ j: = j + 1 $ do
②   $ u: = \hat f[2j] \times \hat g[2j] $;
③   $ v: = \hat f[2j + 1] \times \hat g[2j + 1] $;
④   $ w: = (\hat f[2j] + \hat f[2j + 1])(\hat g[2j] + \hat g[2j + 1]) $;
⑤   $ \hat h[2j]: = u + {\zeta ^{\tau (j)}} \times v $;
⑥   $ \hat h[2j + 1]: = w - u - v $;
⑦  end for
基于混合基NTT计算多项式乘法$ h = fg \in {\mathbb{Z}_q}[x]/ $ $({x^n} - {x^{n/2}} + 1) $的过程为
$ h = \mathcal{I}\mathcal{N}\mathcal{T}\mathcal{T}(\mathcal{N}\mathcal{T}\mathcal{T}(f) \circ \mathcal{N}\mathcal{T}\mathcal{T}(g)) . $
另外,本文同样使用该混合基NTT计算多项式除法$ h = g/f \in {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) $,即计算LTRU方案中的公钥$ h $. 具体而言,其计算过程为
$ h = \mathcal{I}\mathcal{N}\mathcal{T}\mathcal{T}(\hat g \circ {\hat f^{ - 1}}) \text{,} $
其中$ \hat g = \mathcal{N}\mathcal{T}\mathcal{T}(g) $,$ \hat f = \mathcal{N}\mathcal{T}\mathcal{T}(f) $以及
$ {\hat f^{ - 1}} = (\hat f_0^{ - 1},\hat f_1^{ - 1}, … ,\hat f_{n/2 - 1}^{ - 1}) . $
本文使用$ \hat f_i^{ - 1} $表示$ {\hat f_i} $在$ {\mathbb{Z}_q}[x]/({x^2} - {\zeta ^{\tau (i)}}) $中的逆(此时需要$ \hat f_i^{ - 1} $均存在). 实际上,$ \hat f_i^{ - 1} $能够由$ {\hat f_i} = {\hat f_{i,0}} + {\hat f_{i,1}}x $显式求得
$ \hat f_i^{ - 1} = \frac{1}{{\hat f_{i,0}^2 - {\zeta ^{\tau (i)}}\hat f_{i,1}^2}}({\hat f_{i,0}} - {\hat f_{i,1}}x) . $
同时可知,当且仅当$ \hat f_{i,0}^2 - {\zeta ^{\tau (i)}}\hat f_{i,1}^2 $≠0时$ \hat f_i^{ - 1} $存在;另一方面,如果存在某个$ i $使得$ \hat f_{i,0}^2 - {\zeta ^{\tau (i)}}\hat f_{i,1}^2 = 0 $,那么$ f $的逆不存在. 此时公钥$ h $不存在,需要重新采样$ f $直至$ f $的逆存在. 给定$ f $,计算$ {\hat f^{ - 1}} $的伪代码见算法14.
算法14. 计算低次数多项式的逆.
输入:$ \hat f $的系数数组$ \{ \hat f[i]\} _{i = 0}^{n - 1} $,本原单位根$ \{ {\zeta ^{\tau (k)}}\} _{k = 0}^{n/2 - 1} $;
输出:$ {\hat f^{ - 1}} $的系数数组$ \{ {\hat f^{ - 1}}[i]\} _{i = 0}^{n - 1} $.
①  for $ j: = 0 $;$ j < n/2 $;$ j: = j + 1 $ do
②   $ t: = \hat f[2j] \times \hat f[2j] $;
③   $ t: = t - {\zeta ^{\tau (j)}} \times \hat f[2j + 1] \times \hat f[2j + 1] $;
④    $ t: = {t^{ - 1}} $;
⑤    $ {\hat f^{ - 1}}[2j]: = \hat f[2j] \times t $;
⑥   $ {\hat f^{ - 1}}[2j + 1]: = - \hat f[2j + 1] \times t $;
⑦  end for
本文给出了LTRU的便携C实现和优化AVX2实现. 下面将简要介绍LTRU的一些实现细节. 值得注意的是,LTRU的所有实现均采用了常数时间实现技巧,以抵抗一些潜在的侧信道攻击,特别是计时攻击[31].
本文使用的模数$ q = 2\;917 $是低于16 b的素数,所以$ {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) $中的多项式能够使用长度为$ n $、类型为16 b有符号整型的数组来存储.
1) 哈希函数
本文中使用的哈希函数均使用SHA3系列函数来实例化. 具体而言,使用SHA3-256实例化哈希函数$ \mathcal{F} $,使用SHA3-512实例化哈希函数$ \mathcal{H} $. 其中$ \mathcal{H} $以明文消息$ m $作为输入,得到64 B的输出,其中前32 B作为导出的共享密钥,后32 B作为种子并使用SHAKE128来生成加密算法所需的随机数.
2) 秘密多项式
本文使用的秘密多项式如$ f',\;g,\;r $都是根据分布$ {\bar B_2} $采样得到. 每采样一个系数需要4个随机比特,所以采样一个多项式需要$ 4n $个比特,即$ n/2 $字节.
3) 约减算法
在计算多项式系数的加法和乘法时,计算结果存在超出16 b有符号整型的有效表示范围的可能性. 此时需要使用约减算法将计算结果约减到$ [0,q) $. 本文使用Barrett约减算法[57]和Montgomery约减算法[58]. 其中Barrett约减算法主要用于系数加法后的约减;而Montgomery约减算法主要用于系数和系数相乘,或者系数和本原单位根相乘时的约减.
4) 消息的存储形式
注意到在LTRU加密算法中,多项式$ e $是系数范围取自$ \{ 0,1\} $的多项式,所以可以将$ e $视为大小为$ n $的比特串. 实际上,本文使用$ n/8 $个字节(即$ n $位)来存储并表示$ e $,这样能够减少将$ e $在多项式和比特串之间转换的过程,提高效率.
5) 公私钥和密文
公钥和私钥均以NTT域中多项式的形式存储和传输. 具体而言,计算得到$ \hat h $和$ \hat f $之后,以$ \hat h $作为公钥,且以$ \hat f $作为私钥. 这样能在密钥生成算法中省去对$ \hat h $的逆向NTT变换,以及在加密算法中对$ h $的正向NTT变换. 同时,在解密算法中亦省去对私钥$ f $的正向NTT变换. 所以,公钥$ \hat h $和私钥$ \hat f $的每个系数均为12 b,故共需$ 12n $位,即是$ 3n/2 $个字节的存储空间. 另外,由于解封装算法中需要重加密步骤,故封装方案的私钥还需要包含公钥$ \hat h $. 密文的第1项$ c $以正常域中多项式的形式存储和传输,需要$ nd/8 $个字节的存储空间,这是因为压缩密文操作需要在正常域中进行;第2项$ u $是比特串,需要$ n/8 $个字节的存储空间. 在实际传输过程中,密文的第1项和第2项拼接之后总计$ nd/8 $+$ n/8 $个字节.
本节提供LTRU的C实现的细节. 本文使用第4节的高效的混合基NTT来计算LTRU-648的多项式乘法和除法(即计算公钥$ h $). 测试设备为:硬件配置为2.3 GHz的Intel® Core™ i7-10510U CPU和16 GB内存的笔记本电脑,且关闭Turbo Boost和Hyperthreading.操作系统为:核为Linux Kernel 4.4.0的Ubuntu 20.04 LTS操作系统,且gcc版本为9.4.0.编译参数为:-Wall-march=native-mtune=native-O3-fomit-framepointer-Wno-unknown-pragmas.
本文LTRU的C实现只涉及到整型算术操作,特别是16 b有符号整型算术. 在NTT的实现中,由于C语言的“%”运算符不是常数时间实现,其执行时间和输入数据长度密切相关,存在泄露秘密数据的可能性,故本文转向使用常数时间实现的Barrett约减算法和Montgomery约减算法. 对于正向NTT变换,本文使用延迟规约策略[59]来减少约减的次数. 具体而言,对于乘法中使用的Montgomery约减,其输出值范围为$ [ - q,q] $. 本文使用的模数$ q $为12 b,所以在6层FFT trick之后,正向NTT变换输出的多项式范围在$ [ - 7q,7q] $之间,这显然在16 b有符号整型的有效表示范围之内. 故中间计算过程无需进行额外的Barrett约减,而只需要在正向NTT变换结束时进行1次Barrett约减.
本节提供LTRU的AVX2实现细节.AVX2实现主要优化的运算包括:多项式加法/乘法/除法、模约减算法等. 但是,SHA3系列哈希函数并没采用AVX2优化实现,而是继续采用C语言的实现. 这是因为SHA3系列哈希函数难以向量化实现,而目前最高效的实现是基于C语言的[52]. 另外,NTT运算非常耗时,所以NTT运算是AVX2优化的主要目标. 下面主要介绍本文提出的混合基NTT的AVX2实现细节.
AVX2指令集的载入/存储指令一次性载入/存储的数据长度为256 b. 换句话说,指令能够一次性载入/存储16个多项式系数,因为每个系数使用16 b有符号整型表示. 但是,每个多项式共有$ 648 $个系数,其中648并非16的整数倍. 为了能够使用AVX2指令集的载入/存储指令,将648个系数对相邻的16个系数进行划分,得到40个划分单位以及剩下的8个系数,然后对每个划分单位进行数据对齐. 这种方法虽然便于使用载入/存储指令,但不便于在NTT运算中计算基-2 FFT trick步骤和基-3 FFT trick步骤.
为了方便使用AVX2指令集的载入/存储指令,同时方便计算基-2 FFT trick步骤和基-3 FFT trick步骤,本文采用2个系数填充过程:
1) 将648个系数对相邻的12个系数进行划分,得到54个划分单位;
2)把每一个划分单位里面的12个系数拓展到16个系数,即保留原12个系数位置不变,在它们末尾的位置填充4个0.
通过这2个系数填充过程,得到864个系数,以及新的54个划分单位,每个划分单位包含16个系数. 此时每个划分单位能够一次性被载入到寄存器之中. 在完成寄存器一系列计算、存储回内存位置后,多项式系数提取的过程为:
1)将864个系数对相邻的16个系数进行划分,得到54个划分单位;
2) 在每一个划分单位中提取前面的12个系数,舍弃末尾的4个0.
通过这2个系数提取过程,得到原始长度的多项式数组. 系数填充过程和系数提取过程如图2所示.
这种填充过程应用在多项式的NTT运算,如正向变换、逆向变换、点乘和求逆之中. 另外,这种填充过程使得NTT运算以12倍的并行度进行计算,区别于通常的16倍的并行度计算. 这是因为此时每个寄存器只能一次性处理原始多项式的12个系数,而非原始多项式的16个系数. 由于AVX2指令集的载入/存储指令耗时较多,所以应该减少内存访问的次数. 常用的方法是合并处理NTT运算中的若干层. 本文合并正向变换的第2层和第3层的计算. 在此期间,仅需载入一次数据,无需额外的访问内存和数据载入/存储便能够完成第2层和第3层的计算,这能够降低因载入/存储指令带来的CPU周期数的消耗. 本文通过vmovdqa指令完成数据的载入/存储. 在分别载入多项式系数和本原单位根之后,通过vpmulhw指令和vpmullw指令分别计算它们乘积的高位和低位,这样能够高效地计算它们的Montgomery约减的值. 本文的AVX2实现将一些常用的代码段通过macro封装起来,这使得整体代码简洁和可读性强.
计时攻击[31]是一种常见的侧信道攻击,它指的是敌手可以根据密码方案在软硬件环境中的执行时间等信息来推断所执行的运算操作和内容访问情况,继而攻击者可以根据所获取的侧信道信息来推算出该操作所涉及的一些秘密信息,如私钥或者一些秘密值. 目前来说,密码方案的实现几乎都需要考虑计时攻击,并应该采用常数时间实现策略. 因此,本文的LTRU实现过程采用了常数时间实现策略. 最重要的是,本文并没使用非常数时间的指令来操作秘密数据,以及没使用依赖于秘密数据的判断分支语句,也没访问依赖于秘密数据寻址的内存地址. 计算NTT过程中取模使用到的Barrett约减算法和Montgomery约减算法均是常数时间实现[59],且算法本身对任意合适的模数均成立. 至于采样秘密多项式$ f',g,r $,本文均以常数时间的方式来采样. 每次固定使用4 b来生成1个多项式系数. 显然,生成秘密多项式的时间也是恒定的.
本节将比较混合基NTT算法与未使用1-迭代Karatsuba算法和单位根的性质优化乘法数量的NTT算法,以及比较本文LTRU和其他NTRU类型密钥封装方案如NTRU-HRSS[20],SNTRU Prime[21],NTTRU[26],NTRU-A[27],CTRU[28],BAT[29],还有基于模格的密钥封装方案如NIST标准化方案Kyber[22].
表2给出了混合基NTT算法与未使用1-迭代Karatsuba算法和单位根的性质优化乘法数量的NTT算法在理论乘法复杂度分析和具体实现的CPU周期数的比较.
表3和表4展示了本文LTRU和其他方案对比的详细情况. 为方便比较,在此选取与这些方案安全强度接近的参数集,但CTRU和Kyber并没有接近128 b量子安全强度的参数集,所以在此选取它们的推荐参数集. SNTRU Prime选取SNTRU Prime-761参数集,NTRU-A选取$ {\text{NTRU - A}}_{2\;917}^{648} $参数集,CTRU选取CTRU-768参数集,BAT选取BAT-512参数集,Kyber选取Kyber-768参数集. 其中NTRU-HRSS,SNTRU Prime-761,Kyber-768的数据和开源代码来自它们的NIST第3轮材料. NTTRU的数据和开源代码来自文献[26]. $ {\text{NTRU - A}}_{2\;917}^{648} $的数据来自文献[27],CTRU-768的数据来自文献[28],BAT-512的数据来自文献[29].
值得注意的是,本文的混合基NTT和未优化的混合基NTT在多项式环$ {\mathbb{Z}_q}[x]/({x^n} - {x^{n/2}} + 1) $首层CRT同构具有相同的乘法复杂度:正向变换时需要$ n/2 $个乘法,逆向变换时需要$ 3n/2 $个乘法. 为方便比较乘法复杂度,在此记基-2 FFT trick和基-3 FFT trick的层数分别为$ {l_2} $和$ {l_3} $. 在本文的混合基NTT中,每层基-2 FFT trick的正向变换和逆向变换均需要$ n/2 $个乘法. 每层基-3 FFT trick的正向变换和逆向变换均需要$ n $个乘法. 然而,未优化的NTT每层基-3 FFT trick的正向变换和逆向变换均需要$ 2n $个乘法. 因为2种NTT算法的求逆运算相同,于是求逆运算具有相同的乘法复杂度,故可以省去对它们的求逆运算的比较.
从表2可以看出,在比较多项式乘法复杂度时,本文NTT比未优化的NTT在正向变换、点乘和逆向变换方面分别减少了$ n{l_3} $,$ n/2 $,$ n{l_3} $个乘法,总计减少$ 2n{l_3} + n/2 $个乘法. 具体而言,选取参数$ n = 648 $和$ q = 2\;917 $时,此时层数分别为$ {l_2} = 1,{l_3} = 4 $. 测试数据均由C语言实现,并采用O3优化指令. 从具体实现的CPU周期数来看,相比未优化的NTT,本文NTT在正向变换、点乘和逆向变换的CPU周期数分别降低24.9%,20.6%,26.8%,总共降低25.3%.
在表3中,困难性假设指的是该方案所基于的困难性问题. 底层PKE指的是该密钥封装方案所蕴含的底层公钥加密方案的属性,其中IND-CPA指不可区分意义下的选择明文安全性,OW-CPA指单向意义下的选择明文安全性,DPKE指确定性的公钥加密方案,RPKE指随机性的公钥加密方案. |pk|,|ct|,B.W.分别指它们的公钥尺寸、密文尺寸和带宽(公钥尺寸+密文尺寸),单位均是 B. Sec-(C, Q)是方案的安全强度,C表示经典安全强度,Q表示量子安全强度. $ \delta $指方案的错误率.
在表4中,KeyGen,Encaps,Decaps对应的列分别给出这些密钥封装方案在密钥生成算法、密钥封装算法和解封装算法运行10000次的平均CPU周期,单位是kcycle.
需要说明的是,NTRU-HRSS,SNTRU Prime-761,NTTRU,Kyber-768的C实现数据均是将它们的开源C代码在同一平台上运行得到的,旨在为它们的C实现效率提供直观的对比. 至于NTRU-HRSS,SNTRU Prime-761,Kyber-768的AVX2实现的测试数据则是取自SUPERCUP (代号为supercop-20220506,测试设备为3.0GHz Intel Xeon E3-1220 v6)[60];SUPERCUP能够提供密码方案的AVX2实现最新最快的测试数据. NTTRU的AVX2测试数据取自文献[26]. $ {\text{NTRU - }} {\rm{A}}_{2\;917}^{648} $的AVX2测试数据则取自文献[27],BAT-512的AVX2测试数据则取自文献[29],CTRU-768的C实现和AVX2实现的测试数据均是取自文献[28]. 需要注意的是,文献[27-28]没有提供开源C代码和AVX2代码,文献[29]只提供AVX2代码. 且文献[27, 29]只提供AVX2实现的测试数据,故为公平比较,表4只展示$ {\text{NTRU - A}}_{2\;917}^{648} $和BAT-512的AVX2实现的测试数据,而不再展示它们的C实现的测试数据.
经表3和表4的数据分析,与其他基于NTRU格的密钥封装方案NTRU-HRSS[20],SNTRU Prime[21],NTTRU[26],NTRU-A[27],CTRU[28],BAT[29],还有基于模格的密钥封装方案Kyber[22]相比,本文的LTRU具有4点优势:
1) 小的公钥尺寸、密文尺寸和带宽
与NTRU-HRSS,SNTRU Prime-761,NTTRU,$ {\text{NTRU - A}}_{2\;917}^{648} $,CTRU-768,Kyber-768对比,LTRU具有更小的密文尺寸和更小的通信带宽. 具体地,与NTRU-HRSS对比,LTRU的公钥尺寸降低14.6%,密文尺寸降低26.0%,带宽降低20.3%. 与SNTRU Prime-761相比,LTRU的公钥尺寸降低16.1%,密文尺寸降低19.0%,带宽降低17.4%. 与Kyber-768相比,LTRU的公钥尺寸降低17.9%,密文尺寸降低22.6%,带宽降低20.2%.LTRU和$ {\text{NTRU - A}}_{2\;917}^{648} $具有相同长度的公钥尺寸,但是LTRU的密文尺寸更小,降低了13.4%. 由于BAT-512使用复杂的纠错码使得它能使用更小的模数,从而它的带宽比LTRU的更有优势,但复杂的纠错码导致它的密钥生成比LTRU的密钥生成慢了3个数量级.
2) 均衡的安全强度、错误率和带宽
由于LTRU的目标安全强度为128 b,所以它的错误率$ {2^{ - 154}} $可视为可忽略. NTRU-HRSS和BAT-512的量子安全强度只有124 b,并没达到128 b.而Kyber-768具有166 b量子安全强度. CTRU-768具有164 b量子安全强度,与128 b的间距过大,造成过剩的安全性.SNTRU Prime-761,NTTRU,$ {\text{NTRU - A}}_{2\;917}^{648} $虽然达到了128 b安全强度,但其带宽都比LTRU的带宽大. 注意到NTRU-HRSS和SNTRU Prime-761均为零错误率,但是它们需要使用更大的模数$ q $,这无疑增加了通信带宽. 所以,与其他方案对比,LTRU达到了128 b安全强度,且具有与安全强度匹配的、可忽略的错误率,同时能够节省通信带宽.
3) 强的底层PKE方案安全性
由于Kyber-768是基于MLWE困难性假设的,而其他方案都是基于NTRU相关的困难性假设,所以为了公平对比,在此只比较LTRU,NTRU-HRSS,SNTRU Prime-761,NTTRU,$ {\text{NTRU - A}}_{2\;917}^{648} $,CTRU-768,BAT-512 的底层PKE方案安全性. 从表3可以看到,LTRU,CTRU-768,BAT-512的底层PKE方案能够达到IND-CPA安全性,而NTRU-HRSS,SNTRU Prime-761,NTTRU,$ {\text{NTRU - A}}_{2\;917}^{648} $的底层PKE方案均是OW-CPA安全的. 其中CTRU-768和BAT-512均基于2个困难性假设,唯有LTRU仅基于NTRU-OW假设而达到IND-CPA安全性. 不容忽视的是,对底层PKE方案来说,IND-CPA安全性比OW-CPA安全性更强.
4) 高效的实现
从表4可知,LTRU具有出色的实现效率. 具体而言,与NTRU-HRSS的C实现相比,LTRU在密钥生成、封装和解封装等算法上分别快了1462.3倍、58.5倍和90.0倍;与NTRU-HRSS的AVX2实现相比,LTRU在密钥生成算法和解封装算法上分别快了10.9倍和1.7倍,其封装算法的速度与NTRU-HRSS的相当. 另外,与SNTU Prime-761的AVX2实现相比,LTRU在密钥生成、封装和解封装等算法上分别快了30.9倍、1.7倍和1.4倍. 主要原因是LTRU使用了本文提出的高效的混合基NTT计算多项式运算, 而NTRU-HRSS和SNTU Prime-761使用的多项式环不是NTT友好的,它们只能使用效率更低的算法计算多项式运算. 与CTRU-768相比,LTRU的C实现在密钥生成、封装和解封装等算法都更有优势,AVX2实现在解封装算法的速度与CTRU-768的相当. 与BAT-512的AVX2实现相比,LTRU在密钥生成算法上快了3个数量级,在解封装算法上快了1.7倍.
我们注意到,NTTRU和$ {\text{NTRU - A}}_{2\;917}^{648} $使用SHA2系列函数来实例化哈希函数,且使用AES算法作为伪随机函数来生成所需的随机数. 相比于本文的LTRU使用的SHA3系列函数,SHA2系列函数和AES算法更易于向量化实现(如AVX2实现). 为方便与NTTRU和$ {\text{NTRU - A}}_{2\;917}^{648} $比较,表4给出了LTRU-SHA2变体的AVX2实现效率的测试数据.LTRU-SHA2变体使用了与NTTRU和$ {\text{NTRU - A}}_{2\;917}^{648} $相同的SHA2哈希函数以及 AES算法. 尽管LTRU (LTRU-SHA2的变体)的AVX2实现效率稍逊于NTTRU和$ {\text{NTRU - A}}_{2\;917}^{648} $,事实上,从表3和表4中LTRU (LTRU-SHA2的变体)的安全性、带宽和实现效率等数据来看,它们已经能够适用于现实多数场景. 另外,与NTTRU相比,LTRU在生成公钥$ h $时只需要对底层的线性多项式求逆,而NTTRU需要计算底层的2次多项式的逆,这明显更复杂. 同时LTRU的模数$q = $ $ 2\;917 $的NTT比NTTRU的模数$ q = 7\;681 $的NTT在计算资源开销和效率上都更有优势.
与Kyber-768相比,LTRU的实现效率全面占优. 具体而言,与Kyber-768的AVX2实现相比,LTRU在密钥生成、封装和解封装等算法上分别快了1.7倍、2.3倍和1.3倍. 这得益于LTRU在密钥生成算法中使用高效混合基NTT以及在加密和解密算法中只需要计算1个多项式乘法. 然而,Kyber在密钥生成算法和加密算法中均需要使用拒绝采样生成矩阵且需要计算多项式矩阵-向量乘法,其中解封装算法中还有重加密和重新计算多项式矩阵-向量乘法的过程,这些操作明显更加耗时. 与之对比,LTRU方案具有运算简单、实现高效等特点.
基于NTRU格的密码系统具有结构简洁、强安全保障、不受专利影响等优势,有利于设计实用化高效的后量子密码方案. 本文提出了一个仅基于NTRU单向困难性假设构造的、不使用纠错码也能够压缩密文的密钥封装方案LTRU. LTRU包含一个IND-CPA安全的公钥加密方案LTRU.PKE以及一个IND-CCA安全的密钥封装方案LTRU.KEM.本文还提供了针对128 b安全强度的参数集,及其对应的C实现和AVX2实现. 针对LTRU所使用的环$ {\mathbb{Z}_{2\;917}}[x]/({x^{648}} - {x^{324}} + 1) $上的多项式乘法和除法,本文提出了一种高效的混合基NTT算法,该算法结合单位根的性质和1-迭代Karatsuba算法来减少乘法的数量,以提高计算效率. 本文实验结果表明,与NIST标准化方案Kyber-768相比,LTRU的公钥尺寸降低17.9%,密文尺寸降低22.6%,带宽降低20.2%;与NIST第3轮决赛方案NTRU-HRSS相比,LTRU的经典安全强度和量子安全强度分别增强6 b和5 b,以及公钥尺寸降低14.6%,密文尺寸降低26.0%,带宽降低20.3%,并且LTRU的实现效率优于NTRU-HRSS.
未来工作主要包括2点:1)对本文提出的LTRU在多平台上实现,包括ARM Cortex-M4实现和FPGA实现等;2)提出更多的LTRU参数集,使其满足更多的应用场景,如资源受限的IoT设备和智能卡等.
作者贡献声明:梁志闯负责方案的设计和论文撰写;郑婕妤负责方案的实现;赵运磊负责论文修改.

参考文献 引证文献
排序方式:
1
Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Review, 1999, 41(2): 303−332
2
NIST. PQC standardization process: Announcing four candidates to be standardized, plus fourth round candidates [EB/OL]. (2022-07-05) [2023-04-10].https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4
3
中国密码学会. 关于全国密码算法设计竞赛算法评选结果的公示[EB/OL]. (2020-01-02)[2023-04-10].https://www.cacrnet.org.cn/site/content/854.html
Chinese Association for Cryptologic Research. Announcement of the selection results of the national cryptographic algorithm competitions [EB/OL](2020-01-02)[2023-04-10]. https://www.cacrnet.org.cn/site/content/854.html (in Chinese).
4
NIST. Post-quantum cryptography round 1 submissions [EB/OL]. (2017-01-03) [2023-04-10]. https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-1-submissions
5
NIST. Post-quantum cryptography round 2 submissions [EB/OL]. (2019-01-30) [2023-04-10].https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-2-submissions
6
NIST. Post-quantum cryptography round 3 submissions [EB/OL]. (2020-07-23) [2023-04-10].https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions
7
Regev O. On lattices, learning with errors, random linear codes, and cryptography[J]. Journal of the ACM, 2009, 56(6): 1−40
8
Banerjee A, Peikert C, Rosen A. Pseudorandom functions and lattices [C] // Proc of the 31st Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2012: 719–737
9
Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings[C] // Proc of the 29th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2010: 1–23
10
Langlois A, Stehlé D. Worst-case to average-case reductions for module lattices[J]. Designs, Codes and Cryptography, 2015, 75(3): 565−599
11
Hoffstein J, Pipher J, Silverman J H. NTRU: A ring-based public key cryptosystem[C] //Proc of the 3rd Int Algorithmic Number Theory Symp. Berlin: Springer, 1998: 267–288
12
Howgrave-Graham N, Silverman J H, Whyte W. Choosing parameter sets for NTRUEncrypt with NAEP and SVES-3[C] //Proc of the Cryptographers’ Track at the RSA Conf. Berlin: Springer, 2005: 118–135
13
Howgrave-Graham N, Silverman J H, Singer A, et al. NAEP: Provable security in the presence of decryption failures [DB/OL]. IACR Cryptology ePrint Archive, 2003 [2023-04-10].https://eprint.iacr.org/2003/172
14
Hoffstein J, Pipher J, Silverman J H. NTRU: A new high speed public key cryptosystem[C] //Proc of the Rump Session of Crypto96. Berlin: Springer, 1996: 1–11
15
Coppersmith D, Shamir A. Lattice attacks on NTRU[C] //Proc of Int Conf on the Theory and Application of Cryptographic Techniques. Berlin: Springer, 1997: 52–61
16
Garg S, Gentry C, Halevi S. Candidate multilinear maps from ideal lattices[C] //Proc of the 32nd Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2013: 1–17
17
Langlois A, Stehlé D, Steinfeld R. GGHLite: More efficient multilinear maps from ideal lattices[C] //Proc of the 33rd Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2014: 239–256
18
Ducas L, Lyubashevsky V, Prest T. Efficient identity-based encryption over NTRU lattices[C] // Proc of the 20th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2014: 22–41
19
Fouque P A, Hoffstein J, Kirchner P, et al. Falcon: Fast-Fourier lattice-based compact signatures over NTRU[EB/OL]. NIST PQC Round 3 Submission, 2020 [2023-04-10].https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions
20
Chen Cong, Danba O, Hoffstein J. et al. NTRU submission[EB/OL]. NIST PQC round 3 submission, 2020 [2023-04-10]. https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions
21
Bernstein D J, Brumley B, Chen M S, et al. NTRU Prime: Round 3[EB/OL]. NIST PQC Round 3 Submission, 2020 [2023-04-10].https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions
22
Avanzi R, Bos J, Ducas L, et al. CRYSTALS-Kyber: Algorithm specifications and supporting documentation (version 3.01)[EB/OL]. NIST PQC Round 3 Submission, 2020 [2023-04-10].https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions
23
NIST. Status report on the third round of the NIST post-quantum cryptography standardization process [EB/OL]. (2022-07-30) [2023-04-10].https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413-upd1.pdf
24
Business Wire. Business wire security innovation’s NTRUEncrypt adopted as X9 standard for data protection [EB/OL]. (2011-04-11) [2023-04-10].https://www.businesswire.com/news/home/20110411005309/en/Security-Innovations-NTRUEncrypt-Adopted-X9-Standard-Data
25
OpenSSH. OpenSSH release notes [EB/OL]. (2022-10-04) [2023-04-10].https://www.openssh.com/releasenotes.html
26
Lyubashevsky V, Seiler G. NTTRU: Truly fast NTRU using NTT[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019, 2019(3): 180−201
27
Duman J, Hövelmanns K, Kiltz E, et al. A thorough treatment of highly-efficient NTRU instantiations [C] //Proc of the 26th IACR Int Conf on Practice and Theory of Public-Key Cryptography. Berlin: Springer, 2023: 65–94
28
Liang Zhichuang, Fang Boyue, Zheng Jieyu, et al. Compact and efficient KEMs over NTRU lattices [DB/OL]. IACR Cryptology ePrint Archive, 2022 [2023-04-10].https://eprint.iacr.org/2022/579
29
Fouque P A, Kirchner P, Pornin T, et al. BAT: Small and fast KEM over NTRU lattices[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022, 2022(2): 240−265
30
D’Anvers J P, Tiepelt M, Vercauteren F, et al. Timing attacks on error correcting codes in post-quantum schemes[C] //Proc of ACM Workshop on Theory of Implementation Security Workshop. New York: ACM, 2019: 2–9
31
Kocher P C. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[C] // Proc of the 16th Annual Int Cryptology Conf. Berlin: Springer, 1996: 104–113
32
Stehlé D, Steinfeld R. Making NTRU as secure as worst-case problems over ideal lattices[C] //Proc of the 30th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2011: 27–47
33
Wang Yang, Wang Mingqiang. Provably secure NTRUEncrypt over any cyclotomic field[C] //Proc of the 25th Int Conf on Selected Areas in Cryptography. Berlin: Springer, 2018: 391–417
34
Jarvis K, Nevins M. ETRU: NTRU over the Eisenstein integers[J]. Designs, Codes and Cryptography, 2015, 74(1): 219−242
35
Hülsing A, Rijneveld J, Schanck J, et al. High-speed key encapsulation from NTRU[C] //Proc of the 17th Int Conf on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2017: 232–252
36
Bernstein D J, Chuengsatiansup C, Lange T, et al. NTRU prime: Reducing attack surface at low cost[C] //Proc of the 24th Int Conf on Selected Areas in Cryptography. Berlin: Springer, 2017: 235–260
37
Bos J, Ducas L, Kiltz E, et al. CRYSTALS-Kyber: A CCA-secure module-lattice-based KEM[C] //Proc of 2018 IEEE European Symp on Security and Privacy. Piscataway, NJ: IEEE, 2018: 353–367
38
Bellare M, Rogaway P. Random oracles are practical: A paradigm for designing efficient protocols[C] //Proc of the 1st ACM Conf on Computer and Communications Security. New York: ACM, 1993: 62–73
39
Boneh D, Dagdelen Ö, Fischlin M, et al. Random oracles in a quantum world[C] //Proc of the 17th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2011: 41–69
40
Bernstein D J. Multidigit multiplication for mathematicians [EB/OL]. (2001-09-12) [2023-04-10]. http://cr.yp.to/papers.html#m3
41
Cooley J W, Tukey J W. An algorithm for the machine calculation of complex Fourier series[J]. Mathematics of Computation, 1965, 19(90): 297−301
42
Gentleman W M, Sande G. Fast Fourier transforms: For fun and profit[C] // Proc of the AFIPS’66 Fall Joint Computer Conf. New York: ACM, 1966: 563–578
43
Weimerskirch A, Paar C. Generalizations of the Karatsuba algorithm for efficient implementations [DB/OL]. IACR Cryptology ePrint Archive, 2006 [2023-04-10].https://eprint.iacr.org/2006/224
44
Fujisaki E, Okamoto T. Secure integration of asymmetric and symmetric encryption schemes[J]. Journal of Cryptology, 2013, 26(1): 80−101
45
Hofheinz D, Hövelmanns K, Kiltz E. A modular analysis of the Fujisaki-Okamoto transformation[C] //Proc of the 15th Theory of Cryptography Conf. Berlin: Springer, 2017: 341–371
46
Shoup V. Sequences of games: A tool for taming complexity in security proofs [DB/OL]. IACR Cryptology ePrint Archive, 2004 [2023-04-10].https://eprint.iacr.org/2004/332
47
Don J, Fehr S, Majenz C, et al. Online-extractability in the quantum random-oracle model [C] //Proc of the 41st Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2022: 677–706
48
Kannan R. Minkowski’s convex body theorem and integer programming[J]. Mathematics of Operations Research, 1987, 12(3): 415−440
49
Bai Shi, Galbraith S D. Lattice decoding attacks on binary LWE[C] //Proc of the 19th Australasian Conf on Information Security and Privacy. Berlin: Springer, 2014: 322–337
50
Schnorr C P, Euchner M. Lattice basis reduction: Improved practical algorithms and solving subset sum problems[J]. Mathematical Programming, 1994, 66(1): 181−199
51
Chen Yuanmi, Nguyen P Q. BKZ 2.0: Better lattice security estimates[C] //Proc of the 17th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2011: 1–20
52
Alkim E, Ducas L, Pöppelmann T, et al. Post-quantum key exchange—A new hope[C] //Proc of the 25th USENIX Security Symp. Berkeley: USENIX Association, 2016: 327–343
53
Albrecht M R, Curtis B R, Deo A, et al. Estimate all the {LWE, NTRU} schemes![C] //Proc of the 11th Int Conf on Security and Cryptography for Networks. Berlin: Springer, 2018: 351–367
54
Albrecht M, Bai Shi, Ducas L. A subfield lattice attack on overstretched NTRU assumptions[C] //Proc of the 36th Annual Int Cryptology Conf. Berlin: Springer, 2016: 153–178
55
Howgrave-Graham N. A hybrid lattice-reduction and meet-in-the-middle attack against NTRU[C] // Proc of the 27th Annual Int Cryptology Conf. Berlin: Springer, 2007: 150–169
56
Hassan C A, Yayla O. Radix-3 NTT-based polynomial multiplication for lattice-based cryptography [DB/OL]. IACR Cryptology ePrint Archive, 2022 [2023-04-10].https://eprint.iacr.org/2022/726
57
Barrett P. Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor[C] //Proc of Conf on the Theory and Application of Cryptographic Techniques. Berlin: Springer, 1986: 311–323
58
Montgomery P L. Modular multiplication without trial division[J]. Mathematics of Computation, 1985, 44(170): 519−521
59
Seiler G. Faster AVX2 optimized NTT multiplication for ring-LWE lattice cryptography [DB/OL]. IACR Cryptology ePrint Archive, 2018 [2023-04-10].https://eprint.iacr.org/2018/039
60
Bernstein D J, Lange T. eBACS: ECRYPT benchmarking of cryptographic systems [EB/OL]. (2022-06-19) [2023-04-10].https://bench.cr.yp.to
2024年第61卷第4期
92
44
0
引用本文
BibTeX
文章信息
doi: 10.7544/issn1000-1239.202220980
  • 接收时间:2022-11-30
  • 首发时间:2026-11-17
  • 出版时间:2024-04-01
补充材料
相关文章
文章信息
作者
出版历史
  • 收稿日期:2022-11-30
  • 修回日期:2023-05-15
基金
作者信息
    1复旦大学计算机科学技术学院 上海 200433
    2密码科学技术国家重点实验室 北京 100036

通讯作者:

赵运磊()
参考文献
分享链接
https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202220980
分享至
全文二维码

扫描看全文

引用本文
BibTeX
本文的引用情况
2种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏