domain: info math

text:
Najwa Aaraj

Andre Esser

Philippe Gaborit
email: philippe.gaborit@unilim.fr

Mukul Kulkarni

Victor Mateu

Marco Palumbi

Loïc Bidoux
email: loic.bidoux@tii.ae

Table of Contents 1 Introduction

PERK is a digital signature scheme that is designed to provide security against attacks which may use quantum computers, as well as attacks by classical computers. The scheme builds on a zero-knowledge proof of knowledge system based on the conjectured post-quantum security of a variant of the Permuted Kernel Problem (PKP), and hash functions modelled as random oracles. The zeroknowledge proof is constructed from the well established MPC-in-the-head paradigm, and it is then converted into a signature scheme using the Fiat-Shamir transform in the random oracle model. The name of the scheme stems from the difficult problem based on PERmuted Kernels, at the core of the security of the protocol.

We present notations and conventions used in this document in Section 2.1, followed by the definitions of standard cryptographic primitives in Section 2.2. We provide details about proof of knowledge systems and their properties in Section 2.3. We then present definition of signature schemes in Section 2.4, followed by the background on random oracle model and Fiat-Shamir transform in Section 2.4.2. We conclude Section 2 by presenting the new definitions of the variants of the Permuted Kernel Problem (PKP), which are introduced by us in Section 2.5. We provide the constructions of our zero-knowledge proof of knowledge system in Section 3.1 and follow it up with construction of PERK signature scheme in Section 3.2. In Section 4 we give details regarding the parameter sets for different desired security levels. We provide the implementation details along with various benchmarks and performance results in Section 5. We present the formal security proofs for the zero-knowledge proof of knowledge system and PERK signature scheme in Section 6.1 and Section 6.2 respectively. We discuss the security of our proposal in the context of known attacks in Section 7.1 and Section 7.2, and analyze the concrete security estimates of our underlying hardness assumption (variant of PKP) in Section 7.3. We conclude by discussing the advantages and limitations of our proposal in Section 8.

Preliminaries

Notations and Conventions

For integers a, b we denote [a, b] the set of integers i such that a ≤ i ≤ b. We write [n] as a shorthand for [1, n]. We denote S n the group of permutations of the set [n]. Let F q denote the finite field of q elements where q is the power of a prime. Vectors are denoted by bold lower-case letters and matrices by bold capital letters (e.g., v = (v 1 , . . . , v n ) ∈ F n q and M = (m ij ) 1⩽i⩽k 1⩽j⩽n

∈ F k×n q ).
If S is a finite set, we denote by x $ ←-S that x is chosen uniformly at random from S. Similarly, we write x $,θ ←-S, if x is sampled pseudo-randomly from the set S, based on the seed θ.

We use x to denote input and denote its length by |x|. We use λ to denote the security parameter. We call a function f : N → R + negligible, if for all c ∈ N there exists a N 0 ∈ N such that f (n) < 1/n c for all n > N 0 . We write negl(λ) to denote an arbitrary negligible function. We use poly(λ) for function which is polynomially bounded in λ, that is there exists c, λ 0 ∈ N such that poly(λ) ≤ λ c for all λ ≥ λ 0 . We also abbreviate probabilistic polynomial-time as PPT.

Let X and Y be two discrete random variables defined over a finite support D. The statistical distance between the two distributions is defined as

∆(X, Y ) := 1 2 d∈D |Pr[X = d] -Pr[Y = d]|.
We say two ensembles of random variables {X λ } λ∈N , {Y λ } λ∈N are statistically close if there exists a negligible function negl : N → R + such that ∆(X λ , Y λ ) ≤ negl(λ) for all λ ∈ N. We say two ensembles of random variables {X x } x∈{0,1} * , {Y x } x∈{0,1} * are statistically close if there exists a negligible function negl : N → R + such that ∆(X x , Y x ) ≤ negl(|x|) for all x ∈ {0, 1} * .

Standard Cryptographic Primitives

Pseudorandom Generators

Definition 2.1 (Pseudorandom Generator (PRG)). Let p be a polynomial and let G be a deterministic polynomial-time algorithm such that for any λ ∈ N and any input s ∈ {0, 1} λ , the result G(s) is a string of length p(λ). We say that G is a pseudorandom generator if the following conditions hold:

1. Expansion: For every λ ∈ N it holds that p(λ) > λ.

2. Pseudorandomness: For any PPT algorithm D, there is a negligible function negl such that

|Pr[D (G(s)) = 1] -Pr[D(r) = 1]| ≤ negl(λ)
where the first probability is taken over the uniform choice of s ∈ {0, 1} λ and the randomness of D, and the second probability is taken over the choice of r ∈ {0, 1} p(λ) and the randomness of D.

We say G is (t, ϵ PRG )-secure if for every D running in time at most t(λ) the success probability of D is upper bounded by some function ϵ PRG (λ).

Collision-Resistant Hash Functions

Definition 2.2 (Collision-Resistant Hash Functions (CRHF)). Let ℓ, κ be polynomials and and let H = {H k : {0, 1} * → {0, 1} ℓ(λ) ; k ∈ {0, 1} κ(λ) } λ be a family of functions indexed by λ ∈ N. We say that H is collision-resistant if there exists a negligible function negl such that, for any PPT algorithm A it holds that,

Pr x ̸ = x ′ H k (x) = H k (x ′ ) k $ ←-{0, 1} κ(λ) ; (x, x ′ ) ←-A(k)
≤ negl(λ).

Commitments Schemes

Definition 2.3 (Commitment Scheme). A commitment scheme is a tuple of algorithms (Com, Open) such that Com(r, m) returns a commitment c for the message m and randomness r while Open(c, r, m) returns either 1 (accept) or 0 (reject). A commitment scheme is said to be correct if:

Pr b = 1 c ← Com r, m , b ← Open c, r, m = 1.
Definition 2.4 (Computationally Hiding). Let (m 0 , m 1 ) be a pair of messages, the advantage of A against the hiding experiment is defined as:

Adv hiding A (1 λ ) = Pr b = b ′ b $ ←-{0, 1}, r $ ←-{0, 1} λ c ←-Com r, m b , b ′ ←-A.guess(c) - 1 2 .
A commitment scheme is computationally hiding if for all PPT adversaries A and every pair of messages (m 0 , m 1 ), Adv hiding

A (1 λ ) is negligible in λ.
We say Com is (t, ϵ Com )-secure if for every A running in time at most t(λ) the success probability of A is upper bounded by some function ϵ Com (λ).

Definition 2.5 (Computationally Binding). The advantage of an adversary

A against the commitment binding experiment is defined as:

Adv binding A (1 λ ) = Pr   m 0 ̸ = m 1 1 ←-Open c, r 0 , m 0 1 ←-Open c, r 1 , m 1 (c, r 0 , r 1 , m 0 , m 1 ) ←-A.choose(1 λ )   .
A commitment scheme is computationally binding if for all PPT adversaries A, Adv binding A (1 λ ) is negligible in λ.

Merkle Trees

Merkle trees can be used in our context to compress randomness seeds as suggested in [KKW18]. Suppose a party needs to generate N seeds and then to send only N -1 of those seeds (without knowing in advance which seed should not be sent). The principle is to build a binary tree of depth ⌈log 2 (N )⌉. The root of the tree is labeled with a master seed θ. The rest of the tree is labeled inductively by using a PRG of double extension on each parent node and splitting the output on the left and right children.

To reveal all seeds except seed number i ∈ [N ], the principle is to reveal the labels on the siblings of the paths from the root of the tree to leave i. It allows to reconstruct all seeds but seed number i at the cost of communicating ⌊log 2 (N )⌋ labels, which is more effective than communicating N -1 seeds.

Proofs of Knowledge

2.3.1 Zero-Knowledge Proofs of Knowledge Let R ⊆ {0, 1} * × {0, 1} * be a binary relation. If (x; w) ∈ R, we say x is a statement and w is a witness for x. The set of valid witnesses for x is denoted by R(x) = {w | (x; w) ∈ R}. A statement that admits a witness is called a true or valid statement. The set of true statements is denoted by L R := {x : ∃ w such that (x; w) ∈ R}. A binary relation is said to be an NP relation if the validity of a witness w can be verified in time polynomial in the size |x| of the statement x. From now on we assume all relations to be NP relations.

An interactive proof for relation R aims for a prover P to convince a verifier V that a statement x admits a witness, or even that the prover knows a witness w ∈ R(x).

Definition 2.6 (Interactive proof (cf. [AF22])). An interactive proof Π = (P, V) for relation R is an interactive protocol between two probabilistic machines, a prover P and a polynomial time verifier V. Both P and V take as public input a statement x and, additionally, P takes as private input a witness w ∈ R(x), which is denoted as (P(w), V) (x). The verifier V either accepts or rejects the prover's claim of knowing a witness for x, this decision by the verifier is considered the output of the protocol. The set of all messages exchanged in the protocol execution is called a transcript and is denoted ⟨P(x, w), V(x)⟩. We call the either accepting (or resp. rejecting) based on whether the verifier accepts (or rejects) the prover's claim.

We assume that the prover sends the first and the last message in any interactive proof. Hence, the number of messages is always an odd number 2µ + 1. We also say Π is a (2µ + 1)-round proof. It is represented in the following figure. An interactive proof Π is complete if the verifier V accepts honest executions with a public-private input pair (x; w) ∈ R with high probability. It is sound if the verifier rejects the false statements x / ∈ L R with high probability. In this work, we follow the presentation of [AF22] and do not require these properties as part of definition of interactive proofs, but consider them as desirable additional security properties.

Definition 2.7 (Completeness (cf. [AF22])). An interactive proof Π = (P, V) for relation R is complete with completeness error ρ : {0, 1} * → [0, 1] if for every (x; w) ∈ R, Pr[(P(w), V) (x) = reject] ≤ ρ(x).
If ρ(x) = 0 for all x ∈ L R , then Π is said to be perfectly complete.

Definition 2.8 (Soundness (cf. [AF22])). An interactive protocol Π = (P, V) for relation R is sound with soundness error σ : {0, 1} * → [0, 1] if for every x /
∈ L R and every prover P * ,

Pr[(P * , V) (x) = accept] ≤ σ(x).
An interactive proof which is complete and sound allows a prover to convince a verifier that the statement x is true, i.e., x ∈ L R . However, this does not necessarily convince a verifier that the prover actually "knows" the witness w ∈ R(x). This stronger property is captured by the notion of knowledge soundness. Informally, knowledge soundness guarantees that if a prover convinces a verifier about the validity of some statement x with sufficiently high probability, then the prover can actually compute a witness w ∈ R(x) with high probability.1 Definition 2.9 (Knowledge Soundness (cf. [AF22])). An interactive protocol Π = (P, V) for relation R is knowledge sound with knowledge error ε KS : {0, 1} * → [0, 1] if there exists a positive polynomial q and an algorithm Ext, called knowledge extractor, with the following properties: The extractor Ext, given input x and rewindable oracle access to a (potentially dishonest) prover P * , runs in an expected number of steps that is polynomial in |x| and outputs a witness w ∈ R(x) with probability

Pr x; Ext P * (x) ∈ R ≥ ϵ(x, P * ) -ε KS (x) q(|x|) , where ϵ(x, P * ) := Pr[(P * , V) (x) = accept]. If ϵ(x, P * ) = Pr[(P * , V) (x) = accept] > ε KS (x)
, then the success probability of the knowledge extractor Ext in Definition 2.9 is positive. Therefore, ϵ(x, P * ) > ε KS (x) implies that x admits a witness, i.e., x ∈ L R . Hence, knowledge soundness implies soundness.

Definition 2.10 (Proof of Knowledge (cf. [AF22])). An interactive proof that is both complete with completeness error ρ(•) and knowledge sound with knowledge error ε KS (•) is a Proof of Knowledge (PoK) if there exists a polynomial q such that 1 -ρ(x) ≥ ε KS (x) + 1/q (|x|) for all x.

It is desirable to have simple verifiers which can send uniform random challenges to the prover, and efficiently verify the transcript. Public-coin protocols can be turned into non-interactive protocols by using the Fiat-Shamir transformation [FS87]. In this work, we consider only publiccoin protocols.

Next, we discuss the notion of special-soundness. Special-soundness property is easier to check than knowledge soundness and for many protocols knowledge soundness follows from special-soundness. Note that this requires special-sound protocols to be public-coin.

