The security of modern public-key cryptography generally relies on computational intractability assumptions, such as integer factorization and discrete logarithm problems. This paper proposes a fundamentally different foundation for security: the intrinsic mathematical properties of tensor product categoriesâglobalentanglement, rigid decomposition, and sensitivity amplificationâare directly employed as security resources of the cryptosystem. Within the modular representation category of finite simple groups over finite fields, the private key correspondsto an irreducible modular representation, while the public key was originally conceived as the character vector of a tensor product of that representation. However, this paper reveals a fatal structural vulnerability: because the character ofthe base representation is public, an adversary can fully recover the private keycharacter through trivial division, causing the original security assumption to collapse completely. To address this, the paper accomplishes a paradigm shift fromâcharacter-exposure cryptographyâ to âstructure-commitment cryptography,â redefining the public key as a cryptographic commitment to the multiplicity vectorof the tensor product decomposition. Building upon this, the commitment-basedrepresentation recognition problem and the commitment-based tensor product decomposition problem are formalized, and their hardness is argued under both classical and quantum computational models. At the protocol level, it is pointed outthat non-interactive key exchange faces a fundamental obstacle due to the lack ofrepresentation-category homomorphic commitments; consequently, the research focus is shifted to digital signature schemes. The proposed TC-Sig scheme bridges thegap between commitment hiding and multiplicity verification using zero-knowledgeproof techniques, with security reduced to the commitment-based representationrecognition problem in the random oracle model. A feasibility assessment indicatesthat, for candidate groups such as the Mathieu group M12, key generation and commitment computation can be completed within milliseconds, while the introductionof zero-knowledge proofs increases latency to the order of seconds or minutes, making the scheme suitable for low-frequency, high-security scenarios. The security ofthis framework rests on three cornerstones: the classification rigidity of finite simple groups, the one-wayness of commitment schemes, and the non-abelian quantumcomputing barrier, thereby offering a new pathway for post-quantum cryptographyrooted in pure mathematical structure.
We present an elementary proof that the asymptotic entropy of a random walk on a countable abelian group is zero when the entropy of the first step of the random walk is finite. Unlike the traditional proof, our approach does not rely on the boundary theory of random walks. To our best knowledge, our direct proof is new even for the group of integers.
Biscuit is a recent multivariate signature scheme based on the MPC-in-the-Head paradigm. It has been submitted to the NIST competition for additional signature schemes. Signatures are derived from a zero-knowledge proof of knowledge of the solution of a structured polynomial system. This extra structure enables efficient proofs and compact signatures. This short note demonstrates that it also makes these polynomial systems easier to solve than random ones. As a consequence, the original parameters of Biscuit failed to meet the required security levels and had to be upgraded.
In this article we show that all cyclic branched covers of a Seifert link have left-orderable fundamental groups, and therefore admit co-oriented taut foliations and are not $L$-spaces, if and only if it is not an $ADE$ link up to orientation. This leads to a proof of the $ADE$ link conjecture for Seifert links. When $L$ is an $ADE$ link up to orientation, we determine which of its canonical $n$-fold cyclic branched covers $ÎŁ_n(L)$ have non-left-orderable fundamental groups. In addition, we give a topological proof of Ishikawa's classification of strongly quasipositive Seifert links and we determine the Seifert links that are definite, resp. have genus zero, resp. have genus equal to its smooth $4$-ball genus, among others. In the last section, we provide a comprehensive survey of the current knowledge and results concerning the $ADE$ link conjecture.
Open access
Geometric and Algebraic Topology
Geometric Analysis and Curvature Flows
Organometallic Compounds Synthesis and Characterization
Nicholas Brandt, Dennis Hofheinz, Michael KlooĂ, Michael Reichle
We construct the first blind signature scheme that achieves all of the following properties simultaneously: â it is tightly secure under a standard (i.e., non-interactive, non-q-type) computational assumption, â it does not require pairings, â it does not rely on generic, non-black-box techniques (like generic NIZK proofs). The third property enables a reasonably efficient solution, and in fact signatures in our scheme comprise 10 group elements and 29 Zp-elements. Our scheme starts from a pairing-based non-blind signature scheme (Abe et al., JoC 2023), and uses recent techniques of Chairattana-Apirom, Tessaro, and Zhu (CRYPTO 2024) to replace the pairings used in this scheme with non-interactive zero-knowledge proofs in the random oracle model. This conversion is not generic or straightforward (also because the mentioned previous works have converted only significantly simpler signature schemes), and we are required to improve upon and innovate existing techniques in several places. As an interesting side note, and unlike previous works, our techniques only require a non-programmable random oracle, and our signature scheme achieves predicate blindness (which means that the user can prove state ments about the signed message during the signing process).
Lennart Braun, Guilhem Castagnos, Ivan DamgÄrd, Fabien Laguillaumie · 7 authors
We present distributed key generation and decryption protocols for an additively homomorphic cryptosystem based on class groups, improving on a similar system proposed by Braun, DamgĂ„rd, and Orlandi at CRYPTO â23. Our key generation is similarly constant round but achieves lower communication complexity than the previous work. This improvement is in part the result of relaxing the reconstruction property required of the underlying integer verifiable secret sharing scheme. This eliminates the reliance on potentially costly proofs of knowledge in unknown order groups. We present a new method to batch zero-knowledge proofs in unknown order groups which strengthens these improvements. We also present a protocol which is proven secure against adaptive adversaries in the single inconsistent player (SIP) model. Our protocols are secure in the universal composability (UC) framework and provide guaranteed output delivery. We demonstrate the relative efficiency of our techniques by presenting the running times and communication costs associated with our implementation of the statically secure protocol and provide a direct comparison with alternate state of the art constructions.
Liqun Chen, Changyu Dong, Christopher J. P. Newton, Yalan Wang
Group signatures and their variants have been widely used in privacy-sensitive scenarios such as anonymous authentication and attestation. In this paper, we present a new post-quantum group signature scheme from symmetric primitives. Using only symmetric primitives makes the scheme less prone to unknown attacks than basing the design on newly proposed hard problems whose security is less well-understood. However, symmetric primitives do not have rich algebraic properties, and this makes it extremely challenging to design a group signature scheme on top of them. It is even more challenging if we want a group signature scheme suitable for real-world applications, one that can support large groups and require few trust assumptions. Our scheme is based on MPC-in-the-head non-interactive zero-knowledge proofs, and we specifically design a novel hash-based group credential scheme, which is rooted in the SPHINCS+ signature scheme but with various modifications to make it MPC (multi-party computation) friendly. The security of the scheme has been proved under the fully dynamic group signature model. We provide an implementation of the scheme and demonstrate the feasibility of handling a group size as large as 2 60 . This is the first group signature scheme from symmetric primitives that supports such a large group size and meets all the security requirements.
While the amount of data produced and accumulated continues to advance at unprecedented rates, protection and concealment of data increase its prominence as a field of scientific study that requires more action. It is essential to protect privacy-sensitive data at every phase; at rest, at run, and while computations are executed on data. The zero-knowledge proof (ZKP) schemes are a cryptographic tool toward this aim. ZKP allows a party to securely ensure the data's authenticity and precision without revealing confidential or privacy-sensitive information during communication or computation. The power of zero-knowledge protocols is based on intractable problems. There is a requirement to design more secure and efficient zero-knowledge proofs. This demand raises the necessity of determining appropriate intractable problems to develop novel ZKP schemes. In this paper, we present a brief outline of ZKP schemes, the connection of these structures to group-theoretic intractable problems, and annotate a list of intractable problems in group theory that can be employed to devise new ZKP schemes.
Ward Beullens, Samuel Dobson, Shuichi Katsumata, Yi-Fu Lai · 5 authors
Abstract 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>N</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , 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(\cdot )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>·</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -notation hides a very small constant factor, it remains small even for very large group sizes, say $$2^{20}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mn>20</mml:mn> </mml:msup> </mml:math> .
Secure multiparty computation is a focus of the international cryptographic community. The millionaires problem is the most important problem in secure multiparty computation and is a building block for constructing other secure multiparty computation protocols. Several solutions are available to solve this problem, but except for protocols based on garbled circuits, the existing solutions based on public key cryptosystems are only secure in semihonest models. No solution based on a public key cryptosystem is secure against malicious adversaries. This state restricts the resolution of many secure multiparty computation problems in malicious scenarios. A solution that is secure in malicious models is highly applicable in practical application scenarios and is generally appealing. Therefore, the study of the solution to the millionaires problem in a malicious model is of great theoretical and practical significance. In this work, we propose a multiparty computation protocol for the millionaires problem that is secure in a semihonest model. The proposed protocol is simple and easily understandable. We analyze the possible malicious behaviors in this protocol and use zero-knowledge proof and cut-and-choose techniques to resist possible malicious behaviors and thereby convert the protocol into one that is secure in the malicious model. We prove that the proposed protocol is secure in the malicious model by using the well-accepted ideal-real paradigm. Theoretical efficiency analysis shows that the efficiency of our protocol is at least six times that of existing protocols.
An efficient member revocation mechanism is a desirable feature when group signature schemes are applied in practical scenarios. Revocation methods, such as verifier-local revocation (VLR), provide an efficient member revocation in applications of group signatures. However, VLR-group signatures rely on a weaker security notion. On the other hand, group signature schemes for static groups gain stronger security with the full-anonymity security notion. Even though an outsider sees the secret signing keys of all group members in the full-anonymity, the signer is still anonymous. Achieving the full-anonymity for VLR group signature schemes is challenging due to the structure of secret signing keys. The secret signing keys of those schemes consist of tokens, which are used to manage revocation. The reveal of tokens may destroy the anonymity of the signers. We obtain stronger security for the lattice-based VLR group signature schemes by providing a new key generation method, which outputs revocation tokens without deriving from the membersâ secret signing keys. We propose a new group signature scheme from lattices with VLR, which achieves stronger security than the previous related works. To avoid signature forgeries, we suggest a new zero-knowledge proof system that requires signers to validate themselves. Moreover, we output an efficient tracing mechanism.
This paper introduces a new capability for group signatures called message-dependent opening . It is intended to weaken the high trust placed on the opener; i.e., no anonymity against the opener is provided by an ordinary group signature scheme. In a group signature scheme with message-dependent opening (GS-MDO), in addition to the opener, we set up an admitter that is not able to extract any userâs identity but admits the opener to open signatures by specifying messages where signatures on the specified messages will be opened by the opener. The opener cannot extract the signerâs identity from any signature whose corresponding message is not specified by the admitter. This paper presents formal definitions of GS-MDO and proposes a generic construction of it from identity-based encryption and adaptive non-interactive zero-knowledge proofs. Moreover, we propose two specific constructions, one in the standard model and one in the random oracle model. Our scheme in the standard model is an instantiation of our generic construction but the message-dependent opening property is bounded. In contrast, our scheme in the random oracle model is not a direct instantiation of our generic construction but is optimized to increase efficiency and achieves the unbounded message-dependent opening property. Furthermore, we also demonstrate that GS-MDO implies identity-based encryption, thus implying that identity-based encryption is essential for designing GS-MDO schemes.
Inspired by the work of Ghadafi and Groth (ASIACRYPT 2017) on a certain type of computational hardness assumptions in cyclic groups (which they call ``target assumptions''), we initiate an analogous work on another type of hardness assumptions, namely the ``knowledge-of-exponent'' assumptions (KEAs). Originally introduced by Damgard to construct practical encryption schemes secure against chosen ciphertext attacks, KEAs have subsequently been used primarily to construct succinct non-interactive arguments of knowledge (SNARKs), and proved to be inherent to such constructions. Since SNARKs (and their zero-knowledge variant, zk-SNARKs) are already used in practice in such systems as the Zcash digital currency, it can be expected that the use of KEAs will increase in the future, which makes it important to have a good understanding of those assumptions. Using a proof technique first introduced by Bellare and Palacio (but acknowledged by them as being due to Halevi), we first investigate the internal structure of the q-power knowledge-of-exponent (q-PKE) family of assumptions introduced by Groth, which is thus far the most general variant of KEAs. We then introduce a generalisation of the q-PKE family, and show that it can be simplified.
M. Albrecht, Pooya Farshim, Shuai Han, Dennis Hofheinz · 6 authors
Abstract We provide constructions of multilinear groups equipped with natural hard problems from indistinguishability obfuscation, homomorphic encryption, and NIZKs. This complements known results on the constructions of indistinguishability obfuscators from multilinear maps in the reverse direction. We provide two distinct, but closely related constructions and show that multilinear analogues of the $${\text {DDH}} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>DDH</mml:mtext></mml:math> assumption hold for them. Our first construction is symmetric and comes with a $$\kappa $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>Îș</mml:mi></mml:math> -linear map $$\mathbf{e }: {{\mathbb {G}}}^\kappa \longrightarrow {\mathbb {G}}_T$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>e</mml:mi><mml:mo>:</mml:mo><mml:msup><mml:mrow><mml:mi>G</mml:mi></mml:mrow><mml:mi>Îș</mml:mi></mml:msup><mml:mo>â¶</mml:mo><mml:msub><mml:mi>G</mml:mi><mml:mi>T</mml:mi></mml:msub></mml:mrow></mml:math> for prime-order groups $${\mathbb {G}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>G</mml:mi></mml:math> and $${\mathbb {G}}_T$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>G</mml:mi><mml:mi>T</mml:mi></mml:msub></mml:math> . To establish the hardness of the $$\kappa $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>Îș</mml:mi></mml:math> -linear $${\text {DDH}} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>DDH</mml:mtext></mml:math> problem, we rely on the existence of a base group for which the $$\kappa $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>Îș</mml:mi></mml:math> -strong $${\text {DDH}} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>DDH</mml:mtext></mml:math> assumption holds. Our second construction is for the asymmetric setting, where $$\mathbf{e }: {\mathbb {G}}_1 \times \cdots \times {\mathbb {G}}_{\kappa } \longrightarrow {\mathbb {G}}_T$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>e</mml:mi><mml:mo>:</mml:mo><mml:msub><mml:mi>G</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>Ă</mml:mo><mml:mo>âŻ</mml:mo><mml:mo>Ă</mml:mo><mml:msub><mml:mi>G</mml:mi><mml:mi>Îș</mml:mi></mml:msub><mml:mo>â¶</mml:mo><mml:msub><mml:mi>G</mml:mi><mml:mi>T</mml:mi></mml:msub></mml:mrow></mml:math> for a collection of $$\kappa +1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>Îș</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math> prime-order groups $${\mathbb {G}}_i$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>G</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:math> and $${\mathbb {G}}_T$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>G</mml:mi><mml:mi>T</mml:mi></mml:msub></mml:math> , and relies only on the 1-strong $${\text {DDH}} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>DDH</mml:mtext></mml:math> assumption in its base group. In both constructions, the linearity $$\kappa $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>Îș</mml:mi></mml:math> can be set to any arbitrary but a priori fixed polynomial value in the security parameter. We rely on a number of powerful tools in our constructions: probabilistic indistinguishability obfuscation, dual-mode NIZK proof systems (with perfect soundness, witness-indistinguishability, and zero knowledge), and additively homomorphic encryption for the group $$\mathbb {Z}_N^{+}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msubsup><mml:mi>Z</mml:mi><mml:mi>N</mml:mi><mml:mo>+</mml:mo></mml:msubsup></mml:math> . At a high level, we enable âbootstrappingâ multilinear assumptions from their simpler counterparts in standard cryptographic groups and show the equivalence of PIO and multilinear maps under the existence of the aforementioned primitives.
This habilitation thesis deals with cryptographic primitives that preserve the algebraic structure of underlying objects (messages, keys, etc) and their applications to the design of non-interactive zero-knowledge proofs and privacy-enhancing cryptographic primitives.In 2008, Groth and Sahai showed how to make these proof systems relatively efficient in abelian groups endowed with a bilinear map. These techniques, however, require to work with lower-level primitives where handled objects all live in a cyclic abelian group. Among other things, we need to sign messages without destroying their algebraic structure (in particular, without hashing them first) so as to be able to efficiently prove properties about hidden signed messages. The first part of this thesis describes a structure-preserving signature scheme which was the first efficient realization under previously studied algorithmic assumptions. These tools are also utilized in the design of a novel revocation mechanism for group signatures, which allow users to anonymously sign messages on behalf of a population they belong to. The second part of this thesis considers structure-preserving signatures endowed with homomorphic properties. We show how to use them in the design of non-malleable cryptographic primitives. Using linearly homomorphic structurepreserving signatures, we notably obtain non-malleable commitments to group elements and non-interactive zero-knowledge proofs, as well as public-key encryption schemes that resist chosen-ciphertext attacks.
Technology is linking the slightest of our actions to the virtual world. In such connected environments, cryptography aims at building schemes with provable security in order to mathematically protect the users' security in electronic exchanges. Relying on the existence of pairings in bilinear groups wherein the discrete logarithm problem is hard, this thesis puts forth mechanisms to efficiently enhance the privacy in three of the most fundamental cryptographic primitives, namely, digital signatures, encryption schemes and zero-knowledge proofs. Furthermore, these mechanisms support public verifiability so as to force the honesty of all participants in the standard model. We first focus on group signatures, a primitive proposed some 20 years ago, for which we propose the first efficient revocation mechanisms, overcoming the main obstacle to the deployment of this primitive in practical applications. We then focus on P-homomorphic signatures that make it possible to modify a signed message in a controlled way. In particular, we propose new mechanisms providing structure-preserving linearly homomorphic signatures, from which we build the first constant-size non-malleable commitments compatible with standard proof systems, as well as a generalization of this construction into a generic transformation. Finally we further investigate the unexpected applications of this kind of malleable signatures to non-malleable cryptography. This leads us to new proof systems for linear languages which in turn provide the most efficient publicly verifiable CCA-secure threshold encryption to date, and other new extensions.
This paper is an extended version of math.OA/0601528 where we point out and remedy a gap in the proof by P. Julg and G. Kasparov of the Baum-Connes conjecture for discrete subgroups of SU(n,1). In particular, here we explain in details why the non-microlocality of the Heisenberg calculus prevents us from implementing into this framework the classical approach of Seeley to pseudodifferential complex powers, which was the main issue at stake in math.OA/0601528.
In this note we point out and fill a gap in the proof by Julg-Kasparov of the Baum-Connes conjecture with coefficients for discrete subgroups of $\op{SU}(n,1)$. The issue at stake is the proof that the complex powers of the contact Laplacian are element of the Heisenberg calculus. In particular, we explain why we cannot implement into the setting of the Heisenberg calculus the classical Seeley's approach to complex powers.
Abstract. Artinâs braid groups currently provide a promising background for cryptographical applications, since the first cryptosystems using braids were introduced in [2, 3, 18] (see also [22]). A variety of key agreement protocols based on braids have been described, but few authentication or signature schemes have been proposed so far. We introduce three authentication schemes based on braids, two of them being zero-knowledge interactive proofs of knowledge. Then we discuss their possible implementations, involving normal forms or an alternative braid algorithm, called handle reduction, which can achieve good efficiency under specific requirements. 1.