Prev: Draft paper submission deadline is extended: ISP-10, Orlando, USA
Next: Request to review OWASP ESAPI crypto
From: Mok-Kong Shen on 19 Feb 2010 14:43
bmearns wrote:

> Factoradic does not have any gaps: with N unique elements you can
> represent all the integers in the closed range [0, N!-1]. So for
> instance, if you need to convey 8 bits, you need to be able to
> represent all the numbers in [0, 255], which you can do in factoradic
> with N = 6 (because 6!-1 = 719 which is of course greater than 255).
>
> Now if you're set on using repetition, as in you're previous examples
> A appeared twice, I'm not sure off hand whether factoradic will work
> or not. Generally, you would use N /unique/ elements. As I mentioned,
> Wikipedia has a decent introduction to factoradic, specifically in the
> "Permutations" section which shows a little about how permutations
> (without repetition) are mapped to factoradic.

For indexing permutaions of n 'distinct' objects, there are in my humble
view very good codes available on the internet, see e.g.

http://stackoverflow.com/questions/1506078/fast-permutation-number-permutation-mapping-algorithms.

> Factoradic isn't really distinct from lexicographical ordering. All it
> really does is give you a standard way to /compute/ the index of a
> given permutation within the list of all possible permutations. (It so
> happens that the ordering of permutations thus produced does matches
> lexicographic ordering). If you already have code that does this, then
> it's entirely possible that you're already using factoradic, or some
> variation of it, without realizing that it had a name. If you're
> method is not related to factoradic but still works, then there might
> not be any good reason for you to switch to a different method, except
> that factoradic is a fairly standard method for numbering permutations
> so it might be easier to get support for your technique.

Comparatively more complicated is the case with repeated elements, which
is desirable in the present context. I have sometime ago a preliminary
program design for that but don't yet have running code at the moment.
Maybe I'll shortly finish the coding and publish it. However, in my
design "factoric number system" as such doesn't play a role. (I don't
exclude that another way of program design could make use of it, that's
why I questioned in my previous post. On the other hand, I certainly
make use of combinatoric results and the factorial n! is present in
lots of formulae in combinatorics.)

> Looking at your examples where repetition is allowed, I might point
> out that what you've really done is create a base-N number, where N is
> the number of different elements (3 in your example: A, B, and C), and
> each item is a digit. So for instance, if we assign logical digit
> values of A=0, B=1, and C=2, then you have AABC is simply (0,0,1,2) =
> 1*3 + 2*1 = 5, and ABAC is (0,1,0,2) = 1*9 + 0*3 + 2*1 = 11. Is this
> what you were going for? If you're allowing repetition and using
> combinatorics, I think you're probably over working it. With
> repetition, it's simply a base-N number and is probably most easily
> dealt with in that manner, which doesn't require any combinatorics and
> is a bit easier and less computationally intensive.

Certainly one can have many other systems and ways of achieving the
same goal. To use all different objects is, for example, one. What I
have in mind is the case where one from some other considerations
prefers to have a particular set of objects in a szenario, i.e. both
the kinds and the number of each kind are more or less determined by
other criteria.

> Just in terms of steganography, your description raises some concerns,
> but I'm not sure I fully understand your concept. What I got from your
> description is an image of various shapes or objects from some agreed
> upon set (so they can be assigned a sorting value) arranged in some
> order. Again, I may be missing something but this doesn't seem very
> transparent. In other words, the image itself seems like it would be
> fairly suspicious. For limited use, of course, you can get away with
> just about any obscure encoding mechanism you want, but if this had
> widespread use, would there be believable cover stories for sending
> such images back and forth without anyone suspecting ulterior motives?
> Remember, with steganography, your opponent doesn't generally need to
> prove that you're up to anything: all they need to do is sense
> something fishy in what you're doing and then start digging to see if
> they were right.

To often exchange drawings, in contrast to e-mails, could easily
raise suspisions. Further the stego bit rate is fairly low. You are
right in these. (In another recent thread on steganography of text
files, I mentioned the issue of low bit rate but missed to do the same
in this thread.)

BTW, the intention of my original post is sort of "yet another 'tiny'
idea of doing stego". There are in fact lots of good and efficient ways
of secret communications, depending one's preference, etc. One example
is to "abuse" some usenet groups, simply sending encrpted stuffs to
them. The partners can access the messages e.g. from internet cafes,
thus remaining anonymous. They could identify themselves in some
suitable ways and even have the messages provided with authentication.

