# A Commitment Scheme with Output Locality-3 Fit for the IoT Device

Authors: Hideaki Miyaji; Yuntao Wang; Akinori Kawachi; Atsuko Miyaji
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Low output locality is a property of functions, in which every output bit depends on a small number of input bits. In IoT devices with only a fragile CPU, it is important for many IoT devices to cooperate to execute a single function. In such IoT’s collaborative work, a feature of low output locality is very useful. This is why it is desirable to reconstruct cryptographic primitives with low output locality. However, until now, commitment with a constant low output locality has been constructed by using strong randomness extractors from a nonconstant-output-locality collision-resistant hash function. In this paper, we construct a commitment scheme with output locality-3 from a constant-output-locality collision-resistant hash function for the first time. We prove the computational hiding property of our commitment by the decisionalM,δ-bSVP assumption and prove the computational binding property by the M,δ-bSVP assumption, respectively. Furthermore, we prove that the M,δ-bSVP assumption can be reduced to the decisional M,δ-bSVP assumption. We also give a parameter suggestion for our commitment scheme with the 128 bit security.


---

## Body

## 1. Introduction

The computational complexity of cryptographic primitives is a fundamental problem in the construction of highly efficient and secure protocols [1, 2]. In ITCS 2017, Applebaum et al. achieved pioneering results for low-complexity cryptographic constructions of fundamental primitives [3]. Their technique provides a general framework for converting relatively high-complexity cryptographic functions to low-complexity ones, including one-way and pseudorandom functions of low output localities. Furthermore, Applebaum et al. proposed constructions for collision-resistant hash functions of a constant output locality from computationally hard problems of lattices and multivariate polynomials [4]. Interestingly, one of their collision-resistant hash functions with low output locality relies on the hardness assumption of the lattice problem called M,δ-bSVP assumption.The output locality is a natural complexity measure of computational efficiency for Boolean functions. It is known that a Boolean function has output localityk if each output bit depends on a maximum of k input bits. It is obvious that low-output locality functions are implementable by low-depth circuits, implying high parallelizability. In extreme cases, if a function has a constant output locality, it can be decomposed into smaller functions computed using constant-depth circuits in parallel. In IoT devices with only a fragile CPU, it is difficult to execute a single rather large function. For this reason, it is important for many IoT devices to cooperate to execute a single function. In such IoT’s collaborative work, the decomposition property into smaller functions is very useful. Low-depth cryptographic functions play crucial roles in certain protocols as well as IoT devices. For example, the bootstrapping method requires a low-depth decryption function as in lattice-based fully homomorphic public-key encryption [5].There are several quantum-resistant cryptosystems, such as homogeneous cryptosystems and lattice cryptosystems. Output locality is a technology that encourages collaborative work on cryptography. In particular, the construction of cryptographic primitives that are secure against quantum cryptography and satisfy output locality is significant for the widespread use of IoT devices. This paper aims to construct cryptographic primitives that have output locality and are secure against quantum cryptography.On the contrary, a commitment scheme is a fundamental protocol and a key building block of basic cryptographic tasks such as zero-knowledge identification [6]. The scheme is conducted between two parties (i.e., a sender and a receiver) through commitment and decommitment phases. In the commitment phase, the sender converts a message into a commitment string and sends it to the receiver. Then, in the decommitment phase, the sender sends the decommitment string where the message is embedded, which allows the receiver to verify if the commitment string was indeed generated from the message or not. A commitment scheme’s security is formalized based on two properties: the hiding property and the binding property. The hiding property guarantees that no receiver can receive partial information of messages before the decommitment phase. Simultaneously, the binding property ensures that no sender can choose one of more than two candidate messages by switching the decommitment strings in the decommitment phase.The related work is as follows. Note that neither standard commitment schemes such as Pedersen [7] nor Halevi-Micali [8] have low output localities. To achieve a commitment scheme with low output locality, two approaches have been investigated until now. One is proposed in [3], where a transformation from collision-resistant hash functions to commitment schemes that preserve low output locality by using strong randomness extractors in order to obtain the hiding property is provided. Their commitment schemes using this general transformation satisfy the output locality of four.Another one is to avoid using such strong randomness extractors and to construct a commitment scheme directly from a hash function [9, 10], which are our preliminary works. Remark that, in [9], it only proves that the output locality is smaller than the input length, and in [10], it is only claimed that the hiding property is based on the decisional M,δ-bSVP assumption, whereas no concrete proof was given nor the relation between the decisional M,δ-bSVP assumption and M,δ-bSVP assumption was shown. In other words, no secure commitment with output locality-3 has been proposed so far without using strong randomness extractors.Our contributions are as follows. In this paper, we propose a commitment scheme with an output locality of three for the first time. Our construction does not use strong randomness extractors. We construct a commitment scheme directly from a collision-resistant hash function inNC0 without using a strong randomness extractor. We prove its computational hiding property and its computational binding property by using the decisional M,δ-bSVP assumption and M,δ-bSVP assumption, respectively. Furthermore, we prove that the M,δ-bSVP assumption can be reduced to the decisional M,δ-bSVP assumption.To construct such a commitment scheme, we focus on two primitives. The first is a commitment scheme from the short integer solution (SIS) problem [11]. This scheme makes use of a lattice-based collision-resistant hash function of a “matrix-vector multiplication” form, i.e., y=M⋅x for a matrix M∈ℤqm×n, and a vector x∈ℤ2n. Our commitment also follows such a simple construction. As for the lattice-based collision-resistant hash function of low output locality, we use the next primitive of a function fx=M⋅exx, where ex is an expanding function that dilutes the Hamming weight on the input x to achieve collision-resistant properties from the intractability of bSVP [3]. Then, a randomized encoding technique [4] is applied to the function fx to achieve low output locality. Here, a randomized encoding of fx is a randomized mapping f^x,r that generates an output distribution dependent only on fx.Compared to previous works [10] in CANDAR 2020, this paper is the full version of the paper presented at CANDAR 2020. In our preliminary work [10], we have constructed a commitment scheme with output locality-3. However, it does not include any security consideration. In this article, we reconstruct a commitment scheme with output locality-3 based on the M,δ-bSVP assumption and decisional M,δ-bSVP assumption. We describe what we have achieved in this paper in the following:(i)
Prove that theM,δ-bSVP assumption can be reduced to the decisional M,δ-bSVP assumption(ii)
Prove that our commitment scheme satisfies the computational binding property based on theM,δ-bSVP assumption and satisfies the computational hiding property based on the decisional M,δ-bSVP assumption(iii)
Compare our commitment scheme with other previous studiesRoadmap: the remainder of this paper is organized as follows. Section2 summarizes the commitment scheme, the hash function, and the output locality. Section 3 describes the building blocks of our construction. Then, we present our commitment scheme in Section 4. In Section 5, we suggest the parameter of our commitment scheme. Finally, we conclude our work in Section 6.


## 2. Preliminaries