Definition 2.12 (k-out-of-N Special Soundness (cf. [AF22])). Let k, N ∈ N. A 3-round public-coin protocol Π = (P, V) for relation R, with challenge set of cardinality N ≥ k, is k-out-of-N special sound if
there exists a polynomial time algorithm that, on input a statement x and k accepting transcripts (cmt, ch 1 , rsp 1 ), . . . , (cmt, ch k , rsp k ) with common first message cmt and pairwise distinct challenges ch 1 , . . . , ch k , outputs a witness w ∈ R(x). We also say Π is k-special-sound and, if k = 2, it is simply called special-sound.

In order to generalize k-special-soundness to multi-round protocols we will introduce the notion of a tree of transcripts following the definitions given in [ACK21].

Definition 2.13 (Tree of Transcripts (cf. [AF22])). Let k 1 , . . . , k µ ∈ N. A (k 1 , . . . , k µ )-tree of transcripts for a (2µ + 1)-round public-coin protocol Π = (P, V) is a set of K = µ i=1 k i transcripts arranged in the following tree structure. The nodes in this tree correspond to the prover's messages and the edges to the verifier's challenges. Every node at depth i has precisely k i children corresponding to k i pairwise distinct challenges. Every transcript corresponds to exactly one path from the root to a leaf node. For a graphical representation we refer to Figure 1. We refer to the corresponding tree of challenges as a (k 1 , . . . , k µ )-tree of challenges.

We will also write k = (k 1 , . . . , k µ ) ∈ N µ and refer to a k-tree of transcripts.

Definition 2.14 ((k 1 , . . . , k µ )-out-of-(N 1 , . . . , N µ ) Special Soundness (cf. [AF22])). Let k 1 , . . . , k µ , N 1 , . . . , N µ ∈ N. A (2µ + 1)-round public-coin proto- col Π = (P, V) for a relation R, where V samples the i-th challenge from a set cmt rsp 1,1,...,1 µ . . . rsp 1,1,...,kµ µ rsp 1,1 2 ch 1,1 2 . . . rsp 1,k 2 2 ch 1,k 2 2 rsp 1 1 ch 1 1 . . . . . . . . . rsp k 1 ,1 2 ch k 1 ,1 2 . . . rsp k 1 ,k 2 ,...,1 µ . . . rsp k 1 ,k 2 ,...,kµ µ rsp k 1 ,k 2 2 ch k 1 ,k 2 2 rsp k 1 1 ch k 1 1 Fig. 1: (k 1 , k 2 , . . . , k µ ) tree of transcripts of a (2µ + 1)-round public-coin protocol of cardinality N i ≥ k i for 1 ≤ i ≤ µ, is (k 1 , . . . , k µ )-out-of-(N 1 , . . . , N µ ) special-
sound if there exists a polynomial time algorithm that, on a input statement x and a (k 1 , . . . , k µ )-tree of accepting transcripts outputs a witness w ∈ R(x). We also say Π is (k 1 , . . . , k µ ) special-sound.

The following theorem proved in [ACK21] states that special soundness implies knowledge soundness.

Theorem 2.1 ((k 1 , . . . , k µ ) Special Soundness implies Knowledge Soundness [ACK21, Theorem 1] ). Let µ, k 1 , . . . , k µ ∈ N be such that K = Π µ i=1 k i can be upper bounded by a polynomial. Let (P, V) be a (k 1 , . . . , k µ ) special sound (2µ + 1)-round interactive protocol for relation R, where V samples each challenge uniformly at random from a set of cardinality N i for 1 ≤ i ≤ µ. Then (P, V) is knowledge sound with knowledge error

ε KS = µ i=1 N i - µ i=1 (N i -k i + 1) µ i=1 N i ≤ µ i=1 k i -1 N i (1)
We write Π τ := (P τ , V τ ) for the τ -fold parallel repetition of Π, which runs τ instances of Π in parallel and the verifier V τ accepts if all the parallel instances are accepted.

The following theorem proved in [AF22] states that the knowledge soundness is retained (and knowledge error is reduced) via parallel repetition.

Theorem 2.2 (Parallel Repetition for Multi-Round Protocols [AF22, Theorem 4] ). Let (P, V) be a (k 1 , . . . , k µ )-out-of-(N 1 , . . . , N µ ) special sound protocol. Let (P τ , V τ ) be the τ -fold repetition of protocol (P, V) . Then (P τ , V τ ) is knowledge sound with knowledge error ε τ KS , where

ε KS = 1 - µ i=1 (N i -k i + 1) N i (2)
is the knowledge error of (P, V).

MPC-in-the-Head and PoK

Our construction relies on the MPC-in-the-Head (MPCitH) paradigm introduced by Ishai,Kushilevitz,Ostrovsky,and Sahai in [IKOS07,IKOS09]. This paradigm builds a zero-knowledge proof based on a secure multiparty computation (MPC) protocol. Informally, the MPC protocol is used to compute the verification of an NP relation, where the privacy guarantee of the protocol is used to achieve the zero-knowledge property.

The main steps of the proof of knowledge resulting from the MPCitH technique are the following:

1. The prover splits its witness into N parties by secret sharing the witness; 2. The prover then simulates locally ("in her head") all the parties of the MPC protocol which evaluates a boolean function that is expected to be 1 whenever the witness is correct (this is supposed to correspond to the verification of desired NP relation); 3. The prover commits to the views of all the parties in the MPC protocol; 4. The verifier chooses a random subset of N ′ < N parties and asks to reveal their corresponding views; 5. The verifier finally checks that the views of the revealed parties are consistent with each other and with an honest execution of the MPC protocol that yields output 1.

This transformation achieves the zero-knowledge property as long as the views of any N ′ parties do not leak any information about the secret witness.

Since our proof of knowledge is an instantiation of the MPCitH technique for the specific case of r-IPKP, it benefits from an extensive literature of optimizations generic to any MPCitH construction, such as:

-The preprocessing extension, introduced in [KKW18], allows the MPC protocol -used in the MPCitH technique -to rely on a preprocessing phase (under certain conditions) thus drastically reducing the proof size; -the challenge space amplification technique, introduced in [BG23], that is itself an optimization of the PoK with Helper paradigm introduced in [Beu20]; -Merkle trees to reveal a partial number of random seeds, as explained in Section 2.2.4.

Digital Signature Schemes

Definition and properties

Definition 2.16 (Signature Scheme). A signature scheme consists of three probabilistic polynomial time algorithms (KeyGen, Sign, Vf) which work as follows:

-KeyGen 1 λ : The key generation algorithm takes a security parameter as input and outputs a pair of keys (pk, sk). The key sk is the private (secret) signing key and pk is the public key used for verification. -Sign sk (m): The signing algorithm takes as input a secret signing key sk and a message m from some message space (that may depend on pk). It outputs a signature σ ← Sign sk (m). -Vf pk (m, σ): The deterministic verification algorithm takes as input a public key pk, a message m, and a signature σ. It outputs a bit b := Vf pk (m, σ), with b = 1 meaning the signature-message pair is valid and b = 0 meaning it is invalid.

Definition 2.17 (EUF-CMA Security). A signature scheme (KeyGen, Sign, Vf) is EUF-CMA secure if, for all PPT adversaries A there is a negligible function negl(•) such that,

Pr Vf pk (m * , σ * ) = 1 (m * , •) / ∈ Q Sign (pk, sk) ←-KeyGen(1 λ ), (m * , σ * ) ←-A Sign sk (•) (pk) ≤ negl(λ).
where the environment keeps track of the queries to and from the signing oracle via Q Sign .

Fiat-Shamir Transformation

In this section, we explain the random oracle model and Fiat-Shamir transformation used for transforming interactive protocols into non-interactive ones. We closely follow the presentation of [AFK22, Section 2.3] in the following exposition.

In the random oracle model (ROM), algorithms have black-box (or inputoutput) access to an oracle RO : {0, 1} * → Z, called as random oracle, which is instantiated with a uniform random function with domain {0, 1} * and codomain Z. Generally, Z = {0, 1} η for some η ∈ N related to the security parameter. In practice, RO can be implemented by lazy sampling, which means for each input string x ∈ {0, 1} * , RO(x) is sampled uniform randomly from Z and then fixed. To avoid technical difficulties, we limit the domain from {0, 1} * to {0, 1} ≤ℓ , the finite set of all bitstrings of length at most ℓ, for a sufficiently large ℓ ∈ N.

An algorithm A RO that is given black-box access to a random oracle is called a random oracle algorithm. We say A is a Q-query random-oracle algorithm, if it makes at most Q queries to RO (independent of RO).

A natural extension of the ROM is when A is given access to multiple independent random oracles RO 1 , RO 2 , . . . , RO µ , possibly with different codomains. In practice, these random oracles can be instantiated by a single random oracle RO : {0, 1} * → {0, 1} η using the standard techniques for domain separation (refer to [BDG20] for more details) and for sampling random elements from non-binary sets.

The Fiat-Shamir transform [FS87], turns a public-coin interactive proof into a non-interactive proof in random oracle model. The general idea of this transformation is to compute the i-th challenge message ch i as a hash of the i-th prover message a i along with (partial) communication transcript generated till that point. For a Σ-protocol, the challenge ch is computed as ch := H(cmt) or as ch := H(x, cmt), where the former is sufficient for static security, where the statement x is given as input to the dishonest prover, and the latter is necessary for adaptive security, where the dishonest prover can choose the statement x for which it wants to forge a proof.

For multi-round public-coin interactive proofs, there is some degree of freedom in the computation of the i-th challenge. For concreteness we consider a particular version where all previous messages are hashed along with the current message.

Let Π = (P, V) be a (2µ + 1)-round public-coin interactive proof, where the challenge for the i-th round is sampled from set CH i . For simplicity, we consider µ random oracles RO i : {0, 1} ≤ℓ → CH i that map into the respective challenge spaces.

Definition 2.18 )). The static Fiat-Shamir transformation FS [Π] = (P fs , V fs ) is non-interactive proof in ROM, where P RO1.RO2....,ROµ fs (x; w) runs P(x; w) but instead of asking the verifier for the challenge ch i on message a i , the challenges are computed as

ch i = RO i (a 1 , a 2 , . . . , a i-1 , a i ) ;
(3) the output is then the proof π = (a 1 , . . . , a µ+1 ). On input a statement x and a proof π = (a 1 , . . . , a µ+1 ), P RO1.RO2....,ROµ fs

(x, π) accepts if, for ch i as above V accepts the transcript (a 1 , ch 1 , . . . a µ , ch µ , a µ+1 ) on input x.
If the challenges are computed as

ch i = RO i (x, a 1 , ch 1 , . . . a i-1 , ch i-1 , a i ) ; (4)
the resulting non-interactive proof in ROM is called as the adaptive Fiat-Shamir transformation.

The Permuted Kernel Problem and its Variants

In this subsection we give definitions of the computationally hard problems underlying the security of our proposed signature scheme. We start by defining the classical Permuted Kernel Problem [Sha90] in its generic form, similar to [SBC22]: with an inhomogeneous syndrome y as well as a dimension parameter t.

Definition 2. 19 (IPKP problem). Let (q, m, n, t) be positive integers such that m < n,

H ∈ F m×n q , (x i , y i ) ∈ F n q × F m q and π ∈ S n be a permutation such that H π[x i ] = y i for i ∈ [t]
. Furthermore, the matrix whose columns are the x i has full rank. Given H, (x i , y i ) i∈[t] , the Inhomogeneous Permuted Kernel Problem IPKP(q, m, n, t) asks to find π.

The IPKP problem was originally introduced with t = 1 only; in the rest of the article we refer to this version of the problem as mono-dimensional IPKP. Correspondingly, we refer with multi-dimensional IPKP to instances with arbitrary choices of t > 1.

Instead of directly relying on the hardness of IPKP, we consider a relaxed version r-IPKP which allows for more efficient constructions. In this relaxed variant the searched permutation does not necessarily have to satisfy the identity for all given pairs but only for an arbitrary (non-zero) linear combination of those pairs. Definition 2.20 (r-IPKP). Let (q, m, n, t) be positive integers such that m < n,

