## A Zero-Knowledge Proof of Knowledge for Subgroup Distance Problem

Cansu Betin Onur

## Abstract

In this study, we introduce a novel zero-knowledge identification scheme based on the hardness of the subgroup distance problem in the Hamming metric. The proposed protocol, named Subgroup Distance Zero Knowledge Proof (SDZKP), employs a cryptographically secure pseudorandom number generator to mask secrets and utilizes a Sterntype algorithm to ensure robust security properties.

## Index Terms

Zero-knowledge proofs, Subgroup Distance Problem, Hamming Distance

## I. INTRODUCTION

Zero-knowledge proofs (ZKPs) are cryptographic protocols that enable one party (the prover) to convince another party (the verifier) to the truth of a statement without disclosing any additional information beyond the fact that the statement is true [6], [7], [9]. Since their inception, ZKPs have become a fundamental tool in cryptographic research and applications, providing a robust method for secure authentication and privacy-preserving computations. Various identification schemes leveraging ZKPs have been proposed, each relying on different hard mathematical problems to ensure security. One of the pioneering works in this area is Stern's identification scheme, introduced in 1993, which is based on the hardness of the Syndrome Decoding (SD) problem. Stern's protocol laid the groundwork for code-based cryptographic systems, renowned for their resilience to structural attacks and potential for quantum security through the Fiat-Shamir transform. Over the years, numerous enhancements and variations of Stern's protocol have been developed, focusing on improving efficiency and reducing soundness errors.

In this study, we introduce a zero-knowledge identification scheme that relies on the Subgroup Distance Problem (SDP) in the Hamming metric, a problem known for its computational hardness in various metrics and its NP-completeness under certain conditions. The proposed protocol, named Subgroup Distance Zero Knowledge Proof (SDZKP), differs from existing schemes by leveraging the SDP, thus providing a fresh approach to zero-knowledge identification. By converting the confidential information held by the prover into integer tuples and employing a Stern-type algorithm, we ensure that our protocol inherits the robustness and security features of code-based systems.

SDZKP differs from other identification schemes in the literature in terms of the mathematical hard problem on which it is based. However, the confidential information held by the prover is converted into an integer tuple and a Stern type algorithm is executed in SDZKP. For this reason, we place our study in association with code-based protocols. The SDZKP protocol is designed to be both secure and efficient, making use of a cryptographically secure pseudorandom number generator (CSPRNG) for masking secrets. The protocol follows a three-step challenge-response structure, ensuring that the prover can convince the verifier of their knowledge of a secret without revealing any information about it. Our security analysis demonstrates that SDZKP achieves perfect completeness, 3-special-soundness, and statistical zero-knowledge, providing strong guarantees against potential attacks.

In 1993, Stern introduced a code-based identification scheme based on the hardness of the Syndrome Decoding (SD) problem [11]. His work became a foundational work on code-based cryptography. One major feature that makes Stern scheme attractive is its robustness to structural attacks. In other words,

possible attacks appears only to the underlying hard problem. Using Fiat-Shamir transform, Stern protocol can be converted to a quantum secure signature scheme. Various studies have been published focusing on improvement on efficiency and security of Stern protocol. These works are named as Stern-type protocols. First improvement given by V´ eron [12] using General Syndrome Decoding problem and reduced the number of rounds required. Both protocols have 2 3 soundness error. In 2011, Cayrel et. al. [4] and Aguilar et. al. [1] reduced Stern and V´ eron protocols soundness error respectively up to 1 2 using 5 -round protocols. In 2022, Bidoux et. al. [2] introduced an adaptation of the protocol given by Aguilar, Gaborit and Schrek (AGS) [1] on quasi-cyclic SD problem. Also in [5] a zero knowledge protocol achieving soundness error 1 n for arbitrary chosen n is presented under the constrain that the verifier trust some of the variables sent by the prover.

This paper is organized as follows: Section II covers the necessary preliminaries, including basic cryptographic definitions and an overview of the Subgroup Distance Problem. In Section III, we present the detailed design of the SDZKP protocol. Section IV provides a comprehensive security analysis. Finally, we conclude the paper highlighting the contributions and potential future directions for research.

## II. PRELIMINARIES

