6 results sorted by ID
Correlated Pseudorandomness from the Hardness of Quasi-Abelian Decoding
Maxime Bombar, Geoffroy Couteau, Alain Couvreur, Clément Ducros
Cryptographic protocols
Secure computation often benefits from the use of correlated randomness to achieve fast, non-cryptographic online protocols. A recent paradigm put forth by Boyle $\textit{et al.}$ (CCS 2018, Crypto 2019) showed how pseudorandom correlation generators (PCG) can be used to generate large amounts of useful forms of correlated (pseudo)randomness, using minimal interactions followed solely by local computations, yielding silent secure two-party computation protocols (protocols where the...
CycSAT-Unresolvable Cyclic Logic Encryption Using Unreachable States
Amin Rezaei, You Li, Yuanqi Shen, Shuyu Kong, Hai Zhou
Applications
Logic encryption has attracted much attention due to increasing IC design costs and growing number of untrusted foundries. Unreachable states in a design provide a space of flexibility for logic encryption to explore. However, due to the available access of scan chain, traditional combinational encryption cannot leverage the benefit of such flexibility. Cyclic logic encryption inserts key-controlled feedbacks into the original circuit to prevent piracy and overproduction. Based on our...
BeSAT: Behavioral SAT-based Attack on Cyclic Logic Encryption
Yuanqi Shen, You Li, Amin Rezaei, Shuyu Kong, David Dlott, Hai Zhou
Applications
Cyclic logic encryption is newly proposed in the area of hardware security. It introduces feedback cycles into the circuit to defeat existing logic decryption techniques. To ensure that the circuit is acyclic under the correct key, CycSAT is developed to add the acyclic condition as a CNF formula to the SAT-based attack. However, we found that it is impossible to capture all cycles in any graph with any set of feedback signals as done in the CycSAT algorithm. In this paper, we propose a...
Constrained PRFs for NC1 in Traditional Groups
Nuttapong Attrapadung, Takahiro Matsuda, Ryo Nishimaki, Shota Yamada, Takashi Yamakawa
Foundations
We propose new constrained pseudorandom functions (CPRFs) in traditional groups. Traditional groups mean cyclic and multiplicative groups of prime order that were widely used in the 1980s and 1990s (sometimes called ``pairing free'' groups). Our main constructions are as follows.
- We propose a selectively single-key secure CPRF for circuits with depth $O(\log n)$ (that is, $\textbf{NC}^1$ circuits) in traditional groups} where $n$ is the input size. It is secure under the $L$-decisional...
Cyclic Locking and Memristor-based Obfuscation Against CycSAT and Inside Foundry Attacks
Amin Rezaei, Yuanqi Shen, Shuyu Kong, Jie Gu, Hai Zhou
The high cost of IC design has made chip protection one of the first priorities of the semiconductor industry. Although there is a common impression that combinational circuits must be designed without any cycles, circuits with cycles can be combinational as well. Such cyclic circuits can be used to reliably lock ICs. Moreover, since memristor is compatible with CMOS structure, it is possible to efficiently obfuscate cyclic circuits using polymorphic memristor-CMOS gates. In this case, the...
CycSAT: SAT-Based Attack on Cyclic Logic Encryptions
Hai Zhou, Ruifeng Jiang, Shuyu Kong
Cyclic logic encryption is a newly proposed circuit obfuscation technique in hardware security. It was claimed to be SAT-unresolvable because feedback cycles were intentionally inserted under keys into the encryption. We show in the paper that even though feedback cycles introduce extra difficulty for an attacker, they can still be overcome with SAT- based techniques. Specifically, we propose CycSAT Algorithms based on SAT with different acyclic conditions that can efficiently decrypt cyclic...
Secure computation often benefits from the use of correlated randomness to achieve fast, non-cryptographic online protocols. A recent paradigm put forth by Boyle $\textit{et al.}$ (CCS 2018, Crypto 2019) showed how pseudorandom correlation generators (PCG) can be used to generate large amounts of useful forms of correlated (pseudo)randomness, using minimal interactions followed solely by local computations, yielding silent secure two-party computation protocols (protocols where the...
Logic encryption has attracted much attention due to increasing IC design costs and growing number of untrusted foundries. Unreachable states in a design provide a space of flexibility for logic encryption to explore. However, due to the available access of scan chain, traditional combinational encryption cannot leverage the benefit of such flexibility. Cyclic logic encryption inserts key-controlled feedbacks into the original circuit to prevent piracy and overproduction. Based on our...
Cyclic logic encryption is newly proposed in the area of hardware security. It introduces feedback cycles into the circuit to defeat existing logic decryption techniques. To ensure that the circuit is acyclic under the correct key, CycSAT is developed to add the acyclic condition as a CNF formula to the SAT-based attack. However, we found that it is impossible to capture all cycles in any graph with any set of feedback signals as done in the CycSAT algorithm. In this paper, we propose a...
We propose new constrained pseudorandom functions (CPRFs) in traditional groups. Traditional groups mean cyclic and multiplicative groups of prime order that were widely used in the 1980s and 1990s (sometimes called ``pairing free'' groups). Our main constructions are as follows. - We propose a selectively single-key secure CPRF for circuits with depth $O(\log n)$ (that is, $\textbf{NC}^1$ circuits) in traditional groups} where $n$ is the input size. It is secure under the $L$-decisional...
The high cost of IC design has made chip protection one of the first priorities of the semiconductor industry. Although there is a common impression that combinational circuits must be designed without any cycles, circuits with cycles can be combinational as well. Such cyclic circuits can be used to reliably lock ICs. Moreover, since memristor is compatible with CMOS structure, it is possible to efficiently obfuscate cyclic circuits using polymorphic memristor-CMOS gates. In this case, the...
Cyclic logic encryption is a newly proposed circuit obfuscation technique in hardware security. It was claimed to be SAT-unresolvable because feedback cycles were intentionally inserted under keys into the encryption. We show in the paper that even though feedback cycles introduce extra difficulty for an attacker, they can still be overcome with SAT- based techniques. Specifically, we propose CycSAT Algorithms based on SAT with different acyclic conditions that can efficiently decrypt cyclic...