Refine
Document Type
- Preprint (8)
- Article (1)
- Diploma Thesis (1)
- diplomthesis (1)
- Doctoral Thesis (1)
Has Fulltext
- yes (12)
Is part of the Bibliography
- no (12)
Keywords
- Kongress (5)
- Kryptologie (5)
- Online-Publikation (4)
- Commitment Scheme (2)
- Oblivious Transfer (2)
- San Jose (2)
- Blind Signature (1)
- Chinese Remainder Theorem (1)
- Commitment (1)
- Commitment schemes (1)
Institute
- Mathematik (11)
- Informatik (10)
We review the representation problem based on factoring and show that this problem gives rise to alternative solutions to a lot of cryptographic protocols in the literature. And, while the solutions so far usually either rely on the RSA problem or the intractability of factoring integers of a special form (e.g., Blum integers), the solutions here work with the most general factoring assumption. Protocols we discuss include identification schemes secure against parallel attacks, secure signatures, blind signatures and (non-malleable) commitments.
We present efficient non-malleable commitment schemes based on standard assumptions such as RSA and Discrete-Log, and under the condition that the network provides publicly available RSA or Discrete-Log parameters generated by a trusted party. Our protocols require only three rounds and a few modular exponentiations. We also discuss the difference between the notion of non-malleable commitment schemes used by Dolev, Dwork and Naor [DDN00] and the one given by Di Crescenzo, Ishai and Ostrovsky [DIO98].
Informally, commitment schemes can be described by lockable steely boxes. In the commitment phase, the sender puts a message into the box, locks the box and hands it over to the receiver. On one hand, the receiver does not learn anything about the message. On the other hand, the sender cannot change the message in the box anymore. In the decommitment phase the sender gives the receiver the key, and the receiver then opens the box and retrieves the message. One application of such schemes are digital auctions where each participant places his secret bid into a box and submits it to the auctioneer. In this thesis we investigate trapdoor commitment schemes. Following the abstract viewpoint of lockable boxes, a trapdoor commitment is a box with a tiny secret door. If someone knows the secret door, then this person is still able to change the committed message in the box, even after the commitment phase. Such trapdoors turn out to be very useful for the design of secure cryptographic protocols involving commitment schemes. In the first part of the thesis, we formally introduce trapdoor commitments and extend the notion to identity-based trapdoors, where trapdoors can only be used in connection with certain identities. We then recall the most popular constructions of ordinary trapdoor protocols and present new solutions for identity-based trapdoors. In the second part of the thesis, we show the usefulness of trapdoors in commitment schemes. Deploying trapdoors we construct efficient non-malleable commitment schemes which basically guarantee indepency of commitments. Furthermore, applying (identity-based) trapdoor commitments we secure well-known identification protocols against a new kind of attack. And finally, by means of trapdoors, we show how to construct composable commitment schemes that can be securely executed as subprotocols within complex protocols.
We introduce the relationship between incremental cryptography and memory checkers. We present an incremental message authentication scheme based on the XOR MACs which supports insertion, deletion and other single block operations. Our scheme takes only a constant number of pseudorandom function evaluations for each update step and produces smaller authentication codes than the tree scheme presented in [BGG95]. Furthermore, it is secure against message substitution attacks, where the adversary is allowed to tamper messages before update steps, making it applicable to virus protection. From this scheme we derive memory checkers for data structures based on lists. Conversely, we use a lower bound for memory checkers to show that so-called message substitution detecting schemes produce signatures or authentication codes with size proportional to the message length.
Der Begriff der editierfreundlichen Kryptographie wurde von Mihir Bellare, Oded Goldreich und Shafi Goldwasser 1994 bzw. 1995 eingeführt. Mit einem editierfreundlicher Verschlüsselungs- oder Unterschriftenverfahren kann man aus einer Verschlüsselung bzw. Unterschrift zu einer Nachricht schnell eine Verschlüsselung oder Unterschrift zu einer ähnlichen Nachricht erstellen. Wir geben eine Übersicht über die bekannten editierfreundlichen Verfahren und entwickeln sowohl ein symmetrisches als auch ein asymmetrisches editierfreundliches Unterschriftenverfahren (IncXMACC und IncHSig). Wir zeigen, wie man mit editierfreundlichen Schemata überprüfen kann, ob die Implementierung einer Datenstruktur korrekt arbeitet. Basierend auf den Ideen der editierfreundlichen Kryptographie entwickeln wir effiziente Verfahren für spezielle Datenstrukturen. Diese Ergebnisse sind in zwei Arbeiten [F97a, F97b] zusammengefaßt worden.
We show that non-interactive statistically-secret bit commitment cannot be constructed from arbitrary black-box one-to-one trapdoor functions and thus from general public-key cryptosystems. Reducing the problems of non-interactive crypto-computing, rerandomizable encryption, and non-interactive statistically-sender-private oblivious transfer and low-communication private information retrieval to such commitment schemes, it follows that these primitives are neither constructible from one-to-one trapdoor functions and public-key encryption in general. Furthermore, our separation sheds some light on statistical zeroknowledge proofs. There is an oracle relative to which one-to-one trapdoor functions and one-way permutations exist, while the class of promise problems with statistical zero-knowledge proofs collapses in P. This indicates that nontrivial problems with statistical zero-knowledge proofs require more than (trapdoor) one-wayness.
We show lower bounds for the signature size of incremental schemes which are secure against substitution attacks and support single block replacement. We prove that for documents of n blocks such schemes produce signatures of \Omega(n^(1/(2+c))) bits for any constant c>0. For schemes accessing only a single block resp. a constant number of blocks for each replacement this bound can be raised to \Omega(n) resp. \Omega(sqrt(n)). Additionally, we show that our technique yields a new lower bound for memory checkers.
Pseudorandom function tribe ensembles based on one-way permutations: improvements and applications
(1999)
Pseudorandom function tribe ensembles are pseudorandom function ensembles that have an additional collision resistance property: almost all functions have disjoint ranges. We present an alternative to the construction of pseudorandom function tribe ensembles based on oneway permutations given by Canetti, Micciancio and Reingold [CMR98]. Our approach yields two different but related solutions: One construction is somewhat theoretic, but conceptually simple and therefore gives an easier proof that one-way permutations suffice to construct pseudorandom function tribe ensembles. The other, slightly more complicated solution provides a practical construction; it starts with an arbitrary pseudorandom function ensemble and assimilates the one-way permutation to this ensemble. Therefore, the second solution inherits important characteristics of the underlying pseudorandom function ensemble: it is almost as effcient and if the starting pseudorandom function ensemble is efficiently invertible (given the secret key) then so is the derived tribe ensemble. We also show that the latter solution yields so-called committing private-key encryption schemes. i.e., where each ciphertext corresponds to exactly one plaintext independently of the choice of the secret key or the random bits used in the encryption process.
A memory checker for a data structure provides a method to check that the output of the data structure operations is consistent with the input even if the data is stored on some insecure medium. In [8] we present a general solution for all data structures that are based on insert(i,v) and delete(j) commands. In particular this includes stacks, queues, deques (double-ended queues) and lists. Here, we describe more time and space efficient solutions for stacks, queues and deques. Each algorithm takes only a single function evaluation of a pseudorandomlike function like DES or a collision-free hash function like MD5 or SHA for each push/pop resp. enqueue/dequeue command making our methods applicable to smart cards.
We propose a new security measure for commitment protocols, called Universally Composable (UC) Commitment. The measure guarantees that commitment protocols behave like an \ideal commitment service," even when concurrently composed with an arbitrary set of protocols. This is a strong guarantee: it implies that security is maintained even when an unbounded number of copies of the scheme are running concurrently, it implies non-malleability (not only with respect to other copies of the same protocol but even with respect to other protocols), it provides resilience to selective decommitment, and more. Unfortunately two-party uc commitment protocols do not exist in the plain model. However, we construct two-party uc commitment protocols, based on general complexity assumptions, in the common reference string model where all parties have access to a common string taken from a predetermined distribution. The protocols are non-interactive, in the sense that both the commitment and the opening phases consist of a single message from the committer to the receiver.
