Secure strong mapping computing systems, methods, secure computing apparatus and program

A secure strong mapping computing method,

• where Fk and Fv are arbitrary rings;
• [α] is a share generated by secret sharing of α, with α being an arbitrary vector or permutation;
• m and n are predetermined integers greater than or equal to 1;
• u is a predetermined outlier value;
• r∈Fkm is a predetermined vector with elements different from each other;
• and d∈Fvm and x∈Fkn are predetermined vectors,
• the secure strong mapping computing method comprising:
• a first vector joining step performed by a plurality of secure computing apparatuses cooperating with each other and in which a plurality of first vector joining units use a share [r] of the vector r and a share [x] of the vector x to generate a share [k] of a vector k∈[Fk]2m+n which is generated by joining the vector r, the vector x, and the same vector as the vector r;
• a first permutation calculation step performed by the plurality of secure computing apparatuses cooperating with each other and in which a plurality of first permutation calculation units use the share [k] to generate a share [σ] of a permutation σ for stable sorting of the vector k;
• a first vector generation step performed by the plurality of secure computing apparatuses cooperating with each other and which a plurality of first vector generation units use a share [d] of the vector d and u to generate a share [d′] of a vector d′, which is a vector generated by subtracting u from respective elements of the vector d;
• a second vector joining step performed by the plurality of secure computing apparatuses cooperating with each other and in which a plurality of second vector joining units use the share [d′] to generate a share [v] of a vector v∈[Fv]2m+n which is generated by joining the vector d′, a 0-vector with a number of elements of n, and a vector −d′ which is a vector generated by inverting signs of respective elements of the vector d′;
• a first permutation application step performed by the plurality of secure computing apparatuses cooperating with each other and in which a plurality of first permutation application units use the share [v] and the share [σ] to generate a share [σ(v)] of a vector σ(v) which is generated by application of the permutation σ to the vector v;
• a second vector generation step performed by the plurality of secure computing apparatuses cooperating with each other and in which a plurality of second vector generation units use the share [σ(v)] to generate a share [σ(y)] of a vector σ(y), each element of which is a sum of the u and a sum of elements of the vector σ(v) up to an element corresponding to that element, the elements including the element corresponding to that element;
• a first inverse permutation application step performed by the plurality of secure computing apparatuses cooperating with each other and in which a plurality of first inverse permutation application units use the share [σ(y)] and the share [σ] to generate a share [σ−1(σ(y))] of a vector σ−1(σ(y)) which is generated by application of an inverse permutation σ−1 of the permutation σ to the vector σ(y);
• and
• a first vector extraction step performed by the plurality of secure computing apparatuses cooperating with each other and in which a plurality of first vector extraction units use the share [σ−1(σ(y))] to obtain a share [y] of a vector y which is generated by extracting m+1th to m+nth elements of the vector σ−1(σ(y)),
• wherein the share [y] includes identification of outliers.