H ∈ F m×n q , (x i , y i ) ∈ F n q ×F m q and π ∈ S n be a permutation such that H π[x i ] = y i for i ∈ [t]
. Furthermore, the matrix whose columns are the x i has full rank. Given H, (x i , y i ) i∈[t] , the Relaxed Inhomogeneous Permuted Kernel Problem r-IPKP(q, m, n, t) asks to find any π ∈ S n such that H π

i∈[t] κ i • x i = i∈[t] κ i • y i for any κ ∈ F t q \ 0
, where κ := {κ 1 , . . . , κ t } and 0 ∈ F t q is the all zero vector.

The respective hardness of the two above problems are discussed in Section 7.3.

Specifications

PoK for the r-IPKP

Problem Let x = H, (x i , y i ) i∈[t] and let w = π ∈ S n as defined in Definition 2.20. Let R t-r-IPKP be a relation for r-IPKP problem defined as, R t-r-IPKP := H, (x i , y i ) i∈[t] ; π : H π i∈[1,t] κ i • x i = i∈[1,t] κ i • y i for any κ ∈ F q t \ 0
We now present our protocol in Figure 2 that is inspired from [BG23] and [FJR23]. Informally, it consists of three main steps, following the MPCitH paradigm:

1. In the commitment step, the witness π is split into

N compositional shares π 1 , . . . , π N such that π = π N • π N -1 • • • • • π 1 .
The prover also generates N (pseudo) random vectors v 1 , . . . , v N in F n q . The compositional and vector shares are then combined to construct a syndrome Hv, which is committed together with the generated shares (π i s and v i s).

2. The verifier then sends coefficients κ i of an F q -linear combination as a first challenge. The prover then computes values s 1 , . . . , s N with the help of the π i and v i values committed earlier and the public statement

x = H, (x i , y i ) i∈[t]
, such that Hs N = Hv + i∈[t] κ i y i . The prover then sends s i values as its response. In the actual protocol we use a collision-resistant hash function to compress the information sent to the verifier.

3. Finally, the verifier sends an index α ∈ [N ] as the second challenge. The prover reveals all shares π i and v i except the ones with index α. Additionally, the prover reveals the share s α . This allows the verifier to verify the consistency of the views of all the shares except the ones with index α by recomputing the commitments. The verifier can also recompute all the s i values for i ̸ = α and together with s α sent by the prover, the verifier can then reconstruct s N . Finally the verifier computes Hv = Hs N -κ i y i and checks if this value is consistent with the commitment received in first message (Step 1 above). The protocol in Figure 2 satisfies completeness, knowledge soundness, and zero-knowledge properties as stated in Theorem 3.1, Theorem 3.2, and Theorem 3.3 respectively. Theorem 3.1 (Completeness). The protocol presented in Figure 2 is perfectly complete.

Prover P Verifier V Input: (x = (H, (xi) i∈[1,t] , (yi) i∈[1,t] ), w = π) Input: x = (H, (xi) i∈[1,t] , (yi) i∈[1,t] ) θ $ ←-{0, 1} λ For i ∈ {N, . . . , 1}, ⋄ θi $,θ ←-{0, 1} λ , ϕi $,θ i ←-{0, 1} λ , r1,i $,θ i ←-{0, 1} λ ⋄ If i ̸ = 1, πi $,ϕ i ←-Sn, vi $,ϕ i ←-F n q , cmt1,i = Com r1,i, ϕi ⋄ If i = 1, π1 = π -1 2 • • • • • π -1 N • π, v1 $,ϕ 1 ←-F n q , cmt1,1 = Com r1,1, π1 || ϕ1 r1 $,θ ←-{0, 1} λ , v = v N + i∈[1,N -1] π N • • • • • πi+1[vi] cmt1 = Com r1, Hv h1 = H(cmt1, (cmt1,i) i∈[1,N ] ) h1 (κi) i∈[1,t] $ ←-F t q (κi) i∈[1,t] s0 = i∈[1,t] κi • xi For i ∈ [1, N ], ⋄ si = πi[si-1] + vi h2 = H((si) i∈[1,N ] ) h2 α $ ←-[1, N ] α z1 = sα If α ̸ = 1, z2 = (r1 ||π1 || (θi) i∈[1,N ]\α ) If α = 1, z2 = (r1 || (θi) i∈[1,N ]\α ) rsp = (z1, z2, cmt1,α) rsp Compute r1, ( φi, r1,i, πi, vi)i∈[1,N]\α from z2 s0 = i∈[1,t] κi • xi, sα = z1, c mt1,α = cmt1,α For i ∈ [1, N ] \ α, ⋄ si = πi[ si-1] + vi ⋄ If i ̸ = 1, c mt1,i = Com r1,i, φi ⋄ If i = 1, c mt1,1 = Com r1,1, π1 || φ1 cmt1 = Com r1, Hs N -i∈[1,t] κi • yi b1 ←-h1 = H( cmt1, ( cmt1,i) i∈[1,N ] ) b2 ←-h2 = H((si) i∈[1,N ] ) return b1 ∧ b2
Proof. The completeness follows from the protocol description once it is observed that s

N = π i∈[1,t] κ i • x i + v which implies that Hs N - i∈[1,t] κ i • y i = Hπ   i∈[1,t] κ i • x i   + Hv - i∈[1,t] κ i • y i = Hv.
Therefore for every true statement (H, (

x i ) i∈[1,t] , (y i ) i∈[1,t]
) with witness π if the protocol described in Figure 2 is executed honestly then the verifier V accepts with probability 1 for all possible random choices of P and V. ⊓ ⊔ Theorem 3.2 (Knowledge Soundness). The protocol presented in Figure 2 is knowledge sound with knowledge error

ε KS = 1 N + N -1 N • (q t -1)
.

Theorem 3.3 (Special Honest-Verifier Zero Knowledge). Assume that there exists a (t, ϵ PRG )-secure PRG, and the commitment scheme Com is (t, ϵ Com )hiding. Then there exists an efficient simulator Sim which, outputs a transcript such that no distinguisher running in time at most t(λ) can distinguish between the transcript produced by Sim and a real transcript obtained by honest execution of the protocol in Figure 2 with probability better than (ϵ PRG (λ) + ϵ Com (λ)).

We prove Theorem 3.2 and Theorem 3.3 in Section 6.1.1 and Section 6.1.2 respectively.

The PERK Digital Signature Scheme

We now present the signature scheme in Figure 3, Figure 4, and Figure 5 based on the Fiat-Shamir transformation of protocol shown in Figure 2.

1. Sample sk_seed $ ←-{0, 1} λ and pk_seed $ ←-{0, 1} λ 2. Sample π ←-PRG(sk_seed) from Sn 3. Sample (H, (xj ) j∈[1,t] ) ←-PRG(pk_seed) from F m×n q × (F n q ) t 3. For j ∈ [1, t], ⋄ Compute yj = Hπ[xj ] 4. Output (sk, pk) = (sk_seed, (pk_seed, (yj ) j∈[1,t] )) Fig. 3: PERK -KeyGen algorithm Inputs -Secret key sk = sk_seed -Public key pk = (pk_seed, (yj ) j∈[1,t] ) -Message m ∈ {0, 1} * Step 1: Commitment 1. Sample π ←-PRG(sk_seed) from Sn 2. Sample (H, (xj ) j∈[1,t] ) ←-PRG(pk_seed) from F m×n q × (F n q ) t
3. Sample salt and master seed (salt, mseed)

$ ←-{0, 1} 2λ × {0, 1} λ 4. Sample seeds (θ (e) ) e∈[1,τ ] ←-PRG(salt, mseed) from ({0, 1} λ ) τ 5. For each iteration e ∈ [1, τ ], ⋄ Compute (θ (e) i ) i∈[1,N ] ←-TreePRG(salt, θ (e) ) ⋄ For each party i ∈ {N, . . . , 1}, -If i ̸ = 1, sample (π (e) i , v (e) i ) ←-PRG(salt, θ (e) i ) from Sn × F n q -If i = 1, sample v (e) 1 ←-PRG(salt, θ (e) 1 ) from F n q -If i ̸ = 1, compute cmt (e) 1,i = H0(salt, e, i, θ (e) i ) -If i = 1, compute π (e) 1 = (π (e) 2 ) -1 • • • • • (π (e) N ) -1 • π and cmt (e) 1,1 = H0(salt, e, 1, π (e) 1 , θ (e) 1 ) ⋄ Compute v (e) = v (e) N + i∈[1,N -1] π (e) N • • • • • π (e) i+1 [v (e)
i ] and cmt (e) 1 = H0(salt, e, Hv (e) )

Step 2: First Challenge

6. Compute h1 = H1(salt, m, pk, (cmt (e) 1 , cmt (e) 1,i ) e∈[1,τ ],i∈[1,N ] ) 7. Sample (κ (e) j ) e∈[1,τ ],j∈[1,t] ←-PRG(h1) from (F t q ) τ
Step 3: First Response

8. For each iteration e ∈ [1, τ ], ⋄ Compute s (e) 0 = j∈[1,t] κ (e) j • xj ⋄ For each party i ∈ [1, N ], -Compute s (e) i = π (e) i [s (e) i-1 ] + v (e) i
Step 4: Second Challenge 9. Compute h2 = H2(salt, m, pk, h1, (s

(e) i ) e∈[1,τ ],i∈[1,N ] ) 10. Sample (α (e) ) e∈[1,τ ] ←-PRG(h2) from ([1, N ]) τ
Step 5: Second Response Step 1: Parse signature

