Table of Contents

1. Introduction
2. What Is Post-Quantum Cryptography?
3. Quantum Threat to Classical Cryptography
4. Shor’s and Grover’s Algorithms
5. Timeline of Cryptographic Vulnerability
6. Goals of Post-Quantum Cryptography
7. Differences Between PQC and Quantum Cryptography
8. Criteria for PQC Schemes
9. NIST Standardization Project
10. Classes of PQC Algorithms
11. Lattice-Based Cryptography
12. Code-Based Cryptography
13. Multivariate Polynomial Cryptography
14. Hash-Based Cryptography
15. Isogeny-Based Cryptography
16. Symmetric Key Systems and Quantum Attacks
17. Hybrid Cryptography Approaches
18. PQC Digital Signatures
19. PQC Key Encapsulation Mechanisms (KEMs)
20. Real-World Deployment Challenges
21. Performance and Resource Constraints
22. Quantum-Resistant TLS/SSL
23. PQC in IoT and Embedded Systems
24. Migration Strategies
25. Conclusion

---

1. Introduction

Post-Quantum Cryptography (PQC) refers to cryptographic algorithms that are secure against the threat posed by quantum computers. Unlike quantum cryptography, PQC does not rely on quantum mechanics but is designed to resist attacks by quantum algorithms.

---

2. What Is Post-Quantum Cryptography?

PQC is the field of designing, analyzing, and standardizing cryptographic schemes that remain secure in the presence of a large-scale quantum computer. The focus is on public-key cryptography, which is most vulnerable.

---

3. Quantum Threat to Classical Cryptography

Quantum algorithms such as:

• Shor’s Algorithm can break RSA, ECC, and DH
• Grover’s Algorithm speeds up brute-force attacks

This renders much of today’s cryptographic infrastructure insecure in a quantum future.

---

4. Shor’s and Grover’s Algorithms

• Shor’s Algorithm solves integer factorization and discrete log problems in polynomial time.
• Grover’s Algorithm provides a quadratic speedup for brute-force search:
• Reduces symmetric key strength by half (e.g., AES-256 → AES-128 equivalence)

---

5. Timeline of Cryptographic Vulnerability

While large-scale quantum computers are not yet available, the data harvested today may be decrypted in the future — a threat known as “store now, decrypt later.”

---

6. Goals of Post-Quantum Cryptography

• Quantum resistance: Secure even with quantum adversaries
• Backwards compatibility: Deployable in current infrastructure
• Efficient: Reasonable performance on modern hardware

---

7. Differences Between PQC and Quantum Cryptography

Feature	Post-Quantum Crypto	Quantum Cryptography
Based on	Classical mathematics	Quantum physics
Hardware required	None (software only)	Quantum devices
Key distribution	Traditional	Quantum key distribution (QKD)
Maturity	Developing	Experimentally demonstrated

---

8. Criteria for PQC Schemes

• Security under quantum attacks
• Performance (speed, size, memory)
• Robustness and simplicity
• Proven cryptographic foundations
• Resistance to side-channel attacks

---

9. NIST Standardization Project

In 2016, NIST began a competition to standardize PQC schemes. In 2022, it announced Round 3 selections:

• Kyber (lattice-based) for key exchange
• Dilithium and Falcon for signatures
• SPHINCS+ (hash-based) as a fallback

---

10. Classes of PQC Algorithms

1. Lattice-based
2. Code-based
3. Multivariate polynomial
4. Hash-based
5. Isogeny-based

Each has different trade-offs in security, efficiency, and implementation complexity.

---

11. Lattice-Based Cryptography

Based on the hardness of lattice problems like:

• Shortest Vector Problem (SVP)
• Learning With Errors (LWE)

Pros:

• Efficient
• Strong security proofs

Examples:

• Kyber (KEM)
• Dilithium (Signature)

---

12. Code-Based Cryptography

Relies on the difficulty of decoding random linear codes.

