1
Yet Another Move Towards Securing Video Using Sudoku-Fernet

Sunanda Jana1, Swarnajit Bhattacharya1, Mrinmoy Sen1*, Abhinandan Khan2, Arnab Kumar Maji3 and Rajat Kumar Pal2

1Haldia Institute of Technology, WB, India

2University of Calcutta, Kolkata, India

3North-Eastern Hill University, Meghalaya, India

Abstract

In this era of digital communication and multimedia content sharing, ensuring the security and privacy of sensitive video data is of utmost importance. Symmetric key encryption is a widely used technique for securing video content; however, the generation of secure and unpredictable encryption keys remains a challenge. This study proposes a novel approach that employs Sudoku puzzles as a mechanism for generating symmetric keys. Then, by passing the key through fernet module, the Sudoku-Fernet cipher key was extracted for video encryption. The Sudoku puzzle's inherent properties of uniqueness, complexity, and nonlinearity make it an ideal candidate for key generation. The proposed method combines the strength of the Giant Sudoku instance of size 25 × 25 with a cryptographic fernet module to enhance the security of video encryption systems, offering an innovative solution to protect sensitive video content without affecting cost and time.

Keywords: Symmetric key, fernet, sudoku-fernet cipher key, video encryption, security

1.1 Introduction

Sudoku puzzle [1] is a popular logic-based number-placement game that has gained worldwide popularity. Its structure consists of an n × n square grid, containing some clues as preassigned, forming a Sudoku puzzle, where n is an integer and Vn is an integer. Thus, minigrids are formed with size Vn × Vn. In each minigrid, each integer between 1 and n appears only once. Standard Sudoku consists of a 9 × 9 grid divided into nine 3 × 3 subgrids. The goal is to fill in the empty cells with digits from 1 to 9, ensuring that each row, column, and subgrid contains every digit exactly once. Sudoku puzzles can be of various sizes and configurations beyond the classic 9 × 9 grid. Some common Sudoku types are based on different grid sizes [10]:

1. Classic 9 × 9 Sudoku: This is the standard version of Sudoku, where the puzzle is presented on a 9 × 9 grid divided into nine 3 × 3 subgrids. The objective is to fill in the grid such that each row, column, and 3 × 3 subgrid contains numbers 1 through 9 with no repetition.
2. Mini Sudoku (4 × 4): In Mini Sudoku, the puzzle is played on a 4 × 4 grid, divided into four 2 × 2 subgrids. Each row, column, and 2 × 2 subgrid contain numbers 1 through 4.
3. 6 × 6 Sudoku: In 6 × 6 Sudoku, the grid is 6 × 6 in size and is divided into six 2 × 3 subgrids. Each row, column, and 2 × 3 subgrid must contain numbers 1-6.
4. Samurai Sudoku: Samurai Sudoku is a variant that consists of five overlapping 9 × 9 grids. The objective is to fill in the entire arrangement so that each row, column, and 3 × 3 subgrid in each of the five grids contains numbers 1-9.
5. Hyper Sudoku (4 × 4 regions): Hyper Sudoku uses a 9 × 9 grid, but the subgrids are irregular and can have different shapes. In addition, there were four 2 × 2 subregions within the grid. The objective was the same as that of the classic Sudoku.
6. Giant Sudoku: Giant Sudoku puzzles have larger grids, often ranging from 12 × 12 to 25 × 25, or even larger. Larger grid sizes provide more challenging puzzle-solving experience.
7. Diagonal Sudoku: In Diagonal Sudoku, along with the usual rows, columns, and 3 × 3 subgrids, the diagonals must also contain numbers 1 through 9 (or the corresponding numbers for different grid sizes).
8. Irregular Sudoku: Irregular Sudoku, also known as Jigsaw Sudoku, has irregularly shaped subgrids instead of standard 3 × 3 boxes. The objective remains the same: each row, column, and irregular subgrid must contain numbers 1 through 9 (or the corresponding numbers for different grid sizes).
9. Killer Sudoku: Killer Sudoku combines elements of Sudoku and Kakuro. Kakuro is a crossword number puzzle in which each number word must add up to the number provided as a clue above or to the left of it. In this variant, you are given additional information in the form of "cages" that represent the sum of the numbers within that cage. The objective was to fill the grid with numbers that satisfied the sum constraints for each cage.

3D Sudoku [11] is a variation of the classic Sudoku puzzle that adds an extra dimension to the game. Instead of the usual 9 × 9 grid, 3D Sudoku is played on a 9 × 9 × 9 grid, which means that it has nine 3 × 3 × 3 cubes. The objective is the same as that of traditional Sudoku: fill in the grid so that every row, column, and 3 × 3 × 3 cube contains the numbers 1 through 9 with no repetition.

Figure 1.1 shows a 25 × 25 Sudoku instance where clues are highlighted in red, whereas Figure 1.2 provides a solution to that Sudoku instance. Although Sudoku puzzles are primarily enjoyed as recreational games, they have also found interesting applications in various fields. One such application is video encryption, in which Sudoku-based algorithms can be utilized to secure video content.

Figure 1.1 An instance of a 2D Sudoku puzzle of size 25 × 25 with clues highlighted in red.

Figure 1.2 A solution instance of 2D Sudoku puzzle of size 25 × 25 given in Figure 1.1.

A Sudoku instance can be solved in multiple ways because we can start from any given clue present in the minigrids. However, in contemporary literature, no technique has been described to determine the number of starting cells. The starting cell becomes fascinating to a mathematician only if it follows a minimal route, and the removal or inclusion of a single clue may generate another Sudoku instance for which other new solutions may exist. Moreover, no current technique can determine the minimum number of clues to be provided to the cells. This accounts for the maximum number of variations in Sudoku puzzle instances. The authors in [8] stated that a minimum of 17 clues are needed to ensure that a Sudoku instance, if solvable, has only one unique solution. Therefore, any Sudoku puzzle instance with fewer than 17 givens, if valid, must have more than one solution. However, a valid Sudoku instance may have multiple correct solutions even if the instance includes more than 17 clues. Several techniques exist for the solving a Sudoku puzzle, which differ depending on the difficulty level of the puzzle. According to contemporary literature, the level of difficulty of a Sudoku puzzle is governed by its number of clues [9]. The relationship between the difficulty level of a Sudoku puzzle and the number of clues presented is shown in Table 1.1.

In addition to the number of clues, the position of the empty cells also influences the difficulty level. For any two Sudoku puzzle instances with the same number of clues, the puzzle where the clues are present in clusters/groups is assigned a higher difficulty level than the puzzle with an even distribution of clues. According to the row and column constraints presented in [9], the minimum possible number of clues, in each row and column for different difficulty levels is set as given in Table 1.2.

Sudoku can also be used for video encryption. Sudoku puzzles have a unique property that can be used to scramble and encrypt data. Sudoku puzzles can be used to create a 9 × 9 matrix that can be used to map the pixels of a video frame to new positions. This scrambling process makes it difficult for unauthorized users to decrypt a video without the correct key.

Table 1.1 Definition of the Sudoku instance difficulty level according to the number of given clues.

Difficulty level Number of clues 1 (Extremely Easy) >46 2 (Easy) 36-46 3 (Medium) 32-35 4 (Hard) 28-31 5 (Evil) 17-27

Table 1.2 Minimum possible number of clues, in each row and column of a Sudoku instance for different levels of difficulty.

Difficulty level Minimum possible number of clues in each row and column 1 (Extremely Easy) 05 2 (Easy) 04 3 (Medium) 03 4 (Hard) 02 5 (Evil) 00

There are several different ways to use Sudoku puzzles for video encryption. A common method is to use the Sudoku matrix to create a permutation function. This function can then be applied to the pixels of a video frame to scramble them. Another common method is to use a Sudoku matrix to create a substitution function. This function can...