11. For each iteration e ∈ [1, τ ], ⋄ Compute z (e) 1 = s (e) α ⋄ If α (e) ̸ = 1, z (e) 2 = (π (e) 1 || (θ (e) i ) i∈[1,N ]\α (e) ) ⋄ If α (e) = 1, z (e) 2 = (θ (e) i ) i∈[1,N ]\α (e) ⋄ Compute rsp (e) = (z (e) 1 , z (e) 2 , cmt
1. Sample (H, (xj ) j∈[1,t] ) ←-PRG(pk_seed) from F m×n q × (F n q ) t
2. Parse signature as σ = (salt, h1, h2, (z

(e) 1 , z (e) 2 , cmt (e) 1,α (e) ) e∈[1,τ ] ) 3. Recompute (κ (e) j ) e∈[1,τ ],j∈[1,t] ←-PRG(h1) from (F t q ) τ 4. Recompute (α (e) ) e∈[1,τ ] ←-PRG(h2) from ([1, N ]) τ
Step 2: Verification

5. For each iteration e ∈ [1, τ ], ⋄ Compute s (e) 0 = j∈[1,t] κ (e) j • xj and s (e) α = z (e) 1 ⋄ Compute (π (e) i , v (e) i ) i∈[1,N ]\α from z (e) 2 ⋄ For each party i ∈ [1, N ] \ α (e) , -If i ̸ = 1, compute cmt (e)
1,i = H0(salt, e, i, θ

i )

-If i = 1, compute cmt (e)
1,1 = H0(salt, e, 1, π

(e) 1 , θ (e) 1 ) ⋄ For each party i ∈ [1, N ] \ α (e) , -Compute s (e) i = π (e) i [s (e) i-1 ] + v (e) i ⋄ Compute cmt (e) 1 = H0(salt, e, Hs (e) N -j∈[1,t] κ (e) j • yj ) 6. Compute h1 = H1(salt, m, pk, (cmt (e) 1 , cmt (e) 1,i ) e∈[1,τ ],i∈[1,N ] ). 7. Compute h2 = H2(salt, m, pk, h1, (s (e) i ) e∈[1,τ ],i∈[1,N ] ).
8. Output accept if and only if h1 = h1 and h2 = h2.

Fig. 5: PERK -Verify algorithm

Theorem 3.4. Suppose PRG is (t, ϵ PRG )-secure and any adversary running in time t(λ) can solve the the underlying r-IPKP instance with probability at most ϵ r-IPKP . Model H 0 , H 1 , and H 2 as random oracles where H 0 , H 1 , and H 2 have 2λbit output length. Then chosen-message attacker against the signature scheme (PERK) presented in Figure 4, running in time t(λ), making q s signing queries, and making q 0 , q 1 , q 2 queries, respectively, to the random oracles, succeeds in outputting a valid forgery with probability

Pr[Forge] ≤ (q 0 + τ • (N + 1) • q s ) 2 2 • 2 2λ + q s • (q 0 + q 1 + q 2 + q s ) 2 2λ + τ • q s • ϵ PRG (λ) + ϵ r-IPKP + q 2 • ε τ KS , (5)
where

ε KS = 1 N + N -1 N •(q t -1
) . We prove Theorem 3.4 in Section 6.2.1.

Parameter Sets

Parameter Choice

The parameters were chosen as follows:

-PKP parameters (q, n, m, t): Parameters specific to the r-IPKP instance were chosen so as to minimize the signature size while offering concrete bit-security of r-IPKP above the NIST specified thresholds of 143, 207 and 272 bit for category I, III and V. Here we disregard any polynomial factors or additional cost induced by memory access. We give full details on estimating the security of r-IPKP in Section 7.3. We present two sets of parameters for each category, depending on whether t = 3 or t = 5. -MPC parameters (N, τ ): The number of parties and iterations is governed by the knowledge soundness of the protocol. The MPC parameters are also chosen to guarantee a soundness probability of 2 -λ for λ ∈ {128, 192, 256} for category I, III and V respectively. For deriving the soundness we also take into account the Kales-Zavurecha attack, see Section 7.1. Following common practice we propose again two different parameter sets, a short variant using N = 256 and a fast variant using N = 32. 1: Parameters of PERK signature scheme. The aforementioned sizes are the ones used in our implementations except that we also concatenate the public key within the secret key in order to respect the NIST API.

Key and Signature Sizes

Key size. The private key as well as most of the components of the public key can be derived from a seed. The only elements not generated from a seed in the public key are the t syndromes (y i ).

Signature size. The signature consists of a salt and two hashes (h 1 , h 2 ), making a subtotal of 6λ bits, and then τ repetitions of the following:

-A vector z (e) 1 ∈ F n q ; -A permutation in S n ; -N -1 seeds (of size λ) arranged in a PRG tree, hence of size only λ•⌈log 2 (N )⌉; -A commitment cmt (e) 1,α (e) of size 2λ.
Overall, for a security level λ, the key and signature sizes for our signature scheme are captured by the following formulas:

Public key size (bits)

λ + t • m⌈log 2 (q)⌉ Signature size (bits) 6λ + τ • n⌈log 2 (q)⌉ vector in F n q + n⌈log 2 (n)⌉ permutation + λ⌈log 2 (N )⌉ seeds + 2λ commitment
log 2 (n 2 ) < 2⌈log 2 (n)⌉,
the packed permutation takes less memory size. Numbers given in Table 1 take into account this compression technique.

Implementations and Performances

5.1 Instantiation of the scheme 5.1.1 Representation of objects Field elements. Elements of F q are stored in 16 bit unsigned integers.

Vectors. A vector of F n q (respectively F m q ) are represented as an array of length n (respectively of length m) of F q elements.

Matrices.

A matrix H ∈ F m×n q is represented as a two dimensional array of F q elements i.e. an array of length m of arrays of length n.

Permutations. An element of S n is represented as an array of length n of elements in [0, n -1].

Randomness and objects generation

In order to sample elements of F q , we sample a random 16 bits value by getting two bytes from the PRG and assigning the first to the less significant bits and the second to the most significant bits (little endian), then we take the lower ⌈log 2 (q)⌉ bits, rejecting the value if it is equal or greater than q. Random vectors in F n q (respectively matrices in F m×n q ) are sampled uniformly by sampling n (respectively m × n) elements in F q following the aforementioned procedure.

Random permutations in S n are generated using the constant time sorting software djbsort [Ber19]. More precisely, to generate a permutation π ∈ S n , we start with a vector v = (v 0 , • • • , v n-1 ) = (0, 1, • • • , n -1), then we sample a random vector e = (e 0 , • • • , e n-1 ) ∈ (F 16

2 ) n , and we construct a vector p = (p 0 , • • • , p n-1 ), where the high-order bits of p i corresponds to e i and the lowerbits order of p i corresponds to v i . We then sort this integer sequence in constanttime using djbsort, and we extract the permutation π from the lower-order bits p. If there are any duplicate values in the vector e, we discard it and generate a new one. To apply a permutation π ∈ S n to a vector v ∈ F n q , we follow the same process while replacing the vector e by the coefficients of the permutation π.

Parsing objects from/to byte strings

Vectors of F n q (respectively, F m q ) are converted to byte strings using a compact representation in which the unused bits of each element are removed, thus leading to n⌈log 2 (q)⌉ (respectively, m⌈log 2 (q)⌉) long bit string. The compact representation is used for the public key pk, to parse the t syndromes (y i ) and for the signature σ to parse the vectors z (e) 1 ∈ F n q . During the parsing, the coefficients of all the vectors are packed together ensuring that no space is lost between them.

To optimize space usage, the permutations coefficients are packed in couples using the following process. TreePRG. When signing, the signer must generate, for each iteration, a set of N seeds, then reveal N -1 of these based on the challenge. The seeds are then used by the verifier to check that the MPC protocol was setup or simulated correctly. By deriving seeds deterministically in a binary tree, then using the leaf seeds in the protocol, the signer can reveal the N -1 seeds efficiently by revealing intermediate nodes in the tree. In our setting, N is always a power of 2. Seeds are of size λ bits. Nodes and leaves, of size λ bits, are generated using the hash function. The constant H 3 = 0x03 is a domain separator and encoded over one byte. The salt value salt is of size 2 • λ bits.

Expand Tree (sig_perk_expand_theta_tree) Input: A root seed rseed, a salt value salt.

Output: A binary tree consisting in a root seed, N -2 nodes and N leaves (seeds). Nodes, starting from rseed (node 0 ), are indexed from top to down, left to right. Each node generates a digest (2 • λ bits wide) using the hash function H:

digest = H (salt||idx||node i ||H 3 )
where idx is one byte containing the node index. Then set the left child of the node to the leftmost λ bits, and the right child to the rightmost λ bits.

Get Partial Tree Seeds (sig_perk_get_theta_partial_tree_seeds)

Input: A binary tree consisting in a root seed, N -2 nodes and N leaves (seeds) and the index α of the hidden seed. Output: An array of L = log 2 (N ) seeds that allow to rebuild the leaf seeds minus the α one.

The tree is traversed from top to bottom following the path to the α leaf. For each level after the root one, the sibling node/leaf is saved.

Expand Partial Tree (sig_perk_expand_theta_partial_tree) Input: An array of L = log 2 (N ) seeds and the index α of the hidden seed. Output: The partial seed tree where the nodes belonging to the path to α leaf are missing.

The tree is built as in Expand Tree, using the nodes in the array for the siblings belonging to the path to the α leaf.

Keys and signature representation

The secret key sk = π is represented as sk = (sk_seed) where sk_seed is a λ bits seed used to generate π. The public key pk = (H, (

x i ) i∈[1,t] , (y i ) i∈[1,t] ) is represented as pk = (pk_seed, (y i ) i∈[1,t]
) where pk_seed is a λ bits seed used to generate H and

(x i ) i∈[1,t] . The signature σ is represented as (salt, h 1 , h 2 , (rsp (e) ) e∈[1,τ ] ) where:
salt is 2 • λ bits salt generated using the randombytes function ; h 1 (respectively, h 2 ) is a 2 • λ bits digest generated using the hash function The constant H 0 = 0x00 is a domain separator and encoded over one byte.

H(•∥H 1 ) (respectively, H(•∥H 2 )).

Benchmarks and Performances

This section provides performance measures of our PERK implementations.

Benchmark platform. The benchmarks have been performed on a machine running Ubuntu 22.04.2 LTS, that has 64 GB of memory and an Intel ® Core™ i9-13900K @ 3.00 GHz for which the Hyper-Threading and Turbo Boost features were disabled. For each parameter set, the results have been obtained by computing the average from 1000 random instances. The scheme have been compiled with gcc (version 11.3.0). The following third party libraries have been used: XKCP (commit 7fa59c0ec4) and djbsort (version 20190516).

The current implementation require more than 8 MBytes of stack to run the NIST level V parameter sets hence one might need to increase the available stack to run them on some platforms, see the technical documentation (readme file) for additional instructions.

Reference Implementation

The reference implementation is written in C and have been compiled using the compilation flags -O3 -funroll-all-loops -march=native. The performances of our reference implementation on the aforementioned benchmark platform are described Tab. 3. Table 3: Performances of the reference implementation for different instances of PERK. The key generation numbers are in kilo CPU cycles, while the signing and verification numbers are in million CPU cycles.

Optimized Implementation

A constant-time optimized implementation leveraging AVX2 instructions have been provided. Its performances on the aforementioned benchmark platform are described in Tab. 4. The following optimization flags have been used during compilation: -O3 -funroll-all-loops -march=native -mavx2 -mpclmul -msse4.2 -maes. There are two main differences between the reference and optimized implementation. Firstly, the optimized implementation utilizes optimized AVX2 implementations provided by the libraries XKCP and djbsort, whereas the reference implementation relies on 64bit platform plain C implementation of the aforementioned libraries. Secondly, the optimized implementation uses the vectorized implementation from XKCP of 4 parallel instances of Keccak, while the reference implementation uses the non parallel feature.

Known Answer Test Values

Known Answer Test (KAT) values have been generated using the script provided by the NIST. They are available in the folder KATs and files are the same for both reference and optimized implementation. In addition, examples with intermediate values have also been provided in these folders. Notice that one can generate the aforementioned test files using respectively the kat and verbose modes of our implementation. The procedure to follow in order to do so is detailed in the technical documentation.

Expected Security Strength

Our signature scheme is EUF-CMA in the ROM under the assumption of hardness of r-IPKP and with a choice of repetitions τ that makes the probability of a forgery negligible.

The proof of EUF-CMA, written below, happens in two stages:

-We first prove the knowledge soundness and the special honest-verifier zero knowledge of the PoK in Figure 2; -We build on the previous proof to prove that the signature scheme is EUF-CMA.

The estimation of hardness for r-IPKP is given in 7.3 and the choice of τ is covered in 7.1.

6.1 Security Proofs for the Proof of Knowledge 6.1.1 Proof of Theorem 3.2 We restate the Theorem 3.2 below and follow it by its proof.

Theorem 3.2 (Knowledge Soundness). The protocol presented in Figure 2 is knowledge sound with knowledge error

ε KS = 1 N + N -1 N • (q t -1)
.

Proof (Proof of Theorem 3.2). Before proving the knowledge soundness of our protocol, we will first prove the following useful lemma.

Lemma 6.1 ((2, 2)-special soundness). The protocol shown in Figure 2 ). We now show such an extractor which takes 4 accepting transcripts associated with challenges (κ, α 1 ), (κ, α 2 ), (κ ′ , α 1 ), (κ

′ , α 2 ) such that κ = (κ i ) i∈[1,t] , κ ′ = (κ ′ i ) i∈[1,t]
as well as κ ̸ = κ ′ and α 1 ̸ = α 2 , and outputs a solution to the r-IPKP instance defined by (H, (

x i ) i∈[1,t] , (y i ) i∈[1,t] ). Let z (κ * ,α * ) 2
denote the response z 2 computed as shown in Figure 2 when the first and second challenges are κ * and α * respectively. Note that, z (κ,α1) 2 contains all the seeds θ i for i ∈ [1, N ] except i = α 1 . Therefore, the extractor has access to all the seeds θ i for i ∈ [1, N ] since it knows both z (κ,α1) 2 as well as z

(κ,α2) 2 and α 1 ̸ = α 2 . It can compute (π (κ) i , v(κ) i ) i∈[1,N ] and (π (κ ′ ) i , v(κ ′ ) i ) i∈[1,N ] from z (κ,αi) 2 i∈[1,2] and z (κ ′ ,αi) 2 i∈[1,2] respectively. Also, note that the first message h 1 = H(cmt 1 , (cmt 1,i ) i∈[1,N ]
) is common to all the 4 transcripts. Since we assume that H is a collision-resistant hash function, it means that the initial commitments (cmt 1 , (cmt 1,i ) i∈[1,N ] ) are all same in the 4 transcripts. From the binding property of the commitments (cmt 1,i ) i∈[1,N ] , we know that

(π i , vi ) i∈[1,N ] = (π (κ) i , v(κ) i ) i∈[1,N ] = (π (κ ′ ) i , v(κ ′ ) i ) i∈[1,N ] .
The knowledge extractor Ext computes the solution as

