Crooked indifferentiability of enveloped XOR revisited

Rishiraj Bhattacharyya; Mridul Nandi; Anik Raychaudhuri

doi:10.1007/978-3-030-92518-5_4

Crooked indifferentiability of enveloped XOR revisited

Rishiraj Bhattacharyya^*, Mridul Nandi, Anik Raychaudhuri

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

56 Downloads (Pure)

Abstract

In CRYPTO 2018, Russell, Tang, Yung and Zhou (RTYZ) introduced the notion of crooked indifferentiability to analyze the security of a hash function when the underlying primitive is subverted. They showed that the n-bit to n-bit function implemented using enveloped XOR construction (EXor) with 3 n+ 1 many n-bit functions and 3 n² -bit random initial vectors can be proven secure asymptotically in the crooked indifferentiability setting. We identify several major issues and gaps in the proof by RTYZ, We argue that their proof can achieve security only in a restricted setting. We present a new proof of crooked indifferentiability where the adversary can evaluate queries related to multiple messages. Our technique can handle function-dependent subversion.

Original language	English
Title of host publication	Progress in Cryptology – INDOCRYPT 2021
Subtitle of host publication	22nd International Conference on Cryptology in India, Jaipur, India, December 12–15, 2021, Proceedings
Editors	Avishek Adhikari, Ralf Küsters, Bart Preneel
Publisher	Springer
Pages	73-92
Number of pages	20
Edition	1
ISBN (Electronic)	9783030925185
ISBN (Print)	9783030925178
DOIs	https://doi.org/10.1007/978-3-030-92518-5_4
Publication status	Published - 9 Dec 2021
Event	22nd International Conference on Cryptology in India, INDOCRYPT 2021 - Jaipur, India Duration: 12 Dec 2021 → 15 Dec 2021

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13143 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	22nd International Conference on Cryptology in India, INDOCRYPT 2021
Country/Territory	India
City	Jaipur
Period	12/12/21 → 15/12/21

Bibliographical note

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Keywords

Crooked indifferentiability
Enveloped XOR Hash
Simulator
Subverted random oracle

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-92518-5_4

BhattacharyyaR2021Crooked
This version of the contribution has been accepted for publication, after peer review (when applicable) but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/978-3-030-92518-5_4. Use of this Accepted Version is subject to the publisher’s Accepted Manuscript terms of use https://www.springernature.com/gp/open-research/policies/accepted-manuscript-terms
Accepted author manuscript, 452 KBLicence: Other (please specify with Rights Statement)

Cite this

Bhattacharyya, R., Nandi, M., & Raychaudhuri, A. (2021). Crooked indifferentiability of enveloped XOR revisited. In A. Adhikari, R. Küsters, & B. Preneel (Eds.), Progress in Cryptology – INDOCRYPT 2021: 22nd International Conference on Cryptology in India, Jaipur, India, December 12–15, 2021, Proceedings (1 ed., pp. 73-92). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13143 LNCS). Springer. https://doi.org/10.1007/978-3-030-92518-5_4

Bhattacharyya, Rishiraj ; Nandi, Mridul ; Raychaudhuri, Anik. / Crooked indifferentiability of enveloped XOR revisited. Progress in Cryptology – INDOCRYPT 2021: 22nd International Conference on Cryptology in India, Jaipur, India, December 12–15, 2021, Proceedings. editor / Avishek Adhikari ; Ralf Küsters ; Bart Preneel. 1. ed. Springer, 2021. pp. 73-92 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a45c4957cb3a422ea049c39f80a902ba,

title = "Crooked indifferentiability of enveloped XOR revisited",

abstract = "In CRYPTO 2018, Russell, Tang, Yung and Zhou (RTYZ) introduced the notion of crooked indifferentiability to analyze the security of a hash function when the underlying primitive is subverted. They showed that the n-bit to n-bit function implemented using enveloped XOR construction (EXor) with 3 n+ 1 many n-bit functions and 3 n2 -bit random initial vectors can be proven secure asymptotically in the crooked indifferentiability setting. We identify several major issues and gaps in the proof by RTYZ, We argue that their proof can achieve security only in a restricted setting. We present a new proof of crooked indifferentiability where the adversary can evaluate queries related to multiple messages. Our technique can handle function-dependent subversion.",

keywords = "Crooked indifferentiability, Enveloped XOR Hash, Simulator, Subverted random oracle",

author = "Rishiraj Bhattacharyya and Mridul Nandi and Anik Raychaudhuri",

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 22nd International Conference on Cryptology in India, INDOCRYPT 2021 ; Conference date: 12-12-2021 Through 15-12-2021",

year = "2021",

month = dec,

day = "9",

doi = "10.1007/978-3-030-92518-5_4",

language = "English",

isbn = "9783030925178",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "73--92",

editor = "Avishek Adhikari and Ralf K{\"u}sters and Bart Preneel",

booktitle = "Progress in Cryptology – INDOCRYPT 2021",

edition = "1",

}

Bhattacharyya, R, Nandi, M & Raychaudhuri, A 2021, Crooked indifferentiability of enveloped XOR revisited. in A Adhikari, R Küsters & B Preneel (eds), Progress in Cryptology – INDOCRYPT 2021: 22nd International Conference on Cryptology in India, Jaipur, India, December 12–15, 2021, Proceedings. 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13143 LNCS, Springer, pp. 73-92, 22nd International Conference on Cryptology in India, INDOCRYPT 2021, Jaipur, India, 12/12/21. https://doi.org/10.1007/978-3-030-92518-5_4

Crooked indifferentiability of enveloped XOR revisited. / Bhattacharyya, Rishiraj; Nandi, Mridul; Raychaudhuri, Anik.
Progress in Cryptology – INDOCRYPT 2021: 22nd International Conference on Cryptology in India, Jaipur, India, December 12–15, 2021, Proceedings. ed. / Avishek Adhikari; Ralf Küsters; Bart Preneel. 1. ed. Springer, 2021. p. 73-92 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13143 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Crooked indifferentiability of enveloped XOR revisited

AU - Bhattacharyya, Rishiraj

AU - Nandi, Mridul

AU - Raychaudhuri, Anik

PY - 2021/12/9

Y1 - 2021/12/9

N2 - In CRYPTO 2018, Russell, Tang, Yung and Zhou (RTYZ) introduced the notion of crooked indifferentiability to analyze the security of a hash function when the underlying primitive is subverted. They showed that the n-bit to n-bit function implemented using enveloped XOR construction (EXor) with 3 n+ 1 many n-bit functions and 3 n2 -bit random initial vectors can be proven secure asymptotically in the crooked indifferentiability setting. We identify several major issues and gaps in the proof by RTYZ, We argue that their proof can achieve security only in a restricted setting. We present a new proof of crooked indifferentiability where the adversary can evaluate queries related to multiple messages. Our technique can handle function-dependent subversion.

AB - In CRYPTO 2018, Russell, Tang, Yung and Zhou (RTYZ) introduced the notion of crooked indifferentiability to analyze the security of a hash function when the underlying primitive is subverted. They showed that the n-bit to n-bit function implemented using enveloped XOR construction (EXor) with 3 n+ 1 many n-bit functions and 3 n2 -bit random initial vectors can be proven secure asymptotically in the crooked indifferentiability setting. We identify several major issues and gaps in the proof by RTYZ, We argue that their proof can achieve security only in a restricted setting. We present a new proof of crooked indifferentiability where the adversary can evaluate queries related to multiple messages. Our technique can handle function-dependent subversion.

KW - Crooked indifferentiability

KW - Enveloped XOR Hash

KW - Simulator

KW - Subverted random oracle

UR - http://www.scopus.com/inward/record.url?scp=85121903031&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-92518-5_4

DO - 10.1007/978-3-030-92518-5_4

M3 - Conference contribution

AN - SCOPUS:85121903031

SN - 9783030925178

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 73

EP - 92

BT - Progress in Cryptology – INDOCRYPT 2021

A2 - Adhikari, Avishek

A2 - Küsters, Ralf

A2 - Preneel, Bart

PB - Springer

T2 - 22nd International Conference on Cryptology in India, INDOCRYPT 2021

Y2 - 12 December 2021 through 15 December 2021

ER -

Bhattacharyya R, Nandi M, Raychaudhuri A. Crooked indifferentiability of enveloped XOR revisited. In Adhikari A, Küsters R, Preneel B, editors, Progress in Cryptology – INDOCRYPT 2021: 22nd International Conference on Cryptology in India, Jaipur, India, December 12–15, 2021, Proceedings. 1 ed. Springer. 2021. p. 73-92. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-92518-5_4

Crooked indifferentiability of enveloped XOR revisited

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this