Decoding Substitution Ciphers by Means of Word Matching with Application to OCR.

Area of Science:

• Computer Science
• Artificial Intelligence
• Cryptography

Background:

• Substitution ciphers are a cryptographic concept where letters are replaced by symbols.
• Optical Character Recognition (OCR) faces challenges in identifying characters across diverse typefaces and sizes.
• Existing OCR methods struggle with arbitrary character identification, hindering document digitization.

Purpose of the Study:

• To bridge the gap in OCR by solving substitution cipher-like problems.
• To enable automatic translation of scanned documents into standard character codes (e.g., ASCII).
• To develop a more efficient method than n-gram frequency analysis for cipher decryption.

Main Methods:

• A dictionary-based approach utilizing a lexicon of fewer than 500 words.
• Implementation of a heuristic backtrack algorithm.
• Testing on sample texts ranging from 100 to 600 words.

Main Results:

• The heuristic backtrack algorithm efficiently deciphers substitution ciphers.
• The method requires only small ciphertext samples.
• The algorithm explores a minimal subset of the vast search space (26! possibilities).

Conclusions:

• The proposed dictionary-based heuristic backtrack algorithm effectively solves substitution ciphers for OCR applications.
• This approach overcomes limitations of previous methods requiring large datasets.
• Enables robust automatic document translation and character code standardization.