First, we summarize the notations used in this paper.(1)
1k: security parameter(2)
a: message string(3)
r: random string(4)
com: commitment string(5)
dec: decommitment string(6)
εk: negligible function in k(7)
ex: expand function(8)
pp: public parameters(9)
S1k,pp: probabilistic polynomial-time party(10)
Rcom,dec: probabilistic polynomial-time party which executes in the decommitment phase(11)
Rcompp,com: probabilistic polynomial-time party which executes in the commitment phase(12)
c,d: output locality in the ex function(13)
⊥: rejection symbol output by R for invalid inputs(14)
Hwx: Hamming weight of x(15)
Δx: the ratio of “1”s in x(16)
HMex: the hash function we used in this paper(17)
CommMexS,R: our proposed commitment scheme(18)
ℕ: set of natural numbers(19)
m<n∈ℕ(20)
ℳ1n: matrix sampler that generates a uniformly random m×n matrix.(21)
H2p=−plog2p−1−plog21−p denotes the binary entropy function, where p∈0,1(22)
ε: a negligible function throughout this paperNext, we define the commitment scheme, which is as follows [12].Definition 1 (commitment scheme).
A commitment scheme,CommS,R, is a two-phase protocol between two probabilistic polynomial-time parties S and R, which are called the sender and receiver, respectively.
During the first phase (commitment phase),S commits string a to a pair of keys com,dec by executing com,dec←S1k,pp. Then, S sends com (commitment string) to R.
During the second phase (decommitment phase),S sends the keys dec (decommitment string) with a to R. Then, R verifies whether the decommitment string is valid by executing Rcom,dec. If invalid, Rcom,dec outputs a special string, ⊥, meaning that R rejects the decommitment of S. Otherwise, Rcom,dec can efficiently compute the string a revealed by S and verifies whether a was indeed chosen by S during the first phase.
In the following discussion, we provide the security notions of the commitment schemeCommS,R.Definition 2 (computational binding property; see [8]).
We state thatCommS,R is computationally binding if it is computationally infeasible to generate a commitment string com and two decommitment strings, dec,dec′dec≠dec′, such that R will compute a message a from com,dec and a different message a′ from com,dec. In detail, for every probabilistic polynomial-time adversary S′1k,pp, the following occurs:(1)PrRcom,dec≠⊥com,dec,dec′←S′1k,pp:Rcom,dec′≠⊥Rcom,dec≠Rcom,dec′<εk,where εk is a negligible function of k. We then say that the commitment scheme CommS,R is computationally binding.Definition 3 (computational hiding property).
A commitment schemeCommS,R is computationally hiding if for every probabilistic polynomial-time party Rcom, it satisfies(2)Pry1Rcompp,y1=1−Pry2Rcompp,y2=1<εk,where pp is a public parameter generated randomly according to the commitment scheme and yi is a commitment string generated from pp and xi by S for random xi sampled from an unknown distribution to Rcomi=1,2.
The computational security of a commitment scheme in this study uses the following assumption.Definition 4 (M,δ-bSVP assumption; see [3]).
For a weight parameter,δn,δ:ℕ⟶0,1/2, and an efficient sampler ℳ1n that samples m×n binary matrices, the M,δ-bSVP assumption asserts that, for every efficient algorithm Adv, the probability is given by(3)PrM←Rℳ1nAdvM=xs.t.Mx=0andΔx≤δ<εn.
We introduce a feature of the output locality. We start from the definition of a hash function. A hash function converts input bits of arbitrary length into compressed output bits of shorter lengths. We define the collision resistance of a hash function in Definition5.Definition 5 (collision resistance).
We have an arbitrary probabilistic polynomial algorithm,Adv, given a description of the hash function and length parameter as inputs. If the probability of Adv that outputs x,x′∈0,1k satisfying x≠x′andfx=fx′ is negligible, the function is a collision-resistant hash function.(4)PrAdvf,1k⟶x,x′s.t.x≠x′,fx=fx′<εk.
Next, we define the output locality.Definition 6 (output locality).
We say that the functionh has output locality d if each of the output bits depends on at most d input bits.
Finally, we define perfect randomized encoding (PRE). PRE is a technique that can make the output locality a constant.Definition 7 (perfect randomized encoding; see [3]).
Letf:0,1n⟶0,1l be a function. We say that a function f^:0,1n×0,1m⟶0,1s is a PRE of f if there exist an efficient decoding algorithm C and a randomized simulator S that satisfy the following:(i)
Perfect correctness: for every inputx∈0,1n and r∈0,1m, Cf^x;r=fx holds(ii)
Perfect privacy: for everyx∈0,1n, the distribution f^x;r induced by a uniform choice of r←R0,1m is identical to the distribution of Sfx(iii)
Balanced simulation: the distributionSy induced by choosing y←R0,1l is identical to the uniform distribution over 0,1s(iv)
Length preserving: the difference between the output length and the total input length of the encodings−n+m is equal to the difference l−n between the output length and the input length of f


## 3. Building Blocks

In this section, we first define an expanding functionex [3] in Section 3.1. The expanding function is created for the function to apply the M,δ-bSVP assumption. We then show an example of PRE and how to make the output locality constant by using PRE in Section 3.2. We also show how to gain fx from encoded function f^x, which is called perfect correctness in PRE.


### 3.1. Expand Functionex

We give one expanding functionex used in Theorem 4, where ex is a function of 0,1k⟶0,1n that dilutes the relative Hamming weight of the input bits. In order to satisfy the M,δ-bSVP assumption, the relative Hamming weight β of the outputs of exx has to satisfy β≤δ/2δ∈0,1/2.Next, we will explain how the functionex expands the input bits. First, we divide k bit blocks to k/d bit blocks, in which each bit block has d bits, as shown in Figure 1. We execute a function ex0 to each of the d bit blocks, where ex0 expands d bit blocks to c bit blocks, shown in Algorithm 1. Then, every block of the output of ex0 is concatenated as an output of exc⋅k/d=n. The whole algorithm of ex is given in Algorithm 2. The feature of ex is given in Lemma 1.Figure 1
ex function.Algorithm 1:ex0 function.
Input:x∈0,1dOutput:ex0x∈0,1c(1)
Identifyx∈0,1d as a binary representation of natural numbers in 0,…,2d−1(2)
Sety∈0,1c to the x+1-th string of a relative Hamming weight of maximum value β in the lexicographic order(3)
Returny∈0,1cAlgorithm 2:ex function.
Input:x∈0,1kOutput:exx∈0,1n(1)
Partitionk-bit inputs into k/d input blocks of d bits each(2)
Applyex0 to each input block, and generate k/d output blocks of c bits(3)
Returnex0x1ex0x2…ex0xk/d=exxLemma 1 (expand function with low output locality; see [3]).
Forδ∈0,1/2, let β≤δ/2 be the relative Hamming weight of ex. Set n/k≥⌈1/H2β⌉ and c≥⌈1/H2β⌉d for the natural numbers n,k. Then, there exists an efficiently computable function ex:0,1k⟶0,1n such that (1) ex is injective, (2) Δexx≤β for every x, and (3) ex has output locality d.
In this study, the hash functionHMex uses an expanding function defined in Lemma 1.


### 3.2. Construction of PRE

