Dennis Volpano
ABSTRACT
Systems that authenticate a user based on a shared secret (such as a password or PIN) normally allow anyone to query whether the secret is a given value. For example, an ATM machine allows one to ask whether a string is the secret PIN of a (lost or stolen) ATM card. Yet such queries are prohibited in any model whose programs satisfy an information-flow property like Noninterference. But there is complexity-based justification for allowing these queries. A type system is given that provides the access control needed to prove that no well-typed program can leak secrets in polynomial time, or even leak them with nonnegligible probability if secrets are of sufficient length and randomly chosen. However, there are well-typed deterministic programs in a synchronous concurrent model capable of leaking secrets in linear time.
- 1.T. Baker, j. Gill, and R. Solovay. Relativizations of the P =? NP question. SIAM J. Computing, 4(4):431-442, 1975.]]Google Scholar
Cross Ref
- 2.P. Beauchemin, G. Brassaxd, C. Cr~peau, C. Goutier, and C. Pomerance. The generation of random numbers that are provably prime. Journal of Cryptology, 1(1):53-64, 1988.]] Google ScholarDigital Library
- 3.M. Bellare and P. Rogaway. The exact security of digital signatures--how to sign with RSA and Robin. In Proc. Eurocrypt 96. Lecture Notes in Computer Science 1070, 1996.]]Google Scholar
- 4.M. Bellare and P. Rogaway. Practice-oriented provable security. In Proc. of First International Workshop on Information Security. Lecture Notes in Computer Science 1396, 1998.]] Google ScholarDigital Library
- 5.J. Goguen and J. Meseguer. Security policies and security models. In Proceedings 1982 IEEE Symposium on Security and Privacy, pages 11-20, Oakland, CA, 1982.]]Google ScholarCross Ref
- 6.J. Gray, K. Ip, and K. Lui. Provable security for cryptographic protocols--exact analysis and engineering applications. Journal of Computer Security, 6(1,2):23-52, 1998.]] Google ScholarDigital Library
- 7.P. Kocher. Timing attacks on implementations of Diffie-ttellman, RSA, DSS and other systems. In Proceedings 16th Annual Crypto Conference, August 1996.]] Google ScholarDigital Library
- 8.P. Lincoln, J. Mitchell, M. Mitchell, and A. Scedrov. A probabilistic poly-time framework for protocol analysis. In Proceedings 5th A CM Conference on Computer and Communications Security~ San Francisco, CA, November 1998.]] Google ScholarDigital Library
- 9.A. Myers. Jflow: Practical mostly-static information flow control. In Proceedings 26th Symposium on Principles of Programming Languages, pages 228-241, San Antonio, TX, January 1999.]] Google ScholarDigital Library
- 10.B. Schneier. Applied Crypgography. John Wiley & Sons, 1996. Second Edition.]]Google Scholar
- 11.M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.]] Google ScholarDigital Library
- 12.G. Smith and D. Volpano. Secure information flow in a multi-threaded imperative language. In Proceedings 25th Symposium on Principles of Programming Languages, pages 355-364, San Diego, CA, January 1998.]] Google ScholarDigital Library
- 13.D. Voipano and G. Smith. Eliminating covert flows with minimum typings. In Proceedings l Oth IEEE Computer Security Foundations Workshop, pages 156-168, June 1997.]] Google ScholarDigital Library
- 14.D. Volpano and G. Smith. Probabilistic noninterference in a concurrent language. Journal of Computer Security, 7(2,3):231-253, 1999.]] Google ScholarDigital Library
- 15.D. Volpano, G. Smith, and C. Irvine. A sound type system for secure flow analysis. Journal of Computer Security, 4(2,3):167-187, 1996.]] Google ScholarDigital Library
Index Terms
- Verifying secrets and relative secrecy
Recommendations
Sharing multiple secrets in visual cryptography
The secret sharing schemes in conventional visual cryptography are characterized by encoding one shared secret into a set of random transparencies which reveal the secret to the human visual system when they are superimposed. In this paper, we propose a ...
Comments