research-article

On Non-Completeness in Threshold Implementations

Author:

George PetridesAuthors Info & Claims

TIS'19: Proceedings of ACM Workshop on Theory of Implementation Security Workshop

Pages 24 - 28

https://doi.org/10.1145/3338467.3358951

Published: 11 November 2019 Publication History

Get Access

Abstract

In this note we study non-completeness, the key property of Threshold Implementations (TIs). TIs have proved to be a popular method for mitigating side-channel leakage of sensitive information in hardware implementations of cryptographic algorithms.

In particular, we provide a reformulation of non-completeness in terms of set coverings with constraints, and describe a strategy for constructing small such coverings for given parameters.

Our obtained results enable the second order secure hardware implementation of algorithms with cubic functions as components, such as AES and inversion in GF(24), without the need for further decompositions.

References

[1]

Victor Arribas, Begül Bilgin, George Petrides, Svetla Nikova, and Vincent Rijmen. 2018. Rhythmic Keccak: SCA Security and Low Latency in HW. IACR Transactions on Cryptographic Hardware and Embedded Systems, Vol. 2018, 1 (2018), 269--290. https://doi.org/10.13154/tches.v2018.i1.269--290

Crossref

Google Scholar

[2]

Begül Bilgin, Benedikt Gierlichs, Svetla Nikova, Ventzislav Nikov, and Vincent Rijmen. 2014. Higher-order Threshold Implementations. In Proceedings of ASIACRYPT . Lecture Notes in Computer Science, Vol. 8874. 326--343. https://doi.org/10.1007/978-3-662-45608-8_18

Crossref

Google Scholar

[3]

Begül Bilgin, Benedikt Gierlichs, Svetla Nikova, Ventzislav Nikov, and Vincent Rijmen. 2015. Trade-Offs for Threshold Implementations Illustrated on AES. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, Vol. 34, 7 (2015), 1188--1200. https://doi.org/10.1109/TCAD.2015.2419623

Crossref

Google Scholar

[4]

Thomas De Cnudde, Begül Bilgin, Oscar Reparaz, Ventzislav Nikov, and Svetla Nikova. 2015. Higher-Order Threshold Implementation of the AES S-Box. In Proceedings of CARDIS. Lecture Notes in Computer Science, Vol. 9514. 259--272. https://doi.org/10.1007/978-3-319-31271-2_16

Digital Library

Google Scholar

[5]

Karin Gandolfi, Christophe Mourtel, and Francis Olivier. 2001. Electromagnetic Analysis: Concrete Results. In Proceedings of CHES. Lecture Notes in Computer Science, Vol. 2162. 251--261. https://doi.org/10.1007/3-540-44709-1_21

Crossref

Google Scholar

[6]

Paul Kocher, Joshua Jaffe, and Benjamin Jun. 1999. Differential Power Analysis. In Proceedings of CRYPTO. Lecture Notes in Computer Science, Vol. 1666. 388--397. https://doi.org/10.1007/3-540-48405-1_25

Crossref

Google Scholar

[7]

Lauren De Meyer, Begül Bilgin, and Oscar Reparaz. 2019. Consolidating Security Notions in Hardware Masking. IACR Transactions on Cryptographic Hardware and Embedded Systems, Vol. 2019, 3 (2019), 119--147. https://doi.org/10.13154/tches.v2019.i3.119--147

Crossref

Google Scholar

[8]

Svetla Nikova, Christian Rechberger, and Vincent Rijmen. 2006. Threshold Implementations Against Side-channel Attacks and Glitches. In Proceedings of ICICS. Lecture Notes in Computer Science, Vol. 4307. 529--545. https://doi.org/10.1007/11935308_38

Digital Library

Google Scholar

[9]

Svetla Nikova, Vincent Rijmen, and Martin Schläffer. 2008. Secure Hardware Implementation of Non-linear Functions in the Presence of Glitches. In Proceedings of ICICS. Lecture Notes in Computer Science, Vol. 5461. 218--234. https://doi.org/10.1007/978-3-642-00730-9_14

Digital Library

Google Scholar

[10]

