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

计算机应用

可证明安全k-out-of-n不经意传输方案的安全分析与改进

李璐瑶, 戴明, 王青龙

Published May 30, 2014• 0 citations
Publisher

Abstract

不经意传输是密码学研究的一个重要内容.对一种可证明安全的k-out-of-n不经意传输方案安全性进行了分析.该方案的构造方法很新颖,具有很高的计算效率和传输效率.但是分析发现其存在一个明显漏洞,可以使得接收者能够获得发送者发送的全部信息,从而违背了不经意传输的安全性要求.详细分析后,通过引入一个随机数对该方案进行了改进,改进后的方案消除了原方案存在的漏洞,并且传输开销和计算开销与原方案相同,方案安全性同样是建立在判断性Diffie-Hellman （DDH）问题为困难问题的假设之上.

DOI
10.11772/j.issn.1001-9081.2014.05.1296

Related papers

Tighter Concrete Security for the Simplest OT

Iftach Haitner, Gil Segev

The Chou-Orlandi batch oblivious transfer (OT) protocol is a particularly attractive OT protocol that bridges the gap between practical efficiency and strong security guarantees and is especially notable due to its simplicity. The security analysis provided by Chou and Orlandi bases the security of their protocol on the hardness of the computational Diffie-Hellman (CDH) problem in prime-order groups. Concretely, in groups in which no better-than-generic algorithms are known for the CDH problem, their security analysis yields that an attacker running in time t and issuing q random-oracle queries breaks the security of their protocol with probability at most ϵ ≤ q 2 · t / 2 κ / 2 , where κ is the bit-length of the group's order. This concrete bound, however, is somewhat insufficient for 256-bit groups (e.g., for κ = 256 , it does not provide any guarantee already for t = 2 48 and q = 2 40 ). In this work, we establish a tighter concrete security bound for the Chou-Orlandi protocol. First, we introduce the list square Diffie-Hellman problem and present a tight reduction from the security of the protocol to the hardness of solving the list square Diffie-Hellman problem. That is, we completely shift the task of analyzing the concrete security of the protocol to that of analyzing the concrete hardness of the list square Diffie-Hellman problem. Second, we reduce the hardness of the list square Diffie-Hellman problem to that of the decisional Diffie-Hellman (DDH) problem without incurring a multiplicative loss. Our key observation is that although CDH and DDH have the same assumed concrete hardness, relying on the hardness of DDH enables our reduction to efficiently test the correctness of the solutions it produces. Concretely, in groups in which no better-than-generic algorithms are known for the DDH problem, our analysis yields that an attacker running in time t and issuing q ≤ t random-oracle queries breaks the security of the Chou-Orlandi protocol with probability at most ϵ ≤ t / 2 κ / 2 (i.e., we eliminate the above multiplicative q 2 term). We prove our results within the standard real-vs-ideal framework considering static corruptions by malicious adversaries, and provide a concrete security treatment by accounting for the statistical distance between a real-model execution and an ideal-model execution.

IACR Communications in Cryptology•Apr 8, 2025•0 citations

基于RS码生成机制的(k,n)门限量子秘密共享方案

程资, 靳俐荣, 石金晶

文章利用生成矩阵分割法提出了（k,n）量子门限秘密共享方案。与以往经典方案相比,它具有更好的安全性和可靠性。从量子方案的角度看,编码多样性提高了密钥破译难度。针对生成矩阵的循环周期问题和因某些元素不存在本原根而不能构造生成矩阵的问题,文章也提出了解决方案。本文方案的核心思想是参照量子信息与经典信息的对应关系,利用有限域中的本原根构造生成矩阵来实现经典秘密的分割,生成矩阵满足任意k列列向量线性独立;传输采用了基于超密集编码的量子安全直接通信。

信息网络安全•Apr 20, 2016•0 citations

自发辐射放大的量子随机数快速后处理方法

童启夏 Tong Qixia, 胡莹莹 Hu Yingying, 何德勇 He Deyong +1 more

