Skip to main content
main-content

Inhaltsverzeichnis

Frontmatter

Encryption I

Simple and Efficient Public-Key Encryption from Computational Diffie-Hellman in the Standard Model

Abstract
This paper proposes practical chosen-ciphertext secure public-key encryption systems that are provably secure under the computational Diffie-Hellman assumption, in the standard model. Our schemes are conceptually simpler and more efficient than previous constructions. We also show that in bilinear groups the size of the public-key can be shrunk from n to \(2\sqrt{n}\) group elements, where n is the security parameter.
Kristiyan Haralambiev, Tibor Jager, Eike Kiltz, Victor Shoup

Constant Size Ciphertexts in Threshold Attribute-Based Encryption

Abstract
Attribute-based cryptography has emerged in the last years as a promising primitive for digital security. For instance, it provides good solutions to the problem of anonymous access control. In a ciphertext-policy attribute-based encryption scheme, the secret keys of the users depend on their attributes. When encrypting a message, the sender chooses which subset of attributes must be held by a receiver in order to be able to decrypt.
All current attribute-based encryption schemes that admit reasonably expressive decryption policies produce ciphertexts whose size depends at least linearly on the number of attributes involved in the policy. In this paper we propose the first scheme whose ciphertexts have constant size. Our scheme works for the threshold case: users authorized to decrypt are those who hold at least t attributes among a certain universe of attributes, for some threshold t chosen by the sender. An extension to the case of weighted threshold decryption policies is possible. The security of the scheme against selective chosen plaintext attacks can be proven in the standard model by reduction to the augmented multi-sequence of exponents decisional Diffie-Hellman (aMSE-DDH) problem.
Javier Herranz, Fabien Laguillaumie, Carla Ràfols

Cryptanalysis

Algebraic Cryptanalysis of the PKC’2009 Algebraic Surface Cryptosystem

Abstract
In this paper, we fully break the Algebraic Surface Cryptosystem (ASC for short) proposed at PKC’2009 [3]. This system is based on an unusual problem in multivariate cryptography: the Section Finding Problem. Given an algebraic surface \(X(x,y,t)\in\mathbb{F}_p[x,y,t]\) such that \(\deg_{xy} X(x,y,t)= w\), the question is to find a pair of polynomials of degree d, u x (t) and u y (t), such that X(u x (t),u y (t),t) = 0. In ASC, the public key is the surface, and the secret key is the section. This asymmetric encryption scheme enjoys reasonable sizes of the keys: for recommended parameters, the size of the secret key is only 102 bits and the size of the public key is 500 bits. In this paper, we propose a message recovery attack whose complexity is quasi-linear in the size of the secret key. The main idea of this algebraic attack is to decompose ideals deduced from the ciphertext in order to avoid to solve the section finding problem. Experimental results show that we can break the cipher for recommended parameters (the security level is 2102) in 0.05 seconds. Furthermore, the attack still applies even when the secret key is very large (more than 10000 bits). The complexity of the attack is \(\widetilde{\mathcal{O}}(w^{7} d \log(p))\) which is polynomial with respect to all security parameters. In particular, it is quasi-linear in the size of the secret key which is (2 d + 2) log(p). This result is rather surprising since the algebraic attack is often more efficient than the legal decryption algorithm.
Jean-Charles Faugère, Pierre-Jean Spaenlehauer

Maximizing Small Root Bounds by Linearization and Applications to Small Secret Exponent RSA

Abstract
We present an elementary method to construct optimized lattices that are used for finding small roots of polynomial equations. Former methods first construct some large lattice in a generic way from a polynomial f and then optimize via finding suitable smaller dimensional sublattices. In contrast, our method focuses on optimizing f first which then directly leads to an optimized small dimensional lattice.
Using our method, we construct the first elementary proof of the Boneh-Durfee attack for small RSA secret exponents with d ≤ N 0.292. Moreover, we identify a sublattice structure behind the Jochemsz-May attack for small CRT-RSA exponents \(d_p, d_q \leq N^{0.073}\). Unfortunately, in contrast to the Boneh-Durfee attack, for the Jochemsz-May attack the sublattice does not help to improve the bound asymptotically. Instead, we are able to attack much larger values of d p ,d q in practice by LLL reducing smaller dimensional lattices.
Mathias Herrmann, Alexander May