Example: McEliece Cryptosystem
Pros:

• Long-standing resistance to quantum attacks
  Cons:
• Very large public keys

---

13. Multivariate Polynomial Cryptography

Uses multivariate quadratic equations over finite fields.

Example: Rainbow (broken in 2022)
Pros:

• Fast signature generation
  Cons:
• Key generation can be slow and bulky

---

14. Hash-Based Cryptography

Based on Merkle trees and cryptographic hash functions.

Example: SPHINCS+
Pros:

• Very conservative, minimal assumptions
  Cons:
• Large signature sizes

---

15. Isogeny-Based Cryptography

Based on elliptic curve isogenies.

Example: SIDH (Supersingular Isogeny Diffie-Hellman)
Pros:

• Very small keys
  Cons:
• SIDH was broken in 2022; trust in this class has diminished

---

16. Symmetric Key Systems and Quantum Attacks

Symmetric schemes like AES and SHA are quantum-resistant with larger key sizes:

• AES-256 is still safe
• Hash functions must be double the classical strength to resist Grover’s algorithm

---

17. Hybrid Cryptography Approaches

Combining classical and PQC schemes:

\[
\text{Hybrid Encryption} = \text{Classical KEM} + \text{PQC KEM}
\]

Used in TLS (e.g., Google Chrome and Cloudflare experiments)

---

18. PQC Digital Signatures

Crucial for:

• Software updates
• Code signing
• Identity verification

Standardized options: Dilithium, Falcon, SPHINCS+

---

19. PQC Key Encapsulation Mechanisms (KEMs)

Used in:

• TLS handshake
• VPN key exchanges
• Email encryption

Kyber is the leading candidate.

---

20. Real-World Deployment Challenges

• Larger key and signature sizes
• Compatibility with protocols like TLS, SSH, VPNs
• Speed vs memory trade-offs
• Implementation bugs and side channels

---

21. Performance and Resource Constraints

Some schemes (e.g., McEliece) require megabytes of memory, which is infeasible for embedded systems.

---

22. Quantum-Resistant TLS/SSL

• Google, Microsoft, and AWS have tested PQC-enhanced TLS
• Hybrid handshakes: Classical + PQC
• PQC integration into OpenSSL and TLS 1.3 is ongoing

---

23. PQC in IoT and Embedded Systems

• Resource-constrained devices (e.g., smart cards, sensors) require:
• Compact key sizes
• Low CPU usage
• Lightweight PQC schemes are being explored

---

24. Migration Strategies

Organizations should:

1. Inventory cryptographic dependencies
2. Use hybrid schemes during transition
3. Test and pilot PQC integrations
4. Stay updated with NIST and international standards

---

25. Conclusion

Post-Quantum Cryptography is essential for safeguarding digital infrastructure against future quantum threats. By using classical mathematics but quantum-resilient designs, PQC offers a practical path forward for modern cryptography. With ongoing standardization, real-world deployments, and growing industry support, PQC will soon become a foundational part of the security landscape in the quantum era.

---

Table of Contents

1. Introduction
2. What Is Bit Commitment?
3. Importance in Cryptography
4. Classical Bit Commitment
5. Quantum Approach to Bit Commitment
6. Hiding and Binding Properties
7. Quantum Mechanics and Bit Commitment
8. Early Quantum Bit Commitment Proposals
9. Lo-Chau No-Go Theorem
10. Mayers’ Impossibility Proof
11. The Impossibility of Unconditionally Secure QBC
12. Why Perfect Binding and Hiding Can’t Coexist
13. The Role of Quantum Entanglement
14. Mathematical Model of Bit Commitment
15. Cheating Strategies in Quantum Bit Commitment
16. Bit Commitment and No-Cloning Theorem
17. Bit Commitment with Trusted Third Parties
18. Relativistic Quantum Bit Commitment
19. Device-Independent Bit Commitment
20. Cheat-Sensitive Bit Commitment
21. Practical Considerations and Limitations
22. Theoretical Interest and Use Cases
23. Connections to Coin Flipping and Oblivious Transfer
24. Current Research Directions
25. Conclusion