在实用化的高速量子随机数产生器的应用中，使用Toeplitz矩阵作为后处理方法提取量子随机数随机性已成为一种主要的技术路线。然而，Toeplitz矩阵更适合于硬件计算而不适合软件运算，通常需要搭建专门的现场可编程门阵列（FPGA）电路才能进行快速运算。基于自发辐射放大（ASE）的量子随机产生器，提出一种基于简单哈希函数的快速后处理方式。这种方式的时间复杂度仅为O（N），小于Toeplitz矩阵的O（NlogN），并且相对另一种常用的后处理方法，最低有效位（LSBs）后处理，具有更高的随机数提取效率。实验中由所提后处理方法计算得到的随机数已通过美国国家标准与技术研究所（NIST）随机性检测。

Laser & Optoelectronics Progress•Jan 1, 2024•0 citations

Quantum Group Actions

Tomoyuki Morimae, Keita Xagawa

In quantum cryptography, there could be a new world, Microcrypt, where cryptography is possible but one-way functions (OWFs) do not exist. Although many fundamental primitives and useful applications have been found in Microcrypt, they lack ``OWFs-free'' concrete hardness assumptions on which they are based. In classical cryptography, many hardness assumptions on concrete mathematical problems have been introduced, such as the discrete logarithm (DL) problems or the decisional Diffie-Hellman (DDH) problems on concrete group structures related to finite fields or elliptic curves. They are then abstracted to generic hardness assumptions such as the DL and DDH assumptions over group actions. Finally, based on these generic assumptions, primitives and applications are constructed. The goal of the present paper is to introduce several abstracted generic hardness assumptions in Microcrypt, which could connect the concrete mathematical hardness assumptions with applications. Our assumptions are based on a quantum analogue of group actions. A group action is a tuple $(G,S,\star)$ of a group $G$, a set $S$, and an operation $\star:G\times S\to S$. We introduce a quantum analogue of group actions, which we call quantum group actions (QGAs), where $G$ is a set of unitary operators, $S$ is a set of states, and $\star$ is the application of a unitary on a state. By endowing QGAs with some reasonable hardness assumptions, we introduce a natural quantum analogue of the decisional Diffie-Hellman (DDH) assumption and pseudorandom group actions. Based on these assumptions, we construct classical-query pseudorandom function-like state generators (PRFSGs). Because classical group actions are instantiated with many concrete mathematical hardness assumptions, our QGAs could also have some concrete (even OWFs-free) instantiations.

arXiv:2410.04777•Oct 7, 2024•0 citations

宏观投影叠加与量子现象

Zhian Qian

标准量子力学在现象层精确描述了微观现象,但在解释层面留下若干未解问题:叠加态是什么、测量为什么特殊、纠缠为什么违反贝尔不等式、波粒二象性如何理解、延迟选择暗示了什么、退相干的本质是什么。本文在不对称展开研究纲领的基础上,提出一个统一的解释:量子力学不是描述世界底层的理论,而是描述锁定结构在动态时间场中如何读取相位状态的理论。量子现象不是底层的不确定性,而是时间场在静态层上的投影读数。本文进一步提出一个可检验预测:锁定单光子发射相位后,双缝干涉条纹应消失,退化为固定亮点。

•Sep 21, 2026•0 citations

New Quantum-Safe Versions of Decisional Diffie-Hellman Assumption in the General Linear Group and Their Applications: Two New Key-agreements

Abdelhaliem Babiker

Diffie-Hellman key-agreement and RSA cryptosystem are widely used to provide security in internet protocols. But both of the two algorithms are totally breakable using Shor's algorithms. This paper proposes two connected matrix-based key-agreements: (a) Diffie-Hellman Key-Agreement with Errors and (b) RSA-Resemble Key-agreement, which, respectively, bear resemblance to Diffie-Hellman key-agreement and RSA cryptosystem and thereby they gain some of the well-known security characteristics of these two algorithms, but without being subject to Shor's algorithms attacks. That is, the new schemes avoid the direct reliance on the hardness of Discrete Logarithm and Integer Factoring problems which are solvable by Shor's algorithms. The paper introduces a new family of quantum-safe hardness assumptions which consist of taking noisy powers of binary matrices. The new assumptions are derived from Decisional Diffie-Hellman (DDH) assumption in the general linear group GL(n,2) by introducing random noise into a quadruple similar to that which define the DDH assumption in GL(n,2(. Thereby we make certain that the resulting quadruple is secure against Shor's algorithm attack and any other DLP-based attack. Thence, the resulting assumptions, are used as basis for the two key-agreement schemes. We prove that these key-agreements are secure -- in key indistinguishability notion -- under the new assumptions.