For any positive integer m the set { 1 , . . . m } is denoted by [ m. ] The group of permutations on the set [ n ] is denoted by S . n For a finite set A, a $ ← A denotes that a is taken uniformly at random form A. The term 'probabilistic polynomial time' is abbreviated by PPT. On inputs in P , in V respectively, the transcript of two parties P and V is denoted by V iew ( ⟨ P in ( P ) , V ( in V ) ⟩ ) and an execution between P and V giving output out is denoted by ⟨ P in ( P ) , V ( in V ) ⟩ → out. As the subgroup distance problem is defined on the symmetric group S , n the security parameter of the given scheme is n.

## A. Subgroup Distance Problem (SDP)

Given a metric d on the Symmetric group S . n The distance of a permutation α ∈ S n to a subgroup H ≤ S n is defined as

$$d ( \alpha, H ) = \underset { h \in H } { \min } \, d ( \alpha, h )$$

Definition 2.1: ( Subgroup Distance Problem (SDP) ) Given a set of elements { g, h 1 , . . . h m } from S n and given an integer k. Decide whether the distance between g and the subgroup H = ⟨ h , . . . h 1 m ⟩ is at most k.

We would like to draw readers attention to similarity of SDP problem and one of the closest vector problem (CVP) on integer lattices which is considered to be one of the hard problems for post-quantum cryptographic protocols. Roughly speaking, in both problems one is asked to decide (or search) existance of an element from a given subset close enough to given fixed element.

The computational complexity of SDP has been analyzed through various of metrics. In 2006, Pinch showed that SDP is NP-Complete [10] with respect to Cayley Distance. Subsequently, in 2009, Buchheim et al. extended this result to other metrics such as Hamming, Kendall's tau, l p , Lee's and Ulam's distances. Moreover, even when the subgroup is restricted to be an Abelian group of exponent two, the problem remains NP-complete across all these metrics.

The Hamming distance of given two permutations α, β in S n is defined as the number of different entries of α and β.

̸

$$d ( \alpha, \beta ) = | \{ i | \ \alpha ( i ) \neq \beta ( i ) \} |.$$

## B. Basic Cryptographic Definitions

Definition 2.2: A function negl : N → R ≥ 0 is called negligible function if for any natural number c there exists a lower bound n 0 such that negl n ( ) &lt; 1 n c for all n ≥ n . 0

If the probability of a situation occurring is 1 -negl n ( ) for some negligible function negl, we say that the situation appears with overwhelming probability.

Definition 2.3: For security parameter n, two distribution ensembles D ,E n n are said to be computationally indistinguishable if for any PPT algorithm A, the value of the difference

$$| \underset { x \leftarrow D _ { n } } { P r } [ A ( x ) = 1 ] - \underset { x \leftarrow E _ { n } } { P r } [ A ( x ) = 1 ] |$$

is a negligable function.

If the condition is true even if A is allowed to be unbounded, then these distributions are said to be statistically indistinguishable .

Next we define commitment schemes which are effective building blocks frequently used in ZKP design. A commitment scheme should satisfy three basic properties: correctness, binding and hiding properties. We give the definitions of these properties consequently after the definition of commitment schemes.

Definition 2.4: A commitment scheme is a polynomial time algorithm triple Com = ( Setup, Commit, V er ) satisfying correctness, binding and hiding properties. The components of Com are described as below:

- · Setup : On input 1 n , it outputs public parameters PP determining the message, the randomness, the commitment and the opening spaces. Notation: PP ← Setup (1 n ) .
- · Commit : On input PP and a message m, it outputs a commitment-opening pair formally represented as ( c, o ) ← Commit PP,m . ( )
- · V er : On input sequence ( PP,c,m,o ) it outputs a bit b. The case b = 1 refers to c is a valid commitment for m and V er accepts. In the case b = 0 , the committed value fails and V er rejects it. Formally, we represent V er as b ← V er PP, c, m, o . ( )

It is often that commitment algorithm triples take also some randomness r as input. It is implicitly used in the above given definitions.

Definition 2.5: A commitment scheme Com = ( Setup, Commit, V er ) satisfies the following properties:

- · Correctness if

$$\Pr \left [ 1 \leftarrow V e r ( P P, c, m, o ) \colon ( c, o ) \leftarrow C o m m i t ( p p, m ) \right ] = 1$$

- · Computationally (resp. Statistically) Binding if there exists a negligible function neg n ( ) such that for every PPT (resp. unbounded) algorithm A below inequality holds:

̸

$$\Pr \left [ \begin{array} { c } \ p p \leftarrow S e t u p ( 1 ^ { n } ) \\ ( c, m, m ^ { \prime }, o, o ^ { \prime } ) \leftarrow A ( p p ) \end{array} \colon \begin{array} { c } m \neq m ^ { \prime } \\ 1 \leftarrow V e r ( P P, c, m, o ) \\ 1 \leftarrow V e r ( P P, c, m ^ { \prime }, o ^ { \prime } ) \end{array} \right ] \leq n e g ( n )$$

