The Design And Analysis Of Several Pseudorandom Functions Based On Permutations

Pseudorandom functions(PRFs)have many applications,as one of fundamental objects in cryptography.One can use PRFs to design symmetric encryption schemes,key derivation functions,and message authentication codes(MACs),etc.In addition,the security of randomized tweakable circular correlation robust(RTCCR)function used in circuit garbling schemes is equivalent to the one of input-restricted tweakable PRFs,Therefore,it is valuable to construct secure and efficient PRFs or their corresponding variations.Since there are abundant design methods and plenty of instances for pseudorandom permutations(instantiated by block ciphers)and public permutations,to build PRFs based on permutations is an effective design strategy.In particular,to construct beyondbirthday-bound(BBB)secure variable-input-length(VIL)PRFs from pseudorandom permutations(PRPs)and to construct BBB secure fixed-input-length(FIL)PRFs from public permutations are two research topics currently being investigated,and they can be used to construct lightweight MACs and symmetric encryption algorithms,respectively.Meanwhile,the fixed-key block ciphers were utilized to design the RTCCR functions in circuit garbling schemes for the efficiency.However,there are still some shortcomings and gaps in the research on the above mentioned topics.Therefore,we mainly focus on the design and analysis of several PRFs based on permutations in this dissertation.The main contents and innovations of this dissertation are as follows:1.A new paradigm is proposed to design VIL PRFs,and five concrete constructions of VIL PRFs with BBB security are presented.VIL PRFs are mainly used to construct MACs.In this dissertation,we propose a new design paradigm for VIL PRFs based on PRPs and double-block hash functions,named two-key DbHtEDM(Double-block Hash-then-EDM)paradigm.Compared with the previous well-known two-key DbHtS(Double-block Hash-then-Sum)paradigm,more double-block hash functions with good computational performance can be instantiated under our two-key DbHtEDM paradigm,so that more VIL PRFs with BBB security can be obtained.This work provides a theoretical foundation for the construction of secure and efficient MACs.2.The multi-user security of two permutation-based FIL PRFs is analyzed,and a FIL PRF with a minimal structure is constructed based on a single public permutation.The FIL PRFs are suitable for Counter Mode.In this dissertation,we prove that both of the SoEM22 PRF(CRYPTO 2019)and the pEDM PRF(FSE 2022)can achieve the BBB security,in the multi-user setting.Furthermore,we propose a new FIL PRF with a minimal structure by using only a single public permutation(evaluated in forward direction)and an n-bit key,and then we prove that this construction can achieve almost the 2n/3-bit security.This work fills the research gap in the related field.3.It is the first time to analyze the post-quantum security of RTCCR function used in garbling schemes.Three-halves garbling scheme was proposed at CRYPTO 2021,and its security depends on the underlying RTCCR function which was constructed from fixed-key block ciphers.We prove the post-quantum security of the original RTCCR function used in three-halves garbling scheme,in the ideal model.In addition,we propose a new construction of RTCCR function based on block ciphers with a better post-quantum security in the ideal cipher model.This work provides a theoretical foundation for the security of garbling schemes in the quantum computing setting.4.An efficient tweakable PRF is designed based on a single public permutation and a binary linear code,and a corresponding private set intersection(PSI)protocol is constructed.By using a public permutation(instantiated by ChaCha20 permutation with 512 bits)and a binary linear code,we construct a tweakable PRF with good performance on computation,and then we apply it to construct a PSI protocol.Then we prove that this PSI protocol is secure against the semi-honest sender and the malicious receiver,in this dissertation.The final comparison with other related protocols shows that our implemented protocol performs well in the high bandwidth setting.