1. Compute (πi) i∈[1,n] from z (κ,α 1 ) 2 and z (κ,α 2 ) 2 2. Output π = πN • • • • • π1
Let us now check the validity of this solution output by the extractor. By construction, we know that s(κ,α1)

0 = s(κ,α2) 0 = i∈[1,t] κ i • x i . Also, for all i ∈ [1, N ] \ α 1 , s(κ,α1) i = πi [s (κ,α1) i-1 ] + vi . And for all i ∈ [1, N ] \ α 2 , s(κ,α2) i = πi [s (κ,α2) i-1 ] + vi .
Since the transcripts are accepting and V checks h 2 computed as

h 2 = H((s i ) i∈[1,N ] ), due to the collision-resistance property of H, it follows that for all i ∈ [1, N ], s(κ) i = πi [s (κ) i-1 ] + vi , this implies s(κ) N = π[ i∈[1,t] κ i • x i ] + v.
Following a similar argument, we know that

s(κ ′ ) N = π[ i∈[1,t] κ ′ i • x i ] + v.
Based on the binding property of commitment cmt 1 and using the fact that the transcripts are accepting, we can write

Hs (κ) N - i∈[1,t] κ i • y i = Hs (κ ′ ) N - i∈[1,t] κ ′ i • y i =⇒ H(π[ i∈[1,t] κ i • x i ] + v) - i∈[1,t] κ i • y i = H(π[ i∈[1,t] κ ′ i • x i ] + v) - i∈[1,t] κ ′ i • y i =⇒ Hπ[ i∈[1,t] (κ i -κ ′ i ) • x i ] = i∈[1,t] (κ i -κ ′ i ) • y i
This implies that π is a solution of the considered r-IPKP problem.

⊓ ⊔

We can now apply the result of Theorem 2.1 to Lemma 6.1, which concludes the proof.

⊓ ⊔ 6.1.2 Proof of Theorem 3.3 The following proof is inspired from the proof of [CDG + 20, Lemma 6.1] and [FJR22a, FJR22b, Theorem 3]. We now show that the protocol described in Figure 2, Section 3.1, satisfies the special honestverifier zero knowledge property. We assume that the commitment algorithm Com • outputs ℓ(λ)-bit strings as output for some polynomial ℓ. We restate the Theorem 3.3 below and follow it by its proof.

Theorem 3.3 (Special Honest-Verifier Zero Knowledge). Assume that there exists a (t, ϵ PRG )-secure PRG, and the commitment scheme Com is (t, ϵ Com )hiding. Then there exists an efficient simulator Sim which, outputs a transcript such that no distinguisher running in time at most t(λ) can distinguish between the transcript produced by Sim and a real transcript obtained by honest execution of the protocol in Figure 2 with probability better than (ϵ PRG (λ) + ϵ Com (λ)).

Proof (Proof of Theorem 3.3). We begin by describing an efficient simulator Sim which outputs a transcript which is indistinguishable from a real transcript obtained by honest execution of the protocol. Sim on input x = (H, (

x i ) i∈[1,t] , (y i ) i∈[1,t]
) works as follows:

1. Sample κ $ ←-F t q \ 0 and α * $ ←-[N ] 2. Sample θ $ ←-{0, 1} λ 3. For each i ∈ [1, N ] \ {α * } ⋄ θi $,θ ←-{0, 1} λ , ϕi $,θ i ←-{0, 1} λ , r1,i $,θ i ←-{0, 1} λ ⋄ if i ̸ = 1 ▷ πi $,ϕ i ←-Sn, vi $,ϕ i ←-F n q , cmt1,i = Com r1,i, ϕi ⋄ if i = 1 ▷ π1 $ ←-Sn, v1 $,ϕ 1 ←-F n q , cmt1,1 = Com r1,1, π1 || ϕ1 4. For i = α * ⋄ Sample πα * $ ←-Sn, vα * $ ←-F n q , cmt1,α * $ ←-{0, 1} ℓ(λ)
5. Compute r1, v, cmt1, h1 as in the real protocol using the values computed above.

6. Compute π = πN • • • • • π1 7. Compute x such that Hx = i∈[1,t] κi • yi 8. Compute s0 = i∈[1,t] κi • xi 9. For each i ∈ [1, α * -1] ⋄ Compute si = πi[si-1] + vi 10. Compute sα * = πα * [sα * -1] + vα * + π -1 α * +1 • • • • • π -1 N [x -π[ i∈[1,t] κi • xi]] 11. For each i ∈ [α * + 1, N ] ⋄ Compute si = πi[si-1] + vi
12. Compute h2, z1, z2, rsp as in the real protocol using the values computed above.

13. Output (x, h1, (κi) i∈[1,t] , h2, α * , rsp)

Note that the simulator Sim runs in polynomial-time and the challenges sampled in Step 1 are distributed identically to the real world execution since the verifier also samples the challenges uniformly at random. We now show that the transcript output by Sim and a real transcript obtained by honest execution of the protocol in Figure 2 with challenges (κ, α * ) cannot be distinguished with probability better than (ϵ PRG (λ) + ϵ Com (λ)) by any distinguisher running in time at most t(λ). We consider the following sequence of simulators:

Simulator 0 (real world). This simulator takes the statement x = (H, (x i ) i∈[1,t] , (y i ) i∈[1,t] ), witness π, and the challenges (κ, α * ) as input. It then runs the protocol in Figure 2 honestly and outputs the transcript. This transcript is identically distributed as a real-world transcript.

Simulator 1. Simulator 1 works exactly same as Simulator 0 except that instead of computing cmt 1,α * as in the real protocol, it samples a uniform string λ) . The probability of distinguishing Simulator 0 from Simulator 1 by any distinguisher running in time at most t(λ) is upper bounded by ϵ Com (λ).

as cmt 1,α * $ ←-{0, 1} ℓ(
Simulator 2. The only difference between Simulator 1 and Simulator 2 is that, Simulator 2 samples π α * $ ←-S n and v α * $ ←-F n q uniformly at random instead of using the seed-derived randomness from the seed θ. The probability of distinguishing Simulator 2 from Simulator 1 by any distinguisher running in time at most t(λ) is upper bounded by ϵ PRG (λ).

Simulator 3 (Sim). Simulator 3 takes the statement x = (H, (x i ) i∈[1,t] , (y i ) i∈ [1,t] ), and the challenges (κ, α * ) as input and proceeds from Step 2 of Sim defined above. Note that, this simulator does not depend on the witness π.

If α * = 1, then Simulator 2 and Sim work exactly same till Step 5 of Sim. Therefore, h 1 is distributed identically in both the transcripts. Also, s 0 is computed honestly by Sim and hence matches with that computed by Simulator 2. While computing s 1 , both Simulator 2 and Sim add v 1 to it. However, v 1 is sampled uniformly at random by both Simulator 2 and Sim. Hence, s 1 is also distributed identically in both the transcripts. Step 11 of Sim works exactly as Simulator 2 which means h 2 is also distributed identically in both the transcripts. The response rsp in this case is rsp = s 1 , (r

1 ||θ i ) i∈[2,N ] , cmt 1,1
) . As explained above s 1 is uniform random and distributed identically in both transcripts. The seeds (θ i ) i∈[2,N ] and randomness r 1 are computed identically by both the simulators since they work exactly the same way till Step 5 of Sim. Also, cmt 1,1 is sampled uniformly at random in both experiments (refer Simulator 1). Therefore, the transcript (x, h 1 , (κ i ) i∈[1,t] , h 2 , α * , rsp) is distributed identically in Simulator 2 and Sim when α * = 1.

If α * ̸ = 1, then Simulator 2 and Sim work exactly same till Step 5 of Sim, except for sampling of π 1 . Simulator 2 computes π 1 from witness π, whereas Sim samples π 1 uniformly at random. However, the values r 1 , v, cmt 1 , and h 1 are computed independently of π 1 and those are distributed identically in both the transcripts. Also note Simulator 2 computes π 1 by composing it with π -1 α * . Since π α * is sampled uniformly at random by Simulator 2, this implies that π 1 computed by Simulator 2 is also uniform random permutation and hence π 1 is also distributed identically. Also, for i ∈ [0, α * -1], the values s i are computed honestly by Sim and since π 1 is distributed identically the values s i for i ∈ [0, α * -1] are also distributed identically. As in the previous case, while computing s α * , both Simulator 2 and Sim add v α * to it. However, v α * is sampled uniformly at random by both Simulator 2 and Sim. Hence, s α * is also distributed identically in both the transcripts. Step 11 of Sim works exactly as Simulator 2 which means h 2 is also distributed identically in both the transcripts. The response rsp in this case is rsp = s α * , (π 1 ||r 1 ||θ i ) i∈[1,N ]\α * , cmt 1,α * ) . As explained above s α * is uniform random and distributed identically in both transcripts. The seeds (θ i ) i∈[1,N ]\α * and randomness r 1 are computed identically by both the simulators since they work exactly the same way till Step 5 of Sim. Also, cmt 1,α * is sampled uniformly at random in both experiments (refer Simulator 1). Therefore, the transcript (x, h 1 , (κ i ) i∈[1,t] , h 2 , α * , rsp) is distributed identically in Simulator 2 and Sim when α * ̸ = 1.

Therefore, any distinguisher running in time at most t(λ) cannot distinguish between the real-world transcript and the transcript produced by Sim with probability better than (ϵ PRG (λ) + ϵ Com (λ)).

⊓ ⊔ 6.2 Security Proof for the Signature Scheme 6.2.1 Proof of Theorem 3.4 We restate the Theorem 3.4 below and follow it by its proof.

Theorem 3.4. Suppose PRG is (t, ϵ PRG )-secure and any adversary running in time t(λ) can solve the the underlying r-IPKP instance with probability at most ϵ r-IPKP . Model H 0 , H 1 , and H 2 as random oracles where H 0 , H 1 , and H 2 have 2λbit output length. Then chosen-message attacker against the signature scheme (PERK) presented in Figure 4, running in time t(λ), making q s signing queries, and making q 0 , q 1 , q 2 queries, respectively, to the random oracles, succeeds in outputting a valid forgery with probability

Pr[Forge] ≤ (q 0 + τ • (N + 1) • q s ) 2 2 • 2 2λ + q s • (q 0 + q 1 + q 2 + q s ) 2 2λ + τ • q s • ϵ PRG (λ) + ϵ r-IPKP + q 2 • ε τ KS , (5)
where

ε KS = 1 N + N -1 N •(q t -1)
. The following proof is greatly inspired from the proof of the Picnic signature scheme [CDG + 20, Theorem 6.2] and [FJR22a, FJR22b, Theorem 5].

Proof (Proof of Theorem 3.4). Let A be a EUF-CMA attacker against the signature scheme, which makes q s queries to the signing oracle. Also, let q 0 , q 1 , and q 2 respectively denote the number of queries made by A to the random oracles H 0 , H 1 , and H 2 . To prove security we define a sequence of experiments involving A, starting with an experiment in which A interacts with the real signature scheme. We let Pr i [•] refer to the probability of an event in experiment i. We let t(λ) denote the running time of the entire experiment, i.e., including both A's running time and the time required to answer signing queries and to verify A's output.

Experiment 1. This corresponds to the interaction of A with the real signature scheme. In more detail: first KeyGen is run to obtain, the secret key sk = π along with the public key pk = (H, (x j , y j ) j∈[1,t] ), and A is given pk. In addition, we assume that the random oracles H 0 , H 1 , and H 2 are chosen uniformly from the appropriate spaces. A may make signing queries, which will be answered as in the signature algorithm; A may also query any of the random oracles. Finally, A outputs a message-signature pair; we let Forge denote the event that the message was not previously queried by A to its signing oracle, and the signature is valid. Our goal is to upper-bound Pr 1 [Forge].

Experiment 2. We abort the experiment if, during the course of the experiment, a collision occurs in H 0 . The number of queries to any oracle throughout the experiment (by either the adversary or the signing algorithm) is at most

(q 0 + τ • (N + 1) • q s ). Therefore, |Pr 1 [Forge] -Pr 2 [Forge]| ≤ (q 0 + τ • (N + 1) • q s ) 2 2 • 2 2λ .
Experiment 3. We abort the experiment if during the course of the experiment, while answering to a signature query, the sampled salt collides with the value salt in any previous query to H 0 , H 1 , or H 2 . For each single signature query, the probability to abort is upper bounded by (q 0 + q 1 + q 2 + q s ) /2 2λ . Thus,