Implicit Factoring with Shared Most Significant and Middle Bits

Abstract
We study the problem of integer factoring given implicit information of a special kind. The problem is as follows: let N 1 = p 1 q 1 and N 2 = p 2 q 2 be two RSA moduli of same bit-size, where q 1, q 2 are α-bit primes. We are given the implicit information that p 1 and p 2 share t most significant bits. We present a novel and rigorous lattice-based method that leads to the factorization of N 1 and N 2 in polynomial time as soon as t ≥ 2 α + 3. Subsequently, we heuristically generalize the method to k RSA moduli N i  = p i q i where the p i ’s all share t most significant bits (MSBs) and obtain an improved bound on t that converges to t ≥ α + 3.55... as k tends to infinity. We study also the case where the k factors p i ’s share t contiguous bits in the middle and find a bound that converges to 2α + 3 when k tends to infinity. This paper extends the work of May and Ritzenhofen in [9], where similar results were obtained when the p i ’s share least significant bits (LSBs). In [15], Sarkar and Maitra describe an alternative but heuristic method for only two RSA moduli, when the p i ’s share LSBs and/or MSBs, or bits in the middle. In the case of shared MSBs or bits in the middle and two RSA moduli, they get better experimental results in some cases, but we use much lower (at least 23 times lower) lattice dimensions and so we obtain a great speedup (at least 103 faster). Our results rely on the following surprisingly simple algebraic relation in which the shared MSBs of p 1 and p 2 cancel out: q 1 N 2 − q 2 N 1 = q 1 q 2 (p 2 − p 1). This relation allows us to build a lattice whose shortest vector yields the factorization of the N i ’s.
Jean-Charles Faugère, Raphaël Marinier, Guénaël Renault

Protocols I

On the Feasibility of Consistent Computations

Abstract
In many practical settings, participants are willing to deviate from the protocol only if they remain undetected. Aumann and Lindell introduced a concept of covert adversaries to formalize this type of corruption. In the current paper, we refine their model to get stronger security guarantees. Namely, we show how to construct protocols, where malicious participants cannot learn anything beyond their intended outputs and honest participants can detect malicious behavior that alters their outputs. As this construction does not protect honest parties from selective protocol failures, a valid corruption complaint can leak a single bit of information about the inputs of honest parties. Importantly, it is often up to the honest party to decide whether to complain or not. This potential leakage is often compensated by gains in efficiency—many standard zero-knowledge proof steps can be omitted. As a concrete practical contribution, we show how to implement consistent versions of several important cryptographic protocols such as oblivious transfer, conditional disclosure of secrets and private inference control.
Sven Laur, Helger Lipmaa

Multi-query Computationally-Private Information Retrieval with Constant Communication Rate

Abstract
A fundamental privacy problem in the client-server setting is the retrieval of a record from a database maintained by a server so that the computationally bounded server remains oblivious to the index of the record retrieved while the overall communication between the two parties is smaller than the database size. This problem has been extensively studied and is known as computationally private information retrieval (CPIR). In this work we consider a natural extension of this problem: a multi-query CPIR protocol allows a client to extract m records of a database containing n ℓ-bit records. We give an information-theoretic lower bound on the communication of any multi-query information retrieval protocol. We then design an efficient non-trivial multi-query CPIR protocol that matches this lower bound. This means we settle the multi-query CPIR problem optimally up to a constant factor.
Jens Groth, Aggelos Kiayias, Helger Lipmaa

Further Observations on Optimistic Fair Exchange Protocols in the Multi-user Setting

Abstract
Recent research has shown that the single-user security of optimistic fair exchange cannot guarantee the multi-user security. This paper investigates the conditions under which the security of optimistic fair exchange in the single-user setting is preserved in the multi-user setting. We first introduce and define a property called “Strong Resolution-Ambiguity”. Then we prove that in the certified-key model, an optimistic fair exchange protocol is secure in the multi-user setting if it is secure in the single-user setting and has the property of strong resolution-ambiguity. Finally we provide a new construction of optimistic fair exchange with strong resolution-ambiguity. The new protocol is setup-free, stand-alone and multi-user secure without random oracles.
Xinyi Huang, Yi Mu, Willy Susilo, Wei Wu, Yang Xiang