> It also doesn't seem to provide all that much capacity. In order to
> encode a useful amount of information, you need to have a lot of items
> in the picture (if you're not using repetition) or at least a very
> large set of items to choose from (if you're allowing repetition,
> i.e., using base-N numbers you would want N to be quite large so each
> item/digit encodes a large amount of information).

See above for low bit rate.

> Finally, would this be encoded and decoded by computers or done
> manually? If it's done by computers, you would need either very simple
> items (which probably means a small N) or some pretty sophisticated
> image processing code. You could do it manually or semi-manually (have
> a human identify each item, and then let the computer compute the
> encoded value) but then of course you need to rely on the humans not
> to make mistakes, and it might be a pretty slow process.

The suggested method deals only with the ordering of objects. How these
objects are created, by computer or manual, is outside the realm of
the suggestion. As to encoding/decoding, one should preferably use
a computer running the code I indicated above, since it would be too
much work for manual computation in my humble view.

> I hope this isn't too dismissive. You're thinking along good lines and
> I certainly don't mean to discourage you. When I started working on
> permutation based stego, I thought I had come up with something
> entirely new, and I was quite disappointed when I learned it was
> already known, so I hope you're not too disappointed if that happens
> here.

You are conducting fair scientific discussions in my view. I always
sincerely solicit comments and critiques. The more 'explicit' the
(objective) critiques are, the better they are for the discovery of
my own faults. Conversely, I hope that you don't mind, if you find
that somewhere I am rather strongly defending my points. For I believe
it is only through 'hard' exchange of viewpoints between discussion
partners that truth in sciences can be found. In short, I should be
grateful, if you have further comments and critiques.

Thanks,

M. K. Shen

From: Mok-Kong Shen on 22 Feb 2010 10:22
[Addendum]

Another humble idea that similarly relies on some connection
between math and figures in a drawing (thereby "indirectly" hiding
information bits, in contrast to more "direct" exploitations, e.g.
schemes where Morse codes are represented in some explicit form):

There exists a correspondence between the structure of trees and
natural numbers. Hence some (low rate) stego bits could be
transmitted through drawing a tree having the corresponding number.
For in the theory of graphs it is well-known that every tree, whose
n nodes are labeled, has a unique Pr�fer number and, given a arbitrary
numerical value as the (base n) Pr�fer number, the corresponding
labeled tree can be algorithmically determined. Now, what one needs
in our context is not a labeled tree but an unlabled one. However,
from the elementary property of labelling it is evident from the
existence of Pr�fer numbering that a bijective mapping between a
(naturally drawn) unlabeled tree and an (arbitrary) integer exists.
I am currently considering how an efficient C-code for this mapping
could be written. If such a code happens to be already available,
I should be grateful to be able to download it.

Meanwhile I like to once again solicit better ideas in similar veins
from members of the group.

Thanks in advance,

M. K. Shen




From: bmearns on 22 Feb 2010 11:53
On Feb 19, 2:43 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
[snip]
> For indexing permutaions of n 'distinct' objects, there are in my humble
> view very good codes available on the internet, see e.g.
>
> http://stackoverflow.com/questions/1506078/fast-permutation-number-permutation-mapping-algorithms

The method described in that link actually is factoradic encoding. As
I mentioned, if you have already come up with a method that works,
it's very possible that you are already using factoradic without
realizing. This is because factoradic is quite intuitive for this
application and is intimately related to how you would actually build
up a permutation from the set of N items.


> Comparatively more complicated is the case with repeated elements, which
> is desirable in the present context. I have sometime ago a preliminary
> program design for that but don't yet have running code at the moment.
> Maybe I'll shortly finish the coding and publish it. However, in my
> design "factoric number system" as such doesn't play a role. (I don't
> exclude that another way of program design could make use of it, that's
> why I questioned in my previous post. On the other hand, I certainly
> make use of combinatoric results and the factorial n! is present in
> lots of formulae in combinatorics.)

If each item is chosen from the exact same set of unique items, then
it is not at all more complicated, it is actually significantly
easier. Like I said, such a scheme is simply a base-N number system
and doing factorials or any other combinatorics is really making it
much more complicated than it needs to be. I'm not sure what you're
background is, but if you think about it for a little bit, you can
probably see that this is really just base-conversion. If this is not
clear to you and you would like to be, I believe I can explain it
pretty clearly.

But I may still be missing something in your description. In your next
paragraph, it sounds like perhaps you had something more complicated
in mind, where they don't have the same set to choose from for each
item. For instance, perhaps the image must (for whatever strange
reason) include 3 apples, 1 banana, 1 orange, and 2 grapes. Is this
more like what you had in mind? It certainly does complicate things
more and I'm not aware of any encoding schemes for this off hand. If
you have something worked out, I'd be quite interested in seeing it.

>
> Certainly one can have many other systems and ways of achieving the
> same goal. To use all different objects is, for example, one. What I
> have in mind is the case where one from some other considerations
> prefers to have a particular set of objects in a szenario, i.e. both
> the kinds and the number of each kind are more or less determined by
> other criteria.
>


[snip]
> BTW, the intention of my original post is sort of "yet another 'tiny'
> idea of doing stego". There are in fact lots of good and efficient ways
> of secret communications, depending one's preference, etc. One example
> is to "abuse" some usenet groups, simply sending encrpted stuffs to
> them. The partners can access the messages e.g. from internet cafes,
> thus remaining anonymous. They could identify themselves in some
> suitable ways and even have the messages provided with authentication.

This could explain a lot of the mindless rambling that goes on in some
of these newgroups... =)


