Sudoku tables as a special class of Latin squares are studied and a construction for each class of Sudoku tables is introduced. We provide a definition of a Sudoku table of size m as an mĂm table with blocks of size sĂd. Twin Sudoku tables of size m with(s, d)-subtables, where s is a divisor of d, are defined as Sudoku tables with (s Ă d)-subtables and (dĂs)-subtables, simultaneously. Solid Sudoku cubes of size m, which are cubes with subcubes of size sĂsĂd, where s †d and s·d = m, can be divided into subcubes in any face of the Sudoku cube. They have the property that each layer of the cube from each face, which is a table of size m, is a twin Sudoku table. Standard solid Sudoku cubes and 3D Sudoku puzzles are defined as solid cubes in which the subcubes of size m contain m different numbers, and they can be divided into subcubes of size xĂyĂz along the X, Y , and Z axes, respectively. Magic rectangles and nested magic rectangles are constructed. In addition, orthogonal balanced magic Sudoku tables as a class of Sudoku tables in which their blocks are magic are created and a method to construct nested Latin squares is presented. New classes of Sudoku puzzles are obtained from the construction of the Sudoku tables and Sudoku cubes. Since a Sudoku puzzle can be obtained from a Sudoku table by randomly removing some entries of the Sudoku table, creating a new class of Sudoku tables leads to a new class of Sudoku puzzles. To construct these new classes of Sudoku tables cyclotomic cosets of the algebraic group Zn are used. Sudoku tables have applications in different fields of study, and some of these applications are investigated. It is shown that they can be used in cryptography and zero-knowledge proof protocols. Sudoku puzzles are in the class of NP-complete problems, so zero knowledge proof protocols can be based on this class of problems. Sudoku tables like Latin squares can be used to generate locally repairable codes which have application in distributed storage systems.
Imagine sharing that you know a secret without revealing the secret itself. This is what zero-knowledge proofs (ZKPs) aim to do. In ZKPs there is a prover who claims knowledge of something and a verifier who checks this claim. The goal of this project is to further explore current technologies revolving around ZKPs and understand possible adaptations to an everyday application beyond blockchain use cases. To explore the practical use of ZKPs, this project introduces a web puzzle application that keeps the solutions of individual users private using ZKPs. A user can solve a logic- based puzzle like Binairo or Sudoku and check the validity of their solution by sharing only a ZKP of the solution. That way, the solution never leaves the userâs device. To further strengthen the security, the following two checks are implemented: (1) making sure that the solution matches the original puzzle, and (2) integrating the userâs ID during the generation process. These checks prevent users from reusing a proof to âsolveâ other puzzles or for the proof to be stolen by another user. To implement this application, different ZKP frameworks are considered. Circom and snarkjs are selected because of their active development, clear documentation and good web development capabilities. The final result is a secure application that demonstrates how ZKPs can be applied in a realistic and practical way. This highlights their broader potential in digital security. In most applications, the impact of ZKPs is intentionally hidden, as good cybersecurity aims to operate in the background. The ZKP-Puzzles application puts the ZKPs in the spotlight and visualizes how ZKPs work.
Open access
graph theory and CDMA systems
Graph Labeling and Dimension Problems
Advanced Steganography and Watermarking Techniques
Sandip Das, A. Lahiri, Soumen Nandi, Sagnik Sen · 5 authors
An ( n , m ) -graph is characterized by n types of arcs and m types of edges. A homomorphism of an ( n , m ) -graph G to an ( n , m ) -graph H , is a vertex mapping that preserves adjacency, direction, and type. The ( n , m ) -chromatic number of G , denoted by Ï n , m ( G ) , is the minimum value of | V ( H ) | such that there exists a homomorphism of G to H . The theory of homomorphisms of ( n , m ) -graphs have connections with graph theoretic concepts like harmonious coloring, nowhere-zero flows; with other mathematical topics like binary predicate logic , Coxeter groups; and has application to the Query Evaluation Problem (QEP) in graph database. In this article, we show that the arboricity of G is bounded by a function of Ï n , m ( G ) but not the other way around. Additionally, we show that the acyclic chromatic number of G is bounded by a function of Ï n , m ( G ) , a result already known in the reverse direction. Furthermore, we prove that the ( n , m ) -chromatic number for the family of graphs with maximum average degree less than 2 + 2 4 ( 2 n + m ) â 1 , including the subfamily of planar graphs with girth at least 8 ( 2 n + m ) , equals 2 ( 2 n + m ) + 1 . This improves upon previous findings, which proved the ( n , m ) -chromatic number for planar graphs with girth at least 10 ( 2 n + m ) â 4 is 2 ( 2 n + m ) + 1 . It is established that the ( n , m ) -chromatic number for the family T 2 of partial 2-trees is both bounded below and above by quadratic functions of ( 2 n + m ) , with the lower bound being tight when ( 2 n + m ) = 2 . We prove 14 â€ Ï ( 0 , 3 ) ( T 2 ) †15 and 14 â€ Ï ( 1 , 1 ) ( T 2 ) †21 which improves both known lower bounds and the former upper bound. Moreover, for the latter upper bound, to the best of our knowledge we provide the first theoretical proof.
Elena Andreeva, Rishiraj Bhattacharyya, Arnab Roy, Stefano Trevisani
ZK-SNARKs, a fundamental component of privacyoriented payment systems, identity protocols, or anonymous voting systems, are advanced cryptographic protocols for verifiable computation: modern SNARKs allow to encode the invariants of a program, expressed as an arithmetic circuit, in an appropriate constraint language from which short, zero-knowledge proofs for correct computations can be constructed. One of the most important computations that is run through SNARK systems is the verification of Merkle tree (MT) opening proofs, which relies on the evaluation of a fixed-input-length (FIL) cryptographic compression function over binary MTs. As classical, bit-oriented hash functions like SHA-2 are not compactly representable in SNARK frameworks, Arithmetization-Oriented (AO) cryptographic designs have emerged as an alternative, efficient solution. Today, the majority of AO compression functions are built from permutation-based hashing modes, such as Sponge. While this approach allows cost savings, compared to blockcipher-based modes, as it does not require key-scheduling, AO blockcipher schedulers are often cheap to compute. Furthermore, classical bitoriented cryptography has long studied how to construct provably secure compression functions from blockciphers, following the Preneel-Govaerts-Vandewalle (PGV) framework. The potential efficiency gains together with the strong provable security foundations in the classic setting, motivate the study of AO blockcipher-based compression functions. In this work, we propose AO PGV-LC and PGV-ELC, two AO blockcipher-based FIL compression modes inspired by and extending the classical PGV approach, offering flexible input and output sizes and coming with provable security guarantees in the AO setting. We prove the collision and preimage resistance in the ideal cipher model, and give bounds for collision and opening resistance over MTs of arbitrary arity. We compare experimentally the AO PGV-ELC mode over the HADES blockcipher with its popular and widely adopted Sponge instantiation, POSEIDON, and its improved variant POSEIDON2. Our resulting constructions are up to 3Ă faster than POSEIDONAND 2Ă faster than POSEIDON2 in native x86 execution, and up to 50% faster in the Groth16 SNARK framework. Finally, we study the benefits of using MTs of arity wider than two, proposing a new strategy to obtain a compact R1CS constraint system in such case. In fact, by combining an efficient parametrization of the HADES blockcipher over the PGV-ELC mode, together with an optimal choice of the MT arity, we measured an improvement of up to 9Ă in native MT construction time, and up to 2.5Ă in proof generation time, compared to POSEIDON over binary MTs.
A Zero-Knowledge Proof (ZKP) protocol allows a participant to prove the knowledge of some secret without revealing any information about it. While such protocols are typically executed by computers, there exists a line of research proposing physical instances of ZKP protocols. Up to now, many card-based ZKP protocols for pen-and-pencil puzzles, like Sudoku, have been designed. Those games, mostly edited by Nikoli, have simple rules, yet designing them in card-based ZKP protocols is non-trivial. In this work, we propose a card-based ZKP protocol for Usowan, a Nikoli game. In Usowan, for each room of a puzzle instance, there is exactly one piece of false information. The goal of the game is to detect this wrong data amongst the correct data and also to satisfy the other rules. Designing a card-based ZKP protocol to deal with the property of detecting a liar has never been done. In some sense, we propose a physical ZKP for hiding of a liar. This work extends a previous paper appearing in Ref. [1]. In this extension, we propose two other protocols, for Herugolf and Five Cells. The puzzles are specifically chosen because each of those three puzzles shares a common constraint, connectivity. However, showing the connected configuration cannot be done with generic approach and brings new construction to the existing connectivity ZKP protocol. Indeed, in Herugolf, the connectivity is handled with a given length of cell which is decremental (i.e., the length of each connected cell decreases by one at each step). For Five Cells, there is an additional step in the setup allowing to encode all the information needed to ensure a valid ZKP protocol.
Open access
graph theory and CDMA systems
Graph Labeling and Dimension Problems
Advanced Steganography and Watermarking Techniques
Abstract This note is just a modest contribution to prove several classical results in Combinatorics from notions of Duality in some Artinian K -algebras (mainly through the Trace Formula), where K is a perfect field of characteristics not equal to 2. We prove how several classic combinatorial results are particular instances of a Trace (Inversion) Formula in finite $$\mathbb {Q}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Q</mml:mi> </mml:math> -algebras. This is the case with the Exclusion-Inclusion Principle (in its general form, both with direct and reverse order associated to subsets inclusion). This approach also allows us to exhibit a basis of the space of null t -designs, which differs from the one described in Theorem 4 of Deza and Frankl (Combinatorica 2:341â345, 1982). Provoked by the elegant proof (which uses no induction) in Frankl and Pach (Eur J Comb 4:21â23, 1983) of the SauerâShelahâPerles Lemma, we produce a new one based only in duality in the $$\mathbb {Q}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Q</mml:mi> </mml:math> -algebra $$\mathbb {Q}[V_n]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Q</mml:mi> <mml:mo>[</mml:mo> <mml:msub> <mml:mi>V</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> of polynomials functions defined on the zero-dimensional algebraic variety of subsets of the set $$[n]:=\{1,2,\ldots , n\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>n</mml:mi> <mml:mo>]</mml:mo> <mml:mo>:</mml:mo> <mml:mo>=</mml:mo> <mml:mo>{</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>2</mml:mn> <mml:mo>,</mml:mo> <mml:mo>âŠ</mml:mo> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> . All results are equally true if we replace $$\mathbb {Q}[V_n]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Q</mml:mi> <mml:mo>[</mml:mo> <mml:msub> <mml:mi>V</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> by $$K[V_n]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo>[</mml:mo> <mml:msub> <mml:mi>V</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> , where K is any perfect field of characteristics $$\not =2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>â </mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> . The article connects results from two fields of mathematical knowledge that are not usually connected, at least not in this form. Thus, we decided to write the manuscript in a self-contained survey-like style, although it is not a survey paper at all. Readers familiar with Commutative Algebra probably know most of the proofs of the statements described in section 2. We decided to include these proofs for those potential readers not so familiar with this framework.
Sandip Das, A. Lahiri, Soumen Nandi, Sagnik Sen · 5 authors
An $(n,m)$-graph is characterised by having $n$ types of arcs and $m$ types of edges. A homomorphism of an $(n,m)$-graph $G$ to an $(n,m)$-graph $H$, is a vertex mapping that preserves adjacency, direction, and type. The $(n,m)$-chromatic number of $G$, denoted by $Ï_{n,m}(G)$, is the minimum value of $|V(H)|$ such that there exists a homomorphism of $G$ to $H$. The theory of homomorphisms of $(n,m)$-graphs have connections with graph theoretic concepts like harmonious coloring, nowhere-zero flows; with other mathematical topics like binary predicate logic, Coxeter groups; and has application to the Query Evaluation Problem (QEP) in graph database. In this article, we show that the arboricity of $G$ is bounded by a function of $Ï_{n,m}(G)$ but not the other way around. Additionally, we show that the acyclic chromatic number of $G$ is bounded by a function of $Ï_{n,m}(G)$, a result already known in the reverse direction. Furthermore, we prove that the $(n,m)$-chromatic number for the family of graphs with a maximum average degree less than $2+ \frac{2}{4(2n+m)-1}$, including the subfamily of planar graphs with girth at least $8(2n+m)$, equals $2(2n+m)+1$. This improves upon previous findings, which proved the $(n,m)$-chromatic number for planar graphs with girth at least $10(2n+m)-4$ is $2(2n+m)+1$. It is established that the $(n,m)$-chromatic number for the family $\mathcal{T}_2$ of partial $2$-trees is both bounded below and above by quadratic functions of $(2n+m)$, with the lower bound being tight when $(2n+m)=2$. We prove $14 \leq Ï_{(0,3)}(\mathcal{T}_2) \leq 15$ and $14 \leq Ï_{(1,1)}(\mathcal{T}_2) \leq 21$ which improves both known lower bounds and the former upper bound. Moreover, for the latter upper bound, to the best of our knowledge we provide the first theoretical proof.
Ball sort puzzle is a popular logic puzzle consisting of several bins containing balls of multiple colors. Each bin works like a stack; a ball has to follow the last-in first-out order. The player has to sort the balls by color such that each bin contains only balls of a single color. In this paper, we propose a physical zero-knowledge proof protocol for the ball sort puzzle using a deck of playing cards, which enables a prover to physically show that he/she knows a solution with $t$ moves of the ball sort puzzle without revealing it. Our protocol is the first zero-knowledge proof protocol for an interactive puzzle involving moving objects.
Internet of things (IoT) devices generate a massive amount of data every second in our lives. While cloud storage brings convenience to the users, it has the disadvantages of low scalability and weak reliability. Blockchain-based distributed storage eliminates data loss due to the tamper-resistant characteristic. Nonetheless, blockchain storage raises some confidentiality and retrieval efficiency issues of data. Searchable Symmetric Encryption (SSE) is an effective search scheme based on ciphertexts, which ensures data security. However, with the increase of data on the blockchain, the data retrieval on the blockchain will be difficult. In this paper, a Complete Binary Tree Searchable Symmetric Encryption using Blockchain (KCB-BC-SSE) scheme is proposed. According to the number of searchers, the scheme is divided into single searcher and multiple searchers where the search efficiency is improved in theory. And the simulation on ethereum shows the feasibility of our scheme. The security analysis illustrates our scheme achieves security under the chosen keyword attack.
Numberlink is a logic puzzle for which the player has to connect all pairs of cells with the same numbers by non-crossing paths in a rectangular grid. In this paper, we propose a physical protocol of zero-knowledge proof for Numberlink using a deck of cards, which allows a player to physically show that he/she knows a solution without revealing it. In particular, we develop a physical protocol to count the number of elements in a list that are equal to a given secret value without revealing that value, the positions of elements in the list that are equal to it, or the value of any other element in the list. Our protocol can also be applied to verify the existence of vertex-disjoint paths connecting all given pairs of endpoints in any undirected graph.
Denne oppgaven undersÞker og sammenligner trekk ved kryptovaluta basert pÄ blokkjeder med kryptovaluta basert pÄ Rettede Asykliske Grafer (RAG). Blokkjedebasert kryptovaluta mÞter utfordringer pÄ felt som skalering, desentralisering og ressursutnyttelse. Denne oppgaven undersÞker om kryptovaluta som bruker en RAG som sin datastruktur kan lÞse noen av disse utfordringene. For Ä besvare dette spÞrsmÄlet ble bÄde en teoretisk studie og forskjellige eksperimenter pÄ ulike kryptovalutaer gjennomfÞrt. Den teoretiske studien ble gjennomfÞrt for Ä skaffe data pÄ de forskjellige systemene til bruk i sammenligninger mellom dem. Eksperimentene fokuserte pÄ RAG-systemene, siden disse er mye nyere og har mindre forskning enn systemene basert pÄ en blokkjede. \t\n\nResultatene i denne oppgaven viser at RAG systemer generelt sett har bedre lÞsninger for skalerbarhet. Oppgaven viser ogsÄ til flere utfordringer disse RAG baserte systemene har, som for eksempel distribuert tjenestenektangrep og en mangel pÄ insentiver i systemene. Oppgaven peker pÄ demonstrert sikkerhet og lang levetid som de stÞrste fordelene blokkjedesystemene har over RAG-systemene. Oppgaven legger vekt pÄ valgene som er gjort nÄr man gÄr fra blokkjede til RAG som datalager i en kryptovaluta. Det konkluderes med at RAG-systemer tilbyr bedre skalerbarhet men de har ikke samme tillit blant brukere som blokkjedesystemene.
In this note, we consider the problem of verifying the identity of an individual involved in a two party communication activity using a well-known Zero Knowledge protocol for a computationally intractable problem. This problem is the problem of coloring the vertices of a graph using three colors so that no pair of adjacent vertices receives the same color also known as 3-coloring problem. This problem is NP-complete, i.e. Ăt shares with a multitude of other natural combinatorial problems the property that most likely no fast (polynomial) algorithm exists for their solution. In this note, we use randomly generated 3-colorable graphs and use the knowledge of a 3-coloring of them to authenticate individuals. We exploĂŹt the fact that one may easily generate a random 3-colorable graph with a specific 3-coloring that only he/she knows although it is a computationally intractable problem for someone who wants to impersonate the individual to discover a 3-coloring. Therefore, knowledge of a 3-coloring of a graph provides authentication of the individual possessing this knowledge. To prove this knowledge, the individual may use an adaptation of a Zero Knowledge Interactive proof protocol for 3-coloring.
The paper presents a more efficient noninteractive zero knowledge proof system (NIZK) for 3 colorability. The length of the proof is 1/3 and the length of the reference string is 1/4 of those of Blum et al. (1988) respectively. The proposed NIZK is based on the quadratic residuosity assumption.>