---

1. Introduction

Quantum Bit Commitment (QBC) is a cryptographic task in which one party (Alice) commits to a bit \( b \in \{0,1\} \) in such a way that:

• She cannot change it later (binding), and
• The other party (Bob) cannot learn it before she reveals it (hiding).

QBC was once thought to be unconditionally secure using quantum mechanics, but this view has changed drastically.

---

2. What Is Bit Commitment?

It is a two-phase protocol:

1. Commit phase: Alice commits to a bit and gives Bob evidence of her commitment.
2. Reveal phase: Alice opens the commitment; Bob checks consistency with the original commitment.

---

3. Importance in Cryptography

Bit commitment is a foundational primitive for:

• Zero-knowledge proofs
• Secure multi-party computation
• Digital contracts
• Coin flipping protocols

---

4. Classical Bit Commitment

Achieved using:

• Hash functions (computational assumptions)
• Trusted third parties
• Timelock puzzles

But insecure against quantum adversaries if assumptions fail.

---

5. Quantum Approach to Bit Commitment

Initially, quantum protocols appeared to enable unconditionally secure bit commitment using:

• Superposition
• Quantum measurement disturbance
• No-cloning theorem

---

6. Hiding and Binding Properties

• Hiding: Bob cannot learn \( b \) before Alice opens it.
• Binding: Alice cannot change \( b \) after committing.

Quantum physics was hoped to provide both.

---

7. Quantum Mechanics and Bit Commitment

Quantum states seem to allow binding (due to disturbance) and hiding (due to uncertainty). But entanglement enables cheating strategies.

---

8. Early Quantum Bit Commitment Proposals

Early protocols (1990s) used:

• Polarized photons
• Quantum state encoding
• Measurement basis concealment

Believed to be unconditionally secure.

---

9. Lo-Chau No-Go Theorem

Lo and Chau (1997) proved that any protocol claiming to be perfectly hiding and binding is insecure if quantum entanglement is available.

---

10. Mayers’ Impossibility Proof

Dominic Mayers (1996–1997) proved no quantum bit commitment protocol can be both perfectly hiding and binding, without additional assumptions.

---

11. The Impossibility of Unconditionally Secure QBC

Due to quantum purifications, Alice can delay choosing a bit until the reveal phase using entanglement.

---

12. Why Perfect Binding and Hiding Can’t Coexist

The density matrix Bob receives must be the same for both bits (hiding), allowing Alice to delay measurement (breaking binding).

---

13. The Role of Quantum Entanglement

Alice prepares an entangled state:

\[
|\psi\rangle = \frac{1}{\sqrt{2}}(|0\rangle_A |0\rangle_B + |1\rangle_A |1\rangle_B)
\]

She can later project it to either basis — enabling cheating.

---

14. Mathematical Model of Bit Commitment

Let \( \rho_0 \) and \( \rho_1 \) be Bob’s reduced density matrices for bits 0 and 1.

If \( \rho_0 = \rho_1 \), it’s perfectly hiding. But this means Alice can steer the commitment during reveal.

---

15. Cheating Strategies in Quantum Bit Commitment

Using entangled ancilla and deferred measurement:

• Alice commits to a superposition
• Reveals either 0 or 1 by choosing measurement basis

---

16. Bit Commitment and No-Cloning Theorem

While no-cloning prevents Bob from copying qubits, it doesn’t prevent Alice from exploiting entanglement to cheat.

---

17. Bit Commitment with Trusted Third Parties

Adding a trusted third party allows for secure commitments. This is often used in semi-honest or honest-but-curious models.

---

18. Relativistic Quantum Bit Commitment

Protocols based on relativistic signaling constraints:

• Exploit the impossibility of faster-than-light communication
• Use multiple space-time separated agents

Example: Kent’s protocols

---

19. Device-Independent Bit Commitment

Uses violation of Bell inequalities to enforce commitment. Still limited by the no-go theorems unless assumptions are added.

---

20. Cheat-Sensitive Bit Commitment

If cheating is detected with some probability, the protocol can be useful in practice even if not unconditionally secure.

---

21. Practical Considerations and Limitations

• Device calibration
• Synchronization
• Photon loss and detection inefficiency
• Man-in-the-middle attacks

---

22. Theoretical Interest and Use Cases

Despite no-go theorems, QBC is valuable:

• Theoretically for understanding limits of quantum crypto
• Practically under assumptions (relativistic, cheat-sensitive)

---

23. Connections to Coin Flipping and Oblivious Transfer

• Bit commitment is often a component in other protocols.
• Its impossibility constrains unconditional fairness in related tasks.

---

24. Current Research Directions

• Exploring bounded quantum storage models
• Post-quantum secure commitment schemes
• Experimentally feasible cheat-sensitive protocols

---

25. Conclusion

Quantum bit commitment, once thought to be unconditionally secure, was later proven impossible under general conditions due to the power of entanglement and purification. However, relativistic and cheat-sensitive variants show promise for practical use. Understanding QBC helps map the limits of quantum cryptography and inspires novel cryptographic approaches grounded in physical principles.

---

Table of Contents

1. Introduction
2. What Is Coin Flipping in Cryptography?
3. Classical vs Quantum Coin Flipping
4. Applications of Coin Flipping Protocols
5. Types of Quantum Coin Flipping
6. Weak vs Strong Coin Flipping
7. Protocol Requirements
8. Quantum Properties Enabling Coin Flipping
9. Security Definitions
10. Bias in Coin Flipping
11. No-Go Theorems and Limits
12. The Lo-Chau Protocol
13. Ambainis’ Protocol
14. Chailloux-Kerenidis Protocol
15. Lower Bounds and Optimal Bias
16. Mathematical Formulation of Bias
17. Cheat Sensitivity
18. Quantum Coin Flipping and Bit Commitment
19. Realistic Implementation Challenges
20. Role in Quantum Cryptographic Primitives
21. Experimental Demonstrations
22. Comparison with Other Primitives
23. Device-Independent Coin Flipping
24. Current Research and Open Questions
25. Conclusion

---

1. Introduction

Quantum coin flipping is a cryptographic task where two parties — who do not trust each other — want to agree on a random bit (0 or 1) such that neither can bias the outcome unfairly. It leverages the laws of quantum mechanics to enhance fairness and prevent cheating.

---

2. What Is Coin Flipping in Cryptography?

It is a fundamental two-party protocol for generating a shared random outcome, useful for:

• Fair contract signing
• Game theory protocols
• Decision-making systems

---

3. Classical vs Quantum Coin Flipping

Feature	Classical Coin Flipping	Quantum Coin Flipping
Trust model	Requires assumptions	Physics-based
Bias resistance	Susceptible to cheating	Provably bounded
Unconditional security	Not possible	Limited but provable

---

4. Applications of Coin Flipping Protocols

• Cryptographic fairness
• Secure computation
• Dispute resolution
• Blockchain consensus enhancements

---

5. Types of Quantum Coin Flipping

1. Weak coin flipping: Each party has a preferred outcome; the goal is to prevent one party from forcing their outcome.
2. Strong coin flipping: Neither party knows the other’s preference; goal is mutual fairness and cheat-resistance.

---

6. Weak vs Strong Coin Flipping

Feature	Weak Coin Flipping	Strong Coin Flipping
Preference known	Yes	No
Fairness level	Lower	Higher
Complexity	Lower	Higher

---

7. Protocol Requirements

• Completeness: If both parties are honest, they agree on a fair coin.
• Soundness: Cheating parties cannot significantly bias the coin beyond a limit (bias \( \varepsilon \)).

