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

Lecture notes in computer science

Circular Security Separations for Arbitrary Length Cycles from LWE

Venkata Koppula, Brent R. Waters

Published Jan 1, 2016• 23 citations
Publisher
DOI
10.1007/978-3-662-53008-5_24

Related papers

Three’s Compromised Too: Circular Insecurity for Any Cycle Length from (Ring-)LWE

Navid Alamati, Chris Peikert

Lecture notes in computer science•Jan 1, 2016•22 citations

Zeroizing Attacks Against Evasive and Circular Evasive LWE

Shweta Agrawal, Anuja Modi, Anshu Yadav +1 more

Lecture notes in computer science•Dec 1, 2025•7 citations

Separations in circular security for arbitrary length key cycles, revisited

Jinyong Chang, Honglong Dai, Maozhi Xu +1 more

Abstract The circular security of public key encryptions has been drawn great attentions in recent years. The relationship of notions between circular securities and standard ones such as chosen plaintext security (CPA‐security) and chosen ciphertext security (CCA‐security) deserve to be clarified. For any integer n > 0 and n ≠ 2, whether the notions of n‐circular securities can be implied by that of their standard correspondences, such as CPA or CCA security in public key setting, has largely remained open. Koppula, Ramchen, and Waters in TCC'15 recently made a separation in CPA case by proposing a CPA secure scheme that is not n‐circular secure based on the recent candidate constructions of indistinguishable obfuscation. In this work, we consider the CCA case. In particular, inspired by the indistinguishable‐obfuscation‐based construction of Koppula et al., we obtain the following results: We make a separation between the n‐circular CCA security and CCA security for anyn>0. Specifically, we propose a hybrid encryption scheme that achieves the CCA security but fails even in the n‐circular CPA security. Hence, that makes a separation between the CCA security and the n‐circular CCA security (and even the n‐circular CPA security). By revising the previous construction, we also present a CCA secure (hybrid encryption) scheme, which allows an adversary to recover all secret keys when obtaining an encrypted key cycle. Hence, that implies that: if a key cycle arises in a system, then a passive adversary might be able to recover all secret keys even if CCA‐secure encryptions are used. The results in this work, together with that of Koppula et al., confirm that notions of circular securities are stronger than their standard correspondences. Copyright © 2016 John Wiley & Sons, Ltd.

Security and Communication Networks•Nov 25, 2016•2 citations

Efficient Quantum Fully Homomorphic Encryption

Fengxia Liu, Zixian Gong, Kun Tian +3 more

Quantum fully homomorphic encryption (QFHE) enables arbitrary quantum computations on encrypted data, but prior constructions require prohibitive quantum resources--specifically, O(lambda^2) EPR pairs per T-gate evaluation using the Barrington-based approach (DSS16). This paper introduces a unified framework achieving exponential improvement over the generic Barrington-based approach in program length. The central innovation is a novel modular arithmetic program (MA-Program) tailored to learning with errors (LWE) decryption. We show that LWE decryption computes the inner product <sk,ct> mod q, a modular inner product that is NOT a symmetric function. Thus, prior symmetric-function optimizations (Sinha's O(n)-state branching programs) do not apply. Our MA-Program tracks partial sums modulus q with state space Z_q requiring O(log q) bits, yielding programs of state count O(lambda) with binary encoding O(log lambda) and length O(lambda log lambda). This reduces the quantum gadget size from O(lambda^2) to O(lambda log^2 lambda) EPR pairs. To achieve a fully classical client, we transfer all quantum resources (EPR preparation, Bell measurements, adaptive error correction) to the server via the MA-Program gadget framework. Clients only perform classical LWE key generation, Pauli key encryption under classical FHE, and no quantum operations; a layered key structure further eliminates circular security assumptions. For parallel computation, we adopt the MBQC framework with flow functions, supporting up to O(log lambda) parallel measurements per layer. This separates offline resource preparation from online adaptive measurement, enabling parallel processing while maintaining deterministic evaluation.

quant-pharXiv:2604.23490•Apr 28, 2026•0 citations

A New Secure Matrix Multiplication from Ring-LWE

Lihua Wang, Yoshinori Aono, Le Trieu Phong

Lecture notes in computer science•Jan 1, 2018•6 citations

Ring-LWE: Applications to Cryptography and Their Efficient Realization

Sujoy Sinha Roy, Angshuman Karmakar, Ingrid M.R. Verbauwhede

Lecture notes in computer science•Jan 1, 2016•9 citations
Abstract The circular security of public key encryptions has been drawn great attentions in recent years. The relationship of notions between circular securities and standard ones such as chosen plaintext security (CPA‐security) and chosen ciphertext security (CCA‐security) deserve to be clarified. For any integer n > 0 and n ≠ 2, whether the notions of n‐circular securities can be implied by that of their standard correspondences, such as CPA or CCA security in public key setting, has largely remained open. Koppula, Ramchen, and Waters in TCC'15 recently made a separation in CPA case by proposing a CPA secure scheme that is not n‐circular secure based on the recent candidate constructions of indistinguishable obfuscation. In this work, we consider the CCA case. In particular, inspired by the indistinguishable‐obfuscation‐based construction of Koppula et al., we obtain the following results: We make a separation between the n‐circular CCA security and CCA security for anyn>0. Specifically, we propose a hybrid encryption scheme that achieves the CCA security but fails even in the n‐circular CPA security. Hence, that makes a separation between the CCA security and the n‐circular CCA security (and even the n‐circular CPA security). By revising the previous construction, we also present a CCA secure (hybrid encryption) scheme, which allows an adversary to recover all secret keys when obtaining an encrypted key cycle. Hence, that implies that: if a key cycle arises in a system, then a passive adversary might be able to recover all secret keys even if CCA‐secure encryptions are used. The results in this work, together with that of Koppula et al., confirm that notions of circular securities are stronger than their standard correspondences. Copyright © 2016 John Wiley & Sons, Ltd.
Quantum fully homomorphic encryption (QFHE) enables arbitrary quantum computations on encrypted data, but prior constructions require prohibitive quantum resources--specifically, O(lambda^2) EPR pairs per T-gate evaluation using the Barrington-based approach (DSS16). This paper introduces a unified framework achieving exponential improvement over the generic Barrington-based approach in program length. The central innovation is a novel modular arithmetic program (MA-Program) tailored to learning with errors (LWE) decryption. We show that LWE decryption computes the inner product <sk,ct> mod q, a modular inner product that is NOT a symmetric function. Thus, prior symmetric-function optimizations (Sinha's O(n)-state branching programs) do not apply. Our MA-Program tracks partial sums modulus q with state space Z_q requiring O(log q) bits, yielding programs of state count O(lambda) with binary encoding O(log lambda) and length O(lambda log lambda). This reduces the quantum gadget size from O(lambda^2) to O(lambda log^2 lambda) EPR pairs. To achieve a fully classical client, we transfer all quantum resources (EPR preparation, Bell measurements, adaptive error correction) to the server via the MA-Program gadget framework. Clients only perform classical LWE key generation, Pauli key encryption under classical FHE, and no quantum operations; a layered key structure further eliminates circular security assumptions. For parallel computation, we adopt the MBQC framework with flow functions, supporting up to O(log lambda) parallel measurements per layer. This separates offline resource preparation from online adaptive measurement, enabling parallel processing while maintaining deterministic evaluation.