2025/04/11 by Hideaki Miyaji, Atsuko Miyaji
Computer Science · #Cloud Data Security Solutions #Cryptography and Data Security #Cognitive Computing and Networks
paper · doi:10.1109/tit.2025.3559974
A blockchain is an important component in the design of secure distributed file systems, such as cryptocurrencies. One of the key components of the blockchain is the key-value commitment scheme, which constructs a commitment value from two inputs: a key and a value. In a conventional commitment scheme, a single user constructs a commitment value from an input value, whereas in a key-value commitment scheme, multiple users construct a commitment value from their keys and values. Both conventional and key-value commitment schemes must satisfy binding and hiding properties. The key-binding and key-hiding properties guarantee that neither the sender nor the verifier can act maliciously. The concept of a key-value commitment scheme was first proposed by Agrawal et al. in 2020 using a strong RSA assumption. Their scheme satisfies the key-binding but not key-hiding properties. In this paper, we propose two lattice-based key-value commitment schemes, Insert-KVC<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>m</i>/2,<i>n</i>,<i>q</i>,β</sub> and KVC<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>m</i>,<i>n</i>,<i>q</i>,β</sub>, that satisfy both the key-binding and the key-hiding properties. The key-binding property of both Insert-KVC<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>m</i>/2,<i>n</i>,<i>q</i>,β</sub> and KVC<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>m</i>,<i>n</i>,<i>q</i>,β</sub> are proven under the short integer solution (SIS<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∞</sup> <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>n</i>,<i>m</i>,<i>q</i>,β</sub>) problem. The key-hiding property of both Insert-KVC<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>m</i>/2,<i>n</i>,<i>q</i>,β</sub> and KVC<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>m</i>,<i>n</i>,<i>q</i>,β</sub> are proven under the Decisional-SIS<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∞</sup> <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>n</i>,<i>m</i>,<i>q</i>,β</sub>-form problem, which is newly defined in this paper. We demonstrate the difficulty of the Decisional-SIS∞ n,m,q,β-form problem by showing that the Decisional-SIS<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∞</sup> <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>n</i>,<i>m</i>,<i>q</i>,β</sub>-form problem is secure when the SIS∞ n,m,q,β problem is secure. Finally, we analyze the computational costs of Insert-KVC<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>m</i>/2,<i>n</i>,<i>q</i>,β</sub> and KVC<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>m</i>,<i>n</i>,<i>q</i>,β</sub>. Our method is the first lattice-based key-value commitment scheme with proven the key-binding and the key-hiding properties.