Cryptography and algorithmic randomness

DOI10.1007/S00224-014-9545-9MaRDI QIDQ2354584zbMATH OpenOpenAlexFDO

Authors Kohtaro Tadaki, Norihisa Doi

Publication date 20 July 2015

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.2391

zbMATH Keywords

computable analysiscryptographyprovable securityrandom oracle modelalgorithmic randomnessgeneric group model

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Cryptography (94A60) Algorithmic randomness and dimension (03D32)

Abstract: The secure instantiation of the random oracle is one of the major open problems in modern cryptography. We investigate this problem using concepts and methods of algorithmic randomness. In modern cryptography, the random oracle model is widely used as an imaginary framework in which the security of a cryptographic scheme is discussed. In the random oracle model, the cryptographic hash function used in a cryptographic scheme is formulated as a random variable uniformly distributed over all possibility of the function, called the random oracle. The main result of this paper is to show that, for any secure signature scheme in the random oracle model, there exists a specific computable function which can instantiate the random oracle while keeping the security originally proved in the random oracle model. In modern cryptography the generic group model is used also for a similar purpose to the random oracle model. We show that the same results hold for the generic group model. In the process of proving the results, we introduce the notion of effective security, demonstrating the importance of this notion in modern cryptography.

Recommendations

• Deterministic random oracles
• The random oracle methodology, revisited.
• scientific article; zbMATH DE number 1775406
• A random oracle for all of us
• The theory of hash functions and random oracles. An approach to modern cryptography

Cites work

• scientific article; zbMATH DE number 42077 (Why is no real title available?)
• scientific article; zbMATH DE number 1303114 (Why is no real title available?)
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• scientific article; zbMATH DE number 4185033 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• A formal theory of inductive inference. Part I
• A unified approach to the definition of random sequences
• Adapting the Weaknesses of the Random Oracle Model to the Generic Group Model
• Advances in Cryptology - EUROCRYPT 2004
• Algorithmic Information Theory
• Algorithmic randomness and complexity.
• Computability and randomness
• Cryptography and Coding
• Foundations of Cryptography
• Foundations of Cryptography
• How Risky Is the Random-Oracle Model?
• Introduction to modern cryptography
• On initial segment complexity and degrees of randomness
• On the Length of Programs for Computing Finite Binary Sequences
• Process complexity and effective random tests
• Random oracles with(out) programmability
• Randomness and differentiability
• Solovay functions and \(K\)-triviality
• The definition of random sequences
• The random oracle methodology, revisited.

Cited in

(5)

• Random Sources for Cryptographic Systems
• Deterministic random oracles
• scientific article; zbMATH DE number 7528066 (Why is no real title available?)
• scientific article; zbMATH DE number 6536418 (Why is no real title available?)
• The theory of hash functions and random oracles. An approach to modern cryptography

This page was built for publication: Cryptography and algorithmic randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2354584)