- · Computationally (resp. Statistically) Hiding if for any two massages m,m ′ and pp ← Setup (1 n ) the distributions Commit pp,m ( ) and Commit pp,m ( ′ ) are computationally (resp. statistically) indistinguishable.

Next we define interactive protocols and zero-knowledge proof of knowledge. Informally, a zeroknowledge proof of knowledge is a two party protocol between a prover P and a verifier V such that P convinces V that it has the knowledge of a desired secret without revealing any information about the secret. Let us put this in more symbolic language.

Let R be an NP-relation and L be the language corresponding to R. That is L = { x | ∃ w : R x, w ( ) = 1 } . In a zero-knowledge proof of knowledge protocol, for a common input value x , the prover P convinces V that it knows a witness w such that R x, w ( ) = 1 .

Definition 2.6 ( Zero-knowledge proof of knowledge (ZKPoK) ): A zero-knowledge proof of knowledge protocol for language L with respect to a relation R is a protocol between a pair of interactive machines P and V named prover and verifier where P is computationally unbounded and V is probabilistic polynomialtime. It should satisfy the following conditions:

- · Completeness: For every x ∈ L , verifier V always accepts after interacting with a prover P having a witness w.

$$P r [ \langle P ( x, w ), V ( x ) \rangle \rightarrow 1 ] = 1$$

- · Proof of Knowledge (with error ϵ ): For every possibly cheating T -time PPT prover P ∗ with Pr [ ⟨ P , V ∗ ( x ) ⟩ → 1] &gt; ϵ + e there exists a PPT algorithm K (with running time polynomial in 1 e and T ) such that; given rewindable black-box access to P , ∗ on input x the algorithm K outputs a w ′ such that R x, w ( ′ ) = 1 with success probability at least 1 2 . Here K is called the knowledge extractor .
- · Zero Knowledge: For every possibly cheating PPT verifier V ∗ , there exists a PPT algorithm S, called simulator , such that on input x it outputs a transcript S x ( ) which is indistinguishable from V iew ( ⟨ P x, w , V ( ) ∗ ( x ) ⟩ ) . The zero knowledge property is called computational, statistical or perfect zero knowledge depending on whether the two distributions are computationally indistinguishable, statistical indistinguishable or equal respectively.

Under the restriction that P is a PPT algorithm in above definition, the protocol refereed as 'argument' instead of 'proof.' i.e. we define zero knowledge argument of knowledge (ZKAoK). A zero knowledge proof of knowledge is specified as honest verifier zero knowledge proof(or argument) of knowledge if the existence of a PPT simulator S giving output with indistinguishable distribution from V iew ( ⟨ P x, w , V ( ) ( x ) ⟩ ) guarantied only for the honest verifier V.

A stronger notion of knowledge soundness is (two)special-soundness. Here we give the definition of special-soundness for more generic case. Consider 3 -move protocols such that the rounds starts with the prover's move. The moves are named as commitment, challenge and response respectively. The transcripts are denoted by ( C, Ch, Rsp ) in the sequel.

Definition 2.7: A 3 -round protocol is said to have k -special-soundness property if there exists a PPT algorithm K such that for any given k distinct excepted transcripts for the same commitment C, say ( C, Ch , Rsp 1 1 ) , . . . , ( C, Ch , Rsp k k ) , the algorithm K outputs a valid witness w .

Under the assumption that k = poly x ( ) for some polynomial, k -special-soundness strictly implies knowledge soundness by a generic reduction with soundness error ϵ = ( k -1) /N , where N is the cardinality of challenge space [8].

Definition 2.8: A sigma ( Σ ) protocols is a 3 -round honest-verifier zero-knowledge proof of knowledge protocol satisfying k -special-soundness.

## III. SUBGROUP DISTANCE ZERO KNOWLEDGE PROOF (SDZKP)

In this section, we present Subgroup Distance Zero Knowledge Proof (SDZKP) in steps and illustrate it in Figure 1.

## A. Setup

In this section, under the assumption that the subgroup distance problem in Hamming metric is hard for parameters k, n and the subgroup H determined by the generators h , . . . , h 1 m ; we introduce a zero knowledge identification scheme.