We give one construction of PRE for a given functionf:F2n⟶F2 in 1.Construction 1 (see [1]).
Letf be a function f:F2n⟶F2. Then, we separate fx to v functions T1,…,Tv:F2n⟶F2 as follows:(5)fx=T1x+⋯+Tvx,where Tjx can be written by monomial j=1,…,v. For r1,…,rv,r1′,…,rv−1′∈F2, we define a function f^:F2n×F22v−1⟶F22v by(6)f^x,r1,…,rv,r1′,…,rv−1′=T1x−r1,T2x−r2,…,Tvx−rv,r1−r1′,r1′+r2−rv−2′+rv−1−rv−1′+rv.
1 satisfies PRE in Definition 7. Let fx=x1x2+x2x3+x4 where v=3 and n=4. Then, f can be encoded as the following equation:(7)f^x,r1,r2,r3,r1′,r2′=x1x2−r1,x2x3−r2,x4−r3r1−r′,r1′+r2−r2′,r2′+r3.
Equation (7) is an example of 1. Denote by Cz adding all bits in z over F2. Then, we can gain fx from f^x by using C as follows:(8)Cf^x=x1x2−r1+x2x3−r2+x4−r3++r1−r1′+r1′+r2−r2′+r2′+r3=x1x2+x2x3+x4.
It satisfies “perfect correctness” sinceCf^x=fx. From the example of equation (7), the output locality of function fx can be reduced to a constant by using PRE. A quantitative evaluation of the output locality is given in Lemma 2.Lemma 2 (see [1]).
Letf:F2n⟶F2 be a function. Then, let f^ be given as in 1. In particular, if f is a degree-d polynomial written as a sum of monomials, then f^ is a PRE of f with degree d and output locality maxd+1,3 1.


## 3.1. Expand Functionex

We give one expanding functionex used in Theorem 4, where ex is a function of 0,1k⟶0,1n that dilutes the relative Hamming weight of the input bits. In order to satisfy the M,δ-bSVP assumption, the relative Hamming weight β of the outputs of exx has to satisfy β≤δ/2δ∈0,1/2.Next, we will explain how the functionex expands the input bits. First, we divide k bit blocks to k/d bit blocks, in which each bit block has d bits, as shown in Figure 1. We execute a function ex0 to each of the d bit blocks, where ex0 expands d bit blocks to c bit blocks, shown in Algorithm 1. Then, every block of the output of ex0 is concatenated as an output of exc⋅k/d=n. The whole algorithm of ex is given in Algorithm 2. The feature of ex is given in Lemma 1.Figure 1
ex function.Algorithm 1:ex0 function.
Input:x∈0,1dOutput:ex0x∈0,1c(1)
Identifyx∈0,1d as a binary representation of natural numbers in 0,…,2d−1(2)
Sety∈0,1c to the x+1-th string of a relative Hamming weight of maximum value β in the lexicographic order(3)
Returny∈0,1cAlgorithm 2:ex function.
Input:x∈0,1kOutput:exx∈0,1n(1)
Partitionk-bit inputs into k/d input blocks of d bits each(2)
Applyex0 to each input block, and generate k/d output blocks of c bits(3)
Returnex0x1ex0x2…ex0xk/d=exxLemma 1 (expand function with low output locality; see [3]).
Forδ∈0,1/2, let β≤δ/2 be the relative Hamming weight of ex. Set n/k≥⌈1/H2β⌉ and c≥⌈1/H2β⌉d for the natural numbers n,k. Then, there exists an efficiently computable function ex:0,1k⟶0,1n such that (1) ex is injective, (2) Δexx≤β for every x, and (3) ex has output locality d.
In this study, the hash functionHMex uses an expanding function defined in Lemma 1.


## 3.2. Construction of PRE

We give one construction of PRE for a given functionf:F2n⟶F2 in 1.Construction 1 (see [1]).
Letf be a function f:F2n⟶F2. Then, we separate fx to v functions T1,…,Tv:F2n⟶F2 as follows:(5)fx=T1x+⋯+Tvx,where Tjx can be written by monomial j=1,…,v. For r1,…,rv,r1′,…,rv−1′∈F2, we define a function f^:F2n×F22v−1⟶F22v by(6)f^x,r1,…,rv,r1′,…,rv−1′=T1x−r1,T2x−r2,…,Tvx−rv,r1−r1′,r1′+r2−rv−2′+rv−1−rv−1′+rv.
1 satisfies PRE in Definition 7. Let fx=x1x2+x2x3+x4 where v=3 and n=4. Then, f can be encoded as the following equation:(7)f^x,r1,r2,r3,r1′,r2′=x1x2−r1,x2x3−r2,x4−r3r1−r′,r1′+r2−r2′,r2′+r3.
Equation (7) is an example of 1. Denote by Cz adding all bits in z over F2. Then, we can gain fx from f^x by using C as follows:(8)Cf^x=x1x2−r1+x2x3−r2+x4−r3++r1−r1′+r1′+r2−r2′+r2′+r3=x1x2+x2x3+x4.
It satisfies “perfect correctness” sinceCf^x=fx. From the example of equation (7), the output locality of function fx can be reduced to a constant by using PRE. A quantitative evaluation of the output locality is given in Lemma 2.Lemma 2 (see [1]).
Letf:F2n⟶F2 be a function. Then, let f^ be given as in 1. In particular, if f is a degree-d polynomial written as a sum of monomials, then f^ is a PRE of f with degree d and output locality maxd+1,3 1.


## 4. Proposed Commitment Scheme

In this section, we propose a commitment schemeCommMexS,R which is constructed by using ex and H^Mex. The hash function H^Mex is PRE of HMex. We define the decisional M,δ-bSVP assumption and show that the M,δ-bSVP assumption can be reduced to the decisional M,δ-bSVP assumption. Furthermore, we show that our proposed commitment scheme satisfies the binding property and hiding property.


### 4.1. Difference betweenCommMexS,R and the Commitment in [3]

In [3], Applebaum et al. showed how to construct a statistically hiding commitment scheme with output locality-4 from their collision-resistant hash function under the M,δ-bSVP assumption. Their commitment scheme executes a hash function based on a randomness extractor and an ordinary hash function with output locality-4. As a result, two hash functions are required. Furthermore, the randomness extractor is the universal hash function family, so it requires additional random bits to choose a function from the function family. Here, additional bits correspond to the input of the hash function.On the contrary, our commitment scheme has to only execute an ordinary hash function once. Compared with their commitment scheme, our scheme is more efficient. Furthermore, our commitment scheme achieves output locality-3 by introducing the new notion of decisionalM,δ-bSVP assumption.


### 4.2. DecisionalM,δ-bSVP Assumption

We introduce a new notion of decisionalM,δ-bSVP assumption, which is a decisional version of the M,δ-bSVP assumption defined in Definition 4.Definition 8 (decisionalM,δ-bSVP assumption).
For a weight parameterδn:ℕ⟶0,1/2, a uniform distribution U∈ℤ2m, and an efficient sampler ℳ1n that samples m×n binary matrices, the decisional M,δ-bSVP assumption asserts that, for any polynomial algorithm Adv and for every x∈0,1n where δ≤Δx≤1−δ,(9)PrM←Rℳ1n,y1←M⋅xAdvM,y1=1−PrM←RU,y2←UAdvM,y2=1<εn.
We show that theM,δ-bSVP assumption can be reduced to the decisional M,δ-bSVP assumption by referring to the methodology presented in Lemma 4.2 of [13], where Decision LWE is reduced to Search LWE.Theorem 1.
Lety:0,1n⟶0,1m be a function, and define M,δ-bSVP distribution on m-bit strings obtained by choosing x∈0,1n and outputting y=M⋅x. Assume that we have an access to a procedure D which distinguishes the input y sampled from the distribution of M,δ-bSVP or sampled from a uniform distribution U with nonnegligible probability. Then, there exists a polynomial-time algorithm D′ such that given samples from M,δ-bSVP distribution, D′ can output x with nonnegligible probability.Proof.
LetD be a distinguisher which distinguishes an element sampled from the M,δ-bSVP distribution or sampled from a uniform distribution U. Then, we construct D′ which finds x∈ℤ2n of Mx. We first show how D′ finds x1∈ℤ2 which denotes the first coordinate of x. The remaining coordinates can be recovered by the same way.
Given an input ofD′, A=M,y, where y is selected from an M,δ-bSVP distribution. The input of D can be defined as follows. Let x be denoted as x=x1,…,xn and M be denoted by the following equation:(10)M=c11⋯c1j⋯c1n⋮⋱⋮ci1cijcin⋮⋱⋮cm1⋯cmj⋯cmn.
Then,y=Mx∈F2m can be written as(11)y=c11⋅x1⊕c12⋅x2⊕⋯⊕c1n⋅xn⋮cm1⋅x1⊕cm2⋅x2⊕⋯⊕cmn⋅xn.
For randomly chosenk∈ℤ2 and li1∈ℤ2i=1,…,m, compute a pair(12)A′=M⊕l110⋯0⋮⋮⋱⋮lm10⋯0,y⊕l11⋅k⋮lm1⋅k.
Denote the value obtained in equation (12) as A′=M′,y′. Now, D′ sends A′=M′,y′ to D. If k=x1, then y′ can be written as the following equation:(13)y′=c11⊕l11⋅x1⊕⋯⊕c1n⋅xn⋮cm1⊕lm1⋅x1⊕⋯⊕cmn⋅xn.
Since equation (13) can be expressed in the form y′=M′x, D can distinguish that equation (13) is contained in the M,δ-bSVP distribution. Then, D can distinguish that A′ is in the M,δ-bSVP distribution. In contrast, if k≠x1, then y′ will be expressed as(14)y′=Mx⊕l1k⋮lmk,which is clearly not a sample from the M,δ-bSVP distribution. Then, D can distinguish that A′ is in the uniform distribution.
Finally,D′ outputs k=x1 if D outputs M,δ-bSVP distribution. On the contrary, D′ outputs k=x¯1 if D outputs uniform distribution.
All other remaining coordinates inx can be recovered in the same way. Therefore, D′ can output x by using D with nonnegligible probability.
From the contraposition of Theorem1, we can get Corollary 1.Corollary 1.
There is no polynomial algorithm that can break the decisionalM,δ-bSVP assumption under the hardness of the M,δ-bSVP assumption.


### 4.3. Proposed Commitment SchemeCommMexS,R

We analyze the hash functionH^Mex in Section 4.3.1 and show our commitment scheme CommMexS,R in Section 4.3.2.


#### 4.3.1. A Hash FunctionH^Mex for the Commitment Scheme

We first explain a hash functionHMex [3], containing a matrix MM and an expand function ex, as shown in Algorithm 3.Algorithm 3: Hash function: HMexx.
Input:x∈0,1kOutput:M⋅exx∈0,1m(1)
Partitionk-bit inputs into k/d input blocks of d bits each(2)
Applyex0 to each input block, and generate k/d output blocks of c bits(3)
Setexx as exx=ex0x1ex0x2…ex0xk/d(4)
ComputeM⋅exx(5)
ReturnM⋅exxThen, we show the hash functionH^Mex which is PRE of HMex.(15)H^Mex:0,1k×0,1nm⟶0,11+nm.We consider the matrixM as follows:(16)M=c11⋯c1j⋯c1n⋮⋱⋮ci1cijcin⋮⋱⋮cm1⋯cmj⋯cmn=M1⋮Mi⋮Mm,for ci,j∈ℤ2 and Mi∈0,1ni=1,…,m,j=1,…,n. Also, we define the random number t∈0,1nm as t=T1,…,Tm where Ti is taken over uniform Ti∈0,1n in any i∈1,…,m. Furthermore, define exx as exx=exx1,…,exxn where exxi is taken over exxi in any i∈1,…,n. Note that we write the first coordinate of T1 as t11. An algorithm of H^Mex is shown in Algorithm 4. Note that a matrix M∈ℳ1n is treated as a part of the description of the algorithm.Algorithm 4: Algorithm of H^Mex.
Input:x∈0,1k, t∈0,1nmOutput:y^∈0,11+nm(1)
Computeexx from x(2)
for1≤i≤mdo(3)
for1≤j≤n+1do(4)
v←n+1∗i−1+j(5)
ifv=n+1∗i−1+1then(6)
y^v←Mi1∧exx1⊕ti1(7)
else ifv=n+1∗i−1+n+1then(8)
y^v←tin(9)
else(10)
y^v←Mij∧exxj⊕tij⊕tij−1(11)
end if(12)
end for(13)
end for(14)
returny^The hash functionH^Mex is PRE of HMex since the construction of H^Mex is as same as 1. Here, we only give a theorem about PRE of HMex and H^Mex.Theorem 2.
H^Mex satisfies perfect correctness, perfect privacy, balanced simulation, and length preserving for HMex.
We show the output locality ofH^Mex in Theorem 3.Theorem 3.
H^Mex has 3 output localities.Proof.
Let us investigate the output locality ofH^Mex. From the structure of Algorithm 4, the maximum number of input bits on which the output bits depend is 3. Therefore, the output locality of H^Mex is 3.
Next, let us discuss the collision resistance ofH^Mex. If a function satisfies the collision resistance, then its PRE also satisfies the collision resistance [1]. Applebaum et al. proved the collision resistance of HMex. Therefore, the collision resistance of H^Mex follows from [1]. The collision resistance of H^Mex is described in Lemma 3.Lemma 3 (collision resistance ofH^Mex; see [3]).
Let the hash functionH^Mex be a perfectly randomized encoding of HMex. Then, H^Mex has a collision resistance under the M,δ-bSVP assumption.


#### 4.3.2. Commitment SchemeCommMexS,R

We show the commitment schemeCommMexS,R based on H^Mex, which consists of initialization, a commitment phase, and a decommitment phase. In this construction, we use the same matrix M, but we can also refresh a matrix M in a certain period, and the computational binding property and computational hiding property also hold using refreshed matrix M. CommMexS,R:Initialization:Before the commitment phase, bothS and R share the following information:(i)
Algorithm ofex:0,1k⟶0,1n(ii)
MatrixM∈ℳ1n(iii)
1k: security parameterCommitment phase byS:(1)
Choose a random numberr∈0,1k/2 as the key of the hash functions(2)
Choose a message stringa∈0,1k/2, and concatenate a and r as x=a‖r(3)
Choose a random numbert∈0,1nm which is used for PRE(4)
Computeexx∈0,1n(5)
ComputeH^Mexa,r,t∈0,1n+1m(6)
Sendcoma,r,t=H^Mexa,r,t′ as a commitment string comDecommitment phase fromS to R:S executes the following:(1)
S sends a,r∈0,1k/2×0,1k/2 and t∈0,1nm to R as a decommitment string decR executes the following:(1)
Computex=a‖r from dec.(2)
Computeexx.(3)
Compute the commitment stringH^Mexa,r,t and check whether H^Mexa,r,t=com. If this is satisfied, R outputs a. Otherwise, R outputs ⊥.Next, we prove the computational binding property and computational hiding property ofCommMexS,R. We first show the computational binding property.Theorem 4.
CommMexS,R satisfies the computational binding property under the M,δ-bSVP assumption.Proof.
We assume that there exists a probabilistic polynomial-time (PPT) adversary Adv that breaks the computational binding property of the commitment schemeCommMexS,R. Then, Adv can derive the following equation, with nonnegligible function ε′k from Definition 2.(17)PrAdv1k,M⟶com,dec,dec′∧dec≠dec′>ε′k.
From equation (17), com=H^Mexdec, and another PPT adversary Adv’, we can lead the following equation:(18)PrAdv′1k,M⟶dec,dec′∧H^Mexdec=H^Mexdec′∧dec≠dec′>ε′k.
This shows that if PPT Adv can break the computational binding property, it can also break the collision resistance ofH^Mex from equation (18). However, we showed that H^Mex has a collision resistance under the M,δ-bSVP assumption in Lemma 3. Therefore, the commitment scheme CommMexS,R satisfies the computational binding property under the M,δ-bSVP assumption based on the contradiction.
Next, we will prove the computational hiding property ofCommMexS,R.Theorem 5.
CommMexS,R satisfies the computational hiding property under the decisional M,d/4c-bSVP assumption for a constant c/d=n/k.Proof.
We assume that there exists a probabilistic polynomial-time adversary Adv that breaks the computational hiding property ofCommMexS,R. For some distinct a,a′∈0,1k/2, r,r′∈0,1k/2, t,t′∈0,1nm, and some nonnegligible function ε′, we can derive the following equation:(19)PrAdvM,H^Mexa‖r,t=1−PrAdvM,H^Mexa′‖r′,t′=1>ε′k.
Since the decoding procedureC of PRE is a polynomial-time algorithm, there exists a polynomial-time adversary Adv′, which is a composition of the decoding procedure and Adv such that(20)PrAdv′M,M⋅exa‖r=1−PrAdv′M,M⋅exa′‖r′=1>ε′k.
By the hybrid argument, for somea,(21)PrAdv′M,M⋅exa‖r=1−PrAdv′M,U=1>ε′k2.
Sincer is uniformly random over 0,1k/2, for every a∈0,1k/2, we have Δa‖r∈1/8,7/8, and hence, Δexa‖r∈d/8c,7d/8c for a constant c/d=n/k with probability 1−exp−Ωk from the Chernoff bounds. This contradicts the decisional M,δ-bSVP assumption.


### 4.4. Comparison

We compare our proposed commitment scheme with related works of [BDLOP18] and [KTX08] in Table1. Both [BDLOP18] and [KTX08] are also based on lattice-based functions and consist of “matrix-vector multiplication” in the same way as us.Table 1
Comparison of our proposed commitment scheme.
HidingBindingOutput locality[KTX08] [11]StatisticalSIS—[BDLOP18] [14]DKSSKS—[AHIKV17] [3]StatisticalbSVP4This paperD-bSVPbSVP3A commitment scheme [KTX08] can prove its hiding property statistically and its binding property by the SIS problem. However, it did not achieve constant output locality. A commitment scheme [BDLOP18] can prove its hiding property and binding property by DKS and SKS problems, respectively. Nevertheless, it also did not achieve constant output locality.On the contrary, the commitment scheme [AHIKV17] has achieved output locality-4 with its statistically hiding property and its binding property based on theM,δ-bSVP assumption (bSVP). However, their commitment scheme was to execute hash functions twice with a randomness extractor. It was also difficult to construct a commitment scheme with output locality-3 by using a randomness extractor.Our commitment schemeCommMexS,R satisfies output locality-3 by proving its hiding property and binding property by the decisional M,δ-bSVP assumption (D-bSVP) and M,δ-bSVP assumption (bSVP), respectively. Our commitment scheme only executes the hash function H^Mex once and does not use a randomness extractor.


## 4.1. Difference betweenCommMexS,R and the Commitment in [3]

In [3], Applebaum et al. showed how to construct a statistically hiding commitment scheme with output locality-4 from their collision-resistant hash function under the M,δ-bSVP assumption. Their commitment scheme executes a hash function based on a randomness extractor and an ordinary hash function with output locality-4. As a result, two hash functions are required. Furthermore, the randomness extractor is the universal hash function family, so it requires additional random bits to choose a function from the function family. Here, additional bits correspond to the input of the hash function.On the contrary, our commitment scheme has to only execute an ordinary hash function once. Compared with their commitment scheme, our scheme is more efficient. Furthermore, our commitment scheme achieves output locality-3 by introducing the new notion of decisionalM,δ-bSVP assumption.


## 4.2. DecisionalM,δ-bSVP Assumption

