Hmm… an idea comes to mind how to do Private Intersection Set via virtual sequential logic circuit run ontop of Ueli Maurer’s SMPC.
Aside: How to get an sequential logic circuit to work on that? Basically by adding a delay cell to the primitive compontents the SMPC supports. What is an delay cell in this context? Basically a component that acts both as an Output and an Input only the wire value outputed from previous tau/comm-round is the Input wire value this tau/comm-round. Implemented by having each SMPC node hold onto their secret-shares for the wire value to the Output from this tau/comm-round and use them directly as their secret-shares for the wire value for the Input wire.
Here is how the PIS circuit would look like: Think of a k by k grid of tag-value eq-comparators.
Each eq-comparator two value inputs are connected to a value bus running horizationally above it and a value bus running vertically left of it respectively.
The horizationally running buses are driven by Inputs from Alice whilist the vertical ones are driven by Inputs from Bob.
Hold on what is an eq-comparator, you ask? It is a rather simple composite device made up of x many XNOR gates and an multi input AND gate, where x is the bit width of the two input buses of the device.
An XNOR gate itself is a composite made of an XOR gate, which is an primitive, whose output feeds into a NOT gate.
The NOT gate is basically an XOR gate whose one input is from the VCC wire, which should always have the wire value one, and the other is the NOT gate input.
And the VCC wire comes from the output of an AND gate whose inputs comes from VCC labeled Inputs from both Alice and Bob respectively. Btw the VCC feeds to an ON indicator Outputs to Alice and Bob.
So back to the grid of the eq-comparators. The outputs of each eq-comparator in a column feeds into an multi input XOR gate for that column. Same way for rows. This means each eq-comparator output feeds into two multi input XOR gates, one for the column it is in and one for the row it is in.
These column XOR gates’ outputs feed into Outputs to Alice. The row ones feed into Outputs to Bob.
This means that Alice gets to know which tag-value Input columns she shares with Bob.
Bob gets to know which tag-value Input rows he shares with Alice.
However neither gets to know the others other tag-values nor which corrisponding others rows or columns.
There is just a tiny teeny problem with this circuit. As multi input OR gates are quite a bit expensive to compose in this SMPC setup (basically an NAND gate with inverted inputs, and the AND gates costs in tau/comm-round delay) I used an multi input XOR gate. Which I can get away with iff all but one of its inputs is zero.
Alice (or Bob) could feed the same tag-value into two diffrent column/row Inputs thereby denying Bob (or Alice) knowledge that they have the tag-value in common yet learning that Bob (or Alice) has it.
But not to worry, we can add eq-comparators to compare each column (or row) tag-values with every other such and have an Output flags to both Alice and Bob telling them that the other party had put the same tag-value more than once whilist also preventing the column/row outputs.
Or it might be cheaper to just use an multi input OR gate instead of the last XOR gate in each column/row.
Here it is as a BLIF:
# extended Berkley Logic Interchange Format
# basically a .bus command added
# k is 4 in this example
.model PIS
.inputs VCC
.inputs Alice_I1 Alice_I2 Alice_I3 Alice_I4
.inputs Bob_I2 Bob_I2 Bob_I3 Bob_I4
.outputs Alice_O1 Alice_O2 Alice_O3 Alice_O4
.outputs Bob_O1 Bob_O2 Bob_O3 Bob_O4
.subckt eq_comp VCC=VCC a=Alice_I1 b=Bob_I1 o=tmp0
.subckt eq_comp VCC=VCC a=Alice_I1 b=Bob_I2 o=tmp1
.subckt eq_comp VCC=VCC a=Alice_I1 b=Bob_I3 o=tmp2
.subckt eq_comp VCC=VCC a=Alice_I1 b=Bob_I4 o=tmp3
.subckt eq_comp VCC=VCC a=Alice_I2 b=Bob_I1 o=tmp4
.subckt eq_comp VCC=VCC a=Alice_I2 b=Bob_I2 o=tmp5
.subckt eq_comp VCC=VCC a=Alice_I2 b=Bob_I3 o=tmp6
.subckt eq_comp VCC=VCC a=Alice_I2 b=Bob_I4 o=tmp7
.subckt eq_comp VCC=VCC a=Alice_I3 b=Bob_I1 o=tmp8
.subckt eq_comp VCC=VCC a=Alice_I3 b=Bob_I2 o=tmp9
.subckt eq_comp VCC=VCC a=Alice_I3 b=Bob_I3 o=tmpA
.subckt eq_comp VCC=VCC a=Alice_I3 b=Bob_I4 o=tmpB
.subckt eq_comp VCC=VCC a=Alice_I4 b=Bob_I1 o=tmpC
.subckt eq_comp VCC=VCC a=Alice_I4 b=Bob_I2 o=tmpD
.subckt eq_comp VCC=VCC a=Alice_I4 b=Bob_I3 o=tmpE
.subckt eq_comp VCC=VCC a=Alice_I4 b=Bob_I4 o=tmpF
.subckt or_4in VCC=VCC a=tmp0 b=tmp1 c=tmp2 d=tmp3 x=Alice_O1
.subckt or_4in VCC=VCC a=tmp4 b=tmp5 c=tmp6 d=tmp7 x=Alice_O2
.subckt or_4in VCC=VCC a=tmp8 b=tmp9 c=tmpA d=tmpB x=Alice_O3
.subckt or_4in VCC=VCC a=tmpC b=tmpD c=tmpE d=tmpF x=Alice_O4
.subckt or_4in VCC=VCC a=tmp0 b=tmp4 c=tmp8 d=tmpC x=Bob_O1
.subckt or_4in VCC=VCC a=tmp1 b=tmp5 c=tmp9 d=tmpD x=Bob_O2
.subckt or_4in VCC=VCC a=tmp2 b=tmp6 c=tmpA d=tmpE x=Bob_O3
.subckt or_4in VCC=VCC a=tmp3 b=tmp7 c=tmpB d=tmpF x=Bob_O4
.end
.model eq_comp
.inputs VCC
.inputs a b
.outputs o
# we assume here that a and b are buses of bitwidth 16 but most likely would be 128 or 256 in non-example use
.bus bus=a w0=a0 w1=a1 w2=a2 w3=a3 w4=a4 w5=a5 w6=a6 w7=a7 w8=a8 w9=a9 wA=aA wB=aB wC=aC wD=aD wE=aE wF=aF
.bus bus=b w0=b0 w1=b1 w2=b2 w3=b3 w4=b4 w5=b5 w6=b6 w7=b7 w8=b8 w9=b9 wA=bA wB=bB wC=bC wD=bD wE=bE wF=bF
.subckt xnor VCC=VCC a=a0 b=b0 x=t0
.subckt xnor VCC=VCC a=a1 b=b1 x=t1
.subckt xnor VCC=VCC a=a2 b=b2 x=t2
.subckt xnor VCC=VCC a=a3 b=b3 x=t3
.subckt xnor VCC=VCC a=a4 b=b4 x=t4
.subckt xnor VCC=VCC a=a5 b=b5 x=t5
.subckt xnor VCC=VCC a=a6 b=b6 x=t6
.subckt xnor VCC=VCC a=a7 b=b7 x=t7
.subckt xnor VCC=VCC a=a8 b=b8 x=t8
.subckt xnor VCC=VCC a=a9 b=b9 x=t9
.subckt xnor VCC=VCC a=aA b=bA x=tA
.subckt xnor VCC=VCC a=aB b=bB x=tB
.subckt xnor VCC=VCC a=aC b=bC x=tC
.subckt xnor VCC=VCC a=aD b=bD x=tD
.subckt xnor VCC=VCC a=aE b=bE x=tE
.subckt xnor VCC=VCC a=aF b=bF x=tF
.subckt and_16in i0=t0 i1=t1 i2=i3 i4=t4 i5=t5 i6=t6 i7=t7 i8=t8 i9=t9 iA=tA iB=tB iC=tC iD=tD iE=tE iF=tF o=o
.end
.model and_16in
.inputs i0 i1 i2 i3 i4 i5 i6 i7 i8 i9 iA iB iC iD iE iF
.outputs o
.subckt and_4in a=i0 b=i1 c=i2 d=i3 x=t0
.subckt and_4in a=i4 b=i5 c=i6 d=i7 x=t1
.subckt and_4in a=i8 b=i9 c=iA d=iB x=t2
.subckt and_4in a=iC b=iD c=iE d=iF x=t3
.subckt and_4in a=t0 b=t1 c=t2 d=t3 x=o
.end
.model and_4in
.inputs a b c d
.outputs x
.gate AND a=a b=b x=t0
.gate AND a=c b=d x=t1
.gate AND a=t0 b=t1 x=x
.end
.model or_4in
.inputs VCC
.inputs a b c d
.outputs x
.subckt or_2in VCC=VCC a=a b=b x=t1
.subckt or_2in VCC=VCC a=c b=d x=t2
.subckt or_2in VCC=VCC a=t1 b=t2 x=x
.end
.model or_2in
.inputs VCC
.inputs a b
.outputs x
.subckt not VCC=VCC a=a x=t1
.subckt not VCC=VCC a=b x=t2
.subckt nand_2in VCC=VCC a=t1 b=t2 x=x
.end
.model nand_2in
.inputs VCC
.inputs a b
.outputs x
.gate AND a=a b=b x=t1
.subckt not VCC=VCC a=x x=x
.end
.model not
.inputs VCC a
.outputs x
.gate XOR a=a b=VCC x=x
.end