Many evidences have showed that some intelligence agen-cies(often called big brother)attempt to monitor citizens'communica-tion by providing coerced citizens a lot of subverted cryptographic algo-rithms and coercing them to adopt these algorithms.Since legalized services on large number of various applications and system architec-tures depend on digital signature techniques,in the context some coerced users who use double authentication preventing signatures to design some novel digital signature techniques,have some convincing disserta-tions to defuse requests from authorities and big brothers creating some corresponding subverted signatures.As rapid progress in quantum com-puters,National Security Agency advisory memorandum and an-nouncement of National Institute of Standards and Technology proce-dures from standardization focus on some cryptographic algorithms which are post quantum secure.Motivated by these issues,we design an algorithm substitution attack against Fiat-Shamir family based on lattices(e.g.,BLISS,BG,Ring-TESLA,PASSSign and GLP)that are proven post-quantum computational secure.We also show an efficient deterable way to eliminate big brother's threat by leaking signing keys from signatures on two messages to be public.Security proof shows that our schemes satisfy key extraction,un-detectability and deterability.Through parameters analysis and performance evaluation,we demonstrate that our deterring sub-verted Fiat-Shamir signature is practical,which means that it can be applied to privacy and protection in some system architectures.

LIU Jinhui;YU Yong;WU Fusheng;CHENG Yuehua;ZHANG Huanguo

School of Cyber Security,Northwestern Polytechnical University,Xi'an 710072,Shaanxi,China;Research&Development Institute of Northwestern Polytechnical University,Shenzhen 518057,Guangdong,China;School of Cyber Security,Xi'an University of Posts and Telecommunications,Xi'an 710121,Shaanxi,China;School of Computer Science,Guizhou University of Finance and Economics,Guiyang 550025,Guizhou,China;School of Computer Science,Wuhan University,Wuhan 430072,Hubei,China

武汉大学自然科学学报（英文版）

[1]LIU Jinhui;YU Yong;WU Fusheng;CHENG Yuehua;ZHANG Huanguo-.An Algorithm Substitution Attack on Fiat-Shamir Signatures Based on Lattice)[J].武汉大学自然科学学报（英文版）,2022(01):17-25

agen,coerced,subverted,coercing,disserta,defuse,brothers,puters,memorandum,nouncement,proce,dures,BLISS,PASSSign,deterable,deterability

An,Algorithm,Substitution,Attack,Fiat,Shamir,Signatures,Based,Lattice,Many,evidences,have,showed,that,some,intelligence,cies,often,called,big,attempt,monitor,citizens,communica,by,providing,lot,cryptographic,them,adopt,these,algorithms,Since,legalized,services,large,number,various,applications,system,depend,digital,techniques,context,users,who,double,authentication,preventing,signatures,design,novel,convincing,requests,from,authorities,creating,corresponding,rapid,progress,quantum,National,Security,Agency,advisory,Institute,Standards,Technology,standardization,focus,which,are,post,secure,Motivated,issues,substitution,attack,against,family,lattices,BG,Ring,TESLA,GLP,proven,computational,We,also,efficient,way,eliminate,threat,leaking,signing,keys,two,messages,public,proof,shows,our,schemes,satisfy,extraction,detectability,Through,parameters,analysis,performance,evaluation,demonstrate,deterring,practical,means,can,applied,privacy,protection,architectures

0.517911