|Pr 2 [Forge] -Pr 3 [Forge]| ≤ q s • (q 0 + q 1 + q 2 + q s ) 2 2λ .
Experiment 4. The difference with the previous experiment is that, when signing a message m we begin by choosing h 1 and h 2 uniformly at random and then we expand them as (κ

(e) j ) e∈[1,τ ],j∈[1,t] and (α (e) ) e∈[1,τ ] .
Steps 1, 3, and 5 are computed as before, but in Steps 2 and 4 we simply set the output of H 1 to h 1 and the output of H 2 to h 2 .

The outcome of this experiment compared to the previous one only changes if, in the course of answering a signing query, the query to H 1 or the query to H 2 was ever made before (by either the adversary or as a part of answering some other signing query). But this cannot happen since in such a case Experiment 3 would abort. Thus,

Pr 3 [Forge] = Pr 4 [Forge].
Experiment 5. The difference with the previous experiment is that, for each e ∈ [1, τ ], we sample cmt

(e)
1,α (e) uniformly at random instead of making a query to H 0 .

The only difference between this experiment and the previous experiment occurs if, during the course of answering a signing query, the seed θ (e) α (e) (for some e ∈ [1, τ ]) was previously queried to H 0 . However, such collisions cannot occur within the same signing query (since indices e and i are part of the input of H 0 ) and if it occurs from a previous query (signing query or query to H 0 ) then the experiment aborts (according to the difference introduced in Experiment 3). Thus,

Pr 4 [Forge] = Pr 5 [Forge].
Experiment 6. We again modify the experiment. Now, for e ∈ [1, τ ] the signer uses the SHVZK simulator Sim (see proof of Theorem 3.3) to generate the views of the parties during the execution of Step 1 and Step 3. We denote by Sim salt (•) a call to this simulator which appends salt to the sampled seed θ as input to PRG. This simulation results in θ

(e) i , π (e) i
i̸ =α (e) and (s

(e) j ) j∈[1,N ] .
Thus the signing queries are now answered as shown in 6.

Step 0

1. Sample h1 $ ←-{0, 1} 2λ uniformly at random. 2. Sample (κ (e) j ) e∈[1,τ ],j∈[1,t] ←-PRG(h1). 3. Sample h2 $ ←-{0, 1} 2λ uniformly at random. 4. Sample (α (e) ) e∈[1,τ ] ←-PRG(h2).

Sample a uniform random salt salt

$ ←-{0, 1} 2λ .
Steps 1 and 3 For each iteration e ∈ [1, τ ]

1. θ (e) i , π (e) i
i̸ =α (e) , (s

(e) j ) j∈[1,N ] ← Sim salt ((κ (e) j ) e∈[1,τ ],j∈[1,t] , (α (e) ) e∈[1,τ ] ) 2. Choose commitment cmt (e) 1,α (e)
$ ←-{0, 1} 2λ uniform randomly.

3. For i ̸ = α (e) :

⋄ If i ̸ = 1, set cmt (e) 1,i = H0(salt, e, i, θ (e) i )
.

⋄ If i = 1, set cmt (e)
1,1 = H0(salt, e,

. (e) as Hv (e) = (H(s

Compute Hv

(e) N ) -i∈[1,t] κ (e) i
• yi).

Set cmt (e) 1

= H0(salt, e, Hv (e) ).

Steps 2 and 4

1. Set H1(salt, m, pk, (cmt

(e) 1 , cmt (e) 1,i ) e∈[1,τ ],i∈[1,N ]
) equal to h1.

2. Set H2(salt, m, pk, h1, (s

(e) i ) e∈[1,τ ],i∈[1,N ]
) equal to h2.

Step 5 Output signature σ built as 1. For each iteration e ∈ [1, τ ]:

⋄ Compute z (e) 1 = s (e) α ⋄ If α (e) ̸ = 1, z (e) 2 = π (e) 1 || (θ (e)
i ) i∈[1,N ]\α (e) ⋄ If α (e) = 1, z (e) 2 = (θ (e)
i ) i∈[1,N ]\α (e) ⋄ Compute rsp (e) = (z (e) 1 , z (e) 2 , cmt (e)
1,α (e) ) 2. Compute σ = (salt, h1, h2, (rsp (e) ) e∈[1,τ ] ) Fig. 6: Experiment 6: Answer to a signature query for a message m.

Note that the secret π is no longer used for generating signatures. Recall that an adversary against Sim has distinguishing advantage ϵ PRG (λ) (corresponding to execution time t(λ)), since the commitments are built outside of the simulator. Therefore,

|Pr 5 [Forge] -Pr 6 [Forge]| ≤ τ • q s • ϵ PRG (λ).
Experiment 7. At any point during the experiment, we say that the execution e * of a query

h 2 = H 2 (salt, m, pk, h 1 , (s (e) i ) e∈[1,τ ],i∈[1,N ]
) defines a correct witness if the following four conditions are fulfilled:

1. h 1 was output by a previous query

h 1 = H 1 (salt, m, pk, (cmt (e) 1 , cmt (e) 1,i ) e∈[1,τ ],i∈[1,N ] ), 2. each cmt (e * )
1,i in this H 1 -query was output by a previous query cmt

(e * ) 1,i = H 0 (salt, e * , i, θ (e * ) i ) for i ∈ [2, N ], and cmt (e * ) 1,1 = H 0 (salt, e * , 1, π (e * ) 1 , θ (e * ) 1
)

for i = 1. 3. each cmt (e * ) 1
in the above H 1 -query was output by a previous query cmt

(e * ) 1 = H 0   salt, e * ,   Hs (e * ) N - i∈[1,t] κ (e * ) i • y i     4. the permutation π derived from π (e * ) i i∈[1,N ] i.e. π = π (e * ) N •π (e * ) N -1 •• • • π (e * ) 1 satisfies H   π   i∈[1,t] κ i • x i     = i∈[1,t] κ i • y i
for some κ ∈ F q t \ 0, where κ := {κ 1 , . . . , κ t } and 0 ∈ F q t is the all zero vector.

(Note that in all cases the commitments in the relevant prior H 1 -query, if it exists, must be unique since the experiment is aborted if there is ever a collision in H 0 .) In Experiment 7, for each query of the above form made by the adversary to H 2 (where m was not previously queried to the signing oracle), check if there exists an execution e * which defines a correct witness. We let Solve be the event that this occurs for some query to H 2 . Note that, if that event occurs, the

π (e * ) i i∈[1,N ]
(which can be determined from the oracle queries of A) allow the computation of solution to r-IPKP. Therefore,

Pr 7 [Solve] ≤ ϵ r-IPKP . We claim that Pr 7 Forge Solve ≤ q 2 • ε τ KS , where ε KS = 1 N + N -1 N •(q t -1)
is the knowledge soundness error of one execution. To see this, assume Solve does not occur. Then there is no execution of any H 2query which defines a correct witness. When considering an arbitrary execution e ∈ [1, τ ], the attacker can only possibly generate a forgery (using this H 2 -query) if 1. A guesses the first challenge κ (e * ) ∈ F q t \0, where κ (e * ) := κ (e * ) 1

, . . . , κ (e * ) t and 0 ∈ F q t is the all zero vector.

2. or even if cmt

(e * ) 1
̸ = H 0 (salt, e * , (Hs

(e * ) N -i∈[1,t] κ (e * ) i
• y i )) the attacker guesses the second challenge α * such that the views of all remaining N -1 parties are consistent.

Thus, the overall probability with which the attacker can generate a forgery using this H 2 -query is

ε τ KS = 1 q t -1 + 1 - 1 q t -1 • 1 N τ .
The final bound is obtained by taking a union bound over all queries to H 2 . This concludes the proof of Theorem 3.4. ⊓ ⊔

7 Known Attacks

Generic Attacks against Fiat-Shamir Signatures

Kales and Zaverucha in [KZ20], showed a generic attack on the non-interactive version of 5-round PoK schemes. The attack strategy is to guess either one of the challenges (ch 1 or ch 2 ) correctly which permits the prover to cheat. The attacker then aims to split the work by attempting to guess the first challenge for η * instances out of τ parallel repetitions, and tries to guess ch 2 for the remaining (τ -η * ) instances.

If the attacker can guess η * challenges for the first phase correctly, then he can answer all the N possible challenges for the α (e) for those instances. Subsequently, to successfully cheat he has to guess the remaining (τ -η * ) values of α (e) correctly.

The parameter η * allows the attacker to balance the cost for both guessing phases. The overall cost is minimized for a choice of

η * = arg min 0≤η≤τ 1 P 1 (η, τ, q, t) + N (τ -η) (6)
where,

P 1 (η, τ, q, t) := τ j=η 1 q t -1 j q t -2 q t -1 τ -j τ j .
Finally, the total cost for the attacker is thus

W KZ = 1 P 1 (η * , τ, q, t) + N (τ -η * ) . (7)
In [KZ20] the authors classify the 5-round protocols based on whether it is possible for the verifier to detect if the tuple (cmt, ch 1 , rsp 1 ) is valid or not.

If the verifier can detect the validity of this tuple then the scheme is said to possess early abort property. The cost of the attack varies for different schemes based on whether they satisfy the early abort property or not. Our protocol and signature scheme do not possess the early abort property and hence the expected cost of attacking the PERK signature scheme proposed in this work, is given by Equation ( 7)

Attacks on the Permuted Kernel Problem

Despite its long standing history in cryptographic applications [Sha90,BFK + 19, Beu20, BG23] and consequently many cryptanalytic efforts [Geo92, BCCG93, PC94, JJ01, LP11, KMP19, SBC22], algorithms to solve the Permuted Kernel Problem are still rather simple adaptations of combinatorial enumeration and meet-in-the-middle techniques. Even though there has been recent progress on attacks [SBC22], for the mono-dimensional case of IPKP, i.e., Definition 2.19 with t = 1, those attacks do not have a serious effect. For parameters matching NIST's security definition I, III and V they yield a reduced security level of roughly 2,1 and 0 bits. The authors of [SBC22] also study the more general multi-dimensional case of IPKP where t > 1 pairs (x i , y i ) are provided and a permutation π is searched that simultaneously satisfies Hπ(x i ) = y i ∀i ∈ [t].

The difference between IPKP and the r-IPKP (on which our scheme is based) is that the solution in the case of r-IPKP does not necessarily have to be the permutation that works for all the given pairs, but it has to satisfy the PKP identity only for an arbitrary (non-zero) linear combination of those pairs, i.e. any permutation π such that

Hπ i κ i x i = i κ i y i ,
for a choice of the κ i ∈ F q , is a solution. Clearly any algorithm applicable to IPKP can also be applied to find a solution to the r-IPKP problem. However, a solution to r-IPKP does not necessarily have to be a solution to IPKP. Therefore algorithms to solve r-IPKP split into those initially proposed for IPKP and those specifically designed to solve r-IPKP.

Attacks on IPKP

The IPKP problem was introduced by Shamir in 1990 [Sha90]. Still, the best attack on mono-dimensional IPKP is a meet-in-themiddle adaptation known as the KMP algorithm by Koussa, Macario-Rat and Patarin [KMP19]. This algorithm extends easily to t > 1, which was recently formalized in [SBC22]. The multi-dimensional IPKP first appeared in the literature in 2011 [LP11]. However, until recently cryptanalysis only resulted in better algorithms for the particular case of binary fields [PT21]. Recently, Santini, Baldi and Chiraluce [SBC22] proposed the SBC algorithm which extends the KMP algorithm by a pre-processing step. For t > 1, i.e., for the multidimensional case, this results in improvements over the KMP approach. For the concrete complexity estimation of those attacks we rely on the CryptographicEstimators library2 [EVZB23], which incorporates (more efficient) versions of the scripts from the original publications. We give a brief overview of those attacks in Appendix A.1.

Relation between IPKP and the Code Equivalence Problem. In their recent work Santini et al. [SBC22] observed a link between the homogeneous variant of IPKP, i.e, when it holds y i = 0 for all i, and the (sub-)code equivalence problem. For the homogeneous variant, this leads to further restrictions on the parameters to guarantee the hardness of the problem. However, for the inhomogeneous variant, which we consider, this does not apply. We give details on this relation and why it does not translate to IPKP in Appendix A.3.

Attacks on r-IPKP

We introduce the r-IPKP problem together with our scheme. However, it is still very related to the multi-dimensional and monodimensional versions of IPKP and their corresponding hardness. We already discussed the relation to the multi-dimensional case of IPKP.

Let us now focus on the relation between r-IPKP and the mono-dimensional version of IPKP. In this context r-IPKP can be seen as a multi-instance version of IPKP.

Therefore disregard the (most likely) unique solution to r-IPKP which simultaneously solves IPKP for the same t, i.e. the permutation that works for all pairs (x i , y i ). Further, assume that for any of the given pairs (x i , y i ) there exist a permutation π i solving the corresponding mono-dimensional IPKP instance, that is a π i that satisfies Hπ i (x i ) = y i . If we would be forced to recover one of the π i , this would exactly be a multi-instance version of IPKP. However, the r-IPKP allows to recover any permutation that works for an arbitrary linear combination of the given pairs. Clearly, this gives a total of q t different pairs, but unlike the multi-instance case those pairs are related.

In fact, from a coding theory perspective the r-IPKP asks to recover a permutation that works for any codeword and the corresponding syndrome where the code is defined by the generator matrix containing the x i s as rows. We give a new algorithm that exploits this view on the r-IPKP in Appendix A.2. The core idea is to search for a low-weight codeword first and focus on solving the corresponding mono-dimensional IPKP instance specified by this codeword. The lower weight of the codeword leads to a reduced enumeration effort.

As one would expect, the complexity of this algorithm decreases with increasing t. However, for small choices of t, attacks that exploit the link to the multi-dimensional IPKP from the previous section have a lower complexity. Intuitively, in those cases r-IPKP is too close to a multi-instance IPKP as that the extra freedom could outweigh the gain from the extra restrictions on the solution given by the multi-dimensional case of IPKP.

Concrete Complexity of solving r-IPKP

In this section we give details on how the variation of different parameters affects the hardness of r-IPKP. A solid understanding of those effects is crucial for secure parameter selection. As outlined previously, for solving the r-IPKP one can either directly apply an IPKP algorithm or solve one of the single IPKP instances defined by any linear combination of input pairs. Which of the two attack strategies is better depends on the particular choice of parameters.

Effect of the number of solutions. Multiple existing solutions can lead to a maximum speedup that is linear in this amount of solutions. Whether this maximum speedup can be realized depends on the particular algorithm. However, for our parameter selection we conservatively assume that any algorithm can leverage this maximum speedup.

Note that the expected number of solutions differs for the considered subproblems. The expected number of solutions for any random IPKP instance is about Sol IPKP = n! q m•t . Note that the mono-dimensional IPKP instance solved in the context of our new Algorithm 1 is not random but contains z zeros. In this case the amount of expected solutions is only Sol mono IPKP,z = n! q m z! .

Effect of t on the running time. Santini et al. [SBC22] observed that the running time of the KMP algorithm as well as the running time of their SBC algorithm for IPKP is asymptotically independent of t. For concrete parameters, these algorithms still yield speedups for increasing t but the running time quickly converges to a stable minimum. Therefore, based on known algorithms the hardness of IPKP does not seem to deteriorate for high values of t. Contrary, the complexity of our new Algorithm 1 is monotonically decreasing for increasing t. This shows that high choices of t in the r-IPKP context are vulnerable.

To visualize this we consider in Table 5 a fixed instance for increasing t. The SBC algorithm reaches its minimum running time already for t = 10, while Algorithm 1 constantly improves. However, the SBC algorithm has a lower complexity for small choices of t and obtains a larger gain for early increases. Note that for the chosen parameters in Table 5 already a random mono-dimensional IPKP instance has at most one solution in expectation, i.e. Sol mono IPKP ≤ 1.

Effect of m on the running time. Generally the hardness of IPKP is increasing with decreasing m. This holds up to the point where there exist multiple solutions. Previous parameter selection for PKP-based schemes therefore chooses m minimal such that there exists no more than one random solution in expectation. However, for the specific case of the r-IPKP problem, the two sub-problems, i.e., the multi-and mono-dimensional IPKP instances, have a different amount of expected solutions. Here, decreasing m leads, generally, only to an increase of the problem complexity as long as the solution to both sub-problems is still unique. Table 5: Bit complexity of SBC algorithm (T SBC ) and Algorithm 1 (T new ) for increasing t on r-IPKP(n, m, q, t) instance with (n, m, q) = (66, 31, 1021).

Parameter selection. For parameter selection we ensure that the complexity of the SBC algorithm as well as the complexity of our new Algorithm 1 are above the security threshold, when assuming a linear speedup from the existing amount of solutions. Note that it is important to consider both strategies as the IPKP suggests to decrease m to increase the difficulty of the problem. This is related to the low amount of expected solutions Sol IPKP , which allows to decrease m significantly without introducing multiple solutions. Contrary, for any mono-dimensional instance given by the possible linear combinations, there exist several solutions Sol mono IPKP for such small choices of m, which decrease the complexity of Algorithm 1.

Note that we, conservatively, restrict in our parameter selection to small choices of t ∈ {3, 5} to guard against attacks that exploit the specifics of r-IPKP over IPKP. For such small values of t, the SBC algorithm has generally a lower complexity than Algorithm 1 (compare to Table 5). In those cases, the parameter selection process leads to a choice of m which implies a unique solution to the multi-dimensional IPKP instance, while there exist multiple solutions to the mono-dimensional instance solved in the context of Algorithm 1. This leads to a balancing of both complexities via the amount of solutions.

Our complexity estimations ignore polynomial factors and ensure that already the exponential factors of the complexity formulas reach the NIST security levels of 143, 207 and 272 bits of category I, III and V respectively. For the complexity estimation of the SBC algorithm we rely on the CryptographicEstimators library3 incorporating a more efficient version of the script from [SBC22].

For our algorithm we rely on a separate script. Overall this leads to the choices of parameters given in Section 4. We restate those parameter sets in Table 6 together with the complexity estimation following the mentioned methodology.

Note that even though we are quite conservative in parameter selection by restricting to small choices of t, disregarding polynomial factors and assuming

Limitations

In the following, we point out the limitations of PERK.

-While PERK's performance profile is comparable to other MPCitH-based constructions, those can not compete with the fastest post-quantum secure schemes, usually based on structured lattices.

-The security of PERK is based on a new variant of the PKP (r-IPKP) introduced together with the scheme. However, we note that the r-IPKP only slightly deviates from the case of PKP especially in the case of smaller values of t, such as t = 3.

-Since PERK follows the MPC-in-the-head paradigm to construct the zeroknowledge proof of knowledge system, it inherits the generic limitations of such designs. Namely, even if the objects related to the computationally hard problem could be compressed arbitrarily, it would not lead to arbitrarily short signatures, since the amount of auxiliary information is already a significant fraction of the total signature size.

A.1 Attacks on IPKP

In this section we briefly sketch the different approaches to solve the IPKP.

) QH = I m-u H 1 0 H 2 ,
where

