Research on efficient and scalable private set intersection cardinality schemes

To address the issue of high computational overhead in existing two-party private set intersection cardinality (PSI-CA) protocols, an efficient two-party PSI-CA protocol was proposed. Oblivious key-value store (OKVS) and oblivious key-sharing pseudorandom function (OKS-PRF) were leveraged by this protocol to hide information of intersection elements, with execution time being significantly optimized. Moreover, the protocol could be extended to multi-party PSI-CA scenarios. Experimental results show that when the set size is <inline-formula><alternatives><math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M5"><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mn mathvariant="normal">20</mn></mrow></msup></math><graphic specific-use="big" xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="alternativeImage/19E755A3-C80E-497d-B7BF-5325045D78BF-M005.jpg"><?fx-imagestate width="3.72533321" height="2.45533323"?></graphic><graphic specific-use="small" xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="alternativeImage/19E755A3-C80E-497d-B7BF-5325045D78BF-M005c.jpg"><?fx-imagestate width="3.72533321" height="2.45533323"?></graphic></alternatives></inline-formula>, the proposed two-party PSI-CA protocol completes in 36.61 seconds, and the execution speed is 1.8 times than the fastest existing two-party protocol. When the number of participants is <inline-formula><alternatives><math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M6"><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mn mathvariant="normal">3</mn></mrow></msup></math><graphic specific-use="big" xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="alternativeImage/19E755A3-C80E-497d-B7BF-5325045D78BF-M006.jpg"><?fx-imagestate width="2.70933342" height="2.45533323"?></graphic><graphic specific-use="small" xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="alternativeImage/19E755A3-C80E-497d-B7BF-5325045D78BF-M006c.jpg"><?fx-imagestate width="2.70933342" height="2.45533323"?></graphic></alternatives></inline-formula>and the set size is <inline-formula><alternatives><math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M7"><msup><mrow><mn mathvariant="normal">2</mn></mrow><mrow><mn mathvariant="normal">20</mn></mrow></msup></math><graphic specific-use="big" xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="alternativeImage/19E755A3-C80E-497d-B7BF-5325045D78BF-M007.jpg"><?fx-imagestate width="3.72533321" height="2.45533323"?></graphic><graphic specific-use="small" xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="alternativeImage/19E755A3-C80E-497d-B7BF-5325045D78BF-M007c.jpg"><?fx-imagestate width="3.72533321" height="2.45533323"?></graphic></alternatives></inline-formula>, the proposed multi-party PSI-CA protocol completes in 115.32 seconds and can resist collusion among up to <inline-formula><alternatives><math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="M8"><mi>N</mi><mo>-</mo><mn mathvariant="normal">2</mn></math><graphic specific-use="big" xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="alternativeImage/19E755A3-C80E-497d-B7BF-5325045D78BF-M008.jpg"><?fx-imagestate width="7.70466709" height="2.28600001"?></graphic><graphic specific-use="small" xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="alternativeImage/19E755A3-C80E-497d-B7BF-5325045D78BF-M008c.jpg"><?fx-imagestate width="7.70466709" height="2.28600001"?></graphic></alternatives></inline-formula> participants.