Change search
ReferencesLink to record
Permanent link

Direct link
On the impossibility of cryptography with tamperable randomness
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0001-8217-0158
Show others and affiliations
2014 (English)In: 34rd Annual International Cryptology Conference, CRYPTO 2014, 2014, no PART 1, 462-479 p.Conference paper (Refereed)
Abstract [en]

We initiate a study of the security of cryptographic primitives in the presence of efficient tampering attacks to the randomness of honest parties. More precisely, we consider p-tampering attackers that may efficiently tamper with each bit of the honest parties' random tape with probability p, but have to do so in an "online" fashion. Our main result is a strong negative result: We show that any secure encryption scheme, bit commitment scheme, or zero-knowledge protocol can be "broken" with probability p by a p-tampering attacker.The core of this result is a new Fourier analytic technique for biasing the output of bounded-value functions, which may be of independent interest. We also show that this result cannot be extended to primitives such as signature schemes and identification protocols: assuming the existence of one-way functions, such primitives can be made resilient to (1/poly(n))- tampering attacks where n is the security parameter.

Place, publisher, year, edition, pages
2014. no PART 1, 462-479 p.
Keyword [en]
Encryption, Randomness, Tampering, Random processes, Analytic technique, Cryptographic primitives, Encryption schemes, Identification protocol, Security parameters, Zero-knowledge protocols, Cryptography
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
URN: urn:nbn:se:kth:diva-167864DOI: 10.1007/978-3-662-44371-2_26ScopusID: 2-s2.0-84905380508ISBN: 9783662443705OAI: diva2:821243
17 August 2014 through 21 August 2014, Santa Barbara, CA

QC 20150615

Available from: 2015-06-15 Created: 2015-05-22 Last updated: 2015-06-15Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Austrin, Per
By organisation
Theoretical Computer Science, TCS
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle ScholarTotal: 1 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 116 hits
ReferencesLink to record
Permanent link

Direct link