H 1 ∈ F (m-u)×(n-m+u) q ,H 2 ∈ F u×(n-m+u) q
and u is an optimization parameter of the algorithm. By multiplying the syndrome y by the same matrix Q one maintains the validity of the PKP identity

QHπ(x) = I m-u H 1 0 H 2 π(x) = I m-u H 1 0 H 2 x 1 x 2 = (x 1 + H 1 x 2 , H 2 x 2 ) ⊤ = (y 1 , y 2 ) ⊤ = Qy, where Qy = (y 1 , y 2 ) ∈ F m-u q × F u q and π(x) = (x 1 , x 2 ) ∈ F m-u q × F u q .
The algorithm now focuses on solving the identity H 2 x 2 = y 2 . For any found x 2 satisfying the identity it is than checked if x 1 = y 1 -H 1 x 2 and x 2 together form a permutation of x.

Candidates for x 2 are obtained by a meet-in-the-middle enumeration strategy. Therefore x 2 is further split as x 2 = (x 21 , x 22 ), with x 21 , x 22 ∈ F u×((n-m+u)/2) q to obtain the meet-in-the-middle identity

H 2 (x 21 , 0) = y 2 -(0, x 22 ). (8)
Then the algorithm enumerates all candidates for x 21 and x 22 , that is all permutations of any selection of (n -m + u)/2 entries of x. For each such vector the left (resp. right) side of Equation ( 8) is stored in a list L 1 (resp. L 2 ). In a final step the algorithm searches for matches between the lists L 1 and L 2 yielding the candidates for x 2 . From there x 1 can be computed as x 1 = y 1 -H 1 x 2 . If (x 1 , x 2 ) forms a permutation of x this yields the solution π.

The complexity of the algorithm is (up to polynomial factors) linear in the sizes of the lists L 1 , L 2 and L, where L is the list of matches. The expected sizes are

|L 1 | = |L 2 | = n (n -m + u)/2 (n -m + u)/2 ! and |L| = |L 1 × L 2 | q u
Extension to multi-dimensional IPKP. The algorithm can easily be extended to solve IPKP for arbitrary t, as it was recently made explicit in [SBC22]. Therefore let X be the matrix containing the x i as rows and Y containing the y i as columns. Substituting the occurrences of x and y by X and Y resp., where the permutation now operates as a column permutation on matrices, one obtains this generalization. Then of course the definition of (x 1 , x 2 ) and (y 1 , y 2 ) analogously extends to matrices. In terms of complexity, the enumeration effort stays (up to polynomial factors) exactly the same, as the possible number of permutations remains unchanged. The only difference is that the expected size of the list L of matches reduces to |L1×L2| q u•t .

The SBC algorithm. The algorithmic improvement by Santini-Baldi-Chiraluce (SBC) extends the KMP algorithm by a preprocessing step. Assume that the matrix H 2 constructed in the KMP algorithm would contain zero columns. Clearly, those columns could be removed without affecting the validity of the identity H 2 x 2 = y 2 . But in turn this would reduce the enumeration effort to find candidates for x 2 .

The preprocessing step of the SBC algorithm now consists in finding a udimensional subcode of H that has small support w < n -m + u, i.e., an H 2 that contains some zero columns. This can be accomplished by adaptations of Information Set Decoding (ISD) algorithms. Subsequently, the SBC algorithm continues as the KMP algorithm by finding candidates for x 2 in H 2 x 2 = y 2 , now with reduced enumeration complexity. This resulting list of candidates is now treated as the first list, L 1 , in the KMP algorithm.

Note that the KMP algorithm creates two lists each giving candidates for (n -m + u)/2 entries of the permutation. Now, as there are already candidates for w entries in L 1 , the second list enumerates the permutation for further nm + u -w positions. Eventually both lists are matched on u • t coordinates as in the KMP algorithm to obtain a list of final candidates. Note that as in the KMP algorithm now each candidate of the final list reveals n-m+u potential positions of the permutation which can be checked in polynomial time for extending to a full solution.

A.2 A new Algorithm solving r-IPKP

In the following we give a new algorithm for solving r-IPKP. This algorithm focuses on finding a permutation that solves the IPKP defined by any one linear combination of the input pairs, rather than finding the solution to the multidimensional IPKP instance. The algorithm is based on a preprocessing of the given pairs (x i , y i ), a subsequent instance permutation and an adapted KMPstyle enumeration technique. Moreover, our algorithm contains the KMP algorithm as a special case.

The algorithm starts by finding a low Hamming-weight codeword in the code whose generator matrix contains the x i as rows. This task is accomplished by application of an ISD algorithm. Let x ′ = κ i x i be this codeword of weight w and y ′ = κ i y i the corresponding syndrome. We now focus on finding a permutation π that satisfies Hπ(x ′ ) = y ′ . Therefore, we apply a KMP-style enumeration with some modifications. Again we derive the identity H 2 x 2 = y 2 ∈ F u q , with x 2 = (x 21 , x 22 ) as in the usual KMP algorithm. Now, recall that π(x ′ ) = (x 1 , x 2 ) contains n -w zeros. For the enumeration of x 21 and x 22 we now assume that z of those zeros are mapped into x 2 by the permutation. Moreover, we assume that z/2 of those zeros are mapped to x 21 and z/2 to x 22 . This leads to a reduced amount of candidates for x 21 , x 22 that has to be enumerated.

