A One-Time Stegosystem and Applications to Efficient Covert Communication
Abstract We present the first information-theoretic steganographic protocol with an asymptotically optimal ratio of key length to message length that operates on arbitrary covertext distributions with constant min-entropy. Our results are also applicable to the computational setting: our stegosystem can be composed over a pseudorandom generator to send longer messages in a computationally secure fashion. In this respect our scheme offers a significant improvement in terms of the number of pseudorandom bits generated by the two parties in comparison to previous results known in the computational setting. Central to our approach for improving the overhead for general distributions is the use of combinatorial constructions that have been found to be useful in other contexts for derandomization: almost t-wise independent function families.
- Content Type Journal Article
- Pages 1-22
- DOI 10.1007/s00145-012-9135-4
- Aggelos Kiayias, Department of Computer Science and Engineering, University of Connecticut, Storrs, CT, USA
- Yona Raekow, Fraunhofer Institute for Algorithms and Scientific Computing, St. Augustin, Germany
- Alexander Russell, Department of Computer Science and Engineering, University of Connecticut, Storrs, CT, USA
- Narasimha Shashidhar, Department of Computer Science, Sam Houston State University, Huntsville, TX, USA
From: Wed, 24 Oct 2012 17:55:35 GMT
- Journal Journal of Cryptology
- Online ISSN 1432-1378
- Print ISSN 0933-2790
Secure Outsourced Attribute-Based Signatures, by Jin Li, Xiaofeng Chen, Jingwei Li, Chunfu Jia, Duncan S. Wong, Willy Susilo
Attribute-based signature (ABS) is a useful variant of digital signature, which enables users to sign messages over attributes without revealing any information other than the fact that they have attested to the messages. However, heavy computational cost is required during signing in existing work of ABS, which grows linearly with the size of the predicate formula. As a result, this presents a significant challenge for resource-limited users (such as mobile devices) to perform such heavy computation independently. Aiming at tackling the challenge above, we propose and formalize a
new paradigm called OABS, in which the computational overhead at user side is greatly reduced through outsourcing such intensive computation to an untrusted signing-cloud service provider (S-CSP). Furthermore, we apply this novel paradigm to existing ABS to reduce complexity and present two schemes, i) in the first OABS scheme, the number of exponentiations involving in signing is reduced from $O(d)$ to $O(1)$ (nearly three), where $d$ is the upper bound of threshold value defined in the predicate; ii) our second scheme is built on Herranz et al\'s construction with constant-size signatures. The number of exponentiations in signing is reduced from $O(d^2)$ to $O(d)$ and the communication overhead is $O(1)$. Security analysis demonstrates that both OABS schemes are secure in terms of the unforgeability and attribute-signer privacy definitions specified in the proposed security model. Finally, to allow for high efficiency and flexibility, we discuss extensions of OABS and show how to achieve accountability and outsourced verification as well.
Breaking Public Keys - How to Determine an Unknown RSA Public Modulus, by Hans-Joachim Knobloch
Not surprisingly, the common use of any public key crypto system involves publishing the public key and keeping the private key secret. There are however a few applications where both the private and public key are kept secret, thereby effectively converting a public key crypto algorithm to a symmetric algorithm.
We show that if the RSA cryptosystem is used in such a symmetric application, it is possible to determine the public RSA modulus if the public exponent is known and short, such as 3 or F4=65537, and two or more plaintext/ciphertext (or, if RSA is used for signing, signed value/signature) pairs are known.
An Efﬁcient Three-Party Authenticated Key Exchange Protocol for Mobile-Commerce Environments Using Elliptic Curve Cryptography, by Nishant Doshi
In the three party authentication key exchange
(3PAKE) protocol, more than two parties can communicate and
set up common shared secret key using the server. Recently,
Tan et al. proposed an enhanced 3PAKE scheme based on
elliptic curve cryptography (ECC) to minimize the operations and
make compatible for mobile commerce environments. However,
Nose showed the scheme of Tan et al. is susceptible to the
impersonation attack and the man-in-middle attack. However, in
this paper we have shown that Tan et al. protocol is susceptible to
the known session-speciﬁc temporary information attack and the
clock synchronization attack too. Afterwards, we have proposed
the protocol that withstands against the above mentioned attacks.
In addition, our proposed approach is based on the hash function
in place of the encryption/decryption function that was used in
Tan et al. scheme.
Attribute-Based Encryption for Circuits from Multilinear Maps, by Amit sahai and Brent Waters
In this work, we provide the first construction of Attribute-Based
Encryption (ABE) for general circuits. Our construction is based on
the existence of multilinear maps. We prove selective security of
our scheme in the standard model under the natural multilinear
generalization of the BDDH assumption. Our scheme achieves both
Key-Policy and Ciphertext-Policy variants of ABE.
Factor-4 and 6 (De)compression for Values of Pairings using Trace Maps, by Tomoko Yonemura and Taichi Isogai and Hirofumi Muratani and Yoshikazu Hanatani
The security of pairing-based cryptosystems relies on the hardness of the discrete logarithm problems in elliptic curves and in finite fields related to the curves, namely, their embedding fields. Public keys and ciphertexts in the pairing-based cryptosystems are composed of points on the curves or values of pairings. Although the values of the pairings belong to the embedding fields, the representation of the field is inefficient in size because the size of the embedding fields is usually larger than the size of the elliptic curves. We show factor-4 and 6 compression and decompression for the values of the pairings with the supersingular elliptic curves of embedding degrees 4 and 6, respectively. For compression, we use the fact that the values of the pairings belong to algebraic tori
that are multiplicative subgroups of the embedding fields. The algebraic tori can be expressed by the affine representation or the trace representation. Although the affine representation allows decompression maps, decompression maps for the trace representation has not been known. In this paper, we propose a trace representation with decompression maps for the characteristics 2 and 3. We first construct efficient decompression maps for trace maps by adding extra information to the trace representation. Our decompressible trace representation with additional information is as efficient as the affine representation is in terms of the costs of compression, decompression and exponentiation, and the size.
Extending Brickell-Davenport Theorem to Non-Perfect Secret Sharing Schemes, by Oriol Farras and Carles Padro
One important result in secret sharing is Brickell-Davenport Theorem: every ideal perfect secret sharing scheme defines a matroid that is uniquely determined by the access structure. Even though a few attempts have been made, there is no satisfactory definition of ideal secret sharing scheme for the general case, in which non-perfect schemes are considered as well. Without providing another unsatisfactory definition of ideal non-perfect secret sharing scheme, we present a generalization
of Brickell-Davenport Theorem to the general case. After analyzing that result under a new point of view and identifying its combinatorial nature, we present a characterization of the (not necessarily perfect)
secret sharing schemes that are associated to matroids. Some optimality properties of such schemes are discussed.
Evaluating User Privacy in Bitcoin, by Elli Androulaki and Ghassan Karame and Marc Roeschlin and Tobias Scherer and Srdjan Capkun
Bitcoin is quickly emerging as a popular digital payment system. However, in spite of its reliance on pseudonyms, Bitcoin raises a number of privacy concerns due to the fact that all of the transactions that take place are publicly announced in the system.
In this paper, we investigate the privacy guarantees of Bitcoin in the setting where Bitcoin is used as a primary currency for the daily transactions of individuals. More specifically, we evaluate the privacy that is provided by Bitcoin (i) by analyzing the genuine Bitcoin system and (ii) through a simulator that mimics Bitcoin client\'s behavior in the context where Bitcoin is used for all transactions within a university. In this setting, our results show that the profiles of almost 40% of the users can be, to a large extent, recovered even when users adopt privacy measures recommended by Bitcoin. To the best of our knowledge, this is the first work that comprehensively analyzes, and evaluates the privacy implications of Bitcoin. As a by-product, we have designed and implemented the first simulator of Bitcoin; our simulator can be used to model the interaction between Bitcoin users in generic settings.