SCIENCE@home

Lattice-Based Key-Value Commitment Scheme

Hideaki Miyaji,Atsuko Miyaji

Published 2025 in IEEE Transactions on Information Theory

ABSTRACT

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, <inline-formula> <tex-math notation="LaTeX">${\mathsf { Insert}}\text {-}{\mathsf { KVC}}_{m/2,n,q,\beta }$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">${\mathsf {\text {KVC}}}_{m,n,q,\beta }$ </tex-math></inline-formula>, that satisfy both the key-binding and the key-hiding properties. The key-binding property of both <inline-formula> <tex-math notation="LaTeX">${\mathsf { Insert}}\text {-}{\mathsf { KVC}}_{m/2,n,q,\beta }$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">${\mathsf {\text {KVC}}}_{m,n,q,\beta }$ </tex-math></inline-formula> are proven under the short integer solution (<inline-formula> <tex-math notation="LaTeX">${\mathsf {\text {SIS}}}^{\infty } _{n,m,q,\beta }$ </tex-math></inline-formula>) problem. The key-hiding property of both <inline-formula> <tex-math notation="LaTeX">${\mathsf { Insert}}\text {-}{\mathsf { KVC}}_{m/2,n,q,\beta }$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">${\mathsf {\text {KVC}}}_{m,n,q,\beta }$ </tex-math></inline-formula> are proven under the Decisional-<inline-formula> <tex-math notation="LaTeX">${\mathsf {\text {SIS}}}^{\infty } _{n,m,q,\beta }$ </tex-math></inline-formula>-form problem, which is newly defined in this paper. We demonstrate the difficulty of the Decisional-<inline-formula> <tex-math notation="LaTeX">${\mathsf {\text {SIS}}}^{\infty } _{n,m,q,\beta }$ </tex-math></inline-formula>-form problem by showing that the Decisional-<inline-formula> <tex-math notation="LaTeX">${\mathsf {\text {SIS}}}^{\infty } _{n,m,q,\beta }$ </tex-math></inline-formula>-form problem is secure when the <inline-formula> <tex-math notation="LaTeX">${\mathsf {\text {SIS}}}^{\infty } _{n,m,q,\beta }$ </tex-math></inline-formula> problem is secure. Finally, we analyze the computational costs of <inline-formula> <tex-math notation="LaTeX">${\mathsf { Insert}}\text {-}{\mathsf { KVC}}_{m/2,n,q,\beta }$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">${\mathsf {\text {KVC}}}_{m,n,q,\beta }$ </tex-math></inline-formula>. Our method is the first lattice-based key-value commitment scheme with proven the key-binding and the key-hiding properties.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-42 of 42 references · Page 1 of 1

CITED BY