arXiv:2104.04637•Apr 9, 2021•0 citations
不经意传输是密码学研究的一个重要内容.对一种可证明安全的k-out-of-n不经意传输方案安全性进行了分析.该方案的构造方法很新颖,具有很高的计算效率和传输效率.但是分析发现其存在一个明显漏洞,可以使得接收者能够获得发送者发送的全部信息,从而违背了不经意传输的安全性要求.详细分析后,通过引入一个随机数对该方案进行了改进,改进后的方案消除了原方案存在的漏洞,并且传输开销和计算开销与原方案相同,方案安全性同样是建立在判断性Diffie-Hellman （DDH）问题为困难问题的假设之上.
The Chou-Orlandi batch oblivious transfer (OT) protocol is a particularly attractive OT protocol that bridges the gap between practical efficiency and strong security guarantees and is especially notable due to its simplicity. The security analysis provided by Chou and Orlandi bases the security of their protocol on the hardness of the computational Diffie-Hellman (CDH) problem in prime-order groups. Concretely, in groups in which no better-than-generic algorithms are known for the CDH problem, their security analysis yields that an attacker running in time t and issuing q random-oracle queries breaks the security of their protocol with probability at most ϵ ≤ q 2 · t / 2 κ / 2 , where κ is the bit-length of the group's order. This concrete bound, however, is somewhat insufficient for 256-bit groups (e.g., for κ = 256 , it does not provide any guarantee already for t = 2 48 and q = 2 40 ). In this work, we establish a tighter concrete security bound for the Chou-Orlandi protocol. First, we introduce the list square Diffie-Hellman problem and present a tight reduction from the security of the protocol to the hardness of solving the list square Diffie-Hellman problem. That is, we completely shift the task of analyzing the concrete security of the protocol to that of analyzing the concrete hardness of the list square Diffie-Hellman problem. Second, we reduce the hardness of the list square Diffie-Hellman problem to that of the decisional Diffie-Hellman (DDH) problem without incurring a multiplicative loss. Our key observation is that although CDH and DDH have the same assumed concrete hardness, relying on the hardness of DDH enables our reduction to efficiently test the correctness of the solutions it produces. Concretely, in groups in which no better-than-generic algorithms are known for the DDH problem, our analysis yields that an attacker running in time t and issuing q ≤ t random-oracle queries breaks the security of the Chou-Orlandi protocol with probability at most ϵ ≤ t / 2 κ / 2 (i.e., we eliminate the above multiplicative q 2 term). We prove our results within the standard real-vs-ideal framework considering static corruptions by malicious adversaries, and provide a concrete security treatment by accounting for the statistical distance between a real-model execution and an ideal-model execution.
文章利用生成矩阵分割法提出了（k,n）量子门限秘密共享方案。与以往经典方案相比,它具有更好的安全性和可靠性。从量子方案的角度看,编码多样性提高了密钥破译难度。针对生成矩阵的循环周期问题和因某些元素不存在本原根而不能构造生成矩阵的问题,文章也提出了解决方案。本文方案的核心思想是参照量子信息与经典信息的对应关系,利用有限域中的本原根构造生成矩阵来实现经典秘密的分割,生成矩阵满足任意k列列向量线性独立;传输采用了基于超密集编码的量子安全直接通信。
在实用化的高速量子随机数产生器的应用中，使用Toeplitz矩阵作为后处理方法提取量子随机数随机性已成为一种主要的技术路线。然而，Toeplitz矩阵更适合于硬件计算而不适合软件运算，通常需要搭建专门的现场可编程门阵列（FPGA）电路才能进行快速运算。基于自发辐射放大（ASE）的量子随机产生器，提出一种基于简单哈希函数的快速后处理方式。这种方式的时间复杂度仅为O（N），小于Toeplitz矩阵的O（NlogN），并且相对另一种常用的后处理方法，最低有效位（LSBs）后处理，具有更高的随机数提取效率。实验中由所提后处理方法计算得到的随机数已通过美国国家标准与技术研究所（NIST）随机性检测。
In quantum cryptography, there could be a new world, Microcrypt, where cryptography is possible but one-way functions (OWFs) do not exist. Although many fundamental primitives and useful applications have been found in Microcrypt, they lack ``OWFs-free'' concrete hardness assumptions on which they are based. In classical cryptography, many hardness assumptions on concrete mathematical problems have been introduced, such as the discrete logarithm (DL) problems or the decisional Diffie-Hellman (DDH) problems on concrete group structures related to finite fields or elliptic curves. They are then abstracted to generic hardness assumptions such as the DL and DDH assumptions over group actions. Finally, based on these generic assumptions, primitives and applications are constructed. The goal of the present paper is to introduce several abstracted generic hardness assumptions in Microcrypt, which could connect the concrete mathematical hardness assumptions with applications. Our assumptions are based on a quantum analogue of group actions. A group action is a tuple (G,S,⋆)(G,S,\star)(G,S,⋆) of a group GGG, a set SSS, and an operation ⋆:G×S→S\star:G\times S\to S⋆:G×S→S. We introduce a quantum analogue of group actions, which we call quantum group actions (QGAs), where GGG is a set of unitary operators, SSS is a set of states, and ⋆\star⋆ is the application of a unitary on a state. By endowing QGAs with some reasonable hardness assumptions, we introduce a natural quantum analogue of the decisional Diffie-Hellman (DDH) assumption and pseudorandom group actions. Based on these assumptions, we construct classical-query pseudorandom function-like state generators (PRFSGs). Because classical group actions are instantiated with many concrete mathematical hardness assumptions, our QGAs could also have some concrete (even OWFs-free) instantiations.
标准量子力学在现象层精确描述了微观现象,但在解释层面留下若干未解问题:叠加态是什么、测量为什么特殊、纠缠为什么违反贝尔不等式、波粒二象性如何理解、延迟选择暗示了什么、退相干的本质是什么。本文在不对称展开研究纲领的基础上,提出一个统一的解释:量子力学不是描述世界底层的理论,而是描述锁定结构在动态时间场中如何读取相位状态的理论。量子现象不是底层的不确定性,而是时间场在静态层上的投影读数。本文进一步提出一个可检验预测:锁定单光子发射相位后,双缝干涉条纹应消失,退化为固定亮点。
Diffie-Hellman key-agreement and RSA cryptosystem are widely used to provide security in internet protocols. But both of the two algorithms are totally breakable using Shor's algorithms. This paper proposes two connected matrix-based key-agreements: (a) Diffie-Hellman Key-Agreement with Errors and (b) RSA-Resemble Key-agreement, which, respectively, bear resemblance to Diffie-Hellman key-agreement and RSA cryptosystem and thereby they gain some of the well-known security characteristics of these two algorithms, but without being subject to Shor's algorithms attacks. That is, the new schemes avoid the direct reliance on the hardness of Discrete Logarithm and Integer Factoring problems which are solvable by Shor's algorithms. The paper introduces a new family of quantum-safe hardness assumptions which consist of taking noisy powers of binary matrices. The new assumptions are derived from Decisional Diffie-Hellman (DDH) assumption in the general linear group GL(n,2) by introducing random noise into a quadruple similar to that which define the DDH assumption in GL(n,2(. Thereby we make certain that the resulting quadruple is secure against Shor's algorithm attack and any other DLP-based attack. Thence, the resulting assumptions, are used as basis for the two key-agreement schemes. We prove that these key-agreements are secure -- in key indistinguishability notion -- under the new assumptions.