We introduce a new notion of decisionalM,δ-bSVP assumption, which is a decisional version of the M,δ-bSVP assumption defined in Definition 4.Definition 8 (decisionalM,δ-bSVP assumption).
For a weight parameterδn:ℕ⟶0,1/2, a uniform distribution U∈ℤ2m, and an efficient sampler ℳ1n that samples m×n binary matrices, the decisional M,δ-bSVP assumption asserts that, for any polynomial algorithm Adv and for every x∈0,1n where δ≤Δx≤1−δ,(9)PrM←Rℳ1n,y1←M⋅xAdvM,y1=1−PrM←RU,y2←UAdvM,y2=1<εn.
We show that theM,δ-bSVP assumption can be reduced to the decisional M,δ-bSVP assumption by referring to the methodology presented in Lemma 4.2 of [13], where Decision LWE is reduced to Search LWE.Theorem 1.
Lety:0,1n⟶0,1m be a function, and define M,δ-bSVP distribution on m-bit strings obtained by choosing x∈0,1n and outputting y=M⋅x. Assume that we have an access to a procedure D which distinguishes the input y sampled from the distribution of M,δ-bSVP or sampled from a uniform distribution U with nonnegligible probability. Then, there exists a polynomial-time algorithm D′ such that given samples from M,δ-bSVP distribution, D′ can output x with nonnegligible probability.Proof.
LetD be a distinguisher which distinguishes an element sampled from the M,δ-bSVP distribution or sampled from a uniform distribution U. Then, we construct D′ which finds x∈ℤ2n of Mx. We first show how D′ finds x1∈ℤ2 which denotes the first coordinate of x. The remaining coordinates can be recovered by the same way.
Given an input ofD′, A=M,y, where y is selected from an M,δ-bSVP distribution. The input of D can be defined as follows. Let x be denoted as x=x1,…,xn and M be denoted by the following equation:(10)M=c11⋯c1j⋯c1n⋮⋱⋮ci1cijcin⋮⋱⋮cm1⋯cmj⋯cmn.
Then,y=Mx∈F2m can be written as(11)y=c11⋅x1⊕c12⋅x2⊕⋯⊕c1n⋅xn⋮cm1⋅x1⊕cm2⋅x2⊕⋯⊕cmn⋅xn.
For randomly chosenk∈ℤ2 and li1∈ℤ2i=1,…,m, compute a pair(12)A′=M⊕l110⋯0⋮⋮⋱⋮lm10⋯0,y⊕l11⋅k⋮lm1⋅k.
Denote the value obtained in equation (12) as A′=M′,y′. Now, D′ sends A′=M′,y′ to D. If k=x1, then y′ can be written as the following equation:(13)y′=c11⊕l11⋅x1⊕⋯⊕c1n⋅xn⋮cm1⊕lm1⋅x1⊕⋯⊕cmn⋅xn.
Since equation (13) can be expressed in the form y′=M′x, D can distinguish that equation (13) is contained in the M,δ-bSVP distribution. Then, D can distinguish that A′ is in the M,δ-bSVP distribution. In contrast, if k≠x1, then y′ will be expressed as(14)y′=Mx⊕l1k⋮lmk,which is clearly not a sample from the M,δ-bSVP distribution. Then, D can distinguish that A′ is in the uniform distribution.
Finally,D′ outputs k=x1 if D outputs M,δ-bSVP distribution. On the contrary, D′ outputs k=x¯1 if D outputs uniform distribution.
All other remaining coordinates inx can be recovered in the same way. Therefore, D′ can output x by using D with nonnegligible probability.
From the contraposition of Theorem1, we can get Corollary 1.Corollary 1.
There is no polynomial algorithm that can break the decisionalM,δ-bSVP assumption under the hardness of the M,δ-bSVP assumption.


## 4.3. Proposed Commitment SchemeCommMexS,R

We analyze the hash functionH^Mex in Section 4.3.1 and show our commitment scheme CommMexS,R in Section 4.3.2.


### 4.3.1. A Hash FunctionH^Mex for the Commitment Scheme

We first explain a hash functionHMex [3], containing a matrix MM and an expand function ex, as shown in Algorithm 3.Algorithm 3: Hash function: HMexx.
Input:x∈0,1kOutput:M⋅exx∈0,1m(1)
Partitionk-bit inputs into k/d input blocks of d bits each(2)
Applyex0 to each input block, and generate k/d output blocks of c bits(3)
Setexx as exx=ex0x1ex0x2…ex0xk/d(4)
ComputeM⋅exx(5)
ReturnM⋅exxThen, we show the hash functionH^Mex which is PRE of HMex.(15)H^Mex:0,1k×0,1nm⟶0,11+nm.We consider the matrixM as follows:(16)M=c11⋯c1j⋯c1n⋮⋱⋮ci1cijcin⋮⋱⋮cm1⋯cmj⋯cmn=M1⋮Mi⋮Mm,for ci,j∈ℤ2 and Mi∈0,1ni=1,…,m,j=1,…,n. Also, we define the random number t∈0,1nm as t=T1,…,Tm where Ti is taken over uniform Ti∈0,1n in any i∈1,…,m. Furthermore, define exx as exx=exx1,…,exxn where exxi is taken over exxi in any i∈1,…,n. Note that we write the first coordinate of T1 as t11. An algorithm of H^Mex is shown in Algorithm 4. Note that a matrix M∈ℳ1n is treated as a part of the description of the algorithm.Algorithm 4: Algorithm of H^Mex.
Input:x∈0,1k, t∈0,1nmOutput:y^∈0,11+nm(1)
Computeexx from x(2)
for1≤i≤mdo(3)
for1≤j≤n+1do(4)
v←n+1∗i−1+j(5)
ifv=n+1∗i−1+1then(6)
y^v←Mi1∧exx1⊕ti1(7)
else ifv=n+1∗i−1+n+1then(8)
y^v←tin(9)
else(10)
y^v←Mij∧exxj⊕tij⊕tij−1(11)
end if(12)
end for(13)
end for(14)
returny^The hash functionH^Mex is PRE of HMex since the construction of H^Mex is as same as 1. Here, we only give a theorem about PRE of HMex and H^Mex.Theorem 2.
H^Mex satisfies perfect correctness, perfect privacy, balanced simulation, and length preserving for HMex.
We show the output locality ofH^Mex in Theorem 3.Theorem 3.
H^Mex has 3 output localities.Proof.
Let us investigate the output locality ofH^Mex. From the structure of Algorithm 4, the maximum number of input bits on which the output bits depend is 3. Therefore, the output locality of H^Mex is 3.
Next, let us discuss the collision resistance ofH^Mex. If a function satisfies the collision resistance, then its PRE also satisfies the collision resistance [1]. Applebaum et al. proved the collision resistance of HMex. Therefore, the collision resistance of H^Mex follows from [1]. The collision resistance of H^Mex is described in Lemma 3.Lemma 3 (collision resistance ofH^Mex; see [3]).
Let the hash functionH^Mex be a perfectly randomized encoding of HMex. Then, H^Mex has a collision resistance under the M,δ-bSVP assumption.


### 4.3.2. Commitment SchemeCommMexS,R

