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

Secure information transmission based on physical principles

Dima Yu. Grigoriev, Vladimir Shpilrain

Published Jan 1, 2013• 0 citations
OpenAlex

Abstract

Abstract. We employ physical properties of the real world to design a protocol for secure information transmission where one of the parties is able to transmit secret information to another party over an insecure channel, without any prior secret arrangements between the parties. The distinctive feature of this protocol, compared to all known public-key cryptographic protocols, is that neither party uses a one-way function. In particular, our protocol is secure against (passive) computationally unbounded adversary. 1

Related papers

Yao’s Millionaires’ Problem and Public-Key Encryption Without Computational Assumptions

Dima Yu. Grigoriev, László B. Kish, Vladimir Shpilrain

We offer efficient and practical solutions of Yao’s millionaires’ problem without using any one-way functions. Some of the solutions involve physical principles, while others are purely mathematical. One of our solutions (based on physical principles) yields a public-key encryption protocol secure against (passive) computationally unbounded adversary. In that protocol, the legitimate parties are not assumed to be computationally unbounded.

International Journal of Foundations of Computer Science•Jun 1, 2017•9 citations

Contributions to Information Theoretically Secure Communication

Setareh Sharifian

Secure communication ensures the integrity and confidentiality of communication between connected devices. An information-theoretic approach to secure communication gives the strongest confidentiality guarantee by assuming that the attacker has unlimited computing power. The earliest formal model and definition of information-theoretic secure communication is by Shannon, who employed a secret key shared between communicating parties to provide confidentiality. An alternative elegant information-theoretic approach to secure communication views the natural characteristics of the environment (i.e., channel’s noise) as a resource to build security functionalities. This approach was first proposed by Wyner, and the corresponding secure communication model is called the wiretap channel model. These two approaches introduce two primary resources for providing information-theoretic secure communication: the shared secret key and physical properties of the communication medium. In this thesis, we study how to employ the above two resources for secure message transmission. We study this by using channel’s noise in the wiretap channel model. In this model, a sender is connected to the receiver and the adversary through two noisy channels. We propose a new wiretap encoding scheme with strong secrecy that provides perfect secrecy and reliability, asymptotically. The construction treats the noise in the adversary’s channel as a source of randomness that is extracted and used to hide the message from the adversary. We realize the wiretap channel model using cooperative jamming to evaluate the performance of wiretap codes in practice. We consider a model called keyed wiretap channel that unifies Wyner’s model with Shannon’s model of perfect secrecy for information systems, and propose a keyed encoding schemes with strong secrecy and other properties that are attractive in practice. We also study two-party information-theoretic secret key agreement when the two parties have access to samples of a common source of randomness and use a single message transmission to arrive at a shared random key. We propose a secret key agreement protocol in this setting, prove its security, and show its superior performance compared to other known protocols with the same properties. Finally, we propose an information-theoretic secret key agreement over a virtual wiretap channel created by cooperative jamming.

•May 15, 2020•0 citations

Decoy-based information security

Vladimir Shpilrain

Abstract In this survey, we discuss an emerging concept of decoy-based information security, or security without computational assumptions. In particular, we show how this concept can be implemented to provide security against (passive) computationally unbounded adversary in some public-key encryption protocols. In the world of symmetric cryptography, decoy-based security finds a wide range of applications, notably to secure delegation of computation to another party. We single out the scenario where a computationally limited party wants to send an encrypted message to a computationally superior party using the RSA protocol, thereby providing another kind of application of decoy ideas in a public-key setting. With typical RSA parameters, decoy-based method of delegation of computation improves the efficiency for the sender by several orders of magnitude.

journal of Groups complexity cryptology•Jan 1, 2014•0 citations

Transmit Classical and Quantum Information Secretly

Li Yang, Ling-An Wu

This note presents a practical cryptography protocol for transmitting classical and quantum information secretly and directly.

arXiv:quant-ph/0203089•Mar 18, 2002•6 citations

Counterfactual Quantum Cryptography

Tae-Gon Noh

Quantum cryptography allows one to distribute a secret key between two remote parties using the fundamental principles of quantum mechanics. The well-known established paradigm for the quantum key distribution relies on the actual transmission of signal particle through a quantum channel. In this Letter, we show that the task of a secret key distribution can be accomplished even though a particle carrying secret information is not in fact transmitted through the quantum channel. The proposed protocols can be implemented with current technologies and provide practical security advantages by eliminating the possibility that an eavesdropper can directly access the entire quantum system of each signal particle.

arXiv:0809.3979•Physical Review Letters•Dec 1, 2009•251 citations

Secrecy without one-way functions

Dima Yu. Grigoriev, Vladimir Shpilrain

We show that some problems in information security can be solved without using one-way functions. The latter are usually regarded as a central concept of cryptography, but the very existence of one-way functions depends on difficult conjectures in complexity theory, most notably on the notorious “” conjecture. This is why cryptographic primitives that do not employ one-way functions are often called “unconditionally secure”. In this paper, we suggest protocols for secure computation of the sum, product, and some other functions of two or more elements of an arbitrary constructible ring, without using any one-way functions. A new input that we offer here is that, in contrast with other proposals, we conceal “intermediate results” of a computation. For example, when we compute the sum of k numbers, only the final result is known to the parties; partial sums are not known to anybody. Other applications of our method include voting/rating over insecure channels and a rather elegant and efficient solution of the “two millionaires problem”. Then, while it is fairly obvious that a secure (bit) commitment between two parties is impossible without a one-way function, we show that it is possible if the number of parties is at least 3. We also show how our unconditionally secure (bit) commitment scheme for three parties can be used to arrange an unconditionally secure (bit) commitment between just two parties if they use a “dummy” (e.g., a computer) as the third party. We explain how our concept of a “dummy” is different from the well-known concept of a “trusted third party”. Based on a similar idea, we also offer an unconditionally secure k - n oblivious transfer protocol between two parties who use a “dummy”. We also suggest a protocol, without using a one-way function, for the so-called “mental poker”, i.e., a fair card dealing (and playing) over distance. Finally, we propose a secret sharing scheme where an advantage over Shamir's and other known secret sharing schemes is that nobody, including the dealer, ends up knowing the shares (of the secret) owned by any particular player. It should be mentioned that computational cost of our protocols is negligible to the point that all of them can be executed without a computer.

