The Signal protocol is a secure instant messaging protocol that underlies the security of numerous applications such as WhatsApp, Skype, Facebook Messenger among many others. The Signal protocol ...consists of two sub-protocols known as the X3DH protocol and the double ratchet protocol, where the latter has recently gained much attention. For instance, Alwen, Coretti, and Dodis (Eurocrypt’19) provided a concrete security model along with a generic construction based on simple building blocks that are instantiable from versatile assumptions, including post-quantum ones. In contrast, as far as we are aware, works focusing on the X3DH protocol seem limited. In this work, we cast the X3DH protocol as a specific type of authenticated key exchange (AKE) protocol, which we call a
Signal-conforming AKE
protocol, and formally define its security model based on the vast prior works on AKE protocols. We then provide the first efficient generic construction of a Signal-conforming AKE protocol based on standard cryptographic primitives such as key encapsulation mechanisms (KEM) and signature schemes. Specifically, this results in the first post-quantum secure replacement of the X3DH protocol based on well-established assumptions. Similar to the X3DH protocol, our Signal-conforming AKE protocol offers a strong (or stronger) flavor of security, where the exchanged key remains secure even when all the non-trivial combinations of the long-term secrets and session-specific secrets are compromised. Moreover, our protocol has a weak flavor of deniability and we further show how to progressively strengthen it using ring signatures and/or non-interactive zero-knowledge proof systems. Finally, we provide a full-fledged, generic C implementation of our (weakly deniable) protocol. We instantiate it with several Round 3 candidates (finalists and alternates) to the NIST post-quantum standardization process and compare the resulting bandwidth and computation performances. Our implementation is publicly available.
In this paper, we develop and formalize a set of tools to efficiently compute inner-products homomorphically over the ring
Z
p
for small modulus
p
. This allows us to use smaller modulus size in ...various cryptographic primitives based on lattices, which is desirable both from a security and efficiency points of view. Our approach is to directly express the computation of inner-products as a special form of branching program and then homomorphically evaluate them. This is in contrast to previous works that first invoked the Barrington’s theorem to convert the circuit computing the inner-product indirectly into a branching program. The direct computation of branching programs substantially improves the efficiency compared to previous methods since the invocation of the Barrington’s theorem incurred a significant efficiency loss. We obtain the following concrete applications as a result of our technique. (1) We propose new attribute-based encryption (
ABE
) schemes with improved efficiency for several useful predicates in
NC
1
. While previous approaches typically require either a super-polynomial modulus or invocation of the Barrington’s theorem, we manage to make the modulus size polynomially small without relying on any of these. Consequently, we obtain more efficient and secure schemes. (2) We propose a new tightly secure identity-based encryption (
IBE
) scheme from lattices with small polynomial modulus. Compared with the construction by Boyen and Li (Asiacrypt 404–434, Springer, Heidelberg, 2016, 10.1007/978-3-662-53890-6_14), our scheme achieves much better efficiency, albeit assuming the security of a special type of pseudorandom function (
PRF
) by Boneh et al. (TCC 535–554, Springer, Heidelberg, 2018, 10.1007/978-3-540-70936-7_29).
A non-interactive zero-knowledge (NIZK) protocol enables a prover to convince a verifier of the truth of a statement without leaking any other information by sending a single message. The main focus ...of this work is on exploring short pairing-based NIZKs for all
NP
languages based on standard assumptions. In this regime, the seminal work of Groth, Ostrovsky, and Sahai (J.ACM’12) (GOS-NIZK) is still considered to be the state-of-the-art. Although fairly efficient, one drawback of GOS-NIZK is that the proof size is
multiplicative
in the circuit size computing the
NP
relation. That is, the proof size grows by
O
(
|
C
|
κ
)
, where
C
is the circuit for the
NP
relation and
κ
is the security parameter. By now, there have been numerous follow-up works focusing on shortening the proof size of pairing-based NIZKs, however, thus far, all works come at the cost of relying either on a non-standard knowledge-type assumption or a non-static
q
-type assumption. Specifically, improving the proof size of the original GOS-NIZK under the same standard assumption has remained as an open problem. Our main result is a construction of a pairing-based NIZK for all of
NP
whose proof size is
additive
in |
C
|, that is, the proof size only grows by
|
C
|
+
poly
(
κ
)
, based on the computational Diffie-Hellman assumption over specific pairing-free groups and decisional linear (DLIN) assumption. As by-products of our main result, we also obtain the following two results: (1) We construct a
perfectly zero-knowledge
NIZK (NIPZK) for
NP
relations computable in
NC
1
with proof size
|
w
|
·
poly
(
κ
)
where |
w
| is the witness length based on the DLIN assumption. This is the first pairing-based NIPZK for a non-trivial class of
NP
languages whose proof size is independent of |
C
| based on a standard assumption. (2) We construct a universally composable (UC) NIZK for
NP
relations computable in
NC
1
in the erasure-free adaptive setting whose proof size is
|
w
|
·
poly
(
κ
)
from the DLIN assumption. This is an improvement over the recent result of Katsumata, Nishimaki, Yamada, and Yamakawa (CRYPTO’19), which gave a similar result based on a non-static
q
-type assumption. The main building block for all of our NIZKs is a constrained signature scheme with
decomposable online-offline efficiency
. This is a property which we newly introduce in this paper and construct from the DLIN assumption. We believe this construction is of an independent interest.
In a non-interactive zero-knowledge (NIZK) proof, a prover can non-interactively convince a verifier of a statement without revealing any additional information. A useful relaxation of NIZK is a ...designated verifier NIZK (DV-NIZK) proof, where proofs are verifiable only by a designated party in possession of a verification key. A crucial security requirement of DV-NIZKs is unbounded-soundness, which guarantees soundness even if the verification key is reused for multiple statements. Most known DV-NIZKs (except standard NIZKs) for
NP
do not have unbounded-soundness. Existing DV-NIZKs for
NP
satisfying unbounded-soundness are based on assumptions which are already known to imply standard NIZKs. In particular, it is an open problem to construct (DV-)NIZKs from weak paring-free group assumptions such as decisional Diffie–Hellman (DH). As a further matter, all constructions of (DV-)NIZKs from DH type assumptions (regardless of whether it is over a paring-free or paring group) require the proof size to have a multiplicative-overhead
|
C
|
·
poly
(
κ
)
, where |
C
| is the size of the circuit that computes the
NP
relation. In this work, we make progress of constructing DV-NIZKs from DH-type assumptions that are not known to imply standard NIZKs. Our results are summarized as follows:
DV-NIZKs for
NP
from the computational DH assumption over
pairing-free
groups. This is the first construction of such NIZKs on pairing-free groups and resolves the open problem posed by Kim and Wu (CRYPTO’18).
DV-NIZKs for
NP
with proof size
|
C
|
+
poly
(
κ
)
from the computational DH assumption over specific
pairing-free
groups. This is the first DV-NIZK that achieves a compact proof from a standard DH type assumption. Moreover, if we further assume the
NP
relation to be computable in
NC
1
and assume hardness of a (non-static) falsifiable DH type assumption over specific
pairing-free
groups, the proof size can be made as small as
|
w
|
+
poly
(
κ
)
.
In (STOC, 2008), Gentry, Peikert, and Vaikuntanathan proposed the first identity-based encryption (GPV-IBE) scheme based on a post-quantum assumption, namely the learning with errors assumption. ...Since their proof was only made in the random oracle model (ROM) instead of the
quantum
random oracle model (QROM), it remained unclear whether the scheme was truly post-quantum or not. In (CRYPTO, 2012), Zhandry developed new techniques to be used in the QROM and proved security of GPV-IBE in the QROM, hence answering in the affirmative that GPV-IBE is indeed post-quantum. However, since the general technique developed by Zhandry incurred a large reduction loss, there was a wide gap between the concrete efficiency and security level provided by GPV-IBE in the ROM and QROM. Furthermore, regardless of being in the ROM or QROM, GPV-IBE is not known to have a tight reduction in the multi-challenge setting. Considering that in the real-world an adversary can obtain many ciphertexts, it is desirable to have a security proof that does not degrade with the number of challenge ciphertext. In this paper, we provide a much tighter proof for the GPV-IBE in the QROM in the single-challenge setting. In addition, we show that a slight variant of the GPV-IBE has an almost tight reduction in the multi-challenge setting both in the ROM and QROM, where the reduction loss is independent of the number of challenge ciphertext. Our proof departs from the traditional partitioning technique and resembles the approach used in the public key encryption scheme of Cramer and Shoup (CRYPTO, 1998). Our proof strategy allows the reduction algorithm to program the random oracle the same way for all identities and naturally fits the QROM setting where an adversary may query a superposition of all identities in one random oracle query. Notably, our proofs are much simpler than the one by Zhandry and conceptually much easier to follow for cryptographers not familiar with quantum computation. Although at a high level, the techniques used for the single- and multi-challenge setting are similar, the technical details are quite different. For the multi-challenge setting, we rely on the Katz–Wang technique (CCS, 2003) to overcome some obstacles regarding the leftover hash lemma.
We construct an efficient dynamic group signature (or more generally an accountable ring signature) from isogeny and lattice assumptions. Our group signature is based on a simple generic construction ...that can be instantiated by cryptographically hard group actions such as the CSIDH group action or an MLWE-based group action. The signature is of size
O
(
log
N
)
, where
N
is the number of users in the group. Our idea builds on the recent efficient OR-proof by Beullens, Katsumata, and Pintore (Asiacrypt’20), where we efficiently add a proof of valid ciphertext to their OR-proof and further show that the resulting non-interactive zero-knowledge proof system is
online extractable
. Our group signatures satisfy more ideal security properties compared to previously known constructions, while simultaneously having an attractive signature size. The signature size of our isogeny-based construction is an order of magnitude smaller than all previously known post-quantum group signatures (e.g., 6.6 KB for 64 members). In comparison, our lattice-based construction has a larger signature size (e.g., either 126 KB or 89 KB for 64 members depending on the satisfied security property). However, since the
O
(
·
)
-notation hides a very small constant factor, it remains small even for very large group sizes, say
2
20
.
Continuous group key agreements (CGKAs) are a class of protocols that can provide strong security guarantees to secure group messaging protocols such as Signal and MLS. Protection against device ...compromise is provided by commit messages: at a regular rate, each group member may refresh their key material by uploading a commit message, which is then downloaded and processed by all the other members. In practice, propagating commit messages dominates the bandwidth consumption of existing CGKAs.
We propose Chained CmPKE, a CGKA with an asymmetric bandwidth cost: in a group of N members, a commit message costs O(N) to upload and O(1) to download, for a total bandwidth cost of O(N). In contrast, TreeKEM costs (log N) in both directions, for a total cost (N log N). Our protocol relies on generic primitives, and is therefore readily post-quantum.
We go one step further and propose post-quantum primitives that are tailored to \Chained CmPKE, which allows us to cut the growth rate of uploaded commit messages by two or three orders of magnitude compared to naive instantiations. Finally, we realize a software implementation of Chained CmPKE. Our experiments show that even for groups with a size as large as N = 2^10, commit messages can be computed and processed in less than 100 ms.
PDF
