Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Feasibility and Completeness of Cryptographic Tasks in the Quantum World

Serge Fehr, Jonathan I. Katz, Fang Song, Hong-Sheng Zhou, Vassilis Zikas

Published Jan 1, 2013• 19 citations
Publisher
DOI
10.1007/978-3-642-36594-2_16

Related papers

Completeness for Symmetric Two-Party Functionalities - Revisited.

Yehuda Lindell, Eran Omri, Hila Zarosim

Abstract. Understanding the minimal assumptions required for carrying out cryptographic tasks is one of the fundamental goals of theoretical cryptography. A rich body of work has been dedicated to understanding the complexity of cryptographic tasks in the context of (semi-honest) secure two-party computation. Much of this work has focused on the characterization of trivial and complete functionalities (resp., functionalities that can be securely implemented unconditionally, and functionalities that can be used to securely compute all functionalities). All previous works define reductions via an ideal implementation of the functionality; i.e., f reduces to g if one can implement f using an ideal box (or oracle) that computes the function g and returns the output to both parties. Such a reduction models the computation of f as an atomic operation. However, in the real-world, protocols proceed in rounds, and the output is not learned by the parties simultaneously. In this paper we show that this distinction is significant. Specifically, we show that there exist symmetric functionalities (where both parties receive the same outcome), that are neither trivial nor complete under “ideal-box reductions”, and yet the existence of a constant-round protocol for securely computing such a functionality implies infinitely-often oblivious transfer (meaning that it is secure for infinitely-many n’s). In light of the above, we propose an alternative definitional infrastructure for studying the triviality and completeness of functionalities. 1

•Jan 1, 2014•0 citations

Quantum computation and cryptography: an overview

Manuel Calixto

Natural Computing•Aug 14, 2008•9 citations

Development of Quantum Safe Polynomial‐Based Cryptography in Classical and Quantum Framework

Taniya Hasija, K. R. Ramkumar, Bhupendra Singh

ABSTRACT The advent of quantum computers has brought forth a substantial danger to the security of current cryptographic algorithms, necessitating the development of quantum‐resistant algorithms to ensure data protection. The encryption method proposed in this article uses polynomials and is intended to counter key size‐based attacks. This paper brings a novel method of using polynomial interpolations for encryption and decryption, and the proposed algorithm is implemented in both classical and quantum environments to check its feasibility and accuracy. To ensure protection from the outside world, the proposed technique is applied in key generation, encryption, decryption, and confusion‐diffusion modules. This article also tabulated the National Institute of Standard and Technology (NIST) test suit results for randomness acceptability criteria and compares the new algorithm with the Kyber algorithm. While quantum computers are believed to excel in tasks like factorization and optimization, this paper is the first to explore cryptography algorithms in a quantum environment, opening new research possibilities for future cryptographic developments.

Internet Technology Letters•Nov 26, 2024•2 citations

Cryptography in a Quantum World

Gilles Brassard A

arXiv:1510.04256•Lecture notes in computer science•Jan 1, 2016•5 citations

Quantum cryptography: from theory to practice

Eleni Diamanti

•Feb 1, 2014•3 citations

An efficient and secure undeniable signature scheme based on ring learning with error

Akanksha Singh, Harish Chandra, Saurabh Rana

This paper, proposes a novel undeniable signature scheme based on the ring learning with errors (RLWE) problem, a complex lattice problem. In our scheme, authentic signatures can be validated via an interactive protocol, which guarantees that adversaries cannot forge signatures. Moreover, it ensures that honest participants consistently finish the verification procedure. Thus, the scheme is a strong and effective quantum-resistant undeniable signature scheme. Our security analysis, demonstrates resilience against both classical and quantum adversaries, based on the RLWE problem's hardness assumptions. Additionally, the random Oracle model is utilised to evaluate our protocol's security, showing that our scheme satisfies important cryptographic properties like completeness, soundness, and unforgeability. Our work advances the feasibility of post-quantum undeniable signature schemes for real-world cryptographic applications.

International Journal of Ad Hoc and Ubiquitous Computing•Jan 1, 2026•1 citation
Abstract. Understanding the minimal assumptions required for carrying out cryptographic tasks is one of the fundamental goals of theoretical cryptography. A rich body of work has been dedicated to understanding the complexity of cryptographic tasks in the context of (semi-honest) secure two-party computation. Much of this work has focused on the characterization of trivial and complete functionalities (resp., functionalities that can be securely implemented unconditionally, and functionalities that can be used to securely compute all functionalities). All previous works define reductions via an ideal implementation of the functionality; i.e., f reduces to g if one can implement f using an ideal box (or oracle) that computes the function g and returns the output to both parties. Such a reduction models the computation of f as an atomic operation. However, in the real-world, protocols proceed in rounds, and the output is not learned by the parties simultaneously. In this paper we show that this distinction is significant. Specifically, we show that there exist symmetric functionalities (where both parties receive the same outcome), that are neither trivial nor complete under “ideal-box reductions”, and yet the existence of a constant-round protocol for securely computing such a functionality implies infinitely-often oblivious transfer (meaning that it is secure for infinitely-many n’s). In light of the above, we propose an alternative definitional infrastructure for studying the triviality and completeness of functionalities. 1
ABSTRACT The advent of quantum computers has brought forth a substantial danger to the security of current cryptographic algorithms, necessitating the development of quantum‐resistant algorithms to ensure data protection. The encryption method proposed in this article uses polynomials and is intended to counter key size‐based attacks. This paper brings a novel method of using polynomial interpolations for encryption and decryption, and the proposed algorithm is implemented in both classical and quantum environments to check its feasibility and accuracy. To ensure protection from the outside world, the proposed technique is applied in key generation, encryption, decryption, and confusion‐diffusion modules. This article also tabulated the National Institute of Standard and Technology (NIST) test suit results for randomness acceptability criteria and compares the new algorithm with the Kyber algorithm. While quantum computers are believed to excel in tasks like factorization and optimization, this paper is the first to explore cryptography algorithms in a quantum environment, opening new research possibilities for future cryptographic developments.
This paper, proposes a novel undeniable signature scheme based on the ring learning with errors (RLWE) problem, a complex lattice problem. In our scheme, authentic signatures can be validated via an interactive protocol, which guarantees that adversaries cannot forge signatures. Moreover, it ensures that honest participants consistently finish the verification procedure. Thus, the scheme is a strong and effective quantum-resistant undeniable signature scheme. Our security analysis, demonstrates resilience against both classical and quantum adversaries, based on the RLWE problem's hardness assumptions. Additionally, the random Oracle model is utilised to evaluate our protocol's security, showing that our scheme satisfies important cryptographic properties like completeness, soundness, and unforgeability. Our work advances the feasibility of post-quantum undeniable signature schemes for real-world cryptographic applications.