We introduce the k-payment problem: given a total budget of N units, the problem is to represent this budget as a set of coins, so that any k exact payments of total value at most N can be made using k disjoint subsets of the coins. The goal is to minimize the number of coins for any given N and k, while allowing the actual payments to be made on-line, namely without the need to know all payment requests in advance. The problem is motivated by the electronic cash model, where each coin is a long bit sequence, and typical electronic wallets have only limited storage capacity. The k-payment problem has additional applications in other resource-sharing scenarios. Our results include a complete characterization of the k-payment problem as follows. First, we prove a necessary and sufficient condition for a given set of coins to solve the problem. Using this characterization, we prove that the number of coins in any solution to the k-payment problem is at least k H N/k , where H n denotes the nth element in the harmonic series. This condition can also be used to efficiently determine k (the maximal number of exact payments) which a given set of coins allows in the worst case. Secondly, we give an algorithm which produces, for any N and k, a solution with a minimal number of coins. In the case that all denominations are available, the algorithm finds a coin allocation with at most (k+1)H N /(k+1) coins. (Both upper and lower bounds are the best possible.) Finally, we show how to generalize the algorithm to the case where some of the denominations are not available.

No abstract available.

Any system which contains some form of cryptographic authentication, confidentiality and/or identification requires the provisioning of a secure key generation and distribution capability. The key distribution mechanism for wireless cellular systems, such as IS-95 CDMA, IS-136 TDMA and IS-91 Analog, has recently been investigated by the Telephone Industry Association's standards working groups. There are several requirements that a cellular key provisioning system must satisfy; however, the current approaches for such generation and distribution are in general inadequate. As with any commercial application, the system must satisfy cost (e.g., efficiency by all parties, minimal specialized equipment, etc.), convenience and most of all security requirements. The cellular system requirements, however, are much more constraining than most environments since the customers' cellular phones have minimal computational capabilities and the authenticated setup protocol is generally performed with the user and carrier never meeting face to face. Moreover, the cellular phone companies are also insisting, for business competition needs, that the key distribution and generation mechanism is as convenient and transparent to the user (customer) as possible. We propose a cryptographically secure approach for such generation and distribution which will satisfy the phone industries' needs as well as the needs of other applications using slow devices.

In developing secure applications and systems, designers must often incorporate secure user identification in the design specification. In this paper, we study secure off-line authenticated user identification schemes based on a biometric system that can measure a user's biometrics accurately (up to some Hamming distance). The presented schemes enhance identification and authorization in secure applications by binding a biometric template with authorization information on a token such as a magnetic strip. Also developed are schemes specifically designed to minimize the compromising of a user's private biometrics data, encapsulated in the authorization information, without requiring secure hardware tokens. We also study the feasibility of biometrics performing as an enabling technology for secure systems and applications design. We investigate a new technology which allows a user's biometrics to facilitate cryptographic mechanisms.

The invention provides for robust efficient distributed generation of RSA keys. An efficient protocol is one which is independent of the primality test “circuit size”, while a robust protocol allows correct completion even in the presence of a minority of arbitrarily misbehaving malicious parties. The disclosed protocol is secure against any minority of malicious parties (which is optimal). The disclosed method is useful in establishing sensitive distributed cryptographic function sharing services (certification authorities, signature schemes with distributed trust, and key escrow authorities), as well as other applications besides RSA (namely: composite ElGamal, identification schemes, simultaneous bit exchange, etc.). The disclosed method can be combined with proactive function sharing techniques to establish the first efficient, optimal-resilience, robust and proactively-secure RSA-based distributed trust services where the key is never entrusted to a single entity (i.e., distributed trust totally “from scratch”). The disclosed method involves new efficient “robustness assurance techniques” which guarantee “correct computations” by mutually distrusting parties with malicious minority.