arXiv:1301.5069•journal of Groups complexity cryptology•Jan 1, 2013•5 citations
Abstract. We employ physical properties of the real world to design a protocol for secure information transmission where one of the parties is able to transmit secret information to another party over an insecure channel, without any prior secret arrangements between the parties. The distinctive feature of this protocol, compared to all known public-key cryptographic protocols, is that neither party uses a one-way function. In particular, our protocol is secure against (passive) computationally unbounded adversary. 1
Secure communication ensures the integrity and confidentiality of communication between connected devices. An information-theoretic approach to secure communication gives the strongest confidentiality guarantee by assuming that the attacker has unlimited computing power. The earliest formal model and definition of information-theoretic secure communication is by Shannon, who employed a secret key shared between communicating parties to provide confidentiality. An alternative elegant information-theoretic approach to secure communication views the natural characteristics of the environment (i.e., channel’s noise) as a resource to build security functionalities. This approach was first proposed by Wyner, and the corresponding secure communication model is called the wiretap channel model. These two approaches introduce two primary resources for providing information-theoretic secure communication: the shared secret key and physical properties of the communication medium. In this thesis, we study how to employ the above two resources for secure message transmission. We study this by using channel’s noise in the wiretap channel model. In this model, a sender is connected to the receiver and the adversary through two noisy channels. We propose a new wiretap encoding scheme with strong secrecy that provides perfect secrecy and reliability, asymptotically. The construction treats the noise in the adversary’s channel as a source of randomness that is extracted and used to hide the message from the adversary. We realize the wiretap channel model using cooperative jamming to evaluate the performance of wiretap codes in practice. We consider a model called keyed wiretap channel that unifies Wyner’s model with Shannon’s model of perfect secrecy for information systems, and propose a keyed encoding schemes with strong secrecy and other properties that are attractive in practice. We also study two-party information-theoretic secret key agreement when the two parties have access to samples of a common source of randomness and use a single message transmission to arrive at a shared random key. We propose a secret key agreement protocol in this setting, prove its security, and show its superior performance compared to other known protocols with the same properties. Finally, we propose an information-theoretic secret key agreement over a virtual wiretap channel created by cooperative jamming.
Abstract In this survey, we discuss an emerging concept of decoy-based information security, or security without computational assumptions. In particular, we show how this concept can be implemented to provide security against (passive) computationally unbounded adversary in some public-key encryption protocols. In the world of symmetric cryptography, decoy-based security finds a wide range of applications, notably to secure delegation of computation to another party. We single out the scenario where a computationally limited party wants to send an encrypted message to a computationally superior party using the RSA protocol, thereby providing another kind of application of decoy ideas in a public-key setting. With typical RSA parameters, decoy-based method of delegation of computation improves the efficiency for the sender by several orders of magnitude.
Quantum cryptography allows one to distribute a secret key between two remote parties using the fundamental principles of quantum mechanics. The well-known established paradigm for the quantum key distribution relies on the actual transmission of signal particle through a quantum channel. In this Letter, we show that the task of a secret key distribution can be accomplished even though a particle carrying secret information is not in fact transmitted through the quantum channel. The proposed protocols can be implemented with current technologies and provide practical security advantages by eliminating the possibility that an eavesdropper can directly access the entire quantum system of each signal particle.
We show that some problems in information security can be solved without using one-way functions. The latter are usually regarded as a central concept of cryptography, but the very existence of one-way functions depends on difficult conjectures in complexity theory, most notably on the notorious “” conjecture. This is why cryptographic primitives that do not employ one-way functions are often called “unconditionally secure”. In this paper, we suggest protocols for secure computation of the sum, product, and some other functions of two or more elements of an arbitrary constructible ring, without using any one-way functions. A new input that we offer here is that, in contrast with other proposals, we conceal “intermediate results” of a computation. For example, when we compute the sum of k numbers, only the final result is known to the parties; partial sums are not known to anybody. Other applications of our method include voting/rating over insecure channels and a rather elegant and efficient solution of the “two millionaires problem”. Then, while it is fairly obvious that a secure (bit) commitment between two parties is impossible without a one-way function, we show that it is possible if the number of parties is at least 3. We also show how our unconditionally secure (bit) commitment scheme for three parties can be used to arrange an unconditionally secure (bit) commitment between just two parties if they use a “dummy” (e.g., a computer) as the third party. We explain how our concept of a “dummy” is different from the well-known concept of a “trusted third party”. Based on a similar idea, we also offer an unconditionally secure k - n oblivious transfer protocol between two parties who use a “dummy”. We also suggest a protocol, without using a one-way function, for the so-called “mental poker”, i.e., a fair card dealing (and playing) over distance. Finally, we propose a secret sharing scheme where an advantage over Shamir's and other known secret sharing schemes is that nobody, including the dealer, ends up knowing the shares (of the secret) owned by any particular player. It should be mentioned that computational cost of our protocols is negligible to the point that all of them can be executed without a computer.