Addressing Segmentation Ambiguity in Neural Linguistic Steganography (2022)

Abstract: Previous studies on neural linguistic steganography, except Ueoka et al. (2021), overlook the fact that the sender must detokenize cover texts to avoid arousing the eavesdropper’s suspicion. In this paper, we demonstrate that segmentation ambiguity indeed causes occasional decoding failures at the receiver’s side. With the near-ubiquity of subwords, this problem now affects any language. We propose simple tricks to overcome this problem, which are even applicable to languages without explicit word boundaries.

## introduction lying at the intersection of information security and natural language processing, linguistic steganography is the practice of hiding information in cover texts @xcite @xcite . formally, the sender alice encodes a secret message, usually in the form of a bit sequence, into a cover text, while the receiver bob decodes the message. the most important requirement is security: the cover text must be so natural that even if transmitted in a public channel, it does not arouse the suspicion of the eavesdropper eve. in fact, steganography engages in an arms race with steganalysis, the practice of detecting the presence of secret messages @xcite . with the security requirement fulfilled, we also want to increase payload capacity, the size of the secret message relative to the size of the cover text @xcite . compared with dominant cover media in steganography, such as images, videos, and audio @xcite , texts are characterized by a low degree of redundancy. this makes it particularly challenging to enumerate natural variations of text into which bit chunks are encoded @xcite . nevertheless, this difficulty is surmounted to some degree by powerful neural language models (lms) for their ability to suggest probable next tokens in a context-aware man-ner @xcite , and the research focus has shifted towards increasing payload capacity @xcite @xcite . previous studies, however, overlook the fact that alice must detokenize texts before sending them to a public channel; otherwise they arouse eve's suspicion. @xcite were the first to point out that bob may fail to recover the original tokens from detokenized texts, leading to decoding failures. while segmentation ambiguity has been a vexing problem for scriptio continua, or writing systems without explicit word boundaries (e.g., chinese and japanese), the near-ubiquitous use of subwords implies that it now affects any language. for example, suppose that alice generates the english sequence "un ##us ##able". detokenized into "unusable", it is unfortunately re-tokenized into "un ##usable" by bob (figure 1 while recent proposals are flawed, the fact that the problem went unnoticed till @xcite suggests that the errors occur only infrequently. this leads us to the following question: how often do decoding failures occur? we expect that they affect morphologically rich languages and scriptio continua more severely than english. we report our experimental results using russian and japanese in addition to english. although @xcite proposed a simple solution for their edit-based method, it is not applicable to lm-based (generation-based) methods. this motivates us to address the second question: how can generation-based methods overcome segmentation ambiguity? in this paper, we propose a combination of simple tricks to ensure that bob recovers the same tokens as alice (figure 1 (bottom)). the proposed method can be applied not only to subwordbased lms but also to scriptio continua, as we demonstrate for japanese. our code is available at https://github.com/jumon/himitsu . 2 related work ## segmentation ambiguity the basic idea underlying generation-based neural linguistic steganography is to let a powerful neural lm, like gpt-2, enumerate natural variations of text into which bit chunks are encoded (figure 1 (top) ). we assume that alice and bob share the lm and an encoding strategy in advance. following @xcite , we also assume that alice uses some introductory context (prompt) in a way such that bob can use the same prompt during decoding. this helps diversify cover texts. now we consider an ambiguity-unaware method of generation-based steganography. for simplicity, we use block encoding @xcite as the encoding strategy. at alice's side, the lm is given a prompt and proposes probable next tokens at each time step. alice sorts tokens in descending order of probability and performs a two-step filtering to select the top 2 n tokens. she first selects c tokens with probabilities greater than or equal to p and then chooses n such that it is the largest integer that satisfies 2 @xmath0. each of the tokens is given a unique bit chunk of length n, and alice chooses the one that corresponds to the next n bits of the secret message. alice repeats this until she finishes encoding the message. in the end, she detokenizes the text and sends it to bob via a public channel. receiving the cover text, bob first tokenizes it and then feeds the resultant tokens to the lm. he associates tokens with bit chunks in the same way as alice. he decodes the secret message by repeatedly selecting a bit chunk corresponding to the next input token. unfortunately, this method is flawed because detokenization triggers segmentation ambiguity. even if alice generates the tokens "un ##us ##able", bob obtains "un ##usable", which results in a wrong secret message. one might be tempted to use an error correcting code for the secret message, but it is of little help because one segmentation error affects all subsequent tokens. ## proposed method figure 1 (bottom) shows an overview of the proposed method. to overcome the segmentation ambiguity problem in generation-based neural linguistic steganography, we combine two simple tricks: stepwise tokenization and token disambiguation. ## experiments we compared the proposed method with the abovementioned ambiguity-unaware method. for each method, we generated 10,000 cover texts following different prompts. our primary focus was on decoding error rates, or the percentages of decoding failures among the 10,000 trials. a trial was deemed a failure if bob re-tokenized the cover text differently from alice. the proposed method is guaranteed to have a 0% decoding error rate, and we intended to experimentally confirm this. we also evaluated these methods in terms of payload capacity and security. ## discussion although recent studies on generation-based neural linguistic steganography @xcite @xcite exploit the entire vocabulary distributions proposed by an lm, we turn back to naïve block encoding @xcite , which only uses the most probable 2 n tokens. in fact, our solution in its current form is not compatible with the use of the entire vocabulary because with @xmath1, the token disambiguation trick always drops a fixed portion of the vocabulary. the present study should be seen as a proof-of-concept demonstration focusing on segmentation ambiguity. we hope that it sets out a future research direction. ## conclusions linguistic steganography is an interdisciplinary research area that combines information security and natural language processing (nlp). in this paper, we investigated its unexpected connection to the decades-old nlp task of word segmentation. specifically, we shed light on segmentation ambiguity in generation-based neural linguistic steganography. previously proposed methods are flawed if combined with a subword-level lm. we proposed a combination of simple tricks to guarantee the recovery of the original tokens and thus the correct decoding of a secret message. our solution is language-agnostic and is applicable even if no word boundaries are marked. with powerful neural lms, linguistic steganography is approaching the level of practical utility. now is the time to face up to the fact that without detokenization, linguistic steganography is useless.