Private Function Evaluation In Malicious Adversary Model

In this paper we consider the Private Function Computation（PFE）protocol with the linear malicious adversary model.In constructing linear active PFE,one essential building block is to prove the correctness of an extended permutation（EP,Mohassel and Sadeghian at EUROCRYPT 2013）by zero-knowledge protocols with linear complexity.Mohassel,Sadeghian and Smart（ASIACRYPT 2014）proposed ZK_EPto complete the proof of EP.It is a three-phase protocol,and each phase（dummy placement,replication,and permutation）is of size 2g（g is the number of the gates in the circuit）.Its overhead thus seems really outrageous,reducing its practicability.We propose the following three contribution points in this paper in order to improve the usefulness of the PFE protocol with the linear malicious adversary model.（1）We present a novel and efficient framework ZK_DSfor proving the correct EP.We show that double shuffles suffice for EP and no replication phase is required where ZK_DS:one shuffle is of size u+g-o（u is the number of input wires in the circuit and o the number of output wires,g?u,u≈o）,another is of size 2g.Data owner（s）gen-erates the randomness for the first shuffle whose outputs determine outgoing wires of the circuit C_fdefined by the the private function f.Function owner reuses and extends the randomness in the second shuffle whose outputs determine the incoming wires.The computational costs and communication overheads of ZK_DSare only about 27%and31%of ZK_EP,respectively.（2）From ZK_DS,we build a generic construction of 2-party PFE protocol with constant rounds and linear complexity in the malicious adversary model.There is hith-erto only one concrete design of actively secure 2-party PFE protocol（Liu et al.at PKC2022,and LWY hereafter）with constant rounds and linear complexity.One interesting feature of LWY is its function reusability（i.e.,the same function is involved in mul-tiple executions of LWY）which makes its execution more efficiently from the second execution.Nevertheless,in its first execution,LWY is quite involved and inefficient.Our 2-party PFE protocol has better performance and reduces 51.2%communication bits and 52.4%computation costs,compared to the first execution of LWY at the same security level.It even outperforms several 2-party PFE protocols（Katz and Malka at AISACRYPT 2011,and Mohassel and Sadeghian at EUROCRYPT 2013）that are se-cure in the semi-honest adversary model from the communication perspective.The proposed PFE and LWY thus make optimal solutions available for non-reusable and reusable private functions,respectively.（3）From ZK_DS,we build the m-party PFE framework with linear active secu-rity.There is hitherto only one actively secure m-party PFE framework（Mohassel,Sadeghian,and Smart at ASIACRYPT 2014）with linear complexity.However it is based on the expensive ZK_EPto designed framework,which will cause the costs of total protocol becoming impractical.Our m-party PFE framework is based on the less overhead ZK_DSdesign,which is more compact for practical applications.