Cryptography and algorithmic randomness

DOI10.1007/S00224-014-9545-9zbMATH Open1397.94100arXiv1305.2391OpenAlexW2082393816MaRDI QIDQ2354584FDOQ2354584

Authors: Kohtaro Tadaki, Norihisa Doi 

Publication date: 20 July 2015

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

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.

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

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

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)

Cites Work

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

Cited In (5)

• Deterministic random oracles
• Random Sources for Cryptographic Systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)