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
Developing a fair, efficient, and scalable data trading protocol in decentralized networks has attracted much research effort recently. Zero-knowledge contingent payments (ZKCP) allows sellers and buyers to complete their trade fairly over the blockchain using zero-knowledge proofs. However, it suffers from memory-intensive requirements and scalability limitations. In this paper, we propose a practical data trading protocol tailored for Sudoku solutions, which is fair, efficient, and scalable. The core component of our protocol is a zero-knowledge argument for the correctness of a Sudoku solution of homomorphic encryption. This argument achieves sublinear communication complexity and the number of group exponentiations for both proving and verification is linear in the size of Sudoku solutions. The security of our protocol can be proven in the random oracle model under the Decision Diffie-Hellman assumption. In addition, we devise a mechanism that allows buyers to recover the private key through two zero-knowledge proofs and prevents the direct exposure of the decryption key. Furthermore, we implement the proposed protocol on the Ethereum testnet, and the experimental results show a significant improvement in overall efficiency.
Pseudorandom Correlation Functions (PCFs) allow two parties, given correlated evaluation keys, to locally generate arbitrarily many pseudorandom correlated strings, e.g. Oblivious Transfer (OT) correlations, which can then be used by the two parties to jointly run secure computation protocols. In this work, we provide a novel and simple approach for constructing PCFs for OT correlation, by relying on constrained pseudorandom functions for a class of constraints containing a weak pseudorandom function (wPRF). We then show that tweaking the Naor-Reingold pseudorandom function and relying on low-complexity pseudorandom functions allow us to instantiate our paradigm. We further extend our ideas to obtain efficient public-key PCFs, which allow the distribution of correlated keys between parties to be non-interactive: each party can generate a pair of public/secret keys, and any pair of parties can locally derive their correlated evaluation key by combining their secret key with the other partyâs public key. In addition to these theoretical contributions, we detail various optimizations and provide concrete instantiations of our paradigm relying on the Boneh-Ishai-PasselĂšgue-Sahai-Wu wPRF and the Goldreich-Applebaum-Raykov wPRF. Putting everything together, we obtain public-key PCFs with a throughput of 15kâ40k OT/s, which is of a similar order of magnitude to the state-of-the-art interactive PCFs and about 4 orders of magnitude faster than state-of-the art public-key PCFs. As a side result, we also show that public-key PCFs can serve as a building block to construct reusable designated-verifier non-interactive zero-knowledge proofs (DV-NIZK) for NP. Combined with our instantiations, this yields simple and efficient reusable DV-NIZKs for NP in pairing-free groups.
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.
The rise of modern cryptographic protocols such as Zero-Knowledge proofs and secure Multi-party Computation has led to an increased demand for a new class of symmetric primitives. Unlike traditional platforms such as servers, microcontrollers, and desktop computers, these primitives are designed to be implemented in arithmetical circuits. In terms of security evaluation, arithmetization-oriented primitives are more complex compared to traditional symmetric cryptographic primitives. The arithmetization-oriented permutation Grendel employs the Legendre Symbol to increase the growth of algebraic degrees in its nonlinear layer. To analyze the security of Grendel thoroughly, it is crucial to investigate its resilience against algebraic attacks. This paper presents a preimage attack on the sponge hash function instantiated with the complete rounds of the Grendel permutation, employing algebraic methods. A technique is introduced that enables the elimination of two complete rounds of substitution permutation networks (SPN) in the sponge hash function without significant additional cost. This method can be combined with univariate root-finding techniques and Gröbner basis attacks to break the number of rounds claimed by the designers. By employing this strategy, our attack achieves a gain of two additional rounds compared to the previous state-of-the-art attack. With no compromise to its security margin, this approach deepens our understanding of the design and analysis of such cryptographic primitives.
Modern cryptographic protocols such as zero-knowledge proofs and secure multi-party computation have increased the demand for a novel category of symmetric primitives. These primitives are not optimized for traditional platforms such as servers, microcontrollers, and desktop computers but rather for their ability to be implemented in arithmetic circuits. To enable efficient arithmetic operations, they define operations over larger finite fields and use low-degree invertible functions to construct their non-linear layers. Grendel is an arithmetization-oriented permutation that leverages the Legendre Symbol to enhance the growth of algebraic degrees in its non-linear layer. In this paper, we present a preimage attack on the sponge hash function instantiated with the full rounds of the Grendel permutation using algebraic methods. We introduce a technique that allows us to eliminate two full rounds of substitution permutation networks (SPN) in the sponge hash function with minimal or no additional cost. This method can be combined with univariate root-finding techniques and Gröbner basis attacks to break the number of rounds claimed by the designers. By utilizing this strategy, our attack achieves an improvement of two additional rounds compared to the previous state-of-the-art attack. While not breaking its security margin, it allows us to further understand the design and analysis of such cryptographic primitives.
Motivated by new applications such as secure Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Zero-Knowledge proofs (ZK), many MPC-, FHE- and ZK-friendly symmetric-key primitives that minimize the< number of multiplications over Fp for a large prime p have been recently proposed in the literature. These symmetric primitives are usually defined via invertible functions, including (i) Feistel and Lai-Massey schemes and (ii) SPN constructions instantiated with invertible non-linear S-Boxes. However, the âinvertibilityâ property is actually never required in any of the mentioned applications.In this paper, we discuss the possibility to set up MPC-/FHE-/ZK-friendly symmetric primitives instantiated with non-invertible bounded surjective functions. In contrast to one-to-one functions, each output of a l-bounded surjective function admits at most l pre-images. The simplest example is the square map x â x2 over Fp for a prime p â„ 3, which is (obviously) 2-bounded surjective. When working over Fnp for n â„ 2, we set up bounded surjective functions by re-considering the recent results proposed by Grassi, Onofri, Pedicini and Sozzi at FSE/ToSC 2022 as starting points. Given a quadratic local map F : Fmp â Fp for m â {1, 2, 3}, they proved that the shift-invariant non-linear function over Fnp defined as SF (x0, x1, . . . , xnâ1) = y0â„y1â„ . . . â„ynâ1 where yi := F(xi, xi+1) is never invertible for any n â„ 2 · m â 1. Here, we prove that âą the quadratic function F : Fmp â Fp for m â {1, 2} that minimizes the probability of having a collision for SF over Fnp is of the form F(x0, x1) = x20 + x1 (or equivalent);âą the function SF over Fnp defined as before via F(x0, x1) = x20 +x1 (or equivalent) is 2n-bounded surjective.As concrete applications, we propose modified versions of the MPC-friendly schemes MiMC, HadesMiMC, and (partially of) Hydra, and of the FHE-friendly schemes Masta, Pasta, and Rubato. By instantiating them with the bounded surjective quadratic functions proposed in this paper, we are able to improve the security and/or the performances in the target applications/protocols.
In recent years, cryptocurrencies, cryptoassets, electronic coins, tokens, non-fungible tokens, and other various terms for electronic assets have gained prodigious attention in the financial world. From the spike (and subsequent drop) in value of Bitcoin, to people spending millions of dollars on pixelated pictures of punks, the market for these assets has been extremely active despite its ups and downs. However, in addition to potential financial success via crypto markets, the development of crypto technology has allowed for a transformation of how individuals and institutions think of currency, financial security, and access to information Part I of this Comment explains what a cryptoasset is, as well as the current tax regime applicable to them. Part II defines like-kind exchanges and provides the historical context for the nonrecognition event. It also considers the IRSâs recent guidance pertaining to crypto like-kind exchanges. Part III puts forth this Commentâs main arguments for allowing crypto-for-crypto exchanges to qualify as like-kind exchanges.
The surging interest in cryptocurrency has revitalized the research for digital signature schemes with strong security. In particular, signature schemes are investigated to resist the malleability attacks in cryptocurrency platforms. However, existing signature schemes only conquer partial malleability attacks due to various sources of attacks. Other solutions of new transaction realizations cannot simultaneously avoid the malleability attacks on both standard and contract transactions. Furthermore, the malleability attack becomes more stubborn in fast clearing applications. In this paper, we propose SigNT, an accessional signature scheme with unmalleable transaction implementations. The key of SigNT is an improved interactive signature scheme for securely instant confirmation of transactions. Unlike standard signatures, this signature is generated by the owner and block producers. Combining it with several other optimizations (i.e., hash execution of intermediate transactions and secret-based claiming conditions), SigNT achieves complete resistance against malleability attacks in both the standard and contract transactions. As an example, we show an implementation in Bitcoin with the âproviding a depositâ protocol. The security analysis and comparative experiments demonstrate that SigNT has the best resistance against malleability attacks than previous malleability solutions. Besides, better performance is achieved than other schemes.
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.
Lorenzo Grassi, Silvia Onofri, Marco Pedicini, Luca Sozzi
Motivated by new applications such as secure Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Zero-Knowledge proofs (ZK), many MPC-, FHE- and ZK-friendly symmetric-key primitives that minimize the number of multiplications over Fp for a large prime p have been recently proposed in the literature. This goal is often achieved by instantiating the non-linear layer via power maps xâŠxd. In this paper, we start an analysis of new non-linear permutation functions over Fnp that can be used as building blocks in such symmetrickey primitives. Given a local map F : Fmpâ Fp, we limit ourselves to focus on S-Boxes over Fnp for n â„ m defined as SF (x0, x1, . . . , xnâ1) = y0|y1| . . . |ynâ1 where yi := F(xi, xi+1, . . . , xi+mâ1). As main results, we prove thatâą given any quadratic function F : F2pâ Fp, the corresponding S-Box SF over Fnp for n â„ 3 is never invertible;âą similarly, given any quadratic function F : F3p â Fp, the corresponding S-Box SF over Fnp for n â„ 5 is never invertible.Moreover, for each p â„ 3, we present (1st) generalizations of the Lai-Massey construction over Fnp defined as before via functions F : Fmp â Fp for each n = m â„ 2 and (2nd) (non-trivial) quadratic functions F : F3p â Fp such that SF over Fnp for n â {3, 4} is invertible. As an open problem for future work, we conjecture that for each m â„ 1 there exists a finite integer nmax(m) such that SF over Fnp defined as before via a quadratic function F : Fmp âFp is not invertible for each n â„ nmax(m). Finally, as a concrete application, we propose Neptune, a variant of the sponge hash function Poseidon, whose non-linear layer is designed by taking into account the results presented in this paper. We show that this variant leads to a concrete multiplication reduction with respect to Poseidon.
Abstract During the last years, several card-based Zero-Knowledge Proof (ZKP) protocols for Nikoliâs puzzles have been designed. Although there are relatively simple card-based ZKP protocols for a number of puzzles, such as Sudoku and Kakuro, some puzzles face difficulties in designing simple protocols. For example, Slitherlink requires novel and elaborate techniques to construct a protocol. In this study, we focus on three Nikoli puzzles: Nurikabe, Hitori, and Heyawake. To date, no card-based ZKP protocol for these puzzles has been developed, partially because they have a relatively tricky rule that colored cells should form a connected area (namely a polyomino); this rule, sometimes referred to as âBundan-kinâ (in Japanese), complicates the puzzles, as well as facilitating difficulties in designing card-based ZKP protocols. We address this challenging task and propose a method for verifying the connectivity of hidden colored cells in a ZKP manner, such that we construct card-based ZKP protocols for the three puzzles.
This paper defines a new practical construction for a code-based signature scheme. We introduce a new protocol that is designed to follow the recent paradigm known as âSigma protocol with helperâ, and prove that the protocolâs security reduces directly to the Syndrome Decoding Problem. The protocol is then converted to a full-fledged signature scheme via a sequence of generic steps that include: removing the role of the helper; incorporating a variety of protocol optimizations (using e.g., Merkle trees); applying the FiatâShamir transformation. The resulting signature scheme is EUF-CMA secure in the QROM, with the following advantages: (a) Security relies on only minimal assumptions and is backed by a long-studied NP-complete problem; (b) the trusted setup structure allows for obtaining an arbitrarily small soundness error. This minimizes the required number of repetitions, thus alleviating a major bottleneck associated with FiatâShamir schemes. We outline an initial performance estimation to confirm that our scheme is competitive with respect to existing solutions of similar type.
Shikaku is a pencil puzzle consisting of a rectangular grid, with some cells containing a number. The player has to partition the grid into rectangles such that each rectangle contains exactly one number equal to the area of that rectangle. In this paper, we propose two physical zero-knowledge proof protocols for Shikaku using a deck of playing cards, which allow a prover to physically show that he/she knows a solution of the puzzle without revealing it. Most importantly, in our second protocol we develop a general technique to physically verify a rectangle-shaped area with a certain size in a rectangular grid, which can be used to verify other problems with similar constraints.