Novosibirsk State University Journal of Information Technologies
Scientic Journal

ISSN 2410-0420 (Online), ISSN 1818-7900 (Print)

Switch to

All Issues >> Contents: Volume 14, Issue No 4 (2016)

Design of Knapsack Cryptosystems
Maxim Igorevich Vakhrushev, Eugeny Aleksandrovich Zagurskih

Novosibirsk State University
UDC code: 004.056.55

The development of quantum computers endangers the great number modern cryptosystems based on factorization problem, discrete logarithm problem and other, which can be solved in polynomial time on a quantum computer. However, quantum computing algorithms can't efficiently solve NP-hard problems at present. In this paper, we consider two public key cryptosystems based on NP-hard problems: subset sum and integer programming.

Key Words
post-quantum cryptography, knapsack public-key cryptosystem, subset sum problem, NP-hard, knapsack problem

How to cite:
Vakhrushev M. I., Zagurskih E. A. Design of Knapsack Cryptosystems // Vestnik NSU Series: Information Technologies. - 2016. - Volume 14, Issue No 4. - P. 31-38. - ISSN 1818-7900. (in Russian).

Full Text in Russian

Available in PDF

1. T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. 3rd. MIT Press, 2009. 1312 p.
2. S. Martello, P. Toth. Knapsack problems: Algorithms and computer interpretations. WileyInterscience, 1990. 306 p.
3. B. Schneier. Applied Cryptography: Protocols, Algorithms, and Source Code in C. John Wiley & Sons, 1996. 784 p.
4. A. Salomaa. Public-Key Cryptography – Springer Science & Business Media, 1996. 275 p.

Publication information
Main title Vestnik NSU Series: Information Technologies, Volume 14, Issue No 4 (2016).
Parallel title: Novosibirsk State University Journal of Information Technologies Volume 14, Issue No 4 (2016).

Key title: Vestnik Novosibirskogo gosudarstvennogo universiteta. Seriâ: Informacionnye tehnologii
Abbreviated key title: Vestn. Novosib. Gos. Univ., Ser.: Inf. Tehnol.
Variant title: Vestnik NGU. Seriâ: Informacionnye tehnologii

Year of Publication: 2016
ISSN: 1818-7900 (Print), ISSN 2410-0420 (Online)
Publisher: Novosibirsk State University Press
DSpace handle

|Home Page| |All Issues| |Information for Authors| |Journal Boards| |Ethical principles| |Editorial Policy| |Contact Information| |Publication fee| |Open Access Policy| |Old Site in Russian|
© 2006-2018, Novosibirsk State University.