Disreo: Provably Secure No-Box-Extraction Linguistic Steganography Based on Distribution Reorganization

Existing provably secure linguistic steganographic methods typically rely on white-box extraction, which necessitates access to large language models. This requirement is impractical in environments with limited resources. To tackle this issue, we proposeDisreo, a provably secure linguistic steganography based ondistributionreorganization, which extracts the messages without accessing the underlying language model. This is achieved through token position randomization and output probability reorganization for message embedding. Moreover, secret message extraction requires only the synchronization of token positions used during embedding, making it both feasible and fast for devices with constrained computational capabilities. Theoretically, the security ofDisreocan be reduced to the security of the encryption algorithm we employ, and our experimental analyses confirm thatDisreomaintains distribution consistency between stego and cover texts in expectations. In practice,Disreoachieves an average extraction time of 0.015 seconds for 5 bits of secret messages from 100 tokens, with a 100% extraction accuracy. By transitioning from white-box extraction to more practical no-box extraction scenarios,Disreobroadens the scope of steganography applications.