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.
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.