The integers k, n and a set of elements { g, h 1 , . . . h m } from the Symmetric group S n are assumed to be publicly known. The prover claims that it knows an element h ∈ H = ⟨ h , . . . h 1 m ⟩ such that d h, g ( ) ≤ k.

## B. Protocol Design

Employing subgroup distance problem we design a black-box statistical zero knowledge proof of knowledge protocol that we refer to as Subgroup Distance Zero Knowledge Proof (SDZKP). In this protocol, a cryptographically secure pseudorandom number generator (CSPRNG) is used for masking secrets.

Step 1 : The prover selects an element u ∈ H, and a seed integer s for CSPRNG uniform randomly. It generates lengthn integer tuples U and G where the i th-entry of these tuples are u h i ( ( )) and u g i ( ( )) , respectively. Finally, it queries a random masking tuple R = vec n ( CSPRNG s ( )) , evaluates and sends the commitments C 1 = Comm U ( + R ) , C 2 = Comm G ( + R , C ) 3 = Comm s . ( ) Here addition U + R and G + R are component-wise addition of tuples.

Step 2 : The verifier generates a random challenge Ch ∈ { 0 1 2 , , } and sends it to the prover.

Step 3 : Depending on challenge, the prover generates and sends a response Rsp as follows:

- · If Ch = 0 , Rsp = { Z , s 1 } where Z 1 = U + R
- · If Ch = 1 , Rsp = { Z , s 2 } where Z 2 = G + R
- · If Ch = 2 , Rsp = { Z , Z 1 2 }

Step 4 : This is the verification step. If all checks are valid, then verifier accepts. Otherwise, it rejects.

- · For Ch = 0 , the verifier first checks the validity of the commitments C 1 ? = Comm ( Z 1 ) , C 3 ? = Comm ( s . ) Then using the seed s , it obtains the tuple R. It evaluates the tuple U = Z 1 -R and checks whether the corresponding permutation uh is in H.
- · For Ch = 1 , the verifier first checks the validity of the commitments C 2 ? = Comm ( Z 2 ) and C 3 ? = Comm ( s . ) Then it obtains R = vec n ( CSPRNG s ( )) , computes G = Z 2 -R. It reconstructs the permutation ug and evaluates u = ( ug g ) -1 . Then it checks whether u ∈ H.
- · For Ch = 2 , the verifier checks commitments C 1 ? = Comm ( Z 1 ) , C 2 ? = Comm ( Z 2 ) . Finally it evaluates the tuple U -G and checks whether the number of non-zero entries in U -G is less than k.

̸

Fig. 1. The message flow diagram depicting Subgroup Distance Zero Knowledge Proof (SDZKP).

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00395v1-figure-427803aa-ba08-46d7-b7fc-c0a3b56c73e2.jpg)

## IV. SECURITY ANALYSIS

In this section, we will prove that the given protocol is a zero-knowledge proof system.

Theorem 4.1: Protocol SDZKP is a black-box statistical zero knowledge proof of knowledge protocol with knowledge soundness error 2 3 .

Proof 4.1: We will show completeness, 3 -special-soundness and statistical zero knowledge properties.

- · Perfect Completeness: If a prover P having knowledge of an element h ∈ H with d h, g ( ) ≤ k follows the steps of the protocol, an honest verifier always accepts. It is known that the Hamming on

permutation groups are left-invariant [3]. Therefore for any arbitrarily chosen u ∈ H, d uh, ug ( ) = d h, g ( ) ≤ k. Hence the proof of completeness is straightforward.

- · 3-special-soundness: We show that under the assumption that the subgroup distance problem in Hamming metric is hard for parameters k, n and for the subgroup H determined by the generators h , . . . , h 1 m and under the assumption that the used commitment function Comm is computationally binding, SDZKP is 3-special-sound.
- We describe a knowledge extractor K rewinding the protocol for the same randomness u and s . We assume that K gathers three excepted transcripts ( C, Ch , Rsp 1 0 ) , ( C, Ch , Rsp 2 2 ) ( , C, Ch , Rsp 3 2 ) from P where C = ( C , C , C 1 2 3 ) = ( Comm Z ( 1 ) , Comm Z ( 2 ) , Comm s ( )) . As there are only three choices for b, without loss of generality we assume Ch 1 = 0 , Ch 2 = 1 and Ch 3 = 2 . Then Rsp 0 = { Z , s 0 1 0 } , Rsp 1 = { Z , s 1 2 1 } , Rsp 2 = { Z , Z 2 1 2 2 } . Commitment C 1 is verified for the cases Ch = 0 2 , and the commitment C 2 is verified for the cases Ch = 1 2 , . Then Z 0 1 = Z 2 1 and Z 1 2 = Z 2 2 by the binding property of Comm. Similarly s 0 = s 1 guarantied by the validity of C . 3 Therefore we will express the values as Z , Z , s 1 2 without using the Rsp index numbers. The extractor K evaluates U = Z 1 -vec n ( CSPRNG s ( )) and G = Z 2 -vec n ( CSPRNG s ( )) . Then K converts the sequences to permutations ug and uh. Lastly, it outputs h = ( ug g [ -1 ]) -1 ( uh . )
- The validity of first two transcripts guaranties that uh ∈ H and u = ug g [ -1 ] ∈ H. Then, as H is a group, we guarantee that h = u -1 ( uh ) ∈ H.

