Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data.

Andrey Bogdanov

dblp:b/AndreyBogdanov · DBLP profile ↗
← Back
55ranked-venue papers
31as first author
2since 2021 · last 2026
0000-0003-1449-3099ORCID · verified

Domains — the database's venue-derived domains; a paper can count in several

Security and privacy · 44 · 26 first-author · 1 since 2021Systems, architecture and hardware · 6 · 3 first-authorDatabases, data management, data science and information retrieval · 4 · 2 first-authorTheory of computation · 4 · 2 first-authorArtificial intelligence and machine learning · 1 · 1 since 2021Graphics, computer vision, multimedia, augmented reality and games · 1 · 1 since 2021

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Network and information security
25 papers
Cryptographic primitives and cryptanalysis · 93% Hardware security and side channels · 7%
Artificial intelligence
1 paper
Generative modeling · 100%
Interdisciplinary, comprehensive, and emerging computing
1 paper
Computational science and engineering · 100%

Topics — the 30 heaviest of 46, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Cryptographic primitives and cryptanalysis
authenticated encryption
1.552024
The COLM Authenticated Encryption Scheme · J. Cryptol. 2024
Twisted Polynomials and Forgery Attacks on GCM · EUROCRYPT (1) 2015
How to Securely Release Unverified Plaintext in Authenticated Encryption · ASIACRYPT (1) 2014
Cryptographic primitives and cryptanalysis
block cipher
1.392017
White-Box Cryptography Revisited: Space-Hard Ciphers · CCS 2015
How Secure is AES Under Leakage · ASIACRYPT (2) 2015
Midori: A Block Cipher for Low Energy · ASIACRYPT (2) 2015
Machine learning › Generative modeling › diffusion model
conditional generation
1.012026
MetaDiT: Enabling Fine-grained Constraints in High-degree-of Freedom Metasurface Design · AAAI 2026
Machine learning › Generative modeling
diffusion model
1.012026
MetaDiT: Enabling Fine-grained Constraints in High-degree-of Freedom Metasurface Design · AAAI 2026
Machine learning › Generative modeling › diffusion model
diffusion transformer
1.012026
MetaDiT: Enabling Fine-grained Constraints in High-degree-of Freedom Metasurface Design · AAAI 2026
Cryptographic primitives and cryptanalysis
symmetric-key cryptanalysis
0.632017
Linear Cryptanalysis of DES with Asymmetries · ASIACRYPT (1) 2017
Integral and Multidimensional Linear Distinguishers with Correlation Zero · ASIACRYPT 2012
Biclique Cryptanalysis of the Full AES · ASIACRYPT 2011
Cryptographic primitives and cryptanalysis › cryptographic implementation
white-box cryptography
0.522016
Towards Practical Whitebox Cryptography: Optimizing Efficiency and Space Hardness · ASIACRYPT (1) 2016
White-Box Cryptography Revisited: Space-Hard Ciphers · CCS 2015
Cryptographic primitives and cryptanalysis › block cipher
lightweight block cipher
0.532015
Midori: A Block Cipher for Low Energy · ASIACRYPT (2) 2015
Fides: Lightweight Authenticated Cipher with Side-Channel Resistance for Constrained Hardware · CHES 2013
PRESENT: An Ultra-Lightweight Block Cipher · CHES 2007
Cryptographic primitives and cryptanalysis
hash functions
0.432013
SPONGENT: The Design Space of Lightweight Cryptographic Hashing · IEEE Trans. Computers 2013
spongent: A Lightweight Hash Function · CHES 2011
Hash Functions and RFID Tags: Mind the Gap · CHES 2008
Cryptographic primitives and cryptanalysis › hash functions › dedicated hash functions
lightweight hash function
0.432013
SPONGENT: The Design Space of Lightweight Cryptographic Hashing · IEEE Trans. Computers 2013
spongent: A Lightweight Hash Function · CHES 2011
Hash Functions and RFID Tags: Mind the Gap · CHES 2008
Cryptographic primitives and cryptanalysis › block cipher
key-alternating ciphers
0.322013
On the Indifferentiability of Key-Alternating Ciphers · CRYPTO (1) 2013
Key-Alternating Ciphers in a Provable Setting: Encryption Using a Small Number of Public Permutations - (Extended Abstract) · EUROCRYPT 2012
Cryptographic primitives and cryptanalysis › hash function cryptanalysis
collision attack
0.332012
Beyond the Limits of DPA: Combined Side-Channel Collision Attacks · IEEE Trans. Computers 2012
Multiple-Differential Side-Channel Collision Attacks on AES · CHES 2008
Collision Attacks on AES-Based MAC: Alpha-MAC · CHES 2007
Cryptographic primitives and cryptanalysis
linear cryptanalysis
0.312017
Linear Cryptanalysis of DES with Asymmetries · ASIACRYPT (1) 2017
Cryptographic primitives and cryptanalysis › public-key cryptography › signature scheme cryptanalysis
forgery attack
0.212015
Twisted Polynomials and Forgery Attacks on GCM · EUROCRYPT (1) 2015
Cryptographic primitives and cryptanalysis › authenticated encryption
GCM
0.212015
Twisted Polynomials and Forgery Attacks on GCM · EUROCRYPT (1) 2015
Cryptographic primitives and cryptanalysis
leakage-resilient cryptography
0.212015
How Secure is AES Under Leakage · ASIACRYPT (2) 2015
Hardware security and side channels
side-channel attack
0.222015
Beyond the Limits of DPA: Combined Side-Channel Collision Attacks · IEEE Trans. Computers 2012
How Secure is AES Under Leakage · ASIACRYPT (2) 2015
Cryptographic primitives and cryptanalysis › cryptographic foundations › cryptographic models
indifferentiability
0.212013
On the Indifferentiability of Key-Alternating Ciphers · CRYPTO (1) 2013
Cryptographic primitives and cryptanalysis › symmetric cryptography
online ciphers
0.212013
Parallelizable and Authenticated Online Ciphers · ASIACRYPT (1) 2013
Hardware security and side channels
side-channel resistance
0.212013
Fides: Lightweight Authenticated Cipher with Side-Channel Resistance for Constrained Hardware · CHES 2013
Cryptographic primitives and cryptanalysis › hash functions › hash function constructions
sponge construction
0.212013
SPONGENT: The Design Space of Lightweight Cryptographic Hashing · IEEE Trans. Computers 2013
Hardware security and side channels › side-channel attack › power analysis
differential power analysis
0.112012
Beyond the Limits of DPA: Combined Side-Channel Collision Attacks · IEEE Trans. Computers 2012
Cryptographic primitives and cryptanalysis › block cipher
integral distinguisher
0.112012
Integral and Multidimensional Linear Distinguishers with Correlation Zero · ASIACRYPT 2012
Cryptographic primitives and cryptanalysis
provable security
0.112012
Key-Alternating Ciphers in a Provable Setting: Encryption Using a Small Number of Public Permutations - (Extended Abstract) · EUROCRYPT 2012
Cryptographic primitives and cryptanalysis › block cipher cryptanalysis
biclique cryptanalysis
0.112011
Biclique Cryptanalysis of the Full AES · ASIACRYPT 2011
Cryptographic primitives and cryptanalysis
encryption
0.122014
How to Securely Release Unverified Plaintext in Authenticated Encryption · ASIACRYPT (1) 2014
Parallelizable and Authenticated Online Ciphers · ASIACRYPT (1) 2013
Cryptographic primitives and cryptanalysis › block cipher
DES
0.112017
Linear Cryptanalysis of DES with Asymmetries · ASIACRYPT (1) 2017
Cryptographic primitives and cryptanalysis › public-key cryptography
elliptic curve cryptography
0.112008
Time-Area Optimized Public-Key Engines: -Cryptosystems as Replacement for Elliptic Curves? · CHES 2008
Cryptographic primitives and cryptanalysis
public-key cryptography
0.112008
Time-Area Optimized Public-Key Engines: -Cryptosystems as Replacement for Elliptic Curves? · CHES 2008
Cryptographic primitives and cryptanalysis › public-key cryptography › elliptic curve cryptography
scalar multiplication
0.112008
Time-Area Optimized Public-Key Engines: -Cryptosystems as Replacement for Elliptic Curves? · CHES 2008