---

8. Quantum Properties Enabling Coin Flipping

• Superposition
• Quantum entanglement
• No-cloning
• Measurement disturbance

These make it difficult for a party to hide cheating attempts.

---

9. Security Definitions

A coin flipping protocol has bias \( \varepsilon \) if no dishonest party can force the outcome with probability more than \( \frac{1}{2} + \varepsilon \).

---

10. Bias in Coin Flipping

• Bias \( \varepsilon = 0 \) → Perfect fairness (not achievable in practice)
• Goal is to minimize bias to the smallest possible under quantum mechanics

---

11. No-Go Theorems and Limits

• Lo and Chau (1997): Perfect quantum coin flipping (bias = 0) is impossible.
• Kitaev (2002): Strong coin flipping has a minimum achievable bias of \( \varepsilon \geq \frac{1}{\sqrt{2}} – \frac{1}{2} \approx 0.207 \)

---

12. The Lo-Chau Protocol

One of the earliest quantum coin flipping protocols:

• Uses quantum entanglement
• Detects deviation via honesty tests
• Highly theoretical; impractical due to complexity

---

13. Ambainis’ Protocol

A quantum protocol achieving:

• Bias of \( \varepsilon = 0.25 \)
• Simple structure using 3-round communication
• Based on quantum states indistinguishability

---

14. Chailloux-Kerenidis Protocol

Achieves optimal strong coin flipping:

• Bias \( \varepsilon = 0.207 \)
• Based on semidefinite programming optimization
• Proves Kitaev’s lower bound is tight

---

15. Lower Bounds and Optimal Bias

• Best known bias for strong coin flipping: 0.207 (tight bound)
• For weak coin flipping, arbitrarily small bias can be achieved theoretically (Mochon 2007)

---

16. Mathematical Formulation of Bias

Bias for dishonest party \( P \):
\[
\varepsilon_P = \max(|\Pr[\text{outcome}=0] – 0.5|, |\Pr[\text{outcome}=1] – 0.5|)
\]

Goal: \( \varepsilon_P \) as small as possible

---

17. Cheat Sensitivity

Quantum protocols can be made cheat-sensitive:

• Cheating is detected with nonzero probability
• Deterrent effect: parties are discouraged from deviation

---

18. Quantum Coin Flipping and Bit Commitment

Closely related:

• Bit commitment is often a sub-protocol of coin flipping
• Impossibility of perfect bit commitment leads to bounds on coin flipping fairness

---

19. Realistic Implementation Challenges

• Photon loss
• Detector inefficiency
• Timing issues
• Device calibration errors

---

20. Role in Quantum Cryptographic Primitives

Coin flipping can be used in:

• Fair contract signing
• Oblivious transfer
• Leader election in distributed systems

---

21. Experimental Demonstrations

Several photonic experiments have demonstrated:

• Bias-reduced coin flipping with real-world components
• Device imperfections limit achievable bias in practice

---

22. Comparison with Other Primitives

Primitive	Use Case	Quantum Advantage
QKD	Key generation	Unconditional security
Coin Flipping	Fair random decision	Bounded cheating probability
Bit Commitment	Binding + hiding	Limited due to no-go theorems

---

23. Device-Independent Coin Flipping

Uses Bell tests to ensure outcome fairness without trusting devices. Remains an active area of research.

---

24. Current Research and Open Questions

• Efficient protocols with lower bias
• Realistic, fault-tolerant implementations
• Fully device-independent protocols
• Integration with QKD and other systems

---

25. Conclusion

Quantum coin flipping exemplifies the power of quantum mechanics in creating cryptographic protocols where fairness is physically enforced. Though perfect fairness is theoretically impossible, quantum protocols achieve minimal bias, outperforming classical counterparts. With continued advancements, quantum coin flipping could become a core building block of future secure and fair information systems.

---