We introduce new efficient techniques for sharing cryptographic functions in a distributed dynamic fashion. These techniques dynamically and securely transform a distributed function (or secret sharing) representation between t-out-of-l (polynomial sharing) and t-out-of-t (additive sharing). We call the techniques poly-to-sum and sum-to-poly, respectively. Employing these techniques, we solve a number of open problems in the area of cryptographic function sharing. We design a threshold function sharing scheme with proactive security for general functions with a "homomorphic property" (a class which includes all RSA variants and Discrete logarithm variants). The sharing has "optimal resilience" (server redundancy) and enables computation of the function by the servers assuring high availability, security and efficiency. Proactive security enables function sharing among servers while tolerating an adversary which is mobile and which dynamically corrupts and abandons servers (and perhaps visits all of them over the lifetime of the system, as long as the number of corruptions (faults) is bounded within a time period). Optimal resilience assures that the adversary can corrupt any minority of servers at any time-period.

No abstract available.

We suggest a new methodology for "result checking" that enables us to extend the notion of Blum's program result checking to the on-line checking of cryptographic functions. In our model, the checker not only needs to be assured of the correctness of the result but the owner of the program needs to be sure not to give away anything but the requested result on the (authorized) input. The existing approaches for program result checking of numerical problems often ask the program a number of extra queries (different from the actual input). In the case of cryptographic functions, this may be in contradiction with the security requirement of the program owner. Additional queries, in fact, may be used to gain unauthorized advantage (for example, imagine the implications of the on-line checking of a decryption device that requires the decryption of extra ciphertexts). In [Blum88], the notion of a simple checker was introduced where, for the purpose of efficiency, extra queries are not allowed...

Article Free Access Share on How to share a function securely Authors: Alfredo De Santis Dip. di Informatica ed Applicazioni Università di Salerno, Baronissi (SA), Italy Dip. di Informatica ed Applicazioni Università di Salerno, Baronissi (SA), ItalyView Profile , Yvo Desmedt Dept. of EE&CS, Univ. of Wisconsin Milwaukee, WI Dept. of EE&CS, Univ. of Wisconsin Milwaukee, WIView Profile , Yair Frankel GTE Laboratories Incorporated, Waltham, MA GTE Laboratories Incorporated, Waltham, MAView Profile , Moti Yung IBM T. J. Watson Research Center, Yorktown Heights, NY IBM T. J. Watson Research Center, Yorktown Heights, NYView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 522–533https://doi.org/10.1145/195058.195405Published:23 May 1994Publication History 193citation1,775DownloadsMetricsTotal Citations193Total Downloads1,775Last 12 Months169Last 6 weeks18 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A threshold scheme is an algorithm in which a distributor creates l shares of a secret such that a fixed minimum number $( t )$ of shares are needed to regenerate the secret. A perfect threshold scheme does not reveal anything new from an information theoretical viewpoint to $t - 1$ shareholders about the secret. When the entropy of the secret is zero all sharing schemes are perfect, so perfect sharing loses its intuitive meaning. The concept of zero-knowledge sharing scheme is introduced to prove that the distributor does not reveal anything, even from a computational viewpoint. New homomorphic perfect secret threshold schemes over any finite Abelian group for which the group operation and inverses are computable in polynomial time are developed. One of the new threshold schemes also satisfies the zero-knowledge property. A generalization toward a homomorphic zero-knowledge general sharing scheme over any finite Abelian group is discussed and it is proven that ideal homomorphic threshold schemes do not always exist.

The authors extend the use of traditional point-to-point message authentication to multireceiver and/or multisender scenarios. They provide efficient cryptographic authentication methods for point-to-multipoint communication, where a single sender can broadcast (multicast) only one unconditionally secure authenticator for a message and which all receivers can verify. They further develop multipoint-to-point communication (incast) in which any subset (of a specified size) of a group of individuals can transmit a single authenticator (or a signature) for a message using the group's key. This method has been called threshold authentication. It is an application layer that is transparent to the receiver which only deals with the group as one entity. The bandwidth, computations, and storage overheads are reduced substantially when compared with the traditional approach. Threshold authentication hides some aspects of the internal structure of the group, which may be important in interenterprise communication.>