We show the commitment schemeCommMexS,R based on H^Mex, which consists of initialization, a commitment phase, and a decommitment phase. In this construction, we use the same matrix M, but we can also refresh a matrix M in a certain period, and the computational binding property and computational hiding property also hold using refreshed matrix M. CommMexS,R:Initialization:Before the commitment phase, bothS and R share the following information:(i)
Algorithm ofex:0,1k⟶0,1n(ii)
MatrixM∈ℳ1n(iii)
1k: security parameterCommitment phase byS:(1)
Choose a random numberr∈0,1k/2 as the key of the hash functions(2)
Choose a message stringa∈0,1k/2, and concatenate a and r as x=a‖r(3)
Choose a random numbert∈0,1nm which is used for PRE(4)
Computeexx∈0,1n(5)
ComputeH^Mexa,r,t∈0,1n+1m(6)
Sendcoma,r,t=H^Mexa,r,t′ as a commitment string comDecommitment phase fromS to R:S executes the following:(1)
S sends a,r∈0,1k/2×0,1k/2 and t∈0,1nm to R as a decommitment string decR executes the following:(1)
Computex=a‖r from dec.(2)
Computeexx.(3)
Compute the commitment stringH^Mexa,r,t and check whether H^Mexa,r,t=com. If this is satisfied, R outputs a. Otherwise, R outputs ⊥.Next, we prove the computational binding property and computational hiding property ofCommMexS,R. We first show the computational binding property.Theorem 4.
CommMexS,R satisfies the computational binding property under the M,δ-bSVP assumption.Proof.
We assume that there exists a probabilistic polynomial-time (PPT) adversary Adv that breaks the computational binding property of the commitment schemeCommMexS,R. Then, Adv can derive the following equation, with nonnegligible function ε′k from Definition 2.(17)PrAdv1k,M⟶com,dec,dec′∧dec≠dec′>ε′k.
From equation (17), com=H^Mexdec, and another PPT adversary Adv’, we can lead the following equation:(18)PrAdv′1k,M⟶dec,dec′∧H^Mexdec=H^Mexdec′∧dec≠dec′>ε′k.
This shows that if PPT Adv can break the computational binding property, it can also break the collision resistance ofH^Mex from equation (18). However, we showed that H^Mex has a collision resistance under the M,δ-bSVP assumption in Lemma 3. Therefore, the commitment scheme CommMexS,R satisfies the computational binding property under the M,δ-bSVP assumption based on the contradiction.
Next, we will prove the computational hiding property ofCommMexS,R.Theorem 5.
CommMexS,R satisfies the computational hiding property under the decisional M,d/4c-bSVP assumption for a constant c/d=n/k.Proof.
We assume that there exists a probabilistic polynomial-time adversary Adv that breaks the computational hiding property ofCommMexS,R. For some distinct a,a′∈0,1k/2, r,r′∈0,1k/2, t,t′∈0,1nm, and some nonnegligible function ε′, we can derive the following equation:(19)PrAdvM,H^Mexa‖r,t=1−PrAdvM,H^Mexa′‖r′,t′=1>ε′k.
Since the decoding procedureC of PRE is a polynomial-time algorithm, there exists a polynomial-time adversary Adv′, which is a composition of the decoding procedure and Adv such that(20)PrAdv′M,M⋅exa‖r=1−PrAdv′M,M⋅exa′‖r′=1>ε′k.
By the hybrid argument, for somea,(21)PrAdv′M,M⋅exa‖r=1−PrAdv′M,U=1>ε′k2.
Sincer is uniformly random over 0,1k/2, for every a∈0,1k/2, we have Δa‖r∈1/8,7/8, and hence, Δexa‖r∈d/8c,7d/8c for a constant c/d=n/k with probability 1−exp−Ωk from the Chernoff bounds. This contradicts the decisional M,δ-bSVP assumption.


## 4.3.1. A Hash FunctionH^Mex for the Commitment Scheme

We first explain a hash functionHMex [3], containing a matrix MM and an expand function ex, as shown in Algorithm 3.Algorithm 3: Hash function: HMexx.
Input:x∈0,1kOutput:M⋅exx∈0,1m(1)
Partitionk-bit inputs into k/d input blocks of d bits each(2)
Applyex0 to each input block, and generate k/d output blocks of c bits(3)
Setexx as exx=ex0x1ex0x2…ex0xk/d(4)
ComputeM⋅exx(5)
ReturnM⋅exxThen, we show the hash functionH^Mex which is PRE of HMex.(15)H^Mex:0,1k×0,1nm⟶0,11+nm.We consider the matrixM as follows:(16)M=c11⋯c1j⋯c1n⋮⋱⋮ci1cijcin⋮⋱⋮cm1⋯cmj⋯cmn=M1⋮Mi⋮Mm,for ci,j∈ℤ2 and Mi∈0,1ni=1,…,m,j=1,…,n. Also, we define the random number t∈0,1nm as t=T1,…,Tm where Ti is taken over uniform Ti∈0,1n in any i∈1,…,m. Furthermore, define exx as exx=exx1,…,exxn where exxi is taken over exxi in any i∈1,…,n. Note that we write the first coordinate of T1 as t11. An algorithm of H^Mex is shown in Algorithm 4. Note that a matrix M∈ℳ1n is treated as a part of the description of the algorithm.Algorithm 4: Algorithm of H^Mex.
Input:x∈0,1k, t∈0,1nmOutput:y^∈0,11+nm(1)
Computeexx from x(2)
for1≤i≤mdo(3)
for1≤j≤n+1do(4)
v←n+1∗i−1+j(5)
ifv=n+1∗i−1+1then(6)
y^v←Mi1∧exx1⊕ti1(7)
else ifv=n+1∗i−1+n+1then(8)
y^v←tin(9)
else(10)
y^v←Mij∧exxj⊕tij⊕tij−1(11)
end if(12)
end for(13)
end for(14)
returny^The hash functionH^Mex is PRE of HMex since the construction of H^Mex is as same as 1. Here, we only give a theorem about PRE of HMex and H^Mex.Theorem 2.
H^Mex satisfies perfect correctness, perfect privacy, balanced simulation, and length preserving for HMex.
We show the output locality ofH^Mex in Theorem 3.Theorem 3.
H^Mex has 3 output localities.Proof.
Let us investigate the output locality ofH^Mex. From the structure of Algorithm 4, the maximum number of input bits on which the output bits depend is 3. Therefore, the output locality of H^Mex is 3.
Next, let us discuss the collision resistance ofH^Mex. If a function satisfies the collision resistance, then its PRE also satisfies the collision resistance [1]. Applebaum et al. proved the collision resistance of HMex. Therefore, the collision resistance of H^Mex follows from [1]. The collision resistance of H^Mex is described in Lemma 3.Lemma 3 (collision resistance ofH^Mex; see [3]).
Let the hash functionH^Mex be a perfectly randomized encoding of HMex. Then, H^Mex has a collision resistance under the M,δ-bSVP assumption.


## 4.3.2. Commitment SchemeCommMexS,R