Network Coding

Secure Network Coding over the Integers

Abstract
Network coding offers the potential to increase throughput and improve robustness without any centralized control. Unfortunately, network coding is highly susceptible to “pollution attacks” in which malicious nodes modify packets improperly so as to prevent message recovery at the recipient(s); such attacks cannot be prevented using standard end-to-end cryptographic authentication because network coding mandates that intermediate nodes modify data packets in transit.
Specialized “network coding signatures” addressing this problem have been developed in recent years using homomorphic hashing and homomorphic signatures. We contribute to this area in several ways:
  • We show the first homomorphic signature scheme based on the RSA assumption (in the random oracle model).
  • We give a homomorphic hashing scheme that is more efficient than existing schemes, and which leads to network coding signatures based on the hardness of factoring (in the standard model).
  • We describe variants of existing schemes that reduce the communication overhead for moderate-size networks, and improve computational efficiency (in some cases quite dramatically – e.g., we achieve a 20-fold speedup in signature generation at intermediate nodes).
Underlying our techniques is a modified approach to random linear network coding where instead of working in a vector space over a field, we work in a module over the integers (with small coefficients).
Rosario Gennaro, Jonathan Katz, Hugo Krawczyk, Tal Rabin

Preventing Pollution Attacks in Multi-source Network Coding

Abstract
Network coding is a method for achieving channel capacity in networks. The key idea is to allow network routers to linearly mix packets as they traverse the network so that recipients receive linear combinations of packets. Network coded systems are vulnerable to pollution attacks where a single malicious node floods the network with bad packets and prevents the receiver from decoding correctly. Cryptographic defenses to these problems are based on homomorphic signatures and MACs. These proposals, however, cannot handle mixing of packets from multiple sources, which is needed to achieve the full benefits of network coding. In this paper we address integrity of multi-source mixing. We propose a security model for this setting and provide a generic construction.
Shweta Agrawal, Dan Boneh, Xavier Boyen, David Mandell Freeman

Tools

Groth–Sahai Proofs Revisited

Abstract
Since their introduction in 2008, the non-interactive zero-knowledge (NIZK) and non-interactive witness indistinguishable (NIWI) proofs designed by Groth and Sahai have been used in numerous applications. In this paper, we offer two contributions to the study of these proof systems. First, we identify and correct some errors, present in the oringal online manuscript, that occur in two of the three instantiations of the Groth-Sahai NIWI proofs for which the equation checked by the verifier is not valid for honest executions of the protocol. In particular, implementations of these proofs would not work correctly. We explain why, perhaps surprisingly, the NIZK proofs that are built from these NIWI proofs do not suffer from a similar problem. Secondly, we study the efficiency of existing instantiations and note that only one of the three instantiations has the potential of being practical. We therefore propose a natural extension of an existing assumption from symmetric pairings to asymmetric ones which in turn enables Groth-Sahai proofs based on new classes of efficient pairings.
Essam Ghadafi, Nigel. P. Smart, Bogdan Warinschi

Constant-Round Concurrent Non-Malleable Statistically Binding Commitments and Decommitments

Abstract
When commitment schemes are used in complex environments, e.g., the Internet, the issue of malleability appears, i.e., a concurrent man-in-the-middle adversary might generate commitments to values related to ones committed to by honest players. In the plain model, the current best solution towards resolving this problem in a constant number of rounds is the work of Ostrovsky, Persiano and Visconti (TCC’ 09). They constructed a constant-round commitment scheme that is concurrent non-malleable with respect to both commitment and decommitment. However, the scheme is only computationally binding. For application scenarios where the security of receivers is of a great concern, computational binding may not suffice.
In this work, we follow the line of their work and give a construction of statistically binding commitment scheme which is concurrent non-malleable with respect to both commitment and decommitment. Our work can be seen as a complement of the work of Ostrovsky et al. in the plain model. Our construction relies on the existence of a family of pairs of claw-free permutations and only needs a constant number of communication rounds in the plain model. Our proof of security uses non-black-box techniques and satisfies the (most powerful) simulation-based definitions of non-malleability.
Zhenfu Cao, Ivan Visconti, Zongyang Zhang