Of course we do not know a priori if the permutation indeed distributes z/2 zeros onto x 21 and z/2 zeros onto x 22 . Therefore prior to the enumeration we apply a random permutation to the columns of H to redistribute the weight (and zeros) of π(x ′ ). If the enumeration does not lead to a solution we repeat with a different column permutation of H.

A pseudocode description is given in Algorithm 1. Note that for w = n, i.e., a maximum-weight codeword, we resemble the standard KMP algorithm for solving mono-dimensional IPKP.

Analysis of Algorithm 1. Let us start with the correctness of the algorithm. Correctness. Note that the permuted instance (H * , x ′ , y ′ ) with H * = π ′ (H) has solution π ′ • π if π solves the original instance (H, x ′ , y ′ ). Therefore the algorithm correctly returns (π ′ ) -1 • π as the solution to the original instance, where π solves the permuted instance.

Accordingly the solution to the permuted instance is (x 1 , x 2 ) = π ′ (π(x ′ )). Line 9 to 11 enumerate all candidates for x 2 satisfying H 2 x 2 = y 2 , where x 2 = (z 1 , z 2 ) with each of the z i containing z/2 zeros. Note that by construction (x 1 , x 2 ) contains n -w zeros. As the permutation π ′ redistributes the zeros the algorithm can recover the permutation. Complexity. The complexity of the algorithm splits into the cost of finding the short codeword x ′ and the cost of the repeat loop. The codeword is found by application of an ISD algorithm. Let us denote this cost by T ISD .

The cost of the loop is equal to the amount of repetitions times the cost of one iteration. The amount of different permutations until the zeros are distributed as desired is

P = n n-w n-2k n-w-z k z/2 2 ,
where k = (n -m + u)/2. The cost for one iteration is (up to polynomial factors) linear in the involved lists' sizes. Note that we have Precisely, one is asked to find a subcode G of G, an invertible matrix S ∈ F k ′ ×k ′ q , corresponding to a change of basis, and a permutation π such that G ′ = Sπ( G). For k ′ = k the problem is known as the code equivalence problem.

|L i | = k z/2 n -z k -z/2 (k -z/2)! and |L| = |L 1 × L 2 | q u .
The homogeneous version of the IPKP is the dual formulation of the subcode equivalence problem that asks to first recover the permutation π. Therefore one might see the given matrix H as the parity check matrix of G and the matrix with the x i as rows as the generator matrix G ′ . The permuted kernel problem now asks to find a permutation of G ′ , such that H π(G ′ ) ⊤ = 0, or in other words a permutation such that π(G ′ ) is contained in the code with parity-check matrix H as a subcode.

While the subcode equivalence problem, analogously to PKP is known to be NP-complete [BGK17], the special case of code-equivalence, i.e., k = k ′ or in PKP notation n -m = t, is likely to be not [PR97]. In particular, there is a polynomial time algorithm known to solve random instances of the code equivalence problem [Sen00], that is instances where G and G ′ are chosen at random. Therefore, if one wants to ensure difficult instances, one needs to ensure n -m ̸ = t. More specifically, one also needs to make sure that the difference (n -m) -t is large enough, as there is a reduction from subcode equivalence to code equivalence with an overhead of q t(n-m-t) [SBC22].

Note that this whole equivalence relation only holds for the homogeneous variant of IPKP and not for the inhomogeneous variant. Therefore to make use of the mentioned equivalence in our case of IPKP one has to first apply a reduction from the IPKP to its homogeneous variant. This reduction exists, but decreases m by t. Essentially, one has to add those codewords c i that yield the corresponding syndromes, i.e., those with Hc i = y i , to the code with parity-check matrix H. The parity-check matrix H ′ of this enlarged code together with the pairs (x i , y i then define a homogeneous IPKP instance. Note that H ′ now has m ′ = m -t rows. In turn the relation n -m ̸ = t from the homogeneous setting becomes trivial in the inhomogeneous setting, namely n -m ′ ̸ = t ⇔ n -m ̸ = 0. This implies that the inhomogeneous case is inherently harder than the homogeneous case.

  Definition 2.11)). An interactive proof Π = (P, V) is public-coin if all of V's random choices are made public, i.e. are part of the transcript. The message ch i $ ←-CH i of V in the 2i-th round is called the i-th challenge, and CH i is the challenge set.

Fig. 2 :

 2 Fig. 2: PoK leveraging structure for the r-IPKP problem

  Fig. 4: PERK -Sign algorithm

  Let A = 2 b , where b = 6.5 for λ = 128 (b = 7 for λ = 192 and b = 7.5 for λ = 256). Let π ∈ S n , then for any two consecutive coefficients c a and c b of π, we set cp = (A * c a ) + c b . Then, the compact cp representations (2 • b bits) are concatenated and stored into a byte string. The coefficient are then unpacked as follows. We compute c a = cp A and c b = cp mod A. Its worth mentioning that for λ = 192 (i.e, b = 7), the packed coefficients are simply the concatenation c a ||c b . During the parsing the all the cp of all permutations are packed together ensuring that no space is lost between them.Objects are always stored in little endian representation.5.1.4 PRG, Hash functions and TreePRGPRG. The randombytes function provided by the NIST is used to sample uniformly at random the salt and various seeds (sk_seed, pk_seed, mseed). The PRG function is instantiated using SHAKE-128 for λ = 128 and SHAKE-256 otherwise, along with domain separators.Hash functions. The hash functions are instantiated using SHA3-256 for λ = 128, SHA3-384 for λ = 192 and SHA3-512 for λ = 256 along with domain separators.

  The constants H 1 = 0x01 and H 2 = 0x02 are domain separators and encoded over one byte ; -(rsp (e) ) e∈[1,τ ] is a set of τ responses rsp (e) (e) is 2 • λ bits commitment generated using the hash function H(•∥H 0 ).

  The total time complexity therefore amounts toT = Õ (T ISD + (|L 1 | + |L|) • P ) ,the (sub-)code equivalence problem. For the (sub-) code equivalence problem one is given two generator matrices -one generator matrix G of an [n, k] linear code and another G ′ of an [n, k ′ ] code with k ′ ≤ k. The problem now asks to find a subcode G of G of dimension k ′ that maps into G ′ via a permutation.

  Table 1 presents our suggested parameter sets.

				PKP param.		MPC param.
	Parameter Set	λ	q	n	m	t	N	τ	pk size	sk size	σ size
	PERK-I-fast3	128 1021 79 35 3	32	30	0.15 kB	16 B	8.35 kB
	PERK-I-fast5	128 1021 83 36 5	32	28	0.24 kB	16 B	8.03 kB
	PERK-I-short3 128 1021 79 35 3 256	20	0.15 kB	16 B	6.56 kB
	PERK-I-short5 128 1021 83 36 5 256	18	0.24 kB	16 B	6.06 kB
	PERK-III-fast3 192 1021 112 54 3	32	46	0.23 kB	24 B	18.8 kB
	PERK-III-fast5 192 1021 116 55 5	32	43	0.37 kB	24 B	18.0 kB
	PERK-III-short3 192 1021 112 54 3 256	31	0.23 kB	24 B	15.0 kB
	PERK-III-short5 192 1021 116 55 5 256	28	0.37 kB	24 B	13.8 kB
	PERK-V-fast3	256 1021 146 75 3	32	61	0.31 kB	32 B	33.3 kB
	PERK-V-fast5	256 1021 150 76 5	32	57	0.51 kB	32 B	31.7 kB
	PERK-V-short3 256 1021 146 75 3 256	41	0.31 kB	32 B	26.4 kB
	PERK-V-short5 256 1021 150 76 5 256	37	0.51 kB	32 B	24.2 kB
	Table

Table 2 :

 2

Public key and signature sizes in bits Signature compression. Our implementation features an optimization that further reduce the aforementioned signature theoretical size. The idea is to pack the permutation elements two by two. Instead of representing a permutation π ∈ S n as a sequence of n elements in [0, n -1] it is represented as a sequence of ⌈n/2⌉ elements in [0, n 2 -1]. When the following inequality holds

Table 4 :

 4 Performances of the optimized implementation for different instances of PERK. The key generation numbers are in kilo CPU cycles, while the signing and verification numbers are in million CPU cycles.

	Parameter Set	Keygen	Sign	Verify
	PERK-I-fast3	77	7.6	5.3
	PERK-I-fast5	90	7.2	5.1
	PERK-I-short3	80	39	27
	PERK-I-short5	91	36	25
	PERK-III-fast3	167	16	13
	PERK-III-fast5	185	15	12
	PERK-III-short3	175	82	65
	PERK-III-short5	194	77	60
	PERK-V-fast3	304	36	28
	PERK-V-fast5	324	34	26
	PERK-V-short3	300	185	143
	PERK-V-short5	328	171	131

  The algorithm was first proposed for the mono-dimensional IPKP [KMP19] and recently extended to the multi-dimensional case [SBC22]. We outline here the variant for mono-dimensional IPKP first.Initially, the matrix H is transformed into semi-systematic form by applying a change of basis (modelled by the invertible matrix Q

	Fully fledged descriptions, analysis and estimation scripts are given for example
	in [KMP19, SBC22, EVZB23].
	The KMP Algorithm. The algorithm by Koussa, Macario-Rat and Patarin [KMP19]
	is a slight variant of previously known combinatorial techniques [Geo92,BCCG93,
	PC94, JJ01].

Since the protocol presented in this work only achieves computational soundness, and is secure when the prover runs in polynomial time, technically our protocol is an argument of knowledge. However, we avoid this distinction for simplicity.

https://github.com/Crypto-TII/cryptographic_estimators

https://github.com/Crypto-TII/cryptographic_estimators

Table 6: Bit complexity estimation for different PERK parameter sets.

a maximum speedup from multiple solutions, we obtain competitive signature sizes. Also all considered algorithms use as much memory as they consume time, which in a more realistic estimate that accounts for memory access leads to an even higher security margin.

Advantages and Limitations

We now discuss some advantages and limitations of PERK.

Advantages

Some advantages of our design are:

+ PERK features very small public key and secret key sizes along with moderate signature sizes. Therefore, on the combined metric of pk + signature size, PERK produces sizes of approximately 6kB for NIST Security Level I which compares well with other signature schemes.

+ PERK performances are constrained by numerous calls to symmetric cryptographic primitives. Any speedup to the implementation of these primitives directly benefit PERK. In particular, hardware acceleration support for such primitives improves the performance of the scheme.

+ Many efficient post-quantum schemes rely on difficult problems featuring additional structure, such as a (quasi-)cyclic or ring structure. This comes at the cost of less-tight security reductions and potential new attack vectors. In contrast PERK does not introduce objects with such special structure.

+ Resilience against PKP and r-IPKP attacks: A large part of the signature size scales with the security parameter λ (due to the seed trees and commitments) and not directly with the r-IPKP parameters. As a consequence, increasing the r-IPKP parameters has a limited impact on the total size of the signature.

A Details on Security

In this section we provide more details on the considered algorithms for parameter selection. We give a brief sketch of known algorithms to solve IPKP. After that we show how to adapt some of those techniques to the specific case of r-IPKP exploiting the extra degree of freedom. This results in improvements for certain regimes of parameters, where either many pairs are given or many solutions for single linear combinations exist. Afterwards we give details on the link between IPKP and the code equivalence problem.

Algorithm 1: Algorithm Solving r-IPKP

1 For a vector x and an integer k let P x,k be the set of vectors of length k with entries from x (with their maximum occurence as in x).

2 Choose optimal positive u ≤ n -m, w ≤ n, and z ≤ n -w, let k := (n -m + u)/2

3 Find weight-w codeword x ′ = i κixi in the code defined by the xi

while the memory complexity is equal to M = Õ (|L 1 | + |L|) .

In our numerical optimization we use for T ISD the basic ISD procedure by Prange [Pra62] which gives

There are more sophisticated ISD procedures with lower cost, but as T ISD does not dominate the running time, we refrain from further optimizations.

Note that this running time assumes a single existing solution for the considered mono-dimensional instance solved. In case of multiple solutions the running time can be lower, which we discuss in Section 7.3.

A.3 Relation between IPKP and the Code Equivalence Problem

In their recent work Santini et al. [SBC22] also observed the relation between the the homogeneous variant of IPKP, i.e, when it holds y i = 0 for all i, and