We show the commitment schemeCommMexS,R based on H^Mex, which consists of initialization, a commitment phase, and a decommitment phase. In this construction, we use the same matrix M, but we can also refresh a matrix M in a certain period, and the computational binding property and computational hiding property also hold using refreshed matrix M. CommMexS,R:Initialization:Before the commitment phase, bothS and R share the following information:(i)
Algorithm ofex:0,1k⟶0,1n(ii)
MatrixM∈ℳ1n(iii)
1k: security parameterCommitment phase byS:(1)
Choose a random numberr∈0,1k/2 as the key of the hash functions(2)
Choose a message stringa∈0,1k/2, and concatenate a and r as x=a‖r(3)
Choose a random numbert∈0,1nm which is used for PRE(4)
Computeexx∈0,1n(5)
ComputeH^Mexa,r,t∈0,1n+1m(6)
Sendcoma,r,t=H^Mexa,r,t′ as a commitment string comDecommitment phase fromS to R:S executes the following:(1)
S sends a,r∈0,1k/2×0,1k/2 and t∈0,1nm to R as a decommitment string decR executes the following:(1)
Computex=a‖r from dec.(2)
Computeexx.(3)
Compute the commitment stringH^Mexa,r,t and check whether H^Mexa,r,t=com. If this is satisfied, R outputs a. Otherwise, R outputs ⊥.Next, we prove the computational binding property and computational hiding property ofCommMexS,R. We first show the computational binding property.Theorem 4.
CommMexS,R satisfies the computational binding property under the M,δ-bSVP assumption.Proof.
We assume that there exists a probabilistic polynomial-time (PPT) adversary Adv that breaks the computational binding property of the commitment schemeCommMexS,R. Then, Adv can derive the following equation, with nonnegligible function ε′k from Definition 2.(17)PrAdv1k,M⟶com,dec,dec′∧dec≠dec′>ε′k.
From equation (17), com=H^Mexdec, and another PPT adversary Adv’, we can lead the following equation:(18)PrAdv′1k,M⟶dec,dec′∧H^Mexdec=H^Mexdec′∧dec≠dec′>ε′k.
This shows that if PPT Adv can break the computational binding property, it can also break the collision resistance ofH^Mex from equation (18). However, we showed that H^Mex has a collision resistance under the M,δ-bSVP assumption in Lemma 3. Therefore, the commitment scheme CommMexS,R satisfies the computational binding property under the M,δ-bSVP assumption based on the contradiction.
Next, we will prove the computational hiding property ofCommMexS,R.Theorem 5.
CommMexS,R satisfies the computational hiding property under the decisional M,d/4c-bSVP assumption for a constant c/d=n/k.Proof.
We assume that there exists a probabilistic polynomial-time adversary Adv that breaks the computational hiding property ofCommMexS,R. For some distinct a,a′∈0,1k/2, r,r′∈0,1k/2, t,t′∈0,1nm, and some nonnegligible function ε′, we can derive the following equation:(19)PrAdvM,H^Mexa‖r,t=1−PrAdvM,H^Mexa′‖r′,t′=1>ε′k.
Since the decoding procedureC of PRE is a polynomial-time algorithm, there exists a polynomial-time adversary Adv′, which is a composition of the decoding procedure and Adv such that(20)PrAdv′M,M⋅exa‖r=1−PrAdv′M,M⋅exa′‖r′=1>ε′k.
By the hybrid argument, for somea,(21)PrAdv′M,M⋅exa‖r=1−PrAdv′M,U=1>ε′k2.
Sincer is uniformly random over 0,1k/2, for every a∈0,1k/2, we have Δa‖r∈1/8,7/8, and hence, Δexa‖r∈d/8c,7d/8c for a constant c/d=n/k with probability 1−exp−Ωk from the Chernoff bounds. This contradicts the decisional M,δ-bSVP assumption.


## 4.4. Comparison

We compare our proposed commitment scheme with related works of [BDLOP18] and [KTX08] in Table1. Both [BDLOP18] and [KTX08] are also based on lattice-based functions and consist of “matrix-vector multiplication” in the same way as us.Table 1
Comparison of our proposed commitment scheme.
HidingBindingOutput locality[KTX08] [11]StatisticalSIS—[BDLOP18] [14]DKSSKS—[AHIKV17] [3]StatisticalbSVP4This paperD-bSVPbSVP3A commitment scheme [KTX08] can prove its hiding property statistically and its binding property by the SIS problem. However, it did not achieve constant output locality. A commitment scheme [BDLOP18] can prove its hiding property and binding property by DKS and SKS problems, respectively. Nevertheless, it also did not achieve constant output locality.On the contrary, the commitment scheme [AHIKV17] has achieved output locality-4 with its statistically hiding property and its binding property based on theM,δ-bSVP assumption (bSVP). However, their commitment scheme was to execute hash functions twice with a randomness extractor. It was also difficult to construct a commitment scheme with output locality-3 by using a randomness extractor.Our commitment schemeCommMexS,R satisfies output locality-3 by proving its hiding property and binding property by the decisional M,δ-bSVP assumption (D-bSVP) and M,δ-bSVP assumption (bSVP), respectively. Our commitment scheme only executes the hash function H^Mex once and does not use a randomness extractor.


## 5. Parameter Suggestion forCommMexS,R

This section suggests some parameter settings ofCommMexS,R under evaluation based on the short integer solution (SIS) problem in Definition 9.Definition 9 (SISq,m,b; see [11]).
Given a primeq, a positive number b, and a matrix MA∈ℤqn×m, the short integer solution SISq,m,b problem is to find a nonzero vector z∈ℤm such that Az≡0modq and z≤b.
LetM be a matrix in F2m×n. Under the condition of Δx≤δ, the M,δ-bSVP can be reduced to a SISq,m,b problem in the lattice spanned by vectors in KerM, where q=2 and b=n⋅δ, namely, to solve our scheme is reduced to find a short vector vv≤x in a lattice L=v∈ℤn:Mv=0mod2. Denote the norm of the shortest nonzero vector b1 in ML and the second shortest vector independent with b1 by λ1 and λ2, respectively. We estimate parameters as follows:(1)
Estimation ofδ:(a)
λ1L=x=n⋅δ.(b)
λ2L≈n/2πe⋅2m/n by Gaussian heuristic, where the volume of lattice ML is volL=2m and e is the mathematical constant.(c)
Denote byα=m/n and δ<α/2 because of the algebraic attack due to [3]. α shows the ratio between input length and output length.Therefore, we can get a bound ofδ≤0.07 and 0.14≤α by λ1/λ2<1.0 according to the definition of λ1 and λ2 above.(2)
Evaluate the asymptotic complexity to solve a SVP by using Alkim et al.’s estimate proposed in [15], and it had been experimentally verified in [16]. We heuristically set n=m/α, α=5⋅δ, and δ≤0.07. Then, we input the parameters of m,n,δ,q=2; Alkim et al.’s estimate can evaluate the minimal βBKZ which means the target block size used in the lattice reduction algorithm BKZ [17].
Please refer to [18] for a lucid explanation of Alkim et al.’s estimate. We consider the scenario that one hashes 128 bit information, namely, we fix m=128 in the estimate.
Table2 shows parameter suggestions of our scheme CommS,Rcom with respect to security levels of NIST AES-128, AES-192, and AES-256, where βBKZ is the required block size when using the BKZ algorithm to solve M,δ-bSVP. The security levels of “AES-128,” “AES-192,” and “AES-256” refer to three categories in the NIST PQC standardization project [19] in that the brute force attack on AES key search requires at least 2143, 2207, and 2272 classical computing gates, respectively.Table 2
Parameter suggestions form,n, and δ being used in our scheme CommS,Rcom.
Security levelmnδβBKZAES-1281284260.06376AES-1921287310.035601AES-25612810660.024837


## 6. Concluding Remarks

In this paper, we achieved the following:(i)
We proposed a new output locality-3 commitment scheme(ii)
We proved that theM,δ-bSVP assumption is reduced to the decisional M,δ-bSVP assumption(iii)
We proved that its computational binding property and computational hiding property are reduced to theM,δ-bSVP assumption and decisional M,δ-bSVP assumption, respectively(iv)
We evaluated a secure parameter set against the short integer solution (SIS) problemGenerally, it is easy to build protocols based on the decisionalM,δ-bSVP assumption compared with the M,δ-bSVP assumption. Therefore, our proof would shed light on the new construction of protocols whose security is based on the decisional M,δ-bSVP assumption. Also, our method can be used with IoT devices with small CPUs since our method satisfies constant output locality and can be achieved in smaller CPUs. However, it is expected to achieve an output locality-3 commitment scheme with statistical hiding, which is considered an open problem in this work.



---

*Source: 2949513-2021-11-29.xml*