̸

- Also the last accepted transcript shows that the output h satisfies the requred distance property d h, g ( ) = d uh, ug ( ) = |{ i | ( Z 1 -Z 2 ) i = 0 }| ≤ k.
- · Zero Knowledge: Under the assumption that the used commitment scheme is statistically hiding, we show that the given protocol is statistically zero-knowledge by describing a simulator S having blackbox access to a malicious verifier V ∗ . The simulator S given in Algorithm 1 is build on challenge value prediction that will be chosen by V ∗ . Obviously, S runs in polynomial-time. It is allowed to rewind V ∗ at most M times. To see that S generates a transcript statistically indistinguishable from the view of a real interaction, we present an alternative simulator S 0 as an intermediate step in the discussion. The simulator S 0 has the knowledge of the secret h and it follows the same stages with S. i.e., it guesses the challenge value at stage 1 and it rewinds at stage 3 under the described situations in S. The difference is, S 0 does not define or use a fake h ∗ value. It evaluates commitments as described in SDZKP . Therefore, when S 0 makes a successful guess in Ch, the distribution over the commitments viewed in S 0 and in a real proof is identical. At each attempt, it has success probability 5 9 . That is S 0 outputs ⊥ with at most probability ( 4 9 ) M . Next we see that S and S 0 gives statistically indistinguishable outputs. Algorithms S and S 0 executes exactly in the same way except stage 2. At stage 2, While S 0 uses the knowlegde of the secret h, S uses a fake h ∗ value. Both algorithm gives successful output only when Ch,Ch ∗ ∈ { 0 1 , } or Ch ∗ = 2 = Ch. In each case, the committed values are Z 1 = U + R, Z 2 = G + R and s. In both algorithms s is a uniform randomly chosen seed integer for known cryptographically secure pseudorandom number generator CSPRNG. So, the distribution of chosen element s and the generated integer string R = vec n ( CSPRNG s ( )) in S is the same as the distribution of s and R obtained in S , 0 respectively. In both algorithms U and G are random shuffles of length-n integer the tuple (12 . . . n ) . Therefore the distribution of the evaluated tuples Z 1 = U + R, Z 2 = G + R in S and S 0 are statistically indistinguishable.

## V. CONCLUSION

In this paper, we have introduced a novel zero-knowledge identification scheme based on the Subgroup Distance Problem (SDP) in the Hamming metric, named Subgroup Distance Zero Knowledge Proof (SDZKP). Our protocol leverages the inherent computational hardness of the SDP to ensure robust security properties while maintaining efficiency. By utilizing a cryptographically secure pseudorandom number generator (CSPRNG) and a Stern-type algorithm, the SDZKP protocol achieves perfect completeness, 3-special-soundness, and statistical zero-knowledge proof of knowledge, making it resilient against adversaries.

## Algorithm 1 The algorithm of simulator S for SDZKP.

Require: Public parameters and security parameter M.

̸

