Abstract.
We propose a new cryptographic primitive called oblivious signature-based envelope (OSBE). Informally, an OSBE scheme enables a sender to send an envelope (encrypted message) to a receiver, and has the following two properties: (1) The receiver can open the envelope if and only if it has a third party’s (e.g., a certification authority’s) signature on an agreed-upon message. (2) The sender does not learn whether the receiver has the signature or not. We show that OSBE can be used to break policy cycles in automated trust negotiation (ATN) and to achieve oblivious access control.
We develop a provably secure and efficient OSBE protocol for certificates signed using RSA signatures, as well as provably secure and efficient one-round OSBE protocols for Rabin and BLS signatures from recent constructions for identity-based encryption. We also present constructions for Generalized OSBE, where signatures on multiple messages (and possibly by different authorities) are required to open the envelope.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aiello B, Ishai Y, Reingold O: Priced oblivious transfer: How to sell digital goods. In: Advances in Cryptology: EUROCRYPT ‘01, May 2001, pp 119-135
Asokan N, Shoup V, Waidner M: Optimistic fair exchange of digital signatures. IEEE J Selected Areas Commun 18(4):591-610 (2000)
Balfanz D, Durfee G, Shankar N, Smetters D, Staddon J, Wong H-C: Secret handshakes from pairing-based key agreements. In: Proceedings of the IEEE Symposium and Security and Privacy, May 2003, pp 180-196
Bao F, Deng RH, Mao W: Efficient and practical fair exchange protocols with off-line TTP. In: Proceedings of the 1998 IEEE Symposium on Security and Privacy, IEEE Computer Society Press, May 1998, pp 77-89
Bellare M, Rogaway P: Random oracles are practical: A paradigm for designing efficient protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security, ACM Press, 1993, pp 62-73
Biham E, Boneh D, Reingold O: Breaking generalized Diffie-Hellman modulo a composite is no easier than factoring. Inf Proc Lett 70(2):83-87 (1999)
Boneh D, Franklin M: Identity-Based Encryption from the Weil Pairing. In: Proceedings of Crypto 2001. Lecture Notes in Computer Science, vol 2139. Springer, 2001, pp 213-229
Boneh D, Lynn B, Shacham H: Short Signatures from the Weil Pairing. In: Proceedings of Asiacrypt 2001. Lecture Notes in Computer Science, vol 2248, Springer, 2001, pp 514-32
Brands SA: Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy. MIT Press, August 2000
Cocks C: An identity based encryption scheme based on quadratic residues. In: 8th IMA International Conference on Cryptography and Coding, vol 2260, Springer, December 2001, pp 360-363
Di Crescenzo G, Ostrovsky R, Rajagopalan S: Conditional oblivious transfer and timed-release encryption. In: Advances in Cryptology: EUROCRYPT ‘99, Lecture Notes in Computer Science, vol 1592, March 1999, pp 74-89
Gertner Y, Ishai Y, Kushilevitz E, Malkin T: Protecting data privacy in private information retrieval schemes. JCSS 60(3):592-629 (2000). Preliminary version in STOC’98
Goldreich O: The Foundations of Cryptography - Volume 2. Cambridge University Press, May 2004
Goldreich O, Micali S, Wigderson A: How to play any mental game. In: Proceedings of the nineteenth annual ACM conference on Theory of computing, May 1987, pp 218-229
Goldwasser S, Micali S: Probabilistic encryption. J Comput Syst Sci 28(2):270-299 (1984)
Holt JE, Bradshaw RW, Seamons KE, Orman H: Hidden credentials. In: Proceedings of the 2nd ACM Workshop on Privacy in the Electronic Society, October 2003
Joux A: A one round protocol for tripartite Diffie-Hellman. In: Proceddings of the 4th Algorithmic Number Theory Symposium. Lecture Notes in Computer Science, vol 1838, Springer, 2000, pp 385-394
Rabin MO: Digitalized signatures as intractable as factorization. Technical Report MIT/LCS/TR-212, MIT Laboratory for Computer Science, January 1979
Rivest RL, Shamir A, Adleman LM: A method for obtaining digital signatures and public-key cryptosystems. Commun ACM 21:120-126 (1978)
Sakai R, Ohgishi K, Kasahara M: Cryptosystems based on pairing. In: Proceedings of the Symposium on Cryptography and Information Security (SCIS 2000), January 2000
Seamons KE, Winslett M, Yu T: Limiting the disclosure of access control policies during automated trust negotiation. In: Proceedings of the Symposium on Network and Distributed System Security (NDSS’01), February 2001
Shamir A: Identity-based cryptosystems and signature schemes. In Advances in Cryptology: CRYPTO ‘84. Lecture Notes in Computer Science, vol 196, Springer, 1984, pp 47-53
Verheul ER: Self-blindable credential certificates from the weil pairing. In Advances in Cryptology: AsiaCrypt 2001, Lecture Notes in Computer Science, number 2248, Springer, 2001, pp 533-551
Winsborough WH, Li N: Towards practical automated trust negotiation. In: Proceedings of the Third International Workshop on Policies for Distributed Systems and Networks (Policy 2002), IEEE Computer Society Press, June 2002, pp 92-103
Winsborough WH, Seamons KE, Jones VE: Automated trust negotiation. In: DARPA Information Survivability Conference and Exposition, volume I, IEEE Press, January 2000, pp 88-102
Winslett M, Yu T, Seamons KE, Hess A, Jacobson J, Jarvis R, Smith B, Yu L: Negotiating trust on the web. IEEE Internet Computing 6(6):30-37 (2002)
Yao AC: How to generate and exchange secrets. In: Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1986, pp 162-167
Yu T, Winslett M: Unified scheme for resource protection in automated trust negotiation. In: Proceedings of IEEE Symposium on Security and Privacy, IEEE Computer Society Press, May 2003, pp 110-122.
Yu T, Winslett M, Seamons KE: Supporting structured credentials and sensitive policies through interoperable strategies for automated trust negotiation. ACM Trans Inf Syst Security 6(1):1-42 (2003)
Author information
Authors and Affiliations
Corresponding author
Additional information
Received: 30 July 2003, Accepted: 6 August 2004, Published online: 29 November 2004
Ninghui Li: Most of this work was performed while the first author was a Research Associate at the Department of Computer Science, Stanford University in Stanford, CA 94305.
Invited submission to the journal Distributed Computing, special issue of selected papers of PODC 2003. Preliminary version appeared in Proceedings of PODC’2003 under the same title.
Rights and permissions
About this article
Cite this article
Li, N., Du, W. & Boneh, D. Oblivious signature-based envelope. Distrib. Comput. 17, 293–302 (2005). https://doi.org/10.1007/s00446-004-0116-1
Issue Date:
DOI: https://doi.org/10.1007/s00446-004-0116-1