Order-preserving encryption using the hypergeomatric probability distribution leaks about the half bits of a plaintext and the distance between two arbitrary plaintexts. To solve these problems, Popa et al. proposed a mutable order-preserving encoding. This is a keyless encoding scheme that adopts an order-preserving index locating the corresponding ciphertext via tree-based data structures. Unfortunately, it has the following shortcomings. First, the frequency of the ciphertexts reveals that of the plaintexts. Second, the indices are highly correlated to the corresponding plaintexts. For these reasons, statistical cryptanalysis may identify the encrypted fields using public information. To overcome these limitations, we propose a multi-tree approach to the mutable order-preserving encoding. The cost of interactions increases by the increased number of trees, but the proposed scheme mitigates the distribution leakage of plaintexts and also reduces the problematic correlation to plaintexts.
Seungkwang LEE
Dankook University
Nam-su JHO
ETRI
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Seungkwang LEE, Nam-su JHO, "A Multi-Tree Approach to Mutable Order-Preserving Encoding" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 11, pp. 1930-1933, November 2022, doi: 10.1587/transinf.2022NGL0008.
Abstract: Order-preserving encryption using the hypergeomatric probability distribution leaks about the half bits of a plaintext and the distance between two arbitrary plaintexts. To solve these problems, Popa et al. proposed a mutable order-preserving encoding. This is a keyless encoding scheme that adopts an order-preserving index locating the corresponding ciphertext via tree-based data structures. Unfortunately, it has the following shortcomings. First, the frequency of the ciphertexts reveals that of the plaintexts. Second, the indices are highly correlated to the corresponding plaintexts. For these reasons, statistical cryptanalysis may identify the encrypted fields using public information. To overcome these limitations, we propose a multi-tree approach to the mutable order-preserving encoding. The cost of interactions increases by the increased number of trees, but the proposed scheme mitigates the distribution leakage of plaintexts and also reduces the problematic correlation to plaintexts.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2022NGL0008/_p
Copy
@ARTICLE{e105-d_11_1930,
author={Seungkwang LEE, Nam-su JHO, },
journal={IEICE TRANSACTIONS on Information},
title={A Multi-Tree Approach to Mutable Order-Preserving Encoding},
year={2022},
volume={E105-D},
number={11},
pages={1930-1933},
abstract={Order-preserving encryption using the hypergeomatric probability distribution leaks about the half bits of a plaintext and the distance between two arbitrary plaintexts. To solve these problems, Popa et al. proposed a mutable order-preserving encoding. This is a keyless encoding scheme that adopts an order-preserving index locating the corresponding ciphertext via tree-based data structures. Unfortunately, it has the following shortcomings. First, the frequency of the ciphertexts reveals that of the plaintexts. Second, the indices are highly correlated to the corresponding plaintexts. For these reasons, statistical cryptanalysis may identify the encrypted fields using public information. To overcome these limitations, we propose a multi-tree approach to the mutable order-preserving encoding. The cost of interactions increases by the increased number of trees, but the proposed scheme mitigates the distribution leakage of plaintexts and also reduces the problematic correlation to plaintexts.},
keywords={},
doi={10.1587/transinf.2022NGL0008},
ISSN={1745-1361},
month={November},}
Copy
TY - JOUR
TI - A Multi-Tree Approach to Mutable Order-Preserving Encoding
T2 - IEICE TRANSACTIONS on Information
SP - 1930
EP - 1933
AU - Seungkwang LEE
AU - Nam-su JHO
PY - 2022
DO - 10.1587/transinf.2022NGL0008
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 11
JA - IEICE TRANSACTIONS on Information
Y1 - November 2022
AB - Order-preserving encryption using the hypergeomatric probability distribution leaks about the half bits of a plaintext and the distance between two arbitrary plaintexts. To solve these problems, Popa et al. proposed a mutable order-preserving encoding. This is a keyless encoding scheme that adopts an order-preserving index locating the corresponding ciphertext via tree-based data structures. Unfortunately, it has the following shortcomings. First, the frequency of the ciphertexts reveals that of the plaintexts. Second, the indices are highly correlated to the corresponding plaintexts. For these reasons, statistical cryptanalysis may identify the encrypted fields using public information. To overcome these limitations, we propose a multi-tree approach to the mutable order-preserving encoding. The cost of interactions increases by the increased number of trees, but the proposed scheme mitigates the distribution leakage of plaintexts and also reduces the problematic correlation to plaintexts.
ER -