- 1: STAGE 0 : 2: m = 1 3: STAGE 1 : Fix a random challange and a fake secret h ∗ 4: Ch ∗ $ ←{ 0 1 2 , , } 5: if Ch ∗ ∈ { 0 1 , } then 6: h ∗ $ ← H 7: else ▷ Ch ∗ = 2 8: h ∗ ← S n such that d h , g ( ∗ ) ≤ k ▷ can be done efficiently by manipulating g. 9: end if 10: STAGE 2 : Evaluate commitments using h . ∗ 11: s $ ← Z 12: U = ( h ∗ (1) . . . h ∗ ( n )) 13: G = ( h g ∗ (1) . . . h ∗ g n ( )) 14: R = vec n ( CSPRNG s ( )) 15: Z 1 = U + R 16: Z 2 = G + R 17: C 1 = Comm Z ( 1 ) 18: C 2 = Comm Z ( 2 ) 19: C 3 = Comm s ( ) 20: C = ( C , C , C 1 2 3 ) 21: STAGE 3 : Oracle access query to V ∗ and obtain Ch. 22: if Ch,Ch ∗ ∈ { 0 1 , } or Ch ∗ = 2 = Ch then 23: pass to Stage 4 24: else 25: m = m +1 . 26: if m = M, then 27: goto STAGE 1 28: else 29: return ⊥ and abort 30: end if 31: end if 32: STAGE 4 : Follow the protocol response stage with h ∗ 33: if Ch = 0 then 34: Rsp = { Z , s 1 } 35: else if Ch = 1 then 36: Rsp = { Z , s 2 } 37: else if Ch = 2 then 38: Rsp = { Z , Z 1 2 } 39: end if 40: return ( C Ch Rsp , , )

Through this work, we contribute to the ongoing research in zero-knowledge proofs by presenting a new identification scheme that expands the toolkit available to cryptographers and security practitioners. The use of the Subgroup Distance Problem as the underlying hard problem opens new avenues for designing secure cryptographic protocols.

Future work may explore further optimizations of the SDZKP protocol, as well as its application in various cryptographic settings. Additionally, investigating the integration of SDZKP with other cryptographic primitives and protocols could provide new insights and advancements in the field of secure authentication and privacy-preserving computations.

## ACKNOWLEDGEMENT

This work is partially supported by the NLnet foundation under the MoU number 2021-12-510.

## REFERENCES

- [1] C. Aguilar, P. Gaborit, and J. Schrek, 'A new zero-knowledge code based identification scheme with reduced communication,' in 2011 IEEE Information Theory Workshop . IEEE, 2011, pp. 648-652.
- [2] L. Bidoux, P. Gaborit, M. Kulkarni, and N. Sendrier, 'Quasi-cyclic stern proof of knowledge,' in 2022 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2022, pp. 1459-1464.
- [3] P. J. Cameron and T. Wu, 'The complexity of the weight problem for permutation and matrix groups,' Discrete Mathematics , vol. 310, no. 3, pp. 408-416, 2010.
- [4] P.-L. Cayrel, P. V´ eron, and S. M. El Yousfi Alaoui, 'A zero-knowledge identification scheme based on the q-ary syndrome decoding problem,' in International Workshop on Selected Areas in Cryptography . Springer, 2010, pp. 171-186.
- [5] T. Feneuil, A. Joux, and M. Rivain, 'Shared permutation for syndrome decoding: new zero-knowledge protocol and code-based signature,' Designs, Codes and Cryptography , vol. 91, no. 2, pp. 563-608, 2023.
- [6] O. Goldreich, 'Zero-knowledge twenty years after its invention.' IACR Cryptol. ePrint Arch. , vol. 2002, p. 186, 2002.
- [7] O. Goldreich, S. Micali, and A. Wigderson, 'Proofs that yield nothing but their validity or all languages in np have zero-knowledge proof systems,' Journal of the ACM (JACM) , vol. 38, no. 3, pp. 690-728, 1991.
- [8] C. Hazay and Y. Lindell, Efficient secure two-party protocols: Techniques and constructions . Springer Science &amp; Business Media, 2010.
- [9] A. Mohr, 'A survey of zero-knowledge proofs with applications to cryptography,' Southern Illinois University, Carbondale , pp. 1-12, 2007.
- [10] R. Pinch, 'The distance of a permutation from a subgroup of sn, in 'combinatorics and probability'(g. brightwell, i. leader, a. scott, a. thomason eds),' 2007.
- [11] J. Stern, 'A new identification scheme based on syndrome decoding,' in Annual International Cryptology Conference . Springer, 1993, pp. 13-21.
- [12] P. V´ eron, 'Improved identification schemes based on error-correcting codes,' Applicable Algebra in Engineering, Communication and Computing , vol. 8, pp. 57-69, 1997.
Cansu Betin Onur
A Zero-Knowledge Proof of Knowledge for Subgroup Distance Problem
In this study, we introduce a novel zero-knowledge identification scheme
based on the hardness of the subgroup distance problem in the Hamming metric.
The proposed protocol, named Subgroup Distance Zero Knowledge Proof (SDZKP),
employs a cryptographically secure pseudorandom number generator to mask
secrets and utilizes a Stern-type algorithm to ensure robust security
properties.