Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
2005-03-01
2010-02-02
Shiferaw, Eleni A (Department: 2436)
Cryptography
Particular algorithmic function encoding
Public key
Reexamination Certificate
active
07657029
ABSTRACT:
An addition chain is first generated, and then an integer x is derived from it. Doubling and star steps may be implemented in the addition chain. This approach eliminates the computationally expensive step of generating the addition chain from an exponent, and therefore can greatly reduce the computation time of the modular exponentiation.
REFERENCES:
patent: 5987131 (1999-11-01), Clapp
patent: 5999627 (1999-12-01), Lee et al.
patent: 6091819 (2000-07-01), Venkatesan et al.
Schnorr, C.P., “Efficient Identification and Signatures for Smart Cards,” Crypto'89, 1989, pp. 239-252.
deRooij, P., “On the Security of the Schnorr Scheme Using Preprocessing,” Eurocrypt'91, 1991, pp. 71-80.
Schnorr, C.P., “Efficient Signature Generation by Smart Cards,” Universitat Frankfurt, Mar. 1991, pp. 1-22.
de Rooij, Peter, “On Schnorr's Preprocessing for Digital Signature Schemes,” J. Cryptology, v. 10(1), 1997, pp. 1-16.
Boyko, Victor, et al., “Speeding up Discrete Log and Factoring Based Schemes via Precomputations,”EuroCrypt'98, LNCS 1403, 1998, pp. 221-235.
Aiello, William, et al., “Design of Practical and Provably Good Random Number Generators,” J. Algorithms, v. 29(2), 1998, pp. 358-389.
Brickell, Ernest F., et al., “Fast Exponentiation with Precomputation: Algorithms and Lower Bounds,” Nov. 30, 1995, pp. 1-21.
de Rooij, Peter, “Efficient Exponentiation using Precomputation and Vector Addition Chains,” Eurocrypt'94, 1994, pp. 389-399.
Lim, Chae Hoon, et al., “More Flexible Exponentiation with Precomputation,” Crypto'94, 1994, pp. 95-107.
von zur Gathen, Joachim, et al., “Exponentiation in Finite Fields: Theory and Practice Abstract,” AAECC-12, LNCS 1255, 1997, pp. 88-133.
Knuth, Donald E., “The Art of Computer Programming (TAOCP),”Seminumerical Algorithms, 3rd Edition, Addison-Wesley, 1997.
Thurber, Edward G., “Efficient Generation of Minimal Length Addition Chains,”SIAM Journal on Computing, vol. 28, No. 4, 1999, 1 page Abstract.
Coarfa, Cristian, et al., “Performance Analysis of TLS Web Servers,” NDSS'02, 2002, pp. 183-194.
Mironov Ilya
Mityagin Anton
Nissim Kobliner Yaacov
Microsoft Corporation
Shiferaw Eleni A
Woodcock & Washburn LLP
LandOfFree
Systems and methods for generating random addition chains does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systems and methods for generating random addition chains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods for generating random addition chains will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4166362