Methods — techniques the papers use, named apart from their topics

spectrum encoder · 2.0diffusion transformer · 2.0contrastive learning · 2.0block cipher design · 0.4security analysis · 0.3differential cryptanalysis · 0.3linear cryptanalysis · 0.3twisted polynomials · 0.2key recovery reduction · 0.2black-box security · 0.2side-channel countermeasures · 0.2indifferentiability framework · 0.2authenticated encryption · 0.2sponge construction · 0.1hardware-assisted cryptanalysis · 0.1
YearPublicationVenuePosition
2026 MetaDiT: Enabling Fine-grained Constraints in High-degree-of Freedom Metasurface Design
abstract
Metasurfaces are ultrathin, engineered materials composed of nanostructures that manipulate light in ways unattainable by natural materials. Recent advances have leveraged computational optimization, machine learning, and deep learning to automate their design. However, existing approaches exhibit two fundamental limitations: (1) they often restrict the model to generating only a subset of design parameters, and (2) they rely on heavily downsampled spectral targets, which compromises both the novelty and accuracy of the resulting structures. The core challenge lies in developing a generative model capable of exploring a large, unconstrained design space while precisely capturing the intricate physical relationships between material parameters and their high-resolution spectral responses. In this paper, we introduce MetaDiT, a novel framework for high-fidelity metasurface design that addresses these limitations. Our approach leverages a robust spectrum encoder pretrained with contrastive learning, providing strong conditional guidance to a Diffusion Transformer-based backbone. Experiments demonstrate that MetaDiT outperforms existing baselines in spectral accuracy, we further validate our method through extensive ablation studies.
Andrey Bogdanov
AAAI2
2024 The COLM Authenticated Encryption Scheme
Elena Andreeva 0001, Andrey Bogdanov, Nilanjan Datta, Atul Luykx, Bart Mennink, Mridul Nandi, Elmar Tischhauser, Kan Yasuda
J. Cryptol.2
2020 Troika: a ternary cryptographic hash function
Stefan Kölbl, Elmar Tischhauser, Patrick Derbez, Andrey Bogdanov
Des. Codes Cryptogr.4
2017 Linear Cryptanalysis of DES with Asymmetries
Andrey Bogdanov, Philip S. Vejre
ASIACRYPT (1)1
2016 Towards Practical Whitebox Cryptography: Optimizing Efficiency and Space Hardness
Andrey Bogdanov, Takanori Isobe 0001, Elmar Tischhauser
ASIACRYPT (1)1
2016 Integrals Go Statistical: Cryptanalysis of Full Skipjack Variants
Meiqin Wang 0001, Tingting Cui, Huaifeng Chen, Ling Sun 0001, Long Wen 0002, Andrey Bogdanov
FSE6
2016 Hold Your Breath, PRIMATEs Are Lightweight
Danilo Sijacic, Andreas B. Kidmose, Bohan Yang 0001, Subhadeep Banik, Begül Bilgin, Andrey Bogdanov, Ingrid Verbauwhede
SAC6
2015 Midori: A Block Cipher for Low Energy
Subhadeep Banik, Andrey Bogdanov, Takanori Isobe 0001, Kyoji Shibutani, Harunaga Hiwatari, Toru Akishita, Francesco Regazzoni 0001
ASIACRYPT (2)2
2015 How Secure is AES Under Leakage
Andrey Bogdanov, Takanori Isobe 0001
ASIACRYPT (2)1
2015 White-Box Cryptography Revisited: Space-Hard Ciphers
abstract
The need for software security in untrusted environments is ever increasing. White-box cryptography aims to ensure the security of cryptographic algorithms when the attacker has full access to their implementations. However, there is no secure white-box implementation of standard block ciphers such as DES and AES known to date: All published techniques have been practically broken. In this paper, we revisit white-box cryptography and propose a family of white-box secure block ciphers SPACE with several novel features. The design of SPACE is such that the key-extraction security in the white box reduces to the well-studied problem of key recovery for block ciphers (AES in our example) in the standard black-box setting. Moreover, to mitigate code lifting, we introduce the notion of space hardness. It measures the difficulty of compressing the white-box implementation of a cipher, and quantifies security against code lifting by the amount of code that needs to be extracted from the implementation by a white-box attacker to maintain its functionality. SPACE includes several variants with different white-box code sizes. Therefore, it is applicable to a wide range of environments and use cases. One of the variants called N-SPACE can be implemented with different code sizes while keeping the cipher itself unchanged.
Andrey Bogdanov, Takanori Isobe 0001
CCS1
2015 Twisted Polynomials and Forgery Attacks on GCM
Mohamed Ahmed Abdelraheem, Peter Beelen, Andrey Bogdanov, Elmar Tischhauser
EUROCRYPT (1)3
2015 Comb to Pipeline: Fast Software Encryption Revisited
Andrey Bogdanov, Martin M. Lauridsen, Elmar Tischhauser
FSE1
2015 Exploring Energy Efficiency of Lightweight Block Ciphers
Subhadeep Banik, Andrey Bogdanov, Francesco Regazzoni 0001
SAC2
2015 Fast and Memory-Efficient Key Recovery in Side-Channel Attacks
Andrey Bogdanov, Ilya Kizhvatov, Kamran Manzoor, Elmar Tischhauser, Marc Witteman
SAC1
2014 Route 66: Passively Breaking All GSM Channels
Philip S. Vejre, Andrey Bogdanov
ACISP2
2014 On the (In)Equivalence of Impossible Differential and Zero-Correlation Distinguishers for Feistel- and Skipjack-Type Ciphers
Céline Blondeau, Andrey Bogdanov
ACNS2
2014 How to Securely Release Unverified Plaintext in Authenticated Encryption
Elena Andreeva 0001, Andrey Bogdanov, Atul Luykx, Bart Mennink, Nicky Mouha, Kan Yasuda
ASIACRYPT (1)2
2014 APE: Authenticated Permutation-Based Encryption for Lightweight Cryptography
Elena Andreeva 0001, Begül Bilgin, Andrey Bogdanov, Atul Luykx, Bart Mennink, Nicky Mouha, Kan Yasuda
FSE3
2014 Linear hulls with correlation zero and linear cryptanalysis of block ciphers
Andrey Bogdanov, Vincent Rijmen
Des. Codes Cryptogr.1
2014 Towards the optimality of Feistel ciphers with substitution-permutation functions
Kyoji Shibutani, Andrey Bogdanov
Des. Codes Cryptogr.2
2014 Multidimensional zero-correlation attacks on lightweight block cipher HIGHT: Improved cryptanalysis of an ISO standard
abstract
HIGHT is a block cipher designed in Korea with the involvement of Korea Information Security Agency. It was proposed at CHES 2006 for usage in lightweight applications such as sensor networks and RFID tags. Lately, it has been adopted as ISO standard. Though there is a great deal of cryptanalytic results on HIGHT, its security evaluation against the recent zero-correlation linear attacks is still lacking. At the same time, the Feistel-type structure of HIGHT suggests that it might be susceptible to this type of cryptanalysis. In this paper, we aim to bridge this gap. We identify zero-correlation linear approximations over 16 rounds of HIGHT. Based upon those, we attack 27-round HIGHT (round 4 to round 30) with improved time complexity and practical memory requirements. This attack of ours is the best result on HIGHT to date in the classical single-key setting. We also provide the first attack on 26-round HIGHT (round 4 to round 29) with the full whitening key.
Long Wen 0002, Andrey Bogdanov, Huaifeng Chen
Inf. Process. Lett.3
2013 Parallelizable and Authenticated Online Ciphers
Elena Andreeva 0001, Andrey Bogdanov, Atul Luykx, Bart Mennink, Elmar Tischhauser, Kan Yasuda
ASIACRYPT (1)2
2013 Key Difference Invariant Bias in Block Ciphers
Andrey Bogdanov, Christina Boura, Vincent Rijmen, Long Wen 0002
ASIACRYPT (1)1
2013 Fides: Lightweight Authenticated Cipher with Side-Channel Resistance for Constrained Hardware
Begül Bilgin, Andrey Bogdanov, Miroslav Knezevic, Florian Mendel, Qingju Wang 0001
CHES2
2013 On the Indifferentiability of Key-Alternating Ciphers
Elena Andreeva 0001, Andrey Bogdanov, Yevgeniy Dodis, Bart Mennink, John P. Steinberger
CRYPTO (1)2
2013 Bounds in Shallows and in Miseries
Céline Blondeau, Andrey Bogdanov, Gregor Leander
CRYPTO (1)2
2013 Towards Understanding the Known-Key Security of Block Ciphers
Elena Andreeva 0001, Andrey Bogdanov, Bart Mennink
FSE2
2013 ALE: AES-Based Lightweight Authenticated Encryption
Andrey Bogdanov, Florian Mendel, Francesco Regazzoni 0001, Vincent Rijmen, Elmar Tischhauser
FSE1
2013 On the Wrong Key Randomisation and Key Equivalence Hypotheses in Matsui's Algorithm 2
Andrey Bogdanov, Elmar Tischhauser
FSE1
2013 Zero-Correlation Linear Cryptanalysis with FFT and Improved Attacks on ISO Standards Camellia and CLEFIA
Andrey Bogdanov, Huizheng Geng, Long Wen 0002, Baudoin Collard
Selected Areas in Cryptography1
2013 Generalized Feistel networks revisited
Andrey Bogdanov, Kyoji Shibutani
Des. Codes Cryptogr.1
2013 SPONGENT: The Design Space of Lightweight Cryptographic Hashing
abstract
The design of secure yet efficiently implementable cryptographic algorithms is a fundamental problem of cryptography. Lately, lightweight cryptography--optimizing the algorithms to fit the most constrained environments--has received a great deal of attention, the recent research being mainly focused on building block ciphers. As opposed to that, the design of lightweight hash functions is still far from being well investigated with only few proposals in the public domain. In this paper, we aim to address this gap by exploring the design space of lightweight hash functions based on the sponge construction instantiated with present-type permutations. The resulting family of hash functions is called spongent. We propose 13 spongent variants--or different levels of collision and (second) preimage resistance as well as for various implementation constraints. For each of them, we provide several ASIC hardware implementations--ranging from the lowest area to the highest throughput. We make efforts to address the fairness of comparison with other designs in the field by providing an exhaustive hardware evaluation on various technologies, including an open core library. We also prove essential differential properties of spongent permutations, give a security analysis in terms of collision and preimage resistance, as well as study in detail dedicated linear distinguishers.
Andrey Bogdanov, Miroslav Knezevic, Gregor Leander, Deniz Toz, Kerem Varici, Ingrid Verbauwhede
IEEE Trans. Computers1
2012 Integral and Multidimensional Linear Distinguishers with Correlation Zero
Andrey Bogdanov, Gregor Leander, Kaisa Nyberg
ASIACRYPT1
2012 Key-Alternating Ciphers in a Provable Setting: Encryption Using a Small Number of Public Permutations - (Extended Abstract)
Andrey Bogdanov, Lars R. Knudsen, Gregor Leander, François-Xavier Standaert, John P. Steinberger, Elmar Tischhauser
EUROCRYPT1
2012 Zero Correlation Linear Cryptanalysis with Reduced Data Complexity
Andrey Bogdanov
FSE1
2012 The provable constructive effect of diffusion switching mechanism in CLEFIA-type block ciphers
Qingju Wang 0001, Andrey Bogdanov
Inf. Process. Lett.2
2012 Beyond the Limits of DPA: Combined Side-Channel Collision Attacks
abstract
The problem of extracting the highest possible amount of key-related information using the lowest possible number of measurements is one of the central questions in side-channel attacks against embedded implementations of cryptographic algorithms. To address it, this work proposes a novel framework enhancing side-channel collision attacks with divide-and-conquer attacks such as differential power analysis (DPA). An information-theoretical metric is introduced for the evaluation of collision detection efficiency. Improved methods of dimension reduction for side-channel traces are developed based on a statistical model of euclidean distance. Experimental results confirm that DPA-combined collision attacks are superior to both DPA-only and collision-only attacks. The new methods of dimension reduction lead to further complexity improvements. All attacks are treated for the case of AES-128 and are practically validated on a widespread 8-bit RISC microcontroller.
Andrey Bogdanov, Ilya Kizhvatov
IEEE Trans. Computers1
2011 Double SP-Functions: Enhanced Generalized Feistel Networks - Extended Abstract
Andrey Bogdanov, Kyoji Shibutani
ACISP1
2011 Biclique Cryptanalysis of the Full AES
Andrey Bogdanov, Dmitry Khovratovich, Christian Rechberger
ASIACRYPT1
2011 spongent: A Lightweight Hash Function
Andrey Bogdanov, Miroslav Knezevic, Gregor Leander, Deniz Toz, Kerem Varici, Ingrid Verbauwhede
CHES1
2011 On unbalanced Feistel networks with contracting MDS diffusion
Andrey Bogdanov
Des. Codes Cryptogr.1
2011 Hardware SLE solvers: Efficient building blocks for cryptographic and cryptanalyticapplications
Andy Rupp, Thomas Eisenbarth 0001, Andrey Bogdanov, Oliver Grieb
Integr.3
2011 Analysis of 3-line generalized Feistel networks with double SD-functions
Andrey Bogdanov, Kyoji Shibutani
Inf. Process. Lett.1
2010 Differential Cache-Collision Timing Attacks on AES with Applications to Embedded CPUs
Andrey Bogdanov, Thomas Eisenbarth 0001, Christof Paar, Malte Wienecke
CT-RSA1
2010 On the differential and linear efficiency of balanced Feistel networks
Andrey Bogdanov
Inf. Process. Lett.1
2008 Fast multivariate signature generation in hardware: The case of rainbow
abstract
This paper presents a time-area efficient hardware architecture for the multivariate signature scheme Rainbow. As a part of this architecture, a high-performance hardware optimized variant of the well-known Gaussian elimination over GF(2l) and its efficient implementation are presented. The resulting signature generation core of Rainbow requires 63,593 gate equivalents and signs a message in just 804 clock cycles at 67 MHz using AMI 0.35μm CMOS technology. Thus, Rainbow provides significant performance improvements compared to RSA and ECDSA.
Sundar Balasubramanian, Harold W. Carter, Andrey Bogdanov, Andy Rupp, Jintai Ding
ASAP3
2008 Multiple-Differential Side-Channel Collision Attacks on AES
Andrey Bogdanov
CHES1
2008 Time-Area Optimized Public-Key Engines: -Cryptosystems as Replacement for Elliptic Curves?
Andrey Bogdanov, Thomas Eisenbarth 0001, Andy Rupp, Christopher Wolf
CHES1
2008 Hash Functions and RFID Tags: Mind the Gap
Andrey Bogdanov, Gregor Leander, Christof Paar, Axel Poschmann, Matthew J. B. Robshaw, Yannick Seurin
CHES1
2008 Fast Multivariate Signature Generation in Hardware: The Case of Rainbow
abstract
This paper deals with the design of an area-time efficient hardware architecture for the multivariate signature scheme, Rainbow. As a part of this architecture, a high-performance hardware optimized variant of the well-known Gaussian elimination over GF(2l) and its efficient implementation is presented. Besides solving LSEs, the architecture is also re-used for the linear transformation operations of the scheme, thereby saving on area. The resulting signature generation core of Rainbow requires 63,593 gate equivalents and signs a message in just 804 clock cycles. A comparison of our architecture with implementations of the RSA, the ECDSA and the en-TTS scheme shows that Rainbow in hardware provides significant performance improvements.
Sundar Balasubramanian, Andrey Bogdanov, Andy Rupp, Jintai Ding, Harold W. Carter
FCCM2
2007 Collision Attacks on AES-Based MAC: Alpha-MAC
Alex Biryukov, Andrey Bogdanov, Dmitry Khovratovich, Timo Kasper
CHES2
2007 A Hardware-Assisted Realtime Attack on A5/2 Without Precomputations
Andrey Bogdanov, Thomas Eisenbarth 0001, Andy Rupp
CHES1
2007 PRESENT: An Ultra-Lightweight Block Cipher
Andrey Bogdanov, Lars R. Knudsen, Gregor Leander, Christof Paar, Axel Poschmann, Matthew J. B. Robshaw, Yannick Seurin, C. Vikkelsoe
CHES1
2007 Linear Slide Attacks on the KeeLoq Block Cipher
Andrey Bogdanov
Inscrypt1
2006 A Parallel Hardware Architecture for fast Gaussian Elimination over GF(2)
abstract
This paper presents a hardware-optimized variant of the well-known Gaussian elimination over GF(2) and its highly efficient implementation. The proposed hardware architecture can solve any regular and (uniquely solvable) overdetermined linear system of equations (LSE) and is not limited to matrices of a certain structure. Besides solving LSEs, the architecture at hand can also accomplish the related problem of matrix inversion extremely fast. Its average running time for n times n binary matrices with uniformly distributed entries equals 2n (clock cycles) as opposed to about frac14n3in software. The average running time remains very close to 2n for matrices with densities much greater or lower than 0.5. The architecture has a worst-case time complexity of O(n2) and also a space complexity of O(n2). With these characteristics the architecture is particularly suited to efficiently solve medium-sized LSEs as they for example appear in the cryptanalysis of certain stream cipher classes. Moreover, we propose a hardware-optimized algorithm for matrix-by-matrix multiplication over GF(2) which runs in linear time and quadratic space on a similar architecture. This opens up the possibility of building a more complex architecture for efficiently solving larger LSEs by means of Strassen's algorithm which could significantly improve the time complexity of algebraic attacks on various ciphers. As proof-of-concept we realized our architecture on a contemporary low-cost FPGA. The implementation for a 50 times 50 LSE can be clocked with a frequency of up to 300 MHz and computes the solution in 0.33 mus on average
Andrey Bogdanov, M. C. Mertens, Christof Paar, Jan Pelzl, Andy Rupp
FCCM1