Elliptic Curves

Faster Squaring in the Cyclotomic Subgroup of Sixth Degree Extensions

Abstract
This paper describes an extremely efficient squaring operation in the so-called ‘cyclotomic subgroup’ of \(\mathbb{F}_{q^6}^{\times}\), for \(q \equiv 1 \bmod{6}\). Our result arises from considering the Weil restriction of scalars of this group from \(\mathbb{F}_{q^6}\) to \(\mathbb{F}_{q^2}\), and provides efficiency improvements for both pairing-based and torus-based cryptographic protocols. In particular we argue that such fields are ideally suited for the latter when the field characteristic satisfies \(p \equiv 1 \pmod{6}\), and since torus-based techniques can be applied to the former, we present a compelling argument for the adoption of a single approach to efficient field arithmetic for pairing-based cryptography.
Robert Granger, Michael Scott

Faster Pairing Computations on Curves with High-Degree Twists

Abstract
Research on efficient pairing implementation has focussed on reducing the loop length and on using high-degree twists. Existence of twists of degree larger than 2 is a very restrictive criterion but luckily constructions for pairing-friendly elliptic curves with such twists exist. In fact, Freeman, Scott and Teske showed in their overview paper that often the best known methods of constructing pairing-friendly elliptic curves over fields of large prime characteristic produce curves that admit twists of degree 3, 4 or 6.
A few papers have presented explicit formulas for the doubling and the addition step in Miller’s algorithm, but the optimizations were all done for the Tate pairing with degree-2 twists, so the main usage of the high-degree twists remained incompatible with more efficient formulas.
In this paper we present efficient formulas for curves with twists of degree 2, 3, 4 or 6. These formulas are significantly faster than their predecessors. We show how these faster formulas can be applied to Tate and ate pairing variants, thereby speeding up all practical suggestions for efficient pairing implementations over fields of large characteristic.
Craig Costello, Tanja Lange, Michael Naehrig

Efficient Arithmetic on Hessian Curves

Abstract
This paper considers a generalized form for Hessian curves. The family of generalized Hessian curves covers more isomorphism classes of elliptic curves. Over a finite field \(\mathbb{F}_q\), it is shown to be equivalent to the family of elliptic curves with a torsion subgroup isomorphic to ℤ/3ℤ.
This paper provides efficient unified addition formulas for generalized Hessian curves. The formulas even feature completeness for suitably chosen parameters.
This paper also presents extremely fast addition formulas for generalized binary Hessian curves. The fastest projective addition formulas require 9M + 3S, where M is the cost of a field multiplication and S is the cost of a field squaring. Moreover, very fast differential addition and doubling formulas are provided that need only 5M + 4S when the curve is chosen with small curve parameters.
Reza R. Farashahi, Marc Joye

Lossy Trapdoor Functions

CCA Proxy Re-Encryption without Bilinear Maps in the Standard Model

Abstract
Proxy re-encryption (PRE) is a cryptographic application proposed by Blaze, Bleumer, and Strauss. It is an encryption system with a special property in which the semi-honest third party, the proxy, can re-encrypt ciphertexts for Alice into other ciphertexts for Bob without using Alice’s secret key. We can classify PRE into bidirectional and unidirectional schemes. Canetti and Hohenberger formalized the semantic security under chosen ciphertext attack for PRE, the PRE-CCA security. Several schemes satisfy the PRE-CCA security as a bidirectional or unidirectional scheme. However, some PRE schemes need a bilinear map in the standard model, and the other PRE schemes are PRE-CCA secure in the random oracle model before our work. In this paper, we construct a bidirectional PRE-CCA proxy re-encryption without bilinear maps in the standard model. We study lossy trapdoor functions (LTDFs) based on the decisional Diffie-Hellman (DDH) assumption proposed by Peikert and Waters. We define a new variant of LTDFs, re-applicable LTDFs, which are specialized LTDFs for PRE, and use them for our scheme.
Toshihide Matsuda, Ryo Nishimaki, Keisuke Tanaka