> > Finally, would this be encoded and decoded by computers or done
> > manually? If it's done by computers, you would need either very simple
> > items (which probably means a small N) or some pretty sophisticated
> > image processing code. You could do it manually or semi-manually (have
> > a human identify each item, and then let the computer compute the
> > encoded value) but then of course you need to rely on the humans not
> > to make mistakes, and it might be a pretty slow process.
>
> The suggested method deals only with the ordering of objects. How these
> objects are created, by computer or manual, is outside the realm of
> the suggestion. As to encoding/decoding, one should preferably use
> a computer running the code I indicated above, since it would be too
> much work for manual computation in my humble view.

Too an extent that's true, but at some point you need to consider
whether or not it's practical, unless you're doing it strictly as an
academic exercise. The best cryptographic protocol in the world is
worthless if it can't be implemented.

I think a lot of the stumbling points I'm noticing in your idea are
related to the fact that you're trying to do it in images. I know
stego often goes with images, but that's because images contain a lot
of visual redundancy than can be replaced with useful information. In
your scheme, you're really not utilizing this aspect of the image, and
so it's a much less natural fit. I'd like to offer that your idea
sounds like it would be much more useful in other media. For instance,
I've occasionally used my own permutation based stego implementation
to hide information in textual lists: directory listings, address
lists, rosters, playlists, etc. This also makes the process of
actually generating and processing the information much easier since
you don't have to do any image processing.

-Brian
From: Mok-Kong Shen on 22 Feb 2010 13:26
bmearns wrote:
> mok-kong shen wrote:
> [snip]
>> For indexing permutaions of n 'distinct' objects, there are in my humble
>> view very good codes available on the internet, see e.g.
>>
>> http://stackoverflow.com/questions/1506078/fast-permutation-number-permutation-mapping-algorithms
>
> The method described in that link actually is factoradic encoding. As
> I mentioned, if you have already come up with a method that works,
> it's very possible that you are already using factoradic without
> realizing. This is because factoradic is quite intuitive for this
> application and is intimately related to how you would actually build
> up a permutation from the set of N items.

Entirely right. If I could be allowed to be explicit (I attempted to
avoid to be so), I wondered why you had assumed that I did't know that
in your first post in this thread.

>> Comparatively more complicated is the case with repeated elements, which
>> is desirable in the present context. I have sometime ago a preliminary
>> program design for that but don't yet have running code at the moment.
>> Maybe I'll shortly finish the coding and publish it. However, in my
>> design "factoric number system" as such doesn't play a role. (I don't
>> exclude that another way of program design could make use of it, that's
>> why I questioned in my previous post. On the other hand, I certainly
>> make use of combinatoric results and the factorial n! is present in
>> lots of formulae in combinatorics.)
>
> If each item is chosen from the exact same set of unique items, then
> it is not at all more complicated, it is actually significantly
> easier. Like I said, such a scheme is simply a base-N number system
> and doing factorials or any other combinatorics is really making it
> much more complicated than it needs to be. I'm not sure what you're
> background is, but if you think about it for a little bit, you can
> probably see that this is really just base-conversion. If this is not
> clear to you and you would like to be, I believe I can explain it
> pretty clearly.

To tell the entire truth, I asked a time ago for a code for a simplified
case (with only 2 different kinds of objects) in another
internet group. One person offered to dig up his codes he did
previously for the general case (for arbitrarily number of different
kinds of object). But later he presented only the code from index to
permutation but not the code from permutation to index. Later, not
being able to obtain the missing part of his code, I wrote my own code
for the simplified case and published it. If the general case is simple
in your opinion, I should be very grateful, if you would kindly give at
least an adequate pseudo-code of the algorithm, in particular the part
from index to permutation, so that I could write a C-code based on it.

> But I may still be missing something in your description. In your next
> paragraph, it sounds like perhaps you had something more complicated
> in mind, where they don't have the same set to choose from for each
> item. For instance, perhaps the image must (for whatever strange
> reason) include 3 apples, 1 banana, 1 orange, and 2 grapes. Is this
> more like what you had in mind? It certainly does complicate things
> more and I'm not aware of any encoding schemes for this off hand. If
> you have something worked out, I'd be quite interested in seeing it.

This paragraph of yours is in my understanding different in sense from
the previous one and so my last paragraph may have been a wrong answer
due to my misunderstanding of your last paragraph. Now, yes, I "did"
mean a case like what you wrote "... 3 apples, ......". For I wrote in
my original post: " ...a number of selected objects, identical or
different (in kind, size, colour) ....". I thought that should be
quite clear to the readers (BTW, on later occasions I also mentioned
"permutatations with repeated elements").

M. K. Shen
From: Mok-Kong Shen on 22 Feb 2010 13:38
Mok-Kong Shen wrote:
[snip]
> an adequate pseudo-code of the algorithm, in particular the part
> from index to permutation, so that I could write a C-code based on it.

Sorry, typo: please read "... from permutation to index ...".

M. K. Shen
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: Draft paper submission deadline is extended: ISP-10, Orlando, USA
Next: Request to review OWASP ESAPI crypto