(l × X)
mod M =
{
(l ×
x1)
mod M,
(l ×
x2)
mod M, ...,
(l ×
xn)
mod M
}
where l and M are integers. To ensure
practicality in a cryptographic sense, such modulo multiplication
must be invertible, i.e. the transformation must ensure that the
integers contributing to a subset sum can be uniquely (and
efficiently) identified.
Let
s1,
s2, ...
sk,
be random positive integers greater than 1 such that
s1 +
s2 + ... +
sk =
w, for 0<i<k+1,
where w is the number of weights of the key set(s).
Let D =
{
d1,1,
d1,2,
...
d1,s1,
d2,1,
d2,2,
...
d2,s2,
dk,1,
dk,2,
...
dk,sk
}
be the decryption key set, where si =
si for
0<i<k+1.
Let E =
{
e1,1,
e1,2,
...
e1,s1,
e2,1,
e2,2,
...
e2,s2,
ek,1,
ek,2,
...
ek,sk
}
be the encryption key set, where si =
si for
0<i<k+1.
Let N =
{
ni:
i = 1, 2, 3, ...., p
} be the decryption noise set
Let O =
{
oi:
i = 1, 2, 3, ...., p
} be the encryption noise set
ei,j
is derived from
di,j and
oi,j
is derived from
ni,j
Let
f(u, i, j)
=
gi,j,1(u,
ni,j,1) +
gi,j,2(u,
ni,j,2)
+ ... +
gi,j,t(u,
ni,j,t),
where
ni,j,v belongs to N
for 0<v<t+1 is associated with
di,j for decryption, and
g: Z ---> Z.
We require that f retain the invertibility of the
transformations of the cryptographic scheme.
Let
f -1(u,
i, j) =
gi,j,1(u,
oi,j,1) +
gi,j,2(u,
oi,j,2)
+ ... +
gi,j,t(u,
oi,j,t),
where
oi,j,v belongs to O
for 0<v<t+1 is associated with
ei,j for encryption.
Let mi,j be the maximum number of
ei,j's that can be taken to form subset
sums (or ciphertext blocks), where mi,j
can be set to 2h-1 for some positive
integer h > 2.
set D, N, E and
O to empty.
for i from 1 to k
for j from 1 to si
generate zero or more
[3]
random noise elements
ni,j,v and put them in both
N and O, for
v = 1, 2, ..., t
define f(u, i,
j) (gi,j,v(
u, ni,j,v) for
v = 1, 2, ..., t) to
map di,j to the generated
ni,j,v, for
-1<u<mi,j+1
generate random di,j >
F(U)
and put it in both E and D,
where U is the union of E
and O.
end
iterate U (but retaining the identity of
E and O)
end
permute E and O, and adjust
f to retain the original mapping to elements in
O,
(i.e. any e in E maps to the same
element(s) in O before and after the permutation)
Public: Q, O and
f -1, where Q =
{ qi,j:
0<i<k+1,
0<j<sk+1
} is the permuted E
Private: D, N,
f, si, and l,
l-1 and M for each of the
modular multiplications, as well as the permutation
Let plaintext P be transformed to blocks:
B =
{
b1,1,
b1,2, ...,
b1,s1,
b2,1,
b2,2, ...,
b2,s2, ...,
bk,1,
bk,2, ...,
bk,sk
} such that
-1<bi,j<mi,j+1.
A ciphertext block C is defined to be:
C <--- SUM
(
bi,j
×
qi,j
+
f -1
(
bi,j,
i,
j
)
)
for
0<i<k+1,
0<j<sk+1
for i from k down to 1
reverse-iterate C
(i.e. C <--- (l-1 ×
C) mod M)
for j from si down to 1
pi,j <--- C /
di,j,
where the division discards fractions
C <--- C -
(pi,j
× di,j +
f -1
(pi,j,
i, j))
end
end
permute the pi,j's to recover
B =
{bi,j:
0<i<k+1,
0<j<sk+1}
Is an NP-complete problem hard
for the average case?
This may be an easy question. Yet for cryptography,
the answering of it may be far from being complete.
The knapsack problem is NP-complete. However, few if any at
all of the proposed cryptosystems are attempts of explicit constructs
of an NP-complete problem
[4].
The problem some of the knapsack type cryptosystems are built on is
NP-hard, which is quite similar but still different from the
following:
Given a subset sum, find one decomposition of it (into elements
that make up the sum).
A knapsack problem (NP-complete) is commonly presented as
the following decision problem of answering:
Whether or not a given number is a subset sum.
However, a problem, with a set X of n
arbitrary integers, can be presented in a slighly different way:
Find m > -1, the number of
subsets that sum to a given number y.
The average case
[5]
of the above (slightly different) presentation is
at least as hard as the worst case for
NP-completeness.
While the illustration (by the slightly different presentation)
may not have as much significance as we would like for cryptography
as a practical matter, --- for example, to ensure a trapdoor, we are
not able to take the liberty of taking a set of arbitrary integers,
--- the illustration does show, after a fashion, the importance of
the underlying problem and the preservation of that problem in
constructing the cryptosystem. On the other hand, the illustration
does not say that the average case of the underlying
problem must be any easier than the worst for NP-completeness!
Simply put, under the assumption that P is not NP, if
the underlying problem is of strictly lower complexity than an
NP-complete problem, we will not have a system that is as
hard to crack as an NP-complete problem; if the underlying
problem is easy in the average case, the system will suffer from
the same weakness; if the underlying problem is hard but we
distort the problem in the construction of the system, we should
not be too much surprised at the insecurity. The low density of a
knapsack type cryptosystem is a typical example of distortion.
The illustration can work as a reference point to some of the
characteristics historical knapsack type cryptosystems:
c1. structure (e.g. superincreasing property, linearity etc.)
that can not be well hidden
c2. the existence of alternate keys (especially those easy
to get at)
c3. low density
c4. single subset sum solution (that is guaranteed to exist)
c5. the existence of an equivalent zero-one set that
facilitates attacks (such as
L3 and other improvements)
c6. a false solution (a subset sum yet not the desired one)
can be easily verified to be false
Of the 6, c1 exists in some cryptosystems, such as the basic
MH. c2 is devastating and showed up in a quite recently
proposed scheme. c3, c4 and c5 are the ones
nice to L3, to which most of
the knapsack cryptosystems fall prey. Whether we can question the
invincibility of L3 or whether
L3 in conjunction with other
improvements in the attack against Chor-Rivest has showed its fatigue
may still be an open question
[6].
However, one thing may be clear. The success of such attacks has
heavily depended on c4, c5 and in part on c3
as well. So the claim that it is highly likely to find a short
vector (or even the shortest) in polynomial time in most
cases may still be too early and too far from concluding that
knapsack type cryptosystems are just no good.
The purpose of this invention is to remove any and all of
the 6 listed weaknesses. For example, as the noise elements in the
union of E and N do not have to obey the
superincreasing rule, their introduction increases the density of
the effective set (i.e. the union of E and
N which the attacker has to deal with) by more than
offsetting the density lowering effect due to the iterations. As the
functions (i.e. f and g) are irregular,
the existence of an equivalent zero-one set is nullified. Such
a construction can offer very high density (e.g. about 1.3) and
numerous subset sums (e.g. about 230), foiling
L3 and related attacks. Looking
for the shortest vector will no longer be an effective attack as the
desired vector is overwhelmingly not the shortest. Another interesting
point is the de-coupling of the noise elements from the key set
elements. There is not much dependency (of the noise elements) on how
the key elements are constructed. When, in the construction, enough
room is designed into the sets, different mappings can be used in
an independent fashion for individual encryption instances. This
implies that there is no need to reconstruct the whole key, but only
a different set of mappings will suffice in making each encryption a
new problem for the attacker. And due to the independence, the mapping
can be driven by random parameters, i.e. as a function of some random
input. There is no security requirement for the mappings as long as
they fall within allowable ranges. The obvious consequence of this
is the much shorter session keys using the same scheme with the same
key sets and noise sets, and the possibility of sharing the key sets
and noise sets. If the number of f's is sufficiently
large, by keeping f secret, the scheme offers a
different (semi-)secret cryptomode.
One fact not to be overlooked is that obtaining a
decryption key (of a knapsack cryptosystem) via cryptanalysis of the
public key and/or ciphertext has not yet been shown to be easy
in general, remaining up till now an intractable problem.
Therefore, new life can be pumped into the breathing soul of such a
scheme once the ciphertext is strengthened.
Even in the case where attacking a ciphertext block can be
highly successful (assuming that obtaining a decryption key
via cryptanalysis is intractable), we see promise by noting the
fact that, if the average success rate (on cracking a ciphertext
block) is r <1, for any small number s,
there exists some large enough number n such that
rn <s. Its translation: the
average cost of a successful attack (assuming the ciphertext has
n blocks and is made all-or-nothing) is (roughly)
c / rn, where c
is the average cost for successfully cracking a ciphertext block
and successfully realizing a failure (on a block). This
implies that a message with a known value can, in theory, be protected
as much as we would like (by making n as large as
possible). And given r being low, say 80% successful
for an attacker, it will be quite an easy thing, as of now, to cost
the attacker billions of dollars at the sacrifice of some bandwidth.
The above cost-scenario can be made much, much worse for the attacker
when garbage blocks are introduced, assuming that the chance for a
random garbage block happening to be a legitimate ciphertext block
is extremely small (but still possible to be a subset sum). This
mixes in some completeness (in the complexity sense with a flavor
[7]
of finding "m").
It may be interesting to consider some characteristics of such a
scheme versus, for example, RSA. Assuming the attack on RSA is via
factorization by conventional computing means and current
techniques, for a problem of a known size, the sub-exponential cost
of attack can be pretty accurately calculated. The cost and
benefit of an attack can be decided before the attack starts.
Attacking a message protected by the scheme of this invention
can be quite a different picture. It is not known at what cost (other
than the worst case cost) benefit will be reaped. In addition, since
attacks are normally in simulated mode, i.e. with reduced problem
size, the cost factor is in reality even more uncertain, if not an
ultimate surprise of being without bound. Random bits as a fake key
are hardly distinguishable from a public key by this invention,
but are overwhelmingly distinguishable from the RSA modulus. Unlike
schemes that are based on factoring and discrete logarithm, schemes
like that of this invention will not have cycle/period for
Quantum Computing to exploit.
c6 is true for most ciphers. This invention has humbly
tried to address the issue with a purpose to improving the strength
of the average case
[8].
One no less attractive feature of this invention is the high
speed. A system by this invention is not only fast in encryption
and decryption, but also in key generation. This gives the cryptosystem
by this invention the capability of efficient message/session
specific key pairs for actual data encryption or for efficient
establishment of still another layer of key(s) that performs the
actual data encryption.
It will be greatly appreciated for pointing out any errors
in the description. Thanks!
Go to Beginning of Invention
NOTES
1. NEED FINANCIAL HELP! Patent is filed
in the U.S. and application to other countries is intended as well.
However, the high cost of filing world wide is inhibiting. Any
organization or individual who is interested in helping
financially, please contact me at
zhang@metrocall.com
Please be explicit in your terms if possible. Thanks!
back
2. Due to the listed and other characteristics of this
invention, there can be variantions based on the basic
scheme. One variation is depicted in the invention where
a non-secret key is expanded. The expanded version is not directly
usable but remains at least as hard
as an NP-complete problem for an attacker till the protocol
for the public key establishment, which has the security of the basic
scheme.
back
3. The actual number of noise elements may depend on
how the keys are used. When used in private-keying mode, noise
elements may not be needed.
back
4. A problem is not NP-complete if only
YES or NO as an answer (but not both) can be expected.
Theoretically, to be able to answer one is equivalent to being able
to answer the other. As a practical matter in cryptography, the
difference can be prominent only when a hard case appears frequently
enough.
back
5. The value of y is important.
Pertaining to a practical matter, we can assume that y
is much smaller than the largest subset sum yet much larger than the
smallest element in the set.
back
6. Cryptanalysis is to find short-cuts. Certain
cryptanalysis methods are like cutting corners. The cryptanalyst
is allowed to make as many corner-cuts as he wishes to finally reach
the exact cut. However, he is not allowed to make an excessive
cut. In such a situation, he can make fewer cuts (i.e. speedup in
cryptanalysis) by enlarging the chance of over-cutting.
back
7. It is not to show that the problem is made
NP-complete, but the attacker is somehow forced to answer
the NO side of the question.
back
8. All-or-nothing, garbage blocks, the removal of
c6, etc. are all additional, flexible security measures for
different level of security. However, some of such measures do
affect the performance and complexity of the cryptosystem.
back
| ********** ==========
| END
| ========== **********
|
Comments / Information: Please
E-Mail
Return To: Invention
Marketing
Website By: Bertaut.Com