Public Key, Set-(bi)partition

From: Kiuhnm (invalid_at_invali.it)
Date: 04/23/04 

Date: Fri, 23 Apr 2004 18:25:11 GMT

    The set-(bi)partition problem [SBP] consists in splitting a finite set S
of (real) numbers into two disjoint sets A and B such that the sum of the
elements in A is equal to that of the elements in B.

    SBP can be reformulated this way:
let A = {a_0, ..., a_n} and X = {x_0, ..., x_n} be two finite vectors of 'n'
(real) numbers. Estimate X such that <A, X> = 0 and x_i^2 = 1.

    Given a unique solution X, it's easy to generate 's' vectors A_i such
that <A_i, X> = 0.
This version of SBP should be as hard as the normal version with max(n-s, 0)
elements.

    Let 'k' be an integer number, A_i "SBP-vectors" with the same solution,
B_i random vectors, M the plaintext and C(X) the encrypted text defined as
C(X) = <A_0, X>*<B_0, X> + ... + <A_k, X>*<B_k, X> + M

    The polynomial C(X) "should" have n(n+1)/2 terms:
x_1 x_1, x_1 x_2, x_1 x_3, ....., x_1 x_n,
x_2 x_2, x_2 x_3, ......, x_2 x_n,
.
.
.
x_n x_n.

    We are interested in the relative coefficients.
The vectors A_i belong to the Public Key while the vectors B_i are unknown
and completely random.
When 'n' is small enough, it should be impossible to estimate the unknown
coefficients of the vectors B_i, but we want to use a big 'n'.
    First of all let's "eliminate" the quadratic terms x_i^2 by noting that
x_i^2 = 1. I (probably in my ignorance!) think this is the tricky part :-)
This way all the coefficients of the terms x_i^2 will perturb M.
The correct number of terms is therefore n(n-1)/2 + 1 (considering also the
"perturbed" M).

    We used 'k' SBP-vectors in C(x) then the eventual linear system used
to estimate the random coefficients will have kn variables and n(n-1)/2
equations. If k > (n-1)/2, the system will have infinite solutions.
Definitively we want to choose 'k' such that (n-1)/2 < k < n and n-k is
sufficiently big.

    Note that if x_i^2 <> 1 for some 'i' then the probability to be able to
reobtain M is very low.
Note also that C(X) = C(-X) in fact x_i x_j = (-x_i)(-x_j).

    The Private Key is obviously represented by the unique solution to the
'k' SBP-vectors.

Kiuhnm 

--
171df91e41c28448937c01c489acb61291215253

Relevant Pages

  • Re: Nonlinear Least-Squares curve-fitting
    ... coefficients in the model) was aptly described by Reef Fish. ... Rotate this valley so that it's at about a 45 ... represent lines of constant residual sums of squares. ... residual sum of squares is a constant at all points on a given contour ...
    (sci.stat.math)
  • Re: Nonlinear Least-Squares curve-fitting
    ... The root of many difficulties with nonlinear regression (nonlinear ... coefficients in the model) was aptly described by Reef Fish. ... represent lines of constant residual sums of squares. ... residual sum of squares is a constant at all points on a given contour ...
    (sci.stat.math)
  • Re: sum of roots of unity
    ... The sum of the roots of a monic polynomial is ... I'm guessing my posts are being filtered? ... of comparing coefficients -- I believe that the ...
    (sci.math)
  • Re: FFT with semi-implicite scheme
    ... subjected to periodic boundary conditions. ... If we call a_k and b_k the Fourier coefficients of the ... Can somebody tell me in some detail how can adjust the FFT ... that in order to get rid of the coupling I should have taken the sum ...
    (comp.soft-sys.matlab)
  • Re: calculating PI
    ... so P is the sum of the series up to that point. ... average it with the second-last P, and average that average with the ... averaging expression. ... The 16 is just the sum of all the coefficients in the brackets. ...
    (comp.lang.basic.misc)