Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions
type: Item
instance of: scholarly article
title: Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions
zbMATH Open document ID: 1146.68036
author: Jörg Rothe
author: Amitabh Saxena
author: Lane A. Hemaspaandra
published in: Theoretical Computer Science
publication date: 2008-07-31T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 5306527
zbMATH Keywords: computational complexity
zbMATH Keywords: worst-case one-way functions
zbMATH Keywords: associativity
zbMATH Keywords: commutativity
zbMATH Keywords: strong noninvertibility
MaRDI profile type: Publication
full work available at URL: j.tcs.2008.03.014
OpenAlex ID: W2082976544
cites work: P-Printable Sets
cites work: Q3692867
cites work: Q4293543
cites work: A note on the complexity of cryptography (Corresp.)
cites work: Inverting onto functions.
cites work: Foundations of Cryptography
cites work: Complexity Measures for Public-Key Cryptosystems
cites work: One-way functions and the nonisomorphism of NP-complete sets
cites work: The complexity theory companion
cites work: If P \(\neq\) NP then some strongly noninvertible functions are invertible
cites work: Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory
cites work: Characterizing the existence of one-way permutations
cites work: Theoretical Computer Science
cites work: Tight lower bounds on the ambiguity of strong, total, associative, one-way functions
cites work: One-way permutations and self-witnessing languages
cites work: Q5812175
cites work: On some natural complete operators
cites work: An observation on associative one-way functions in complexity theory
cites work: On characterizing the existence of partial one-way permutations
cites work: A survey of one-way functions in complexity theory
cites work: Relative complexity of checking and evaluating
cites work: On hardness of one-way functions
cites work: Q4205082
DOI: 10.1016/J.TCS.2008.03.014
description: scientific article; zbMATH DE number 5306527