More Constructions of Lossy and Correlation-Secure Trapdoor Functions

Abstract
We propose new and improved instantiations of lossy trapdoor functions (Peikert and Waters, STOC ’08), and correlation-secure trapdoor functions (Rosen and Segev, TCC ’09). Our constructions widen the set of number-theoretic assumptions upon which these primitives can be based, and are summarized as follows:
  • Lossy trapdoor functions based on the quadratic residuosity assumption. Our construction relies on modular squaring, and whereas previous such constructions were based on seemingly stronger assumptions, we present the first construction that is based solely on the quadratic residuosity assumption.
  • Lossy trapdoor functions based on the composite residuosity assumption. Our construction guarantees essentially any required amount of lossiness, where at the same time the functions are more efficient than the matrix-based approach of Peikert and Waters.
  • Lossy trapdoor functions based on the d-Linear assumption. Our construction both simplifies the DDH-based construction of Peikert and Waters, and admits a generalization to the whole family of d-Linear assumptions without any loss of efficiency.
  • Correlation-secure trapdoor functions related to the hardness of syndrome decoding.
David Mandell Freeman, Oded Goldreich, Eike Kiltz, Alon Rosen, Gil Segev

Chosen-Ciphertext Security from Slightly Lossy Trapdoor Functions

Abstract
Lossy Trapdoor Functions (LTDFs), introduced by Peikert and Waters (STOC 2008) have been useful for building many cryptographic primitives. In particular, by using an LTDF that loses a (1 − 1/ω(logn)) fraction of all its input bits, it is possible to achieve CCA security using the LTDF as a black-box. Unfortunately, not all candidate LTDFs achieve such a high level of lossiness. In this paper we drastically lower the lossiness required to achieve CCA security, showing that an LTDF that loses only a noticeable fraction of a single bit can be used in a black-box way to build CCA-secure PKE. To show our result, we build on the recent result of Rosen and Segev (TCC 2009) that showed how to achieve CCA security from functions whose products are one-way on particular types of correlated inputs. Lastly, we give an example construction of a slightly lossy TDF based on the assumption that it is hard to distinguish the product of two primes from the product of three primes.
Petros Mol, Scott Yilek

Protocols II

Efficient Set Operations in the Presence of Malicious Adversaries

Abstract
We revisit the problem of constructing efficient secure two-party protocols for set-intersection and set-union, focusing on the model of malicious parties. Our main results are constant-round protocols that exhibit linear communication and a linear number of exponentiations with simulation based security. In the heart of these constructions is a technique based on a combination of a perfectly hiding commitment and an oblivious pseudorandom function evaluation protocol. Our protocols readily transform into protocols that are UC-secure.
Carmit Hazay, Kobbi Nissim

Text Search Protocols with Simulation Based Security

Abstract
This paper presents an efficient protocol for securely computing the fundamental problem of pattern matching. This problem is defined in the two-party setting, where party P 1 holds a pattern and party P 2 holds a text. The goal of P 1 is to learn where the pattern appears in the text, without revealing it to P 2 or learning anything else about P 2’s text. Our protocol is the first to address this problem with full security in the face of malicious adversaries. The construction is based on a novel protocol for secure oblivious automata evaluation which is of independent interest. In this problem party P 1 holds an automaton and party P 2 holds an input string, and they need to decide if the automaton accepts the input, without learning anything else.
Rosario Gennaro, Carmit Hazay, Jeffrey S. Sorensen

Discrete Logarithm

Solving a 676-Bit Discrete Logarithm Problem in GF(36n )

Abstract
Pairings on elliptic curves over finite fields are crucial for constructing various cryptographic schemes. The η T pairing on supersingular curves over GF(3 n ) is particularly popular since it is efficiently implementable. Taking into account the Menezes-Okamoto-Vanstone (MOV) attack, the discrete logarithm problem (DLP) in GF(36n ) becomes a concern for the security of cryptosystems using η T pairings in this case. In 2006, Joux and Lercier proposed a new variant of the function field sieve in the medium prime case, named JL06-FFS. We have, however, not yet found any practical implementations on JL06-FFS over GF(36n ). Therefore, we first fulfill such an implementation and we successfully set a new record for solving the DLP in GF(36n ), the DLP in GF(36·71) of 676-bit size. In addition, we also compare JL06-FFS and an earlier version, named JL02-FFS, with practical experiments. Our results confirm that the former is several times faster than the latter under certain conditions.
Takuya Hayashi, Naoyuki Shinohara, Lihua Wang, Shin’ichiro Matsuo, Masaaki Shirase, Tsuyoshi Takagi

