Secure and efficient off-line digital money (extended abstract)
Lecture notes in computer sciencePublished 1 January 1993
Matthew Franklin, Moti Yung
Citations85
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that off-line coin schemes can be implemented securely and efficiently, where security is proven based on the hardness of the discrete log function and a pre-processing stage, and where efficiency is in a new sense.
Abstract
No off-line electronic coin scheme has yet been proposed which is both provably secure with respect to natural cryptographic assumptions and efficient with respect to reasonable measures. We show that off-line coin schemes can be implemented securely and efficiently, where security is proven based on the hardness of the discrete log function and a pre-processing stage, and where efficiency is in a new sense that we put forth in this work: "a protocol is efficient if its communication complexity is independent of the computational complexity of its participants" (and thus the communication length and number of encryption operations is only a low-degree polynomial of the input).
Keywords
Computer Science
IEEE Transactions on Information TheoryNew directions in cryptography
14,441 Citations1976Whitfield Diffie, Martin E. Hellman
Communications of the ACMA method for obtaining digital signatures and public-key cryptosystems
13,142 Citations1983Ronald L. Rivest, Adi Shamir +1 more
Communications of the ACMA method for obtaining digital signatures and public-key cryptosystems
13,083 Citations1978Ronald L. Rivest, Adi Shamir +1 more
An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key, soriers or other secure means are not needed to transmit keys.
How to generate and exchange secrets
3,712 Citations1986Andrew Chi-Chih Yao
It is shown how two parties A and B can interactively generate a random integer N = p¿q such that its secret, i.e., the prime factors, is hidden from either party individually but is recoverable jointly if desired.
SIAM Journal on ComputingThe Knowledge Complexity of Interactive Proof Systems
3,186 Citations1989Shafi Goldwasser, Silvio Micali +1 more
A computational complexity theory of the “knowledge” contained in a proof is developed and examples of zero-knowledge proof systems are given for the languages of quadratic residuosity and 'quadratic nonresiduosity.
Communications of the ACMSecurity without identification: transaction systems to make big brother obsolete
1,650 Citations1985David Chaum
The large-scale automated transaction systems of the near future can be designed to protect the privacy and maintain the security of both individuals and organizations.
SIAM Journal on ComputingHow to Generate Cryptographically Strong Sequences of Pseudorandom Bits
1,323 Citations1984Manuel Blum, Silvio Micali
A hard-core predicate for all one-way functions
1,196 Citations1989Oded Goldreich, Leonid A. Levin
This paper proves a conjecture of [Levin 87, sec. 5.6.2] that the scalar product of Boolean vectors p, g, x is a hard-core of every one-way function ƒ, and extends to multiple (up to the logarithm of security) such bits and to any distribution on the x.
Lecture notes in computer scienceUntraceable Electronic Cash
1,109 Citations1990David Chaum, Amos Fiat +1 more
An electronic cash protocol including the steps of using a one-way function f1 to generate an image f1 (x1) from a preimage x1 and receiving from the second party a note including a digital signature.
Journal of CryptologyZero-knowledge proofs of identity
1,034 Citations1988Uriel Feige, Amos Fiat +1 more
This paper defines the definition of unrestricted input zero- knowledge proofs of knowledge in which the prover demonstrates possession of knowledge without revealing any computational information whatsoever (not even the one bit revealed in zero-knowledge proofs of assertions).
Universal one-way hash functions and their cryptographic applications
964 Citations1989Moni Naor, Moti Yung
A Universal One-Way Hash Function family is defined, a new primitive which enables the compression of elements in the function domain and it is proved constructively that universal one- way hash functions exist if any 1-1 one-way functions exist.
Pseudo-random generation from one-way functions
710 Citations1989Russell Impagliazzo, Leonid A. Levin +1 more
From one-way functions of type (1) or (2) it is shown how to construct pseudo-random generators secure against small circuits or fast algorithms, respectively, and vice-versa.
One-way functions are necessary and sufficient for secure signatures
692 Citations1990John Rompel
This paper is interested in signature schemes which are secure agMnst existential forgery under adaptive chosen message attacks, and the existence of trapdoor permutations can be shown to be necessary and sufficient for secure encryption schemes.
Proofs that yield nothing but their validity and a methodology of cryptographic protocol design
544 Citations1986Oded Goldreich, Silvio Micali +1 more
This paper demonstrates the generality and wide applicability of zero-knowledge proofs, a notion introduced by Goldwasser, Micali and Rackoff that efficiently demonstrate membership in the language without conveying any additional knowledge.
One-way functions are essential for complexity based cryptography
341 Citations1989Russell Impagliazzo, Michael Luby
It is shown that many of the standard cryptographic tasks are equivalent to the usual definition of a one-way function, and thus the security of any proposed protocol for these tasks is implicitly based on a function being 'one-way.
Lecture notes in computer scienceUniversal Electronic Cash
306 Citations2007Tatsuaki Okamoto, Kazuo Ohta
The main advantage of the new system is that the customer can subdivide his cash balance into many pieces in any way he pleases until the total value of all subdivided piece equals C.
SIAM Journal on ComputingNoninteractive Zero-Knowledge
285 Citations1991Manuel Blum, Alfredo De Santis +2 more
If deciding quadratic residuosity (modulo composite integers whose factorization is not known) is computationally hard, it is shown that the NP-complete language of satisfiability also possesses noninteractive zero-knowledge proofs.
Lecture notes in computer scienceOn-Line/Off-Line Digital Signatures
238 Citations2007Shimon Even, Oded Goldreich +1 more
A general construction which transforms any (ordinary) digital signature scheme to an on-line/off-line signature scheme is presented, entailing a small overhead, and allows us to prove that the existence of signature schemes which are unforgeable by known message attack is a (necessary and) sufficient condition for the existence.
Lecture notes in computer sciencePayment Systems and Credential Mechanisms with Provable Security Against Abuse by Individuals
148 Citations1990Ivan Damgård
This work presents constructions for which it can be proved, that no individual can cheat successfully, unless he possesses an algorithm that contradicts a single plausible intractability assumption.
Lecture notes in computer scienceDisposable Zero-Knowledge Authentications and Their Applications to Untraceable Electronic Cash
118 Citations2007Tatsuaki Okamoto, Kazuo Ohta
A new untraceable electronic cash scheme satisfying both untraceability and unreusablity is proposed, which overcomes the problems of the previous scheme proposed by Chaum, Fiat and Naor through its greater efficiency and provable security under reasonable cryptographic assumptions.
Pseudo-random generators under uniform assumptions
118 Citations1990Johan Håstad
The main result of this paper is to indeed prove that oneway functions in the uniform model imply uniformly secure generators.
Choice Reviews OnlineUses of randomness in algorithms and protocols
86 Citations1991Joe Kilian
The Goldwasser-Kilian algorithm is the first to yield a polynomial size proof of its assertions, ensuring correctness while still provably running fast on most inputs, and this new primality test implies for the first time and without any assumptions that large certified primes can be generated in expectedPolynomial time under a distribution that is close to uniform.
SIAM Journal on ComputingThe Discrete Logarithm Hides $O(\log n)$ Bits
69 Citations1988Douglas L. Long, Avi Wigderson
It is shown that obtaining any information about the “most significant” bits of x, given $g^x (\bmod p)$, is equivalent to computing discrete logarithms $\b mod p$.
Lecture notes in computer scienceHow to Break and Repair a “Provably Secure” Untraceable Payment System
60 Citations2007Birgit Pfitzmann, Michael Waidner
This work shows how to break the untraceability of that untraceable payment system with provable security against abuse by individuals, and presents a similar construction for unt traceable electronic cash.
Electronic Wallet
30 Citations1984Shimon Even, Oded Goldreich +1 more
Lecture notes in computer scienceCommunication efficient Zero-knowledge Proofs of knowledge
20 Citations1992Alfredo De Santis, Giuseppe Persiano
It is shown that, after a constant-round preprocessing stage, it is possible to give any polynomial number of Non-Interactive Zero-Knowledge Proofs of Knowledge for any NP language.
Lecture notes in computer scienceMaking Electronic Refunds Safer
16 Citations2007Rafael Hirschfeld
It is shown how to break an electronic cash protocol due to van Antwerpen, and an alternative protocol is given that fixes the problem.