A Single Secret Leader Election (SSLE) enables a group of parties to randomly choose exactly one leader from the group with the restriction that the identity of the leader will be known to the chosen leader and nobody else. At a later time, the elected leader should be able to publicly reveal her identity and prove that she is the elected leader. The election process itself should work properly even if many registered users are passive and do not send any messages. SSLE is used to strengthen the security of proof-of-stake consensus protocols by ensuring that the identity of the block proposer remains unknown until the proposer publishes a block. Boneh, Eskandarian, Hanzlik, and Greco (AFT'20) defined the concept of an SSLE and gave several constructions. Their most efficient construction is based on the difficulty of the Decision Diffie-Hellman problem in a cyclic group. In this work we construct the first efficient SSLE protocols based on the standard Learning With Errors (LWE) problem on integer lattices, as well as the Ring-LWE problem. Both are believed to be post-quantum secure. Our constructions generalize the paradigm of Boneh et al. by introducing the concept of a re-randomizable commitment (RRC). We then construct several post-quantum RRC schemes from lattice assumptions and prove the security of the derived SSLE protocols. Constructing a lattice-based RRC scheme is non-trivial, and may be of independent interest.
A Single Secret Leader Election (SSLE) enables a group of parties to randomly choose exactly one leader from the group with the restriction that the identity of the leader will be known to the chosen leader and nobody else. At a later time, the elected leader should be able to publicly reveal her identity and prove that she is the elected leader. The election process itself should work properly even if many registered users are passive and do not send any messages. SSLE is used to strengthen the security of proof-of-stake consensus protocols by ensuring that the identity of the block proposer remains unknown until the proposer publishes a block. Boneh, Eskandarian, Hanzlik, and Greco (AFT'20) defined the concept of an SSLE and gave several constructions. Their most efficient construction is based on the difficulty of the Decision Diffie-Hellman problem in a cyclic group. In this work we construct the first efficient SSLE protocols based on the standard Learning With Errors (LWE) problem on integer lattices, as well as the Ring-LWE problem. Both are believed to be post-quantum secure. Our constructions generalize the paradigm of Boneh et al. by introducing the concept of a re-randomizable commitment (RRC). We then construct several post-quantum RRC schemes from lattice assumptions and prove the security of the derived SSLE protocols. Constructing a lattice-based RRC scheme is non-trivial, and may be of independent interest.
This note describes a key exchange method based on the ring-LWE (RLWE)
assumption. It builds upon several results, including Regev's
landmark quantum reduction from certain worst case lattice problems
(approx. GapSVP and SIVP) to random instances of the search variant of
a particular learning problem (LWE). It also builds on the follow on
work of Lyubashevsky, Peikert and Regev on the average case hardness
of the RLWE search variant for polynomially bounded numbers of RLWE
samples, along with novel applications of automorphism groups in
number fields for a RLWE search to decision reduction (thereby
demonstrating pseudorandomness of RLWE in these number fields).
Subsequently, these results were adopted for the construction of
Diffie-Hellman like key exchange methods by Peikert, and then by
Lindner and Peikert followed by Ding and then by Ding, Xie and Lin who
proposed efficient variants of such protocols. Subsequent work by
Peikert proposed another efficient variant, phrased as a key
encapsulation method, incorporating a low bandwidth reconciliation
technique allowing two parties to exactly agree on a uniformly
distributed secret value from noisy RLWE instances. This was followed
by a concrete instantiation with parameter sets by Bos, Costello,
Naehrig, Stebila, followed by another instantiation by Alkim, Ducas,
Poppelmann and Schwabe with the same ring polynomial but a smaller
modulus and a different reconciliation method. Unlike most other
public key cryptography based key exchange methods, it is believed
that RLWE based key exchange would remain secure in the event that an
adversary is able to build a quantum computer. This document is a
product of the Crypto Forum Research Group (CFRG).
In an electronic election several cryptographic proofs are implemented to guarantee that all the process has been fair. Many cryptographic primitives are based on the hardness of the discrete logarithm, factorization and other related problems. However, these problems are efficiently computable with a quantum computer, and new proofs are needed based on different assumptions not broken by quantum computers. Lattice based cryptography seems one of the most promising post-quantum alternatives. In this thesis we present a coercion resistant cast as intended proof and a proof of a shuffle, both completely based on lattice problems as Inhomogeneous Short Integer Solution (ISIS) and Ring Learning With Errors (RLWE). With the first we prove to the voter that his vote correctly encodes his voting option, without allowing him to prove to a third party that he has chosen a specific option, to avoid the possibility of vote selling. Shuffles are permutations and re-encryptions of casted votes performed by mixing network nodes (mix- net nodes), so that the output can not be related with the input and nobody can link a decrypted vote with the voter who casted it. Given that the goal is to make the output not linkable to the input it is essential to provide a proof of it being a correct shuffle that has preserved the integrity of the votes, without deleting, adding of modifying any of them. To prove both things we have constructed non interactive zero-knowledge proofs, from which anyone can be convinced that a statement is true (with overwhelming probability over a security parameter) with- out revealing any information about the elements that witness it being true.
We present a new framework for constructing practically efficient publicly verifiable secret sharing (PVSS) with non-interactive dealers , in that the dealer may go offline after sending a single message, and is not involved in the share verification process. We use identity-based encryption (IBE) and commitments as the main ingredients and avoid expensive zero-knowledge proofs. By instantiating them with post-quantum secure schemes, a lattice-based IBE and a hash-based commitment, we obtain our first construction: a post-quantum secure PVSS with non-interactive dealers that outperforms the prior lattice-based practical construction by Gentry et al. [Eurocrypt 2022]. However, to enable the aggregation of PVSS transcripts (which facilitates many additional applications such as secure voting), we propose our second construction by replacing hash-based commitments with Pedersen's homomorphic commitments. While this does not achieve full-fledged post-quantum security (as Pedersen's scheme is not quantum safe), it still provides privacy against a post-quantum adversary. We prove the security of this construction in a new model, which we call long-lasting security. This model guarantees that the protocol is secure in the present (pre-quantum era) while maintaining privacy in the long term (post-quantum era). This new model is of independent interest for constructing efficient schemes that are resilient to the harvest-now-decrypt-later line of attacks. In this model, we propose a blockchain-compatible secure voting scheme using our PVSS scheme. Our PVSS schemes demonstrate practical efficiency: our post-quantum PVSS shares a secret among 1024 receivers in 667 ms and verifies the dealing in < 5 ms, and communicates 4.4MB, overall whereas the state of the art [Gentry et al., Eurocrypt 2022] communicates 251MB and requires 2060s for dealing the secret.
We introduce NTRU-VRF, the first verifiable random function (VRF) constructed directly from the NTRU lattice hardness assumption, and instantiated concretely using the NIST-standardized Falcon-512 (FN-DSA) signature scheme. A VRF is a pseudorandom function that produces a publicly verifiable proof of correctness for each output. All currently deployed VRFs (IETF RFC 9381, Algorand, Ethereum) rely on elliptic-curve assumptions broken by Shor's algorithm. Prior post-quantum VRF constructions either require only a few-time security guarantee (Esgin et al., ePrint 2020/1222), rely on symmetric primitives that lack a worst-case lattice hardness reduction (Buser et al., ePrint 2021/302), or are based on Module-LWE/Module-SIS rather than NTRU. No prior work constructs a many-time, lattice-based VRF from NTRU hardness with a formal security proof. Our construction exploits a fundamental and previously unformalized property of Falcon's deterministic signing mode: for any fixed public key and input, there exists exactly one valid short-norm signature. This unique-signature property is the key structural feature that transforms a lattice signature into a VRF. We prove three theorems: Uniqueness: For any input, the NTRU-VRF output is unique. This follows directly from the unique-short-coset-vector property of the NTRU lattice. Pseudorandomness: If the Short Integer Solution (SIS) problem on NTRU lattices is hard and the hash function is modelled as a random oracle, then the VRF output is computationally indistinguishable from a uniformly random value. Provability: The Falcon signature is an efficient, publicly verifiable proof, checkable by any party holding the public key. As a concrete application, we define PQ-Sortition, a post-quantum proof-of-stake leader-election protocol that replaces ECVRF-based sortition with our NTRU-VRF construction. We provide the entropy-chain design, stake-weighted win condition, adaptive liveness mechanism, equivocation slashing, and a formal security analysis of the resulting consensus protocol. Instantiated with Falcon-512, NTRU-VRF achieves a VRF output of 32 bytes, a proof size of <= 666 bytes, evaluation time of ~0.8 ms, and verification time of ~0.1 ms on standard hardware—significantly outperforming all existing post-quantum VRF constructions and making it the first many-time, compact, lattice-based VRF suitable for high-throughput blockchain consensus.
Post-quantum group key exchange protocols have become an increasingly critical area of research due to the potential threat quantum computers pose to classical cryptographic schemes. Traditional group key exchange protocols, often based on Diffie-Hellman and other number-theoretic assumptions, are vulnerable to quantum attacks. To address this challenge, we propose a novel group key exchange protocol that leverages lattice-based cryptography. Specifically, our approach utilizes lattice trapdoors and a re-encryption mechanism based on the Ring Learning With Errors (RLWE) problem. This design not only achieves post-quantum security but also enhances efficiency and flexibility in dynamic group settings. A common challenge in most protocols is the computational cost of deriving new keys as group members join and leave. Our approach effectively reduces this cost, making key updates more efficient and practical. Our protocol is proven secure under standard lattice assumptions, providing a promising solution for quantum-resistant group key exchange.
The anonymous network model was introduced by Angluin in (STOC '80, pages 82-93) to understand the fundamental properties of distributed computing by examining how much each party in a network needs to know about its own identity and the identities of other parties. In this model, all parties with the same number of communication links are identical. When studying the model, the problem of electing a unique leader is the central problem in the sense that once a unique leader is elected, he can assign a unique identity to each party. It was proved in the literature, however, that it is impossible to deterministically solve the leader election problem with any finite amount of communication. This contrasts sharply with the situation in the quantum setting: the present authors gave quantum algorithms that exactly solve the problem on anonymous quantum networks, where quantum communication and computation can be performed (TOCT, vol.4, no.1, article 1). The core of their algorithm consists of somewhat tricky unitary operators, which eliminate the possibility of ties during (quantum) coin flipping and thereby reduce the number of leader candidates with certainty. This paper presents a new quantum leader election algorithm that is based on quantum reduction via exact amplitude amplification to a classically solvable problem, computing a certain symmetric function, which provides more intuitive reasoning behind the existence of exact quantum algorithms for leader election. The algorithm first achieves a round complexity that is linear in the number of parties, i.e., the largest possible diameter plus one of the underlying graph of the network.