Using Equivalence Classes to Accelerate Solving the Discrete Logarithm Problem in a Short Interval

Abstract
The Pollard kangaroo method solves the discrete logarithm problem (DLP) in an interval of size N with heuristic average case expected running time approximately \(2 \sqrt{N}\) group operations. It is well-known that the Pollard rho method can be sped-up by using equivalence classes (such as orbits of points under an efficiently computed group homomorphism), but such ideas have not been used for the DLP in an interval. Indeed, it seems impossible to implement the standard kangaroo method with equivalence classes.
The main result of the paper is to give an algorithm, building on work of Gaudry and Schost, to solve the DLP in an interval of size N with heuristic average case expected running time of close to \(1.36\sqrt{N}\) group operations for groups with fast inversion. In practice the algorithm is not quite this fast, due to the usual problems with pseudorandom walks such as fruitless cycles. In addition, we present experimental results.
Steven D. Galbraith, Raminder S. Ruprai

Encryption II

Functional Encryption for Inner Product: Achieving Constant-Size Ciphertexts with Adaptive Security or Support for Negation

Abstract
In functional encryption (FE) schemes, ciphertexts and private keys are associated with attributes and decryption is possible whenever key and ciphertext attributes are suitably related. It is known that expressive realizations can be obtained from a simple FE flavor called inner product encryption (IPE), where decryption is allowed whenever ciphertext and key attributes form orthogonal vectors. In this paper, we construct (non-anonymous) IPE systems with constant-size ciphertexts for the zero and non-zero evaluations of inner products. These schemes respectively imply an adaptively secure identity-based broadcast encryption scheme and an identity-based revocation mechanism that both feature short ciphertexts and rely on simple assumptions in prime order groups. We also introduce the notion of negated spatial encryption, which subsumes non-zero-mode IPE and can be seen as the revocation analogue of the spatial encryption primitive of Boneh and Hamburg.
Nuttapong Attrapadung, Benoît Libert

Security of Encryption Schemes in Weakened Random Oracle Models

(Extended Abstract)
Abstract
Liskov proposed several weakened versions of the random oracle model, called weakened random oracle models (WROMs), to capture the vulnerability of ideal compression functions, which are expected to have the standard security of hash functions, i.e., collision resistance, second-preimage resistance, and one-wayness properties. The WROMs offer additional oracles to break such properties of the random oracle. In this paper, we investigate whether public-key encryption schemes in the random oracle model essentially require the standard security of hash functions by the WROMs. In particular, we deal with four WROMs associated with the standard security of hash functions; the standard, collision tractable, second-preimage tractable, first-preimage tractable ones (ROM, CT-ROM, SPT-ROM, and FPT-ROM, respectively), done by Numayama et al. for digital signature schemes in the WROMs. We obtain the following results: (1) The OAEP is secure in all the four models. (2) The encryption schemes obtained by the Fujisaki-Okamoto conversion (FO) are secure in the SPT-ROM. However, some encryption schemes with FO are insecure in the FPT-ROM. (3) We consider two artificial variants wFO and dFO of FO for separation of the WROMs in the context of encryption schemes. The encryption schemes with wFO (dFO, respectively) are secure in the CT-ROM (ROM, respectively). However, some encryption schemes obtained by wFO (dFO, respectively) are insecure in the SPT-ROM (CT-ROM, respectively). These results imply that standard encryption schemes such as the OAEP and FO-based one do not always require the standard security of hash functions. Moreover, in order to make our security proofs complete, we construct an efficient sampling algorithm for the binomial distribution with exponentially large parameters, which was left open in Numayama et al.’s paper.
Akinori Kawachi, Akira Numayama, Keisuke Tanaka, Keita Xagawa

Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes

Abstract
We present a fully homomorphic encryption scheme which has both relatively small key and ciphertext size. Our construction follows that of Gentry by producing a fully homomorphic scheme from a “somewhat” homomorphic scheme. For the somewhat homomorphic scheme the public and private keys consist of two large integers (one of which is shared by both the public and private key) and the ciphertext consists of one large integer. As such, our scheme has smaller message expansion and key size than Gentry’s original scheme. In addition, our proposal allows efficient fully homomorphic encryption over any field of characteristic two.
N. P. Smart, F. Vercauteren

Signatures

Unlinkability of Sanitizable Signatures

Abstract
Sanitizable signatures allow a designated party, called the sanitizer, to modify parts of signed data such that the immutable parts can still be verified with respect to the original signer. Ateniese et al. (ESORICS 2005) discuss five security properties for such signature schemes: unforgeability, immutability, privacy, transparency and accountability. These notions have been formalized in a recent work by Brzuska et al. (PKC 2009), discussing also the relationships among the security notions. In addition, they prove a modification of the scheme of Ateniese et al. to be secure according to these notions.
Here we discuss that a sixth property of sanitizable signature schemes may be desirable: unlinkability. Basically, this property prevents that one can link sanitized message-signature pairs of the same document, thus allowing to deduce combined information about the original document. We show that this notion implies privacy, the inability to recover the original data of sanitized parts, but is not implied by any of the other five notions. We also discuss a scheme based on group signatures meeting all six security properties.
Christina Brzuska, Marc Fischlin, Anja Lehmann, Dominique Schröder

Confidential Signatures and Deterministic Signcryption

Abstract
Encrypt-and-sign, where one encrypts and signs a message in parallel, is usually not recommended for confidential message transmission as the signature may leak information about the message. This motivates our investigation of confidential signature schemes, which hide all information about (high-entropy) input messages. In this work we provide a formal treatment of confidentiality for such schemes. We give constructions meeting our notions, both in the random oracle model and the standard model. As part of this we show that full domain hash signatures achieve a weaker level of confidentiality than Fiat-Shamir signatures. We then examine the connection of confidential signatures to signcryption schemes. We give formal security models for deterministic signcryption schemes for high-entropy and low-entropy messages, and prove encrypt-and-sign to be secure for confidential signature schemes and high-entropy messages. Finally, we show that one can derandomize any signcryption scheme in our model and obtain a secure deterministic scheme.
Alexander W. Dent, Marc Fischlin, Mark Manulis, Martijn Stam, Dominique Schröder

Identity-Based Aggregate and Multi-Signature Schemes Based on RSA

Abstract
We propose new identity-based multi-signature (IBMS) and aggregate signature (IBAS) schemes, secure under RSA assumption. Our schemes reduce round complexity of previous RSA-based IBMS scheme of Bellare and Neven [BN07] from three to two rounds. Surprisingly, this improvement comes at virtually no cost, as the computational efficiency and exact security of the new scheme are almost identical to those of [BN07]. The new scheme is enabled by a technical tool of independent interest, a class of zero-knowledge proofs of knowledge of preimages of one-way functions which is straight-line simulatable, enabling concurrency and good exact security, and aggregatable, enabling aggregation of parallel instances of such proofs into short multi/aggregate signatures.
Ali Bagherzandi, Stanisław Jarecki

Lattice Mixing and Vanishing Trapdoors: A Framework for Fully Secure Short Signatures and More

Abstract
We propose a framework for adaptive security from hard random lattices in the standard model. Our approach borrows from the recent Agrawal-Boneh-Boyen families of lattices, which can admit reliable and punctured trapdoors, respectively used in reality and in simulation. We extend this idea to make the simulation trapdoors cancel not for a specific forgery but on a non-negligible subset of the possible challenges. Conceptually, we build a compactly representable, large family of input-dependent “mixture” lattices, set up with trapdoors that “vanish” for a secret subset which we hope the forger will target. Technically, we tweak the lattice structure to achieve “naturally nice” distributions for arbitrary choices of subset size. The framework is very general. Here we obtain fully secure signatures, and also IBE, that are compact, simple, and elegant.
Xavier Boyen

Backmatter

Weitere Informationen

Premium Partner