One-Way Functions Using Algorithmic and Classical Information Theories

被引：0
作者：
Luís Antunes
Armando Matos
Alexandre Pinto
André Souto
Andreia Teixeira
机构：
[1] Faculdade de Ciências da Universidade do Porto,Computer Science Department
[2] Instituto de Telecomunicações,Security and Quantum Information Group
[3] Laboratório de Inteligência Artificial e Ciências de Computadores,HASLab
[4] Instituto Superior da Maia,Mathematical Department
[5] Instituto de Engenharia de Sistemas e Computadores,undefined
[6] Instituto Superior Técnico da Universidade Técnica de Lisboa,undefined
来源：
Theory of Computing Systems | 2013年 / 52卷
关键词：
Kolmogorov complexity; One-way functions; Symmetry of information; Yao entropy;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We prove several results relating injective one-way functions, time-bounded conditional Kolmogorov complexity, and time-bounded conditional entropy.
引用
收藏
页码：162 / 178
页数：16
相关论文
共 20 条
  • [1] Blum M.(1984)How to generate cryptographically strong sequences of pseudo-random bits SIAM J. Comput. 13 850-864
  • [2] Micali S.(1966)On the length of programs for computing finite binary sequences J. ACM 13 547-569
  • [3] Chaitin G.(1988)A digital signature scheme secure against adaptive chosen-message attacks SIAM J. Comput. 17 281-308
  • [4] Goldwasser S.(2009)Some properties of Renyi entropy and Renyi entropy rate Inf. Sci. 179 2426-2433
  • [5] Micali S.(2004)The world according to Renyi: thermodynamics of multifractal systems Ann. Phys. 312 17-7
  • [6] Rivest R.(1965)Three approaches to the quantitative definition of information Probl. Inf. Transm. 1 1-100
  • [7] Golshani L.(1993)Symmetry of information and one-way functions Inf. Process. Lett. 46 95-22
  • [8] Pasha E.(1995)On symmetry of information and polynomial time invertibility Inf. Comput. 121 14-962
  • [9] Yari G.(2009)Comparing notions of computational entropy Theory Comput. Syst. 45 944-22
  • [10] Jizba P.(1964)A formal theory of inductive inference, part I Inf. Control 7 1-124
12