Oscar Reparaz, Begül Bilgin, Svetla Nikova, Benedikt Gierlichs, and Ingrid Verbauwhede. 2015. Consolidating Masking Schemes. In Proceedings of CRYPTO. Lecture Notes in Computer Science, Vol. 9215. 764--783. https://doi.org/10.1007/978-3-662-47989-6_37

Crossref

Google Scholar

Cited By

View all

Piccione EAndreoli SBudaghyan LCarlet CDhooghe SNikova SPetrides GRijmen V(2023)An Optimal Universal Construction for the Threshold Implementation of Bijective S-BoxesIEEE Transactions on Information Theory10.1109/TIT.2023.328753469:10(6700-6710)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3287534
Petrides G(2022)On decompositions of permutation polynomials into quadratic and cubic power permutationsCryptography and Communications10.1007/s12095-022-00600-815:1(199-207)Online publication date: 18-Jul-2022
https://doi.org/10.1007/s12095-022-00600-8
Arribas VZhang ZNikova S(2021)LLTI: Low-Latency Threshold ImplementationsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2021.312352716(5108-5123)Online publication date: 2021
https://doi.org/10.1109/TIFS.2021.3123527

Index Terms

On Non-Completeness in Threshold Implementations
1. Security and privacy
  1. Security in hardware
    1. Hardware attacks and countermeasures
      1. Side-channel analysis and countermeasures

Recommendations

Threshold Implementations in the Robust Probing Model
TIS'19: Proceedings of ACM Workshop on Theory of Implementation Security Workshop

Threshold Implementations (TI) are provably secure algorithmic countermeasures against side-channel attacks in the form of differential power analysis. The strength of TI lies in its minimal algorithmic requirements. These requirements have been studied ...
On Non-uniformity in Threshold Sharings
TIS '16: Proceedings of the 2016 ACM Workshop on Theory of Implementation Security

In threshold schemes one represents each sensitive variable by a number n of shares such that their (usually) bitwise sum equals that variable. These shares are initially generated in such a way that any subset of n-1 shares gives no information about ...
On Secure and Side-Channel Resistant Hardware Implementations of Post-Quantum Cryptography
ARES '22: Proceedings of the 17th International Conference on Availability, Reliability and Security

Currently, many post-quantum cryptography schemes have been implemented on various hardware platforms in order to provide efficient solutions in cybersecurity services. As researchers and hardware developers focus primarily on designs providing small ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

TIS'19: Proceedings of ACM Workshop on Theory of Implementation Security Workshop

November 2019

43 pages

ISBN:9781450368278

DOI:10.1145/3338467

Program Chairs:
Begül Bilgin
Rambus-Cryptography Research, NL
,
Svetla Petkova-Nikova
KU Leuven, Belgium
,
Vincent Rijmen
KU Leuven, Belgium

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 November 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Norges Forskningsråd

Conference

CCS '19

Sponsor:

SIGSAC

CCS '19: 2019 ACM SIGSAC Conference on Computer and Communications Security

November 11, 2019

London, United Kingdom

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
125
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)5

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Piccione EAndreoli SBudaghyan LCarlet CDhooghe SNikova SPetrides GRijmen V(2023)An Optimal Universal Construction for the Threshold Implementation of Bijective S-BoxesIEEE Transactions on Information Theory10.1109/TIT.2023.328753469:10(6700-6710)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3287534
Petrides G(2022)On decompositions of permutation polynomials into quadratic and cubic power permutationsCryptography and Communications10.1007/s12095-022-00600-815:1(199-207)Online publication date: 18-Jul-2022
https://doi.org/10.1007/s12095-022-00600-8
Arribas VZhang ZNikova S(2021)LLTI: Low-Latency Threshold ImplementationsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2021.312352716(5108-5123)Online publication date: 2021
https://doi.org/10.1109/TIFS.2021.3123527

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Threshold Implementations in the Robust Probing Model

On Non-uniformity in Threshold Sharings

On Secure and Side-Channel Resistant Hardware Implementations of Post-Quantum Cryptography